プチコン3号 14日目 グラフィックスとアニメーション

プチコン3号にはスプライトやBG以外に、画面に直接絵を描く命令もあります。
描ける図形は
・矩形(線幅1ピクセル、塗りつぶし無し)
・矩形(塗りつぶし)
・直線(線幅1ピクセル)
・真円(線幅1ピクセル、塗りつぶし無し)
・点(1ピクセル)
の5種類で、さらに
・領域塗りつぶし(領域の境界の色指定可)
も可能です。
多角形や楕円、太い線などは描けません。
命令は、ダイレクトモードから簡単に試すことができます。

pc14-1.jpg

これらの命令の実行速度は結構速いので、スクリーンを消しては絵を描き、を繰り返すと、描いた絵を動かすことができます。
そこで、ボールを床に落とすと弾むような感じで、円がスクリーンの中を弾んで動くアニメーションを作ってみました。

pc14-2.jpg

11個のボールがポンポン弾みながら画面の中を動きます。

プログラムリストはこちらです。

pc14-3.jpg
N=10:G=0.2:SCW=400:SCH=240
DIM X[N+1],Y[N+1],R[N+1]
DIM V[N+1],V0[N+1],DX[N+1],C[N+1]
FOR I=0 TO N
R[I]=10+RND(40)
X[I]=R[I]+RND(SCW-2*R[I])
V0[I]=-(5+RND(30)/10)
Y[I]=SCH-R[I]
V[I]=V0[I]
DX[I]=(RND(2)*2-1)*(RND(3)+1)
C[I]=RND(&HFFFFFF) OR &HFF404040
NEXT
CLS
@LOOP
GCLS
IF BUTTON(1) AND 16 THEN END
FOR I=0 TO N
GCIRCLE X[I],Y[I],R[I],C[I]
GPAINT X[I],Y[I],C[I],C[I]
V[I]=V[I]+G
IF Y[I] > SCH-R[I] THEN V[I]=V0[I]
INC Y[I],V[I]
INC X[I],DX[I]
IF X[I] > SCW-R[I] || X[I] < 1+R[I] THEN
DX[I]=-DX[I]
ENDIF
NEXT
VSYNC 1
GOTO @LOOP

今回のプログラムは、比較的簡単な内容です。
最初に定数の宣言です。

N=10:G=0.2:SCW=400:SCH=240

Nは円の個数-1、Gは加速度、SCWはスクリーンの横方向のピクセル数(Width)SCHはスクリーンの縦方向のピクセル数(Height)です。
次に、円を表すために必要なパラメータを、円の個数分、配列で宣言しています。
各変数の意味は、下図を見てください。

初期化時に、各円のY座標は画面下部に接する位置(床に接触した状態)とし、VYの初期値V0を上方向にランダムに与えています。
このV0が、床から跳ね返って上に向かう瞬間の初速になります。

X軸方向の移動量は、-1, 1のいずれか(RND(2)*2-1)をランダムに決め、さらにそれを1~3倍(RND(3)+1)しています。

pc14-4.jpg

ループの中では、まずGCLSで画面全体を消去します。
次にボタンの状態をチェックして、Aボタンが押されていればプログラム終了です。

そのあと、各ボールの処理をするループになります。
まずGCIRCLEで円を描き、GPAINTでその中を塗りつぶします。
境界色をGCIRCLEの色指定と同じ色にしていますので、他の描画済みの円があっても上書きします。

次にY座標の計算です。
まず、Y方向の速度VYに重力を表す加速度Gを加算します。
落下速度が時間につれて大きくなっていきますので、円の動きは下方向に向かって加速していきます。
この様子は下図を見てください。
pc14-5.jpg
そのあと、現在のY座標をチェックし、円の下端がスクリーンの下端を超えていたら、VYを初期値であるV0にリセットします。
V0は画面上方向に向かう初速ですので、これで円が床から上に跳ね上がります。

この部分ですが、物理法則から考えると

VY=-VY

