矩形(デフォルトで正方形)をなるべく隙間が出来ないように左上から敷き詰める。
画面をスプレッドシートとして扱い、空き領域を「セル」として管理する。
矩形(デフォルトで正方形)をなるべく隙間が出来ないように左上から敷き詰める。
画面をスプレッドシートとして扱い、空き領域を「セル」として管理する。
/*
矩形敷き詰め問題
表計算ソフトのシートの要領で空き領域を管理する。
爆速だけどメモリ消費が多い(100個の矩形で6MB程)。
左上から詰めていくから、任意の矩形を1つ置いた時に、必要に応じてその右辺と底辺の延長線でシートを分割すればよい。
ある矩形Sを1つ置い後、(必要に応じてシートを分割した後に)、「Sの右隣列の連続した空きセルの最も上のもの」および「Sの1つ下の列の連続した空きセルの最も左のもの」を矩形配置試行セルに加えれば良い。
*/
#cmpopt varinit 1
//#define DEBUG //コメントアウトでデバッグモード(logmes使うので遅い)
#module
#deffunc debugmes str str_
#ifdef DEBUG@
logmes str_
#endif
return
#global
#define global TRUE 1
#define global FALSE 0
#define global SIZE_OF_INT 4
#define global INVALID_CELL_ID -1
#define global SX_FIELD 800 //フィールド(今回は画面全体)のサイズ
#define global SY_FIELD 800
#module Cell sx, sy, used, id_right, id_lower //セルクラス
/*
sx,sy : セルのサイズ
used : 使用済みor not
id_right, id_left : 右隣, 直下のセルへのポインタ(モジュール変数の配列内におけるID。以下「ポインタ」はこれを意味する。)
隣がない場合は INVALID_CELL_ID とする
*/
id_=0
#modinit int sx_, int sy_, int used_, int id_right_, int id_lower_
sx=sx_ : sy=sy_
used=used_
id_right=id_right_ : id_lower=id_lower_
mref id_,2
return id_
#modcfunc local get_sx
return sx
#modcfunc local get_sy
return sy
#modcfunc local get_used
return used
#modcfunc local get_id_right
return id_right
#modcfunc local get_id_lower
return id_lower
#modfunc local set_size int sx_, int sy_
sx=sx_ : sy=sy_
return
#modfunc local set_used int used_
used=used_
return
#modfunc local set_id_right int id_right_
id_right=id_right_
return
#modfunc local set_id_lower int id_lower_
id_lower=id_lower_
return
#modcfunc local is_rightEnd
return id_right==INVALID_CELL_ID
#modcfunc local is_bottom
return id_lower==INVALID_CELL_ID
#global
#module class_try_cells num_try_cells, array_cell_id, array_dist //矩形配置試行セルのリストのクラス。インスタンスは1個だけ。
#modinit int first_cell_id_
num_try_cells=1 //試行セルの個数
array_cell_id=first_cell_id_ //試行セルのポインタの配列
array_dist=0 //試行セルの、原点からの距離(int)の配列。昇順に並んでいる。↑の配列とリンク。
return
#modcfunc local get_num_try_cells
return num_try_cells
#modcfunc local get_try_cell int order_id_ //order_id_ 番目の試行セルのポインタを返す
return array_cell_id(order_id_)
#modcfunc local exists int id_, local return_code //そのセルが存在するか？。
/*
id_ : セルのポインタ
*/
return_code=FALSE
repeat num_try_cells
if (id_==array_cell_id(cnt)) {return_code=TRUE : break}
loop
return return_code
#modfunc local add_try_cell int cell_id_, int dist_ //試行セルの登録
/*
cell_id_ : 試行セルへのポインタ
dist_ : そのセルの原点からの距離
*/
if (exists@class_try_cells(thismod, cell_id_)) {return}
array_cell_id(num_try_cells)=-1 : array_dist(num_try_cells)=0 //ダミー書き込み。配列長が不足の場合に自動確保を促す。
repeat num_try_cells+1 //挿入
if ((dist_ < array_dist(cnt))||(cnt==num_try_cells)) {
//場所を開ける
memcpy array_cell_id, array_cell_id, SIZE_OF_INT*(num_try_cells-cnt), SIZE_OF_INT*(cnt+1), SIZE_OF_INT*cnt
memcpy array_dist, array_dist, SIZE_OF_INT*(num_try_cells-cnt), SIZE_OF_INT*(cnt+1), SIZE_OF_INT*cnt
//追加
array_cell_id(cnt)=cell_id_ : array_dist(cnt)=dist_
num_try_cells++
break
}
loop
return
#modfunc local remove_try_cell int cell_id_ //試行セルを削除
repeat num_try_cells
if (array_cell_id(cnt)==cell_id_) {
//空席を詰める
memcpy array_cell_id, array_cell_id, SIZE_OF_INT*(num_try_cells-cnt-1), SIZE_OF_INT*cnt, SIZE_OF_INT*(cnt+1)
memcpy array_dist, array_dist, SIZE_OF_INT*(num_try_cells-cnt-1), SIZE_OF_INT*cnt, SIZE_OF_INT*(cnt+1)
break
}
loop
num_try_cells--
return
#global
#module sheet_contro //シート操作モジュール
#deffunc init_sheet //シート初期化
sheet=0 : newmod sheet, Cell, SX_FIELD, SY_FIELD, FALSE, INVALID_CELL_ID, INVALID_CELL_ID //シート全体を巨大な単セルに
id_baseCell=stat //左上セルのポインタ
num_cell_x=1 : num_cell_y=1 //x,y方向のセルの数(=列数, 行数)
try_cells=0 : newmod try_cells, class_try_cells, id_baseCell //矩形配置試行セルリストの唯一インスタンス
return
#defcfunc get_top_cell int idx_, local id //その列(idx_)の最上行のセル
id=id_baseCell
repeat idx_ : id=get_id_right@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
return id
#defcfunc get_bottom_cell int idx_, local id //その列の最下行のセル
id=get_top_cell(idx_)
repeat num_cell_y-1 : id=get_id_lower@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
return id
#defcfunc get_leftEnd_cell int idy_, local id //その行(idy_)の最左列のセル
id=id_baseCell
repeat idy_ : id=get_id_lower@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
return id
#defcfunc get_rightEnd_cell int idy_, local id //その行の最右列のセル
id=get_leftEnd_cell(idy_)
repeat num_cell_x-1 : id=get_id_right@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
return id
#defcfunc index2id int idx_, int idy_, local id //(列,行)からセルのポインタへ
id=id_baseCell
repeat idx_ : id=get_id_right@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
repeat idy_ : id=get_id_lower@Cell(sheet(id)) : assert(id!=INVALID_CELL_ID) : loop
return id
#deffunc id2index int id_, var idx_, var idy_, local id, local cx, local cy //セルのポインタから(列,行)へ
id=id_ : cx=0 : cy=0
repeat
if (is_rightEnd@Cell(sheet(id))) {break}
id=get_id_right@Cell(sheet(id))
cx++
loop
repeat
if (is_bottom@Cell(sheet(id))) {break}
id=get_id_lower@Cell(sheet(id))
cy++
loop
idx_=num_cell_x-cx-1 : idy_=num_cell_y-cy-1
return
#deffunc index2pos int idx_, int idy_, var x_, var y_, local id //その(列,行)より左上の領域のサイズ
id=id_baseCell : x_=0 : y_=0
repeat idx_ : x_+=get_sx@Cell(sheet(id)) : id=get_id_right@Cell(sheet(id)) : loop
repeat idy_ : y_+=get_sy@Cell(sheet(id)) : id=get_id_lower@Cell(sheet(id)) : loop
return
#defcfunc index2distance int idx_, int idy_, local x, local y //その(列,行)の原点からの距離
index2pos idx_,idy_, x,y
return int(sqrt(x*x + y*y))
#defcfunc id2distance int id_, local idx, local idy //そのセルの原点からの距離
id2index id_, idx,idy
return index2distance(idx,idy)
#deffunc div_x int idx_, int sx_new, local id //x方向にシートを分割
/*
idx_ : 分割したい列。この列を縮めて右側に新しい列を挿入
[方針]
下端から作る
*/
//「その右に新しいセルが作られるセル達」のID。上から順に詰める。
stack_id=get_top_cell(idx_)
repeat num_cell_y-1, 1
stack_id(cnt)=get_id_lower@Cell(sheet(stack_id(cnt-1)))
loop
new_cell_id=INVALID_CELL_ID
repeat num_cell_y
id=stack_id(num_cell_y-1-cnt)
//新しいセル
sy=get_sy@Cell(sheet(id))
newmod sheet, Cell, sx_new,sy, get_used@Cell(sheet(id)), get_id_right@Cell(sheet(id)), new_cell_id
new_cell_id=stat
//既存のセルの調整
set_size@Cell sheet(id), get_sx@Cell(sheet(id))-sx_new, sy
set_id_right@Cell sheet(id), new_cell_id
loop
num_cell_x++
return
#deffunc div_y int idy_, int sy_new, local id, local idx, local idy //y方向にシートを分割
/*
idy_ : 分割したい行。この行を縮めて下側に新しい行を挿入
[方針]
右端から作る
*/
//「その下に新しいセルが作られるセル達」のID。左から順に詰める。
stack_id=get_leftEnd_cell(idy_)
repeat num_cell_x-1, 1
stack_id(cnt)=get_id_right@Cell(sheet(stack_id(cnt-1)))
loop
new_cell_id=INVALID_CELL_ID
repeat num_cell_x
id=stack_id(num_cell_x-1-cnt)
//新しいセル
sx=get_sx@Cell(sheet(id))
newmod sheet, Cell, sx, sy_new, get_used@Cell(sheet(id)), new_cell_id, get_id_lower@Cell(sheet(id))
new_cell_id=stat
//既存のセルの調整
set_size@Cell sheet(id), sx, get_sy@Cell(sheet(id))-sy_new
set_id_lower@Cell sheet(id), new_cell_id
loop
num_cell_y++
return
#defcfunc top_continuous_free_cell int idx_, int idy_, local id, local id2, local idy //そのセルを含む列の、そのセルと連続した空きセルのうち最上のもの
id=index2id(idx_,idy_) : idy=idy_
repeat idy_
idy-- : id2=index2id(idx_,idy)
if (get_used@Cell(sheet(id2))==TRUE) {break}
id=id2
loop
return id
#defcfunc leftEnd_continuous_free_cell int idx_, int idy_, local id, local id2, local idx //そのセルを含む行の、そのセルと連続した空きセルのうち最左のもの
id=index2id(idx_,idy_) : idx=idx_
repeat idx_
idx-- : id2=index2id(idx,idy_)
if (get_used@Cell(sheet(id2))==TRUE) {break}
id=id2
loop
return id
#deffunc indicate_cell int id_, local idx, local idy, local x, local y //デバッグ用。指定のセルを強調表示
id2index id_, idx,idy
index2pos idx,idy, x,y
color 255,0,0
line x,y, x+get_sx@Cell(sheet(id_))-1,y+get_sy@Cell(sheet(id_))-1
line x+get_sx@Cell(sheet(id_))-1,y, x,y+get_sy@Cell(sheet(id_))-1
return
#deffunc draw int idx_, int idy_, int sx_, int sy_, local x, local y //矩形の描画
/*
idx_,idy_ : 列,行
sx_,sy_ : 矩形のサイズ
*/
color rnd(200),rnd(200),rnd(200)
index2pos idx_,idy_, x,y
boxf x,y, x+sx_-1, y+sy_-1
return
#defcfunc local place_at int id_, int sx_, int sy_, local id, local id2, local idx, local idy //そのセルを左上として可能ならば矩形を配置する
/*
id_ : セルのポインタ
sx_, sy_ : 矩形サイズ
*/
#ifdef DEBUG@
if (get_used@Cell(sheet(id_))==TRUE) {
indicate_cell id_
logmes ""
repeat get_num_try_cells@class_try_cells(try_cells)
logmes get_try_cell@class_try_cells(try_cells, cnt)
loop
}
assert(get_used@Cell(sheet(id_))==FALSE)
#endif
flg_cannot=FALSE
//x方向の必要セル数を調べる
num_cell_x_require=1
id=id_ : sx_remain=sx_
repeat
if (get_used@Cell(sheet(id))) {flg_cannot=TRUE : break}
sx_remain-=get_sx@Cell(sheet(id))
if (sx_remain<=0) {break}
num_cell_x_require++
if (is_rightEnd@Cell(sheet(id))) {flg_cannot=TRUE : break}
id=get_id_right@Cell(sheet(id))
loop
if (flg_cannot) {return FALSE}
//y方向の必要セル数を調べる
num_cell_y_require=1
id=id_ : sy_remain=sy_
repeat
if (get_used@Cell(sheet(id))) {flg_cannot=TRUE : break}
sy_remain-=get_sy@Cell(sheet(id))
if (sy_remain<=0) {break}
num_cell_y_require++
if (is_bottom@Cell(sheet(id))) {flg_cannot=TRUE : break}
id=get_id_lower@Cell(sheet(id))
loop
if (flg_cannot) {return FALSE}
//配置
id2index id_, idx, idy
idx_used_cell_rightmost=idx+num_cell_x_require-1 //今回消費されるセルの中で最も右側のもののxインデックス
idy_used_cell_bottom=idy+num_cell_y_require-1
//食べ残しが発生したセルを分割
if (sx_remain<0) {div_x idx_used_cell_rightmost, -sx_remain}
if (sy_remain<0) {div_y idy_used_cell_bottom, -sy_remain}
//使用済みセルをマーク
id=id_
repeat num_cell_x_require
id2=id
repeat num_cell_y_require
set_used@Cell sheet(id2), TRUE
id2=get_id_lower@Cell(sheet(id2))
loop
id=get_id_right@Cell(sheet(id))
loop
//新しい矩形配置試行セルの登録
if (idx_used_cell_rightmost<num_cell_x-1) {
id=top_continuous_free_cell(idx_used_cell_rightmost+1, idy)
add_try_cell@class_try_cells try_cells, id, id2distance(id)
}
if (idy_used_cell_bottom<num_cell_y-1) {
id=leftEnd_continuous_free_cell(idx, idy_used_cell_bottom+1)
add_try_cell@class_try_cells try_cells, id, id2distance(id)
}
//描画
draw idx,idy, sx_,sy_
return TRUE
#defcfunc place int sx_, int sy_, local id //できるだけ原点に近い場所に矩形を配置する。矩形配置試行セルで片っ端から試す。どうしても無理なら FALSE を返す。
assert((sx_>=1)&&(sy_>=1))
debugmes "num_cell_x,num_cell_y = "+num_cell_x+","+num_cell_y
debugmes "there are "+get_num_try_cells@class_try_cells(try_cells)+" try-cells."
return_code=FALSE
repeat get_num_try_cells@class_try_cells(try_cells)
id=get_try_cell@class_try_cells(try_cells, cnt)
if (get_used@Cell(sheet(id))) {remove_try_cell@class_try_cells try_cells, id : continue} //もしも矩形配置試行セルが使用済みになっているのを見つけたら削除しておく。これ重要
debugmes "trying to use cell "+id
if (place_at(id, sx_, sy_)) {
remove_try_cell@class_try_cells try_cells, id
return_code=TRUE
debugmes " ->SUCCEEDED"
break
} else {
debugmes " ->FAILED"
}
loop
return return_code
#global
/* main */
#uselib "winmm"
#cfunc timeGetTime "timeGetTime"
#define WID_MAIN 0
#define NUM_SQUARE 100
screen WID_MAIN, SX_FIELD, SY_FIELD
//よ～い...
mes str(NUM_SQUARE)+" squares"
mes "ready..."
repeat 3 : mes 3-cnt : wait 100 : loop
//どん！
time_start=timeGetTime()
randomize
init_sheet //シートを初期化
repeat NUM_SQUARE
//新たに追加する矩形のサイズ
sx_new=limit(100-((cnt/10)*10) ,1) : sy_new=limit(100-((cnt/10)*10) ,1)
//sy_new=int((0.5+0.1*rnd(11))*sx_new) //縦横比のバリエーションをもたせる場合はここをコメントアウト
sx_new+=sx_new\2 : sy_new+=sy_new\2//偶数にする
//追加
debugmes "square "+(cnt+1)
if (place(sx_new, sy_new)) {
debugmes "placement SUCCEEDED"
} else {
debugmes "placement FAILED"
}
debugmes "------------------------------"
title str(cnt+1)+" squares" //コメントアウトすると高速
loop
//結果発表
time_end=timeGetTime()
dialog "required time : "+(time_end-time_start) + " ms"