オブジェクトID for HSP3 †
オブジェクトIDの割り当てルールから、BMSCR構造体からオブジェクト管理領域へのポインタmem_objをたどってオブジェクトのハンドルが無効(0,NULL)かどうかを順番に調べる方法がまず考えられると思います。
|
+
| | SAMPLE1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
-
|
|
!
| #module
#defcfunc getobj
mref bm, 96 + ginfo_sel
if bm(72)=0: return 0
dupptr obj, bm(71), bm(72)*48 ret = bm(72)
repeat bm(72)
if obj(cnt*12+2)=0{
ret = cnt
break
}
loop
return ret
#global
randomize
repeat 5
chkbox "Check"+getobj(), chk.getobj()
loop
n = rnd(5)
clrobj n, n
chkbox "Check"+getobj(), chk.getobj()
|
|
ただし、この方法は線形探索でアルゴリズム的には最も簡単で、最も遅い方法です。
オブジェクトが多くなれば時間がかかることは明白です。(実際には制限が1024個なので最悪のケースでもかかる時間は微々たるものだと思います。)
この方法は使用/未使用IDをプログラマが自己管理していないため、直接システムを参照するしかない、採らざるを得ない方法です。
ただしシステムを直接参照するので自己管理の手間が省ける分、メモリ消費は最も小さくなります。
次に配列を用いて未使用かどうかを自己管理するサンプルです。
ここでも探索アルゴリズムは線形探索で行っていきます。
|
+
| | SAMPLE2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
-
|
-
|
|
|
|
!
-
|
|
|
!
!
-
|
|
-
|
|
|
|
|
|
|
!
|
!
| #const OBJMAX 10
#enum FREE = 0 #enum BUSY #enum UNCHECKED = 0 #enum CHECKED
font msgothic, 24
dim rec, OBJMAX dim chk, OBJMAX
repeat
wait 100
n = rnd(OBJMAX) color 255,255,255: boxf: color 0
if rec(n) = BUSY{
pos 64, n*24
if chk(n) = CHECKED{
clrobj n, n
rec(n) = FREE: chk(n) = UNCHECKED
mes "選出したID " + n + " を削除しました"
}
else{
objprm n, CHECKED
mes "選出したID " + n + " をチェックしました"
}
}
else{
foreach rec
if rec(cnt) = FREE{
pos 0, cnt*24
chkbox "Check"+cnt, chk(cnt)
pos 64, cnt*24
mes "オブジェクトID " + cnt + " が割り当てられました"
rec(cnt) = BUSY
break
}
loop
}
loop
|
|
オブジェクトIDの使用状況は配列変数recで管理されています。
オブジェクトを割り当てる時は、直前に配列変数recを先頭から順番に未使用(FREE)のIDを探します。
この方法はSAMPLE1と大して変わらない上に自己管理のためのメモリを消費してしまいます。
- 使用中IDの探索
- 選出したIDが使用中かどうかは配列要素の添え字を指定して参照するだけで取得できるのでO(1)のオーダーで実行できます。
- 再利用IDの登録
- 再利用IDの登録は配列要素の添え字を指定して未使用フラグを立てるだけなので0(1)のオーダーで実行できます。
- 再利用IDの検索
- 配列要素を先頭から順番に検索するので0(N)のオーダーがかかります。
|
|
ここで改めて管理方法を考え直してみると、オブジェクトIDがもれなく割り当てられていれば、次に割り当てられるIDは「現在のオブジェクトの数」だけで取得できます。
なぜ管理が必要なのかといえば、ところどころ削除したりして未使用のIDがあるために、割り当てられるIDが一定でないからです。
このため、「次に割り当てられるIDを管理する」データが必要になってきますが、これは現在のオブジェクトの数と再利用されるIDとその数を管理すれば実現できます。
また、(平均すると)すべてのIDの使用状況を管理せずに済み、消費メモリも減らすことができ、あらかじめ管理用データのサイズを決めておかなくても済みます。
|
+
| | SAMPLE3
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
-
|
|
|
|
!
-
|
|
|
|
-
|
|
|
!
|
|
!
-
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
!
-
|
|
|
|
|
!
|
#const HORZ_SIZE 64
#const VERT_SIZE 24
#ifdef SPEEDTEST
#const HORZ_MAX 10
#const VERT_MAX 20
#else
#const HORZ_MAX 1
#const VERT_MAX 20
#endif
#const OBJMAX HORZ_MAX * VERT_MAX
#enum UNCHECKED = 0
#enum CHECKED
#define ctype x(%1) (%1) / VERT_MAX * HORZ_SIZE
#define ctype y(%1) (%1) \ VERT_MAX * VERT_SIZE
#define swap(%1,%2) %1^=%2: %2^=%1: %1^=%2
font msgothic, 24
cur_max = 0 rec_max = 0
repeat
#ifdef SPEEDTEST
wait 10
#else
wait 100
#endif
n = rnd(OBJMAX)
color 255,255,255: boxf: color 0
if n >= cur_max {
if rec_max: gosub *RecycleObject: else: gosub *NewObject
continue
}
if rec_max {
rec_exist = 0
repeat rec_max
if n = rec(cnt) {
rec_exist = 1
gosub *RecycleObject
break
}
loop
if rec_exist: continue
}
if chk(n) {
clrobj n, n
chk(n) = UNCHECKED
i = rec_max
rec(rec_max) = n: rec_max++
repeat
if i = 0: break
if rec(i-1) > rec(i): break
swap rec(i-1), rec(i)
i--
loop
#ifndef SPEEDTEST
pos x(n)+HORZ_SIZE, y(n)
mes "選出したID "+n+" を削除しました"
#endif
}
else{
objprm n, CHECKED
#ifndef SPEEDTEST
pos x(n)+HORZ_SIZE, y(n)
mes "選出したID "+n+" をチェックしました"
#endif
}
loop
stop
*RecycleObject
rec_max--
rec_id = rec(rec_max)
pos x(rec_id), y(rec_id)
chkbox ""+rec_id, chk(rec_id)
#ifndef SPEEDTEST
pos x(rec_id)+HORZ_SIZE, y(rec_id)
mes "オブジェクトID "+rec_id+" を再利用しました"
#endif
return
*NewObject
new_id = cur_max
cur_max++
pos x(new_id), y(new_id)
chkbox ""+new_id, chk(new_id)
#ifndef SPEEDTEST
pos x(new_id)+HORZ_SIZE, y(new_id)
mes "オブジェクトID "+new_id+" が割り当てられました"
#endif
return
|
|
SAMPLE3で再利用されるIDを管理しているのがリサイクルテーブルと呼んでいる配列recです。
オブジェクトを削除したらリサイクルテーブルに削除したIDを登録します。
オブジェクトを作成する際はリサイクルテーブルを調べ、再利用可能なIDがあれば利用し、リサイクルテーブルからそのIDを削除します。
- 使用中IDの探索
- 選出したIDが使用中かどうかはリサイクルテーブルに登録されていないIDなのでO(N)のオーダーがかかります。*1
- 再利用IDの登録
- リサイクルテーブルをソート状態に保つため、適切な位置へ挿入するのにO(N)のオーダーがかかります。*2
- 再利用IDの検索
- リサイクルテーブルがソート状態にあるため、最小のIDはO(1)のオーダーで取得できます。
|
|
- 私の欠点は結論にたどり着くまでの前置きが長すぎること... -- kz3
- いやいや、前置きがあるからこそ納得するんですから（＾＾；） -- ちたん?
- あーちたんさんコメントありがとうございます。これでちたんさんも開発wiki仲間ですね
![[bsmile2]](./image/face/bigsmile2.png)
サンプルの動作が混乱しそうですが、注目すべき動作は、「削除されたオブジェクトがIDの若いものから再利用されている」かつ「再利用されたオブジェクトのチェック状態が適切に反映されている」の2点です。チェック状態が適切に反映されているのは、オブジェクトを実際に配置する前に割り当てられるIDが取得できていて、きちんと配列chkの添え字と一致しているからですね。 -- kz3
- 選出したIDのオブジェクトを配置する(../HSP2)のとは違うので注意です。 -- kz3
![[hsp3]](./image/req/hsp3.png)
