motchy869さんが投稿したコード一覧

HSP 矩形敷き詰め問題

/*
	矩形敷き詰め問題

	 表計算ソフトのシートの要領で空き領域を管理する。
	爆速だけどメモリ消費が多い(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"

よく投稿されているコード

タグ

最近投稿されたコード