としても良さそうに思えます。
しかし、今回は速度を整数ではなく浮動小数で表しているため、演算の際の計算誤差の問題があって、跳ね返るたびにだんだんVYの絶対値が小さくなっていってしまいます。

その後はX座標の計算ですが、こちらは座標が整数値ですので、画面の左右端でDXの符号を反転させるだけです。

今回のプログラムですが、Nの値をいろいろ変えてみると、18個(N=17)までは画面がちらつかずに描画することができました。
塗りつぶした円を描く命令が無いので、GCIRCLEとGPAINTを組み合わせて描きましたが、それでもかなり速いですね。

なお、プログラムの中身は大きく変えずに命令の実行順序を変えれば、さらにちらつきを少なくすることができます。
ループの中のFOR~NEXT文で、円1つずつ、描画と座標の計算をしていますが、ここを2つのFOR~NEXTループに分解して、まず全部の円を描画し、その後で全部の円の座標の計算をするように変更すると、21個(N=20)まで描けました。

プチコン3号 13日目 本体を傾けてキャラクタを動かす

3DSは移動や傾きを検出するモーションセンサがついています。今回はこれを使って、9日目のプログラムを傾きでコントロールするように変更してみました。

3DSには加速度センサが搭載されていて、平行移動(前後上下左右)の「加速度」、および回転(ピッチ、ロール、ヨー)の「速度」を計測できます。
SmileBASICではその値を読み出すことができるほか、回転については、時間軸に沿って速度を積算することで、トータルの回転角も得られるようになっています。
今回は、このトータルの回転角を使って、下画面が水平のときはキャラクタは静止し、画面を傾けたときは傾いた方向へ移動するようなプログラムを作ってみました。

座標がX、Y、Zの3つの軸で表されるのと同様、角度も以下の3つの値で表されます。

(1)X軸の周りでの回転(ピッチ)
(2)Y軸の周りでの回転(ロール)
(3)Z軸の周りでの回転(ヨー)

いずれも、原点から座標軸の正の方向を見て左回りで角度を測ります。

pc13-1.jpg

SmileBASICで値を読み出すには、

GYROA OUT P,R,Y

とします。
P,R,Yにそれぞれピッチ、ロール、ヨーの値が入ります。

このとき、角度の値は「度」ではなく「ラジアン」という単位で与えられます。
ラジアンで計測すると、180度がπ(パイ)ラジアンになります。
πは円周率のπ、すなわち3.14159265…です。
逆方向へ傾けた場合は負の値になりますので、角度の値の範囲は-πからπまでです。

なおGYROAコマンドを使うには、あらかじめ

XON MOTION

でモーションセンサをオンにしておかなければなりません。

また、先に書いたようにGYROAで読み出すトータルの回転角は、実際には回転の速度を積算したものです。
そのため、長期間使っていると誤差が出てきます。
水平位置に戻しても、水平ではなく角度がついているように認識される、ということが起こります。
これをリセットするには

GYROSYNC

命令を使います。
この命令を実行すると、その時点で3つの角度が全てゼロにリセットされます。

それではプログラムリストです。
実行すると下画面にキャラクタが表示され、画面を傾けるとトコトコと歩きます。
表示関連は、9日目の記事で説明しましたので今回は説明は省略します。

pc13-2.jpg
XSCREEN 2,255,2
DISPLAY 1
GX=184:GY=104:GC=2904
C=GC+4:C_OLD=GC
SPSET 0,C
SPSCALE 0,2,2
XON MOTION
GYROSYNC
@LOOP
SPOFS 0,GX,GY
IF C != C_OLD THEN
SPANIM 0,"I",15,C+1,15,C+2,15,C+3,15,C,0
C_OLD = C
ENDIF
IF BUTTON(1) AND 16 THEN GYROSYNC
GYROA OUT P,R,Y
DX=0:DY=0
IF ABS(P) > 0.05 THEN DY=SGN(-P)
IF ABS(R) > 0.05 THEN DX=SGN(R)
GX=MAX(MIN(GX+DX,384),0)
GY=MAX(MIN(GY+DY,224),0)
C=(3-(DY>=0)*(DX+2))*4+GC
IF DY != 0 || DX != 0 THEN
SPSTART 255
ELSE
SPSTOP 255
ENDIF
VSYNC 1
GOTO @LOOP

