HSPでモートン番号（Z-order曲線）テーブルを作成して空間インデックスを扱うTips
こんにちは。HSP（Hot Soup Processor）でゲームやツールを作っている皆さん、今日はモートン番号（Morton number）を使った空間分割のテクニックをご紹介します。モートン番号とは、多次元座標（2Dや3Dなど）を1次元の整数に変換する手法で、Z-order曲線（Z字曲線）とも呼ばれます。座標の各軸のビットを交互に並べ替える（ビットインターリーブ）ことで実現され、空間的に近い点が1次元上でも近くになるという局所性の良い性質を持っています。これにより、四分木（quadtree）や八分木（octree）などの空間インデックスを効率的に扱えるようになります。特に、範囲検索（ある矩形領域内の点を素早く探す）で威力を発揮します。モートン番号の範囲を計算すれば、該当する葉ノードを連続した番号として取得できるからです。
今回のコードは、事前にモートン番号テーブルを作成しておき、高速に座標からモートン番号を取得したり、範囲のモートン番号を計算したりできるモジュールです。1次元?4次元まで対応し、分割レベル（空間の細かさ）も柔軟に設定可能です。主な機能テーブル作成：MakeMortonNoTable 次元数, 分割レベル, テーブル変数
個別空間番号取得：テーブルから直接インデックスでアクセス（例: table(x, y)）
範囲空間番号取得：GetLinerNo2d(table, x1, y1, x2, y2) などで、矩形範囲の最小?最大モートン番号を計算（範囲検索に便利）
次元数・分割レベル取得：GetDimensionality(table)、GetDivisionLevel(table)
//--"MortonNo.hsp"
#ifndef MortonNo
#module MortonNo mtable
#modinit int dimensionality, int division_level
max = 1 << division_level ; 一つの軸上にある空間の数
LeafSpace = 1 << division_level * dimensionality ; 総葉空間数
dim bt, max
for i,, max
repeat 30 / dimensionality
if i >> cnt & 1: bt(i) | 1 << cnt * dimensionality
loop
next
if dimensionality == 1{
dim mtable, max
repeat max
mtable(cnt) = LeafSpace | bt(cnt)
loop
}else: if dimensionality == 2{
dim mtable, max, max
repeat max
b = LeafSpace | bt(cnt) << 1
dup D, mtable(0, cnt)
repeat max
D(cnt) = b | bt(cnt)
loop
loop
}else: if dimensionality == 3{
dim mtable, max, max, max
for i,, max
b1 = LeafSpace | bt(i) << 2
repeat max
b = b1 | bt(cnt) << 1
dup D, mtable(0, cnt, i)
repeat max
D(cnt) = b | bt(cnt)
loop
loop
next
}else: if dimensionality == 4{
dim mtable, max, max, max, max
for j,, max
b2 = LeafSpace | bt(j) << 3
for i,, max
b1 = b2 | bt(i) << 2
repeat max
b = b1 | bt(cnt) << 1
dup D, mtable(0, cnt, i, j)
repeat max
D(cnt) = b | bt(cnt)
loop
loop
next
next
}
mref thisID, 2
return thisID
#modfunc __duptable array a
__duparray a, mtable
return
#deffunc __duparray array a, array c
dup a, c
i = __get_pval(a)
dupptr S, i + 8 , 4: S = length(c)
dupptr S, i + 12, 4: S = length2(c)
dupptr S, i + 16, 4: S = length3(c)
dupptr S, i + 20, 4: S = length4(c)
return
#defcfunc __get_pval var
#deffunc ______ int pval
return pval
#defcfunc __MSB32 int, double w
#deffunc ___MSB32 double, int w
if w <= 0: return (w < 0) * 32
return (w >> 20) - 1022
#deffunc __MakeMortonNoTable int dimensionality, int division_level, array a
if (dimensionality < 1) | (dimensionality > 4) | (division_level * dimensionality > 30): return 1
dup S, index(dimensionality, division_level)
if S < 0: newmod table, MortonNo, dimensionality, division_level: S = stat ; 作成済みでなければ作成
__duptable table(S), a
return 0
#deffunc __DelMortonNotable int dimensionality, int division_level
dup S, index(dimensionality, division_level)
if S >= 0: delmod table(S): S = -1
return
#defcfunc __GetDimensionality array a
if length4(a): return 4
if length3(a): return 3
if length2(a): return 2
return 1
#deffunc __InitMortonNo
dim index, 5, 30
for i,, 600, 4
lpoke index, i, -1
next
return
#global
__InitMortonNo
//以下インターフェース ( このモジュールで使用可能になる全ての機能です )
//Most Significant Bit 取得
#define global ctype MSB32(%1) __MSB32(,%1)
//多次元配列シャローコピー
#define global DupArray(%1,%2) __duparray %1, %2
//テーブル作成
#define global MakeMortonNoTable(%1, %2, %3) __MakeMortonNoTable %1, %2, %3
//テーブル削除
#define global DelMortonNoTable(%1, %2) __DelMortonNoTable %1, %2
//テーブルから、その次元を取得
#define global ctype GetDimensionality(%1) __GetDimensionality(%1)
//テーブルから、その分割レベルを取得
#define global ctype GetDivisionLevel(%1) MSB32(length(%1) - 1)
//テーブルと範囲を指定して空間番号を取得
#define global ctype GetLinerNo1d(%1,%2,%3 ) (%1(%2 ) >> MSB32(%1(%2 ) ^ %1(%3 )))
#define global ctype GetLinerNo2d(%1,%2,%3,%4,%5 ) (%1(%2,%3 ) >> MSB32(%1(%2,%3 ) ^ %1(%4,%5 )))
#define global ctype GetLinerNo3d(%1,%2,%3,%4,%5,%6,%7 ) (%1(%2,%3,%4 ) >> MSB32(%1(%2,%3,%4 ) ^ %1(%5,%6,%7 )))
#define global ctype GetLinerNo4d(%1,%2,%3,%4,%5,%6,%7,%8,%9) (%1(%2,%3,%4,%5) >> MSB32(%1(%2,%3,%4,%5) ^ %1(%6,%7,%8,%9)))
#endif
//--"MortonNo.hsp" --End Of File
//-------二次元(四分木)での空間番号テスト--------
//対象範囲
sx = 100
sy = 60
ex = ginfo_sx - 100
ey = ginfo_sy - 10
//分割レベル
divlevel = 2
font "", 20
レベル変更 = 1
*main
if レベル変更{
divlevel = limit(divlevel + レベル変更 / 120, 0, 8)
divsizex = double(ex - sx) / (1 << divlevel)
divsizey = double(ey - sy) / (1 << divlevel)
max = (1 << divlevel) - 1
//テーブル作成 次元数, 分割レベル, このテーブルを指す変数
MakeMortonNoTable 2 , divlevel , jtable
DupArray table, jtable ; コピーで使ってみるテスト
}
title "ドラッグしてください ホイールで分割レベル変更" + " 次元数 = " + GetDimensionality(table) + " 分割レベル = " + GetDivisionLevel(table)
レベル変更 = mousew
x = double(mousex)
y = double(mousey)
dragging = key
getkey key, 1
color: boxf
if key{
if dragging = 0{
mx = x
my = y
}
x1 = limit((mx - sx) / divsizex, 0, max)
y1 = limit((my - sy) / divsizey, 0, max)
x2 = limit(( x - sx) / divsizex, 0, max)
y2 = limit(( y - sy) / divsizey, 0, max)
color 200, 200, 200
boxf mx, my, x, y
color 0, 50, 255
circle mx - 4, my - 4, mx + 4, my + 4
circle x - 4, y - 4, x + 4, y + 4
pos 0, 0
color 200, 0, 255
mes "点１の空間番号 = " + table(x1, y1)
mes "点２の空間番号 = " + table(x2, y2)
mes "範囲の空間番号 = " + GetLinerNo2d(table, x1, y1, x2, y2)
}
for j, divlevel, -1, -1
hsvcolor j * 191 / 11, 220, 220
m = 1 << j
for i, m , -1 , -1
_x = sx + i * (ex - sx) / m
_y = sy + i * (ey - sy) / m
line sx, _y , ex, _y
line _x, sy, _x , ey
next
next
redraw
redraw 2
await 16
goto *mainなぜテーブル化するのか？
通常のモートン番号計算はビット操作でリアルタイムに可能ですが、HSPのようなスクリプト言語ではループ処理が遅くなりがちです。そこで、事前にテーブルを作成しておくことで、座標→番号の変換を配列参照だけで超高速にできます。特に大量の点を扱うゲーム（衝突判定、空間ソートなど）で有効です。このモジュールは1?4次元に対応しており、3Dゲームのoctreeや、4Dの特殊処理にも拡張可能です。HSPは軽快に動く言語なので、こうした空間インデックスを簡単に試せて楽しいですよね。衝突検出の最適化や、大規模な粒子シミュレーションなどにぜひ活用してみてください！質問や改良案があれば、コメントでお知らせください。皆さんのHSP作品を楽しみにしています！
ソースコードに寄せてAI(Grok)さんに文章を生成してもらいました(2025/12)
コメント