【四分木】HSPで大量の当たり判定を検出する【モートン順序】

目的

　YouTubeで見たSIRモデルのシミュレーションが(プログラム的に)面白かったので、HSPで出来るかな？と思い試行錯誤します。
　コロナによる緊急事態宣言も解除されて、完全に機を逸した感がありますが良しとします。

動画リンク(YouTube)
　感染はどのように広がる？シミュレーションを用いて解説【新型コロナ自粛解除するとどうなる？】

　動画の説明欄にPythonソースのリンクが張られているので、読める方はそちらを参考にされた方がよろしいかと思います。ただし、そのソースはリアルタイムに描画するのではなく、フレーム単位で描画されたバッファを動画に変換しているようです。

SIRモデルとは

　SIRモデル（エスアイアールモデル）とは、感染症などの流行過程を端的に表した方程式だそうです。詳しくはwiki。ここでは大量の衝突判定の一例として取り上げます。

HSPとは

　おにたま@onionsoftwareさんが作成されたプログラミング言語です。フリーウェアだよ、やったね！
　インタプリタ言語ということもあって、実行速度はお察し下さい。今回はWindows版HSP3.6beta1で作成します。

こんなのが作れます(Qiita)
　HSP3で簡単なアクション作ってみた
速度比較(Qiita)
　パラレルベンチマーク [C++/D/C#/VB/JS/HSP/Python/Ruby]

参考にしたリンク

リンク１ 四分木やモートン順序の理解(外部リンク)
　ゲームつくろー！ - その８ 4分木空間分割を最適化する！
リンク２ 実装したソース(外部リンク)
　Subterranean Flower Blog - JavaScriptで大量のオブジェクトの当たり判定を効率的にとる
リンク３ Qiitaの記事
　Qiita - 超高速2D当たり判定プログラムを作りたかった

実装にあたって

• HSPにはリスト構造がありません。クラスもありません。配列とモジュール型変数を使って何とかします。
• オブジェクトは丸いですが、矩形で判定します。sin(),cos()なんて使ってられません。
• 衝突したオブジェクトは、状態を変更するだけで反発しません。よくわかりません。
• オブジェクトの数は500とします。並列処理で描画すればもっといけるかも→mistプラグイン
• FPSは30くらいとします。というかFPS計っていません。
• 四分木やモートン順序に関しては何も言えません。リンクを見てください。

線形リストの実装

　一番厄介だったのが、「線形四分木に登録するリストをHSPでどんなデータ構造で表現したらいいか」ということでした。リンク２ではJavascriptで以下の図のような構造をしていました。

　拡張性の高いコーディングをされていたので、実際は線形四分木リスト自体も拡張できるようになっていました。

補足
　線形四分木リストの要素番号は、登録したオブジェクトがどの場所に存在しているかを示しています。要素0に登録されたオブジェクトは、四分木空間の階層1,インデックス0の場所に存在します。これは

要素番号=((4^(階層-1)-1))/3+インデックス
(小数点以下切り捨て、^はべき乗)

で計算できます。階層3、インデックスが10の位置に存在するオブジェクトだったら、((4^(3-1)-1)/3+10で要素番号15に登録されます。
　登録したオブジェクトは、その要素に登録されているオブジェクト同士と衝突判定をし、さらにその階層が存在する親階層に登録されたオブジェクトとも衝突判定をします。例えば階層3、インデックス10のオブジェクトは以下の図の赤い場所に存在するオブジェクトと当たり判定を行います。

　この当たり判定処理を作る(要素番号0から再帰を使って親リストを作成する)際に、線形四分木リストが必要になってきます。

1.実装にあたっての問題点

• 自動拡張するデータ構造がない。
  
  　　作成当初、拡張できるのはモジュール型変数を宣言(newmod)するときぐらいだろうと思ってました。
• (Actor)クラスをモジュール型変数で表現するとして、作成したモジュール型変数をどのようにリストに追加していくか。
  
  　　モジュール型変数を格納するデータ構造が必要。あるかもしれないけど知らない。アドレスで管理すればあるいは？とも思ったけど、アドレスからモジュール型変数の実体を参照するのってできるの？ 出来ます。　出来たとしても自分が作ったらメモリ破壊しちゃうかも。
• null を示すデータ表現がない。
  
  　　ないらしい。

2.検証してみる

　とりあえず問題点のその２をテストしてみる。以下は整数型配列にそのままモジュール型変数をぶち込むという、実行する前から駄目そうなソースコード。

test1.hsp

#module M_BOX _mX, _mY, _mW, _mH
	#modinit
		_mW = rnd(100) + 1
		_mH = rnd(100) + 1
		_mX = rnd(640-_mW)
		_mY = rnd(480-_mH)
		return
	#modfunc boxDraw
		boxf _mX, _mY, _mX+_mW, _mY+_mH
		return
#global

#define	BOX_NUM	10

dim a, BOX_NUM

// 作成
repeat BOX_NUM
	newmod mBoxs, M_BOX
loop

// 配列に登録
repeat BOX_NUM
	a.cnt = mBoxs.cnt
loop

// メソッドへのアクセス
repeat BOX_NUM
	boxDraw a.cnt
loop
// 廃棄処理
foreach mBoxs
	delmod mBoxs.cnt
loop

実行結果。Errorを吐くことなく実行される。

一応 knowbug で配列 a の中身を見てみる。モジュール変数 _mx , _my が異常に増えてる。おまけに _mw がない！

　knowbug の結果(変数の内容)は実行するたびに変わり、メモリがやばい事になってることが分かります。

3.出来ることからやってみる

　(Actor)クラスはオブジェクトの位置や、描画メソッドなどを持っています。これならモジュール型変数で実装できそう。
　こんなコードになりました。

//**************************************************************
// キャラクタモジュール
//**************************************************************
#module M_CHARA _mX, _mY, _mW, _mH, _mVX, _mVY, _mStatus, _mCount
	// 初期化処理
	#modinit
		// 位置を乱数で指定
		return
	// 解放処理
	#modterm
		return
	// 更新メソッド
	#modfunc charaUpdate
		// 速度分だけ移動する
		return
	// 描画メソッド
	#modfunc charaDraw
		return
	// Top取得
	#modcfunc charaTop
		return _mY
	// Bottom取得
	#modcfunc charaBottom
		return _mY + _mH

	～他モジュール変数のgetter～

	// 衝突時メソッド
	#modfunc charaHit var _chara
		// 自身のステータスを変更
		_mStatus = 1
		// 引数のキャラ型変数のステータスも変更
		charaChangeStatus _chara, 1
		return
	// 状態変更メソッド
	#modfunc charaChangeStatus int _i
		_mStatus = _i
		return
#global

　さてクラスは実装できましたが、それを管理/格納するデータ構造は出来てません。どうしたものやら。

4.HSPの仕様

　話は変わって、HSP3.x系には面白い(と取るか邪悪と取るか?)仕様がありました。
　HSPでは整数型などの変数は宣言する必要がなく、勝手に自動確保してくれます。例えば a = 0 など代入する時点で、a という変数が使われてなければ、この場合整数型として確保してくれます。この機能のおかげで、実数型変数がいつのまにか整数型に変わってしまったり、タイプミスすると変数が勝手に追加されるのですが、これはユーザー側の問題ですね。すいません。
　これは配列変数でも同じことが起きます。

HSP プログラミングマニュアルより
3.8.変数
任意の名前をつけた変数を扱うことができます。変数とは、代入により内容 を変化させることのできる容れ物のようなものです。
変数は、アルファベットまたは日本語で始まる59文字(半角)以下の文字列で 識別されます。変数は代入により数値や文字列などさまざまな情報を格納することができます。 また、1つの変数の中にインデックスをつけて複数の情報を格納するための、配列変数を利用することができます。
3.9.配列変数
配列変数の要素は、代入された時点で自動的に確保されます。 たとえば、a(2)=5のように書いた場合は、a(2)が自動的に確保され 5という値が代入されます。ただし、a(1000)=0と書いた場合には、 a(0)～a(1000)までの要素すべてがメモリに確保されてしまうので、要素の数値は0から順番に使用するように注意してください。

例えば、下のコードは正常に動作します。

test2.hsp

	a = -1		; この時点では1つの整数型変数で配列変数ではない

	// 1次元配列になる
	a.1 = 1		; この時点で1次元配列となる
	a.10 = 10	; ここで1次要素の配列を追加してもOK

	mes "1次元配列"
	foreach a
		mes a.cnt
	loop

	// 2次元配列になる
	a(0,1) = 11	; ここで2次元配列となる
	a(0,2) = 12
	a(0,3) = 13

	mes "2次元配列"
	repeat length2(a)
		mes a(0,cnt)
	loop

;	a.11 = 110	; ここで1次要素の配列を追加しようとするとError

実行結果。

　この話は以下のリンクが分かりやすいと思います。

• HSPTV!掲示板 - 配列変数の自動追加
• HSP開発wiki - 変数領域の自動確保

　閑話休題。

5.整数型配列で自動拡張する構造を作る

　ということで、整数ならば配列を使って管理できるのではないかと考えました。片方向リンクリストにして挿入も削除も出来るようにするのも良いと思いますが、リストは毎回全削除して、登録と参照だけできるようにすれば配列でも出来そうです。ついでに親の衝突リストを作る(再帰処理)際にスタックが必要になるため、スタックとしても使えるようにします。
　以下のコードが出来ました。

//**************************************************************
// 整数型配列スタックモジュール
//**************************************************************
#module M_ARRAYSTACK _mArray, _mLength
	// 初期化処理
	#modinit
		dim _mArray
		_mLength = 0
		return
	// 解放処理
	#modterm
		aryClear thismod
		return
	// 要素の追加
	#modfunc aryPush int _element
		_mArray._mLength = _element
		_mLength ++
		return _mLength
	// 配列モジュール型の追加
	#modfunc aryPushArray var _array
		repeat aryLength(_array)
			aryPush thismod, aryGet(_array,cnt)
		loop
		return _mLength
	// スタック用Pop
	#modfunc aryPop var _val
		if _mLength > 0 {
			_mLength --
			_val = _mArray._mLength
			return 0
		}
;		dialog "スタックがありません！"
		return -1
	// 要素の参照
	#modcfunc aryGet int _index
		return _mArray._index
	// 配列の削除
	#modfunc aryClear
		dim _mArray
		_mLength = 0
		return
	// 配列の長さを取得
	#modcfunc aryLength
		return _mLength
	// デバッグ用
	#modfunc aryMes
		repeat _mLength
			mes strf("[%2d]:%2d",cnt,_mArray.cnt)
		loop
		return
#global

　別に生の配列を使えば良いのですが、配列の長さも一緒に管理したくモジュール型にしてみました。配列が無ければ aryLength() が 0 を返してくれるので、Null 判定も出来るようになりました。

6.キャラクタモジュール型変数に配列番号をつける

　あとはキャラクタモジュール型変数自身に配列番号を持たせて、登録された配列番号からモジュール型変数にアクセスできれば完成です。
　以下のリンクが参考になりました。要するにモジュール型変数を作成するときに mref id, 2 を使えばモジュール型変数の添え字の番号が入るという事だと思います。ただ何かの拍子に id の値が変化するときがあったので(何だったか忘れた)、取得した値は普通の変数に代入するのがベターかなと思いました。

• HSPTV!掲示板 - 構造体の利便性・必要性
• HSP開発wiki - hsp3/モジュール変数

//**************************************************************
// キャラクタモジュール
//**************************************************************
#module M_CHARA _mID, _mStatus, _mX, _mY, _mW, _mH, _mVX, _mVY, _mCount
	// 初期化処理
	#modinit
		mref _mID, 2
;		mref _id, 2
;		_mID = _id
		_mW = 5.0
		_mH = 5.0
		_mX = 1.0*rnd(WIN_W-_mW)+1
		_mY = 1.0*rnd(WIN_H-_mH)+1
		
		～

成果物

　全探索バージョン　わぁ～、おっそーい！

　四分木バージョン　わぁ～、はっやーい！ と言うほどでもないけど、目に見えて速くなってますね。

無駄に github にソースコードと実行ファイルを置いてるので、そちらも良かったらダウンロードしてみてください。

• github - funsuke/testCollision

　ファイルの名前が英数字じゃなかったため、ダウンロードした時に文字化けして開けませんでした。ファイル名を変更しました。

追加の話

　モジュール型変数をアドレスで管理する方法を HSP のヘルプファイルを眺めてたら見つけたので、サンプルコードを載せときます。

test3.hsp

#module M_BOX _mX, _mY, _mW, _mH
	#modinit
		_mW = rnd(100) + 1
		_mH = rnd(100) + 1
		_mX = rnd(640-_mW)
		_mY = rnd(480-_mH)
		return
	#modfunc boxDraw
		boxf _mX, _mY, _mX+_mW, _mY+_mH
		return
#global

#define	BOX_NUM	10

dim a, BOX_NUM

// 作成
repeat BOX_NUM
	newmod mBoxs, M_BOX
loop

// 配列に登録
repeat BOX_NUM
	a.cnt = varptr(mBoxs.cnt)
loop

// メソッドへのアクセス
repeat BOX_NUM
	pos 0,16*cnt
	mes a.cnt
	dupptr tmp, a.cnt, 16, 5
	boxDraw tmp
loop

// 廃棄処理
foreach mBoxs
	delmod mBoxs.cnt
loop

こっちの方が速いかもしれないなぁと思いつつ、疲れたので寝ます。