初期設定として

XON MOTION
GYROSYNC

を実行しています。
そのあとループの中で

IF BUTTON(1) AND 16 THEN GYROSYNC

としていますので、Aボタンを押せばいつでも角度の誤差をリセットできます。

次にGYROAで角度を読み出していますが、そのあと

IF ABS(P) > 0.05

というように値の絶対値をチェックしています。
これは、水平からある程度傾いたときに初めて「傾いた」と認識させるためです。
0.05ラジアン以上傾いたときのみ、DXとDYに値を設定しています。
ちなみに0.05ラジアンは、180*(0.05/3.14)=2.87度くらいです。

また、ピッチについては、上の図からも判るとおり、画面を手前から向こうへ傾けたときに正の値になりますが、このときキャラクタを画面上に向かって(Y座標が小さくなる方向へ)歩かせるので、ピッチの値とDYは正負が逆になります。

今回はこれで終わりです。
角度での入力は、単純にパッドやタッチパネルの代わりに使うよりも、物理的な動きをシミュレートするときなどに使うと良さそうです。

プチコン3号 12日目 再び迷路生成プログラムについて

pc12-1.jpg

前回作成した「迷路探検ゲーム」のプログラムは、迷路生成には5日目に作成したプログラムを使っています。
5日目のプログラムで使用したアルゴリズムは、「バイナリーツリー法」と言います。
バイナリーツリー(二分木)とは、枝が二又に分かれる木のようなデータ構造です。
バイナリーツリー法で生成した迷路は、その経路がスタート地点を根とし、右または下方向だけに伸びていくバイナリーツリーになります。
下図を見れば、実際そうなっていることが解るでしょう。

pc12-2.jpg

さて、バイナリーツリー法の迷路は、欠点があります。
その話の前に、「良い迷路」とはどういうものかを考えてみましょう。
一言で言えば、「一見して正解が判りづらいもの」ということになると思います。

下図を見てください。
迷路のすべての通路に紐を置き、それらを各部屋の中央で結んでツリー構造を作ります。
そして、スタート地点とゴール地点をつかんで引っ張り、まっすぐに伸ばしたと考えます。
すると、図の左の迷路は図の右のように表せます。

pc12-3.jpg

良い迷路とは、このように正解を中央の一本道で表現したとき、
・正解の道が短すぎず、
・正解の道からの脇道が少なすぎず、
・脇道が正解に比べて短すぎない
というような迷路だと考えることができます。

例えば図(A)のような迷路は、脇道は多いが短すぎるため、すぐ袋小路に行き当たってしまいます。
また図(B)のような迷路は、脇道は複雑ですが肝心の正解が短いため、すぐゴールへ到達してしまう可能性があります。

ではバイナリーツリー法で作られた迷路はどうでしょうか?

このアルゴリズムでは、正解の道の長さは「迷路の幅+迷路の高さ」が最大です。
なぜならUターン、つまり連続して2回右へ曲がったり、連続して2回左へ曲がることができないからです。
これは「北か西、どちらかの壁を残す」というルールから来ています。
Uターンするような経路を作ろうとしたら、このルールを満たさない部屋が必要になります。

正解の道の長さ、脇道の長さ、共にあまり長くすることができないのはバイナリーツリー法の欠点です。
また、上で述べたとおりUターンするような経路が作れないことも問題です。

というわけで、今回は5日目の記事よりも良い迷路を生成するアルゴリズム「リカーシブ・バックトラッカー法」による迷路生成プログラムを作ってみました。

5日目の記事でも紹介しましたが、以下のリンクで様々な迷路生成アルゴリズムが解説されています。

"Algorithm" is Not a Four-Letter Word

「リカーシブ・バックトラッカー法」は、その中でも比較的、簡単に良い迷路を生成するアルゴリズムです。
これは、以下のようなルールで迷路を作ります。

(1)現在地の部屋は、元来た部屋へ向かう以外の方向はすべて壁があると考える。
(2)現在地のすぐ隣の部屋で、まだ訪れていない部屋を(ランダムに)選び、壁を壊してその部屋へ進む。
(3)もし周囲が全て訪れたことのある部屋ならば、来た道をひとつ引き返す。
(4)再び(1)から始める。

これを繰り返すと、最終的に全ての部屋を回り終えた後、出発点の部屋にまで戻ってきます。
それ以上は引き返せませんので、これで迷路が完成です。
ちなみに「リカーシブ」とは再帰的、すなわちある作業をより簡単な作業に分解すると、その中に再び同じ作業が含まれているような性質を指します。
また「バックトラック」とは、来た道をなぞって戻っていくようなイメージです。

今回は、この「リカーシブ・バックトラッカー法」による迷路生成プログラムを作ってみました。

基本的なデータ構造は5日目と同じです。
すなわち、部屋が縦横に規則正しく並んでいて、各部屋は「西」と「北」に壁があるものと考えます。
また、迷路の周囲を「入れない部屋」が取り囲んでいて、壁を壊してその部屋へ進むことはできないものとします。

上記を二次元配列を使って表現する点も同じです。
ただし、今回は「西の壁と北の壁の両方が無い部屋」もありえますので、部屋の壁の状態と、配列の数値との対応は

・北、西に壁:3
・北に壁:2
・西に壁:1
・壁無し:0
・未訪問:-1
・入れない:4

というように変更します。
迷路の初期状態は、すべての部屋が「-1」で、その周囲を「4」の部屋が取り囲んでいます。

pc12-4.jpg

「リカーシブ・バックトラック法」では、進めなくなったらどんどん後戻りしますので、元来た部屋をすべて記録しておく必要があります。
そのために「スタック」を使います。

スタック(Stack)とは積み重ねたものという意味ですが、その名の通り、データを追加するときは古いデータの上に新しいデータを積み重ねます。
そして、データを取り出すときは、新しいデータから取り出していきます。
積み重ねる操作を「Push」、取り出す操作を「Pop」と言います。

pc12-5.jpg

未訪問の部屋へ移動するときは、今いる部屋の座標をスタックへ「Push」します。
そして、後戻りするときは、戻るべき部屋の座標をスタックから「Pop」します。
SmileBASICでは、配列をスタックのように扱う命令「PUSH」「POP」が用意されていますので、今回はこれを使います。
なおSmileBASICの「PUSH」「POP」命令は、DIMで宣言した配列のサイズを超えた場合には配列のサイズを自動で大きくします。

(なお「リカーシブ」なプログラムの書き方としては、関数定義の中でその関数自身を呼び出すやり方が有名です。SmileBASICも、DEF文を使ってそのような関数定義が書けます。
ただ、残念なことに現在のバージョンのSmileBASICは再帰呼び出しできる回数に制限があり、それを超えるとエラーになってしまいます。具体的には、千数百回程度が限界のようです。
迷路の経路の最大の長さをこの回数が以下にしないとエラーになってしまいます。エラーにならない迷路のサイズは、目安としては50×50程度までです。
40×40の迷路でも1600部屋ありますから、脇道無しならエラーになる可能性があります。
そのため、今回は再帰呼び出しではなく、ループとスタックを使ってプログラムを実現しています。)

それではプログラムリストです。

pc12-6.png
M_W=199:M_H=119
DIM R[M_W+2,M_H+2]
FOR J=0 TO M_H+1
FOR I=0 TO M_W+1
IF I==0 || I==M_W+1 || J==0 || J==M_H+1 THEN
R[I,J]=4
ELSE
R[I,J]=-1
ENDIF
NEXT
NEXT
DIM XSTK[0],YSTK[0],DIR[4]
PUSH XSTK,0:PUSH YSTK,1
X=1:Y=1:R[X,Y]=3
ACLS:GFILL 1,1,399,239:GPSET 399,238,0
REPEAT
GLINE X*2,Y*2,XSTK[LEN(XSTK)-1]*2,YSTK[LEN(YSTK)-1]*2,0
N=0
IF R[X+1,Y] < 0 THEN DIR[N]=0:INC N
IF R[X,Y+1] < 0 THEN DIR[N]=1:INC N
IF R[X-1,Y] < 0 THEN DIR[N]=2:INC N
IF R[X,Y-1] < 0 THEN DIR[N]=3:INC N
IF N > 0 THEN
PUSH XSTK,X:PUSH YSTK,Y
ON DIR[RND(N)] GOTO @E,@S,@W,@N
@E:X=X+1:R[X,Y]=1:GOTO @DONE
@S:Y=Y+1:R[X,Y]=2:GOTO @DONE
@W:R[X,Y]=R[X,Y] AND 1
X=X-1:R[X,Y]=3:GOTO @DONE
@N:R[X,Y]=R[X,Y] AND 2
Y=Y-1:R[X,Y]=3:GOTO @DONE
@DONE
ELSE
X=POP(XSTK):Y=POP(YSTK)
ENDIF
UNTIL X==0
REPEAT UNTIL BUTTON(0):GCLS

1行目で、迷路のサイズを決めています。
今回は迷路の描画にはグラフィックスを使い、400ドット×240ドットの画面の2×2ドットで迷路の1部屋を表現することにしました。
それに合わせて、画面全体を迷路にする199×119という巨大迷路にしています。

最初の配列の初期化処理は、5日目のときとほぼ同じです。
ただし、先に説明したように、初期値は壁が「4」それ以外が「-1」となっています。

12行目で、座標を格納するスタックのための配列XSTK、YSTKと、進むことができる方向を記録するための配列DIRを宣言しています。
そして、スタックに座標(0,1)をプッシュしていますが、これは座標ではなくて「スタックが空である」ことの目印のために使います。
迷路の中の座標でX=0となるのは迷路の周囲の壁だけであり、迷路の中の座標でXがゼロになることはないからです。

スタート地点は(1,1)とし、その部屋を訪問済みにしています。壁は西・北とも「あり」の状態です。

そして、REPEAT~UNTILのループで迷路の全ての部屋を訪問します。
ループから抜けられるのはX==0のときですが、この条件が満たされるのは13行目でスタックにプッシュした0がポップされたときだけです。

まず、現在の部屋の上下左右の部屋が訪問済みかどうかチェックし、未訪問ならその方向を配列「DIR」に追加します。
方向は、東・南・西・北をそれぞれ0,1,2,3で表します。

Nには、DIRに格納されている方向の個数が入ります。
(実はDIRもスタックにしても良かったのですが、スタックを簡単に空にする命令が見当たらなかったので止めました。)

そして、未訪問の部屋が1つ以上ある場合は、まず現在地をスタックにプッシュします。
次いで

DIR[RND(N)]

で、未訪問の方向を1つ、ランダムに選び、その方向に進みます。

進んだ先の部屋では、進行方向と整合するように北・西の壁の設定をします。
たとえば東の部屋へ進んだら、進んだ先の部屋に西の壁があるのはおかしいので、「北の壁のみあり」の状態にします。

西に進む処理で

R[X,Y]=R[X,Y] AND 1

という処理をしていますが、これは「現在いる部屋の西の壁を取り払う(北の壁は、あっても無くても現状維持)」ことを表します。
同様に北に進む処理では、現在いる部屋の北の壁を取り払います。

未訪問の部屋がひとつも無かった(N==0)場合は、スタックからX,Yをひとつ取り出し、そこへ移動します。
(つまり、来た道を1つ引き返す。)

スクリーンいっぱいの迷路ですが、けっこうあっという間に作成が終わります。
やはり、BASICとはいえ昔のマシンとは違いますね。
そもそも昔の8ビット機だったら、200×100の配列を使うプログラムなんて、ちょっと使うのがドキドキするようなメモリ食いのプログラムだったと思います。