検証05-2：pyxelのパレットファイルの読み込み

pyxelのカラーパレット変更は「colors.from_list」を使用する以外にパレットファイルを読み込む方法があります。

リソースファイル(.pyxres)の読み込み時に、同じフォルダにリソースファイルと同名のパレットファイル(.pyxpal)が存在する場合、そのパレットファイルを読み込んでパレットの設定色が変更されます。

例：

リソースファイルが

a.pyxres

の場合、パレットファイルは

a.pyxpal

になります。

パレットファイルは改行区切りの16進数で書かれたカラーコード(0～ffffff)が色数分書かれたファイルです。

例：pyxelのデフォルトのカラーパレット

↓ここから----------------------------

0
2b335f
7e2072
19959c
8b4852
395c98
a9c1ff
eeeeee
d4186c
d38441
e9c35b
70c6a9
7696de
a3a3a3
ff9798
edc7b0

↑ここまで----------------------------

サンプルとして、pyxelデフォルト+セーフカラーのパレットファイル(231色)の内容をGoogleドキュメントに載せました。

pyxelデフォルト+セーフカラーのパレットファイル

パレットファイルに設定可能な色数(行数)は1～255の範囲になります。

16色未満でも設定は可能ですが、その場合はリソースエディタのパレットの一部が選択出来なくなります。

※上図は黒「0」,白「ffffff」の2色のみに設定した場合です。白の右側全てと下段のパレットは選択出来ません。

なお、パレットファイルを空ファイルにするとエラーが発生します。

※リソースエディタは起動しますが、点を書き込む等の何かを描く操作でエラーになります。

パレットファイルから読み込んだ場合、設定したパレットより後ろのパレット番号を指定するとエラーが発生します。

例：パレットファイルが30行だった場合、「pyxel.colors[50]=0xdddddd」等はインデックスエラー発生

※「colors.from_list」でパレットを追加した場合も同様です。

そのため、プログラム実行中にパレットの書き換えを行う場合は、予めパレットを254まで確保しておくとパレット数に関しては管理が不要になります。

無駄になる場合もありますが、シビアな環境でなければインデックス管理が少し楽になるかも知れません。

以上です。

検証05-1：pyxelのカラーパレットの色追加

pyxelはver2.0からカラーパレットを追加して16色を超える色数が使える様になっています。

pyxelの公式サイトの情報で「グラフィックス」の「colors」の項に載っている一文、

「パレットの…」の説明にある「colors.from_list」と「colors.to_list」とその中の例が参考になりそうなので、そこから調べてみました。

・「colors.to_list」：現在のカラーパレットをリストで取得

・「colors.from_list」：カラーパレットをリストでまとめて更新

・「colors[n]」※nは0～254：指定したインデックスのカラーパレットを1つだけ更新

範囲外のインデックスを使用したり、要素が255を超えるリストを設定すると以下のエラーが発生します。

----------------------------

pyo3_runtime.PanicException: Number of colors must be between 1 to 255

----------------------------

※インデックスは「0～254」の255色が指定可能です。

pyxelのサンプルプログラム「05_color_palette.py」には16色分のカラーパレットを表示する機能があります。

このサンプルを少し手直しして、追加されたカラーパレットも表示出来る様にしてみました。

手直ししたソースはGoogleドキュメントに載せてあります。

カラーパレット追加

実行画面

パレット番号の0～15は既存のカラーパレットのカラーコードがそのまま設定されています。

16～230は以下のパターンでカラーコードを設定しています。

・各色相の値は0x00→0x33→0x66→0x99→0xcc→0xff→繰り上がって0x00に戻るのを繰り返す。

・0x10000倍の桁が赤、0x100倍の桁が緑、0x1倍の桁が青。

・0xffffffで終了。

※要はWebセーフカラー(ブラウザやOSの種類に関係なく、Web ページで常に表示できる216色のカラー)です。

追加用カラーコード一覧：PNoは通し番号(パレット番号は既存の最終パレット番号(=15)+PNoになります)

※PNo=0(カラーコード：0x000000)はpyxelデフォルトのカラーパレット0に存在するので追加対象から除外

上記から更にカラーパレットを追加して最大数の254まで埋めてみます。

以下の図はパレット番号231以降を最大値(254)まで0埋めして、最終インデックスが分かりやすい様にパレット番号254には0xddddddを上書きで設定しています。

この様に、カラーパレットを最大255色まで設定することが可能です。

次に色を追加することによる画像読み込み時の色変換の変化を確認します。

pyxelではpng等の画像ファイルを読み込んだ際に画像の中のカラーパレットに存在しない色がカラーパレットに存在する近い色に自動変換されます。

そこで、カラーパレットの色数が16色の時と、色数を増やした時とで同じ画像がどの様に変換されるかを比較してみます。

読み込む画像は、Windows標準ソフトのペイントで色の編集時に表示されるカラーパレット部分を切り取って使用します。

ペイント

赤矢印の部分をクリックすると色の編集画面が表示されます。

↓↓↓

「色の編集」で表示されるカラーパレットの部分だけを切り取ってファイルに保存します。

↓↓↓

このファイルをプログラムから参照可能な場所に置いて、pyxelのイメージクラスのloadメソッドで読み込んで表示します。

読み込んで表示した結果が以下になります。

左が16色のまま読み込んだ画像、右がパレット番号230までカラーパレットを追加して読み込んだ画像

※カラーパレット追加前に画像を読み込むと16色の状態で変換されるので、画像はカラーパレット追加後に読み込みます。

この様により多くの色が使用された画像に変換されることが分かります。

上記のテストではカラーコードを機械的に設定して追加しましたが、設定する色を調整することでより繊細な色彩の画像に変換することも可能になります。

サンプルとして、以下の花(ツバキ)の画像をカラーパレットを変更して読み込んでみます。

オリジナル画像

左から、

・pyxelデフォルトのカラーパレット

・上記のテストで機械的にパレット番号230まで設定したカラーパレット

・pyxelデフォルト+この画像で使用された色に合わせたカラーパレット

となります。

右の画像のカラーパレットは以下の様になっています。

この様に画像に特化したパレット構成にすると再現性がかなり高くなるのが分かると思います。

カラーパレットがこれだけ増えると、キャラやオブジェクト等に少しずつパレットを割り振って、表示するもの毎に部分的に書き換えながら使うと色数はほぼ無制限と考えられます。パレットの管理は大変そうですが…

以上です。

検証04-4：擬似3D迷路の多階層化(pyxel版)

壁伸ばし法で作成した迷路は、(偶数,偶数)のマスは必ず壁になり、(奇数,奇数)のマスは必ず通路になる特徴があります。

※左上の座標を(y,x)=(0,0)とした場合

例えば通路に宝箱や仕掛けを作ろうとした場合、(奇数,奇数)のマスに作れば壁かどうかをいちいち調べる必要がなく設置出来ます。

この特徴から(奇数,奇数)のマスに梯子やエレベータ等の(y,x座標が移動しない)垂直昇降装置を作ると、別の迷路でも大きさが同じなら確実に通路に移動することが出来ます。

そこで、今回は同じ大きさの迷路を多階層化して、謎のワープ装置で上の階(つまり別の迷路)の同じ座標に移動する処理を組み込んでみました。

あと、迷路が難解になり過ぎるので自分の周囲だけを確認出来るミニマップを右下に付けました。

こちらも参照：

『検証04-1：迷路内の擬似３Ｄ化(pyxel版)(1)：擬似３Ｄの描画』

pyxelの機能でgifを作ってみました。

操作方法：

前進：↑ボタン、左旋回：←ボタン、右旋回：→ボタン、振り返り：↓ボタン

壁色変更：スペースキー、迷路リセット：Qキー

※マウスでの操作も可能です。

前進、振り返り：マウスホイール、左旋回：左クリック、右旋回：右クリック

迷路リセット：左右同時クリック(操作が少しシビアですが…)

※ゲームコントローラーでの操作も可能です。

※PS4のゲームパッドでテストしました

前進：↑、振り返り：↓、左旋回：←、右旋回：→、

迷路リセット：OPTIONSボタン(STARTボタン？)

※謎のワープ装置のマスに移動すると装置が勝手に起動してワープします。

※ゴールに到達しても「GOAL!」と表示されるだけです。

ソースはGoogleドキュメントに載せてあります。

迷路の多階層化

githubにhtmlを置いて実行出来る様にしてみました。

web版

リソース：イメージバンク0

迷路内の擬似３Ｄ化のリソースに謎のワープ装置を追加しました。

※下向き三角は下層へのワープ用ですが今回は未使用です。

以上です。

検証04-3：迷路内の擬似３Ｄ化(pyxel版)(3)：壁の描画順

視界内に表示される壁を把握して実際に壁を描画する際、壁の見た目上の重なりを表現するために描画する順序を工夫する必要があります。

工夫と言っても難しいことではなく遠い壁から描画して、先に描画した壁が後に描画した壁に上書きされることを利用します。

奥の壁の一部が手前の壁に隠れる場合に、隠れる部分の描画範囲の計算などの特別な考慮をする必要なく壁の遠近を表現出来ます。

但し、同じ距離の壁の内横壁をセットで描画する場合、より外側から描画する必要があります。

壁の描画順の例

・遠距離→中距離→近距離→側の順で描画します。

・同距離の中で、遠距離は横壁を描画しないので順不同、他は端から順に描画します。

※中距離の描画順は上記の例以外に、左2→左1→右2→右1→0でも問題ありません。

サンプルマップを使用して壁が上書きされて一部(または全部)が隠れる様子を確認します。

サンプルマップ：自分の位置=(7,3)＆上向き

※描画のロジックの一部をコメントアウトして手前の壁が表示されない様に調整しながら確認します。

1.遠距離のみ(赤枠の範囲)表示

→遠距離の正面壁のみ表示されます。

2.遠距離＋中距離を表示

→左側の遠距離の壁が中距離の壁に上書きされて見えなくなります。

3.遠距離＋中距離＋近距離を表示

→遠距離と中距離の壁全てが近距離の壁に上書きされて見えなくなります。

4.遠距離＋中距離＋近距離＋側を表示

→右側の近距離の壁が側の壁に上書きされて見えなくなります。

この様に遠くの壁から順に描画することで、描画範囲の細かい調整等をすることなく遠くの壁が隠れて見えないことを表現出来ます。

但し、例えば見える範囲のみマッピングしていく様な機能を追加する場合にはどこが見えなくなるのかを正確に把握する必要があるので、壁の一部分だけ見えている場合の描画が楽になる程度になります。

以上です。

検証04-2：迷路内の擬似３Ｄ化(pyxel版)(2)：「向き」と「視界」②

２. 三角関数を使用した相対座標の求め方

視界内の相対座標を求める際に、予め4方向全ての相対座標をリスト等に入れておいて使用することも出来ますが、ここでは三角関数のsinとcosを用いて使用時点で計算して求めます。

コンピュータの座標で三角関数を使用するに当たり、ひとつ注意があります。

数学の座標平面とコンピュータの画面の座標ではY軸のプラスとマイナスの向きが逆になります。

そこで、Y座標を求めるのに使用するcosは取得した結果にマイナスを掛けて使用します。

※追記

斜めの計算は必要なかったので、現在は上(0°)・右(90°)・下(180°)・左(270°)の4方向で計算しています。

↓以下はあまり考えずに取り合えず作ってみた時のやり方の説明です。

まずcos(マイナスを掛けるので正確には"-cos")とsinの角度毎の値を確認します。この表の値は自分の位置から見ている方向を表すベクトルになります。

※使用する際は-cosとsinの値をROUND関数で四捨五入します。

・45°毎の-cosとsinの一覧表

※便宜上、この表は「CS表」と略します。

※上表の-cosとsinの値はROUND関数に影響が出ない範囲で丸めています。

　→例えば、実際の-cos 45°の値は-0.70710678…となります。

※表外の丸数字は、自分の周囲の相対座標取得時に使用します。

イメージとしては、Y軸が逆向きの座標平面の真ん中に立って、その角度をROUND(-cos)とROUND(sin)が示す距離分見ている感じになります。

2-(1) 上向きの相対座標の求め方

2-(1)-1 自分の位置(0,0)の周囲の相対座標の求め方

上向き(角度0°)時の視界は-90°～90°の範囲になり、CS表の「⑦⑧①②③」の値が対象となります。

座標平面で表すと下図の範囲になります。

視界のイメージ図(上向きの場合)

視界内の相対座標表(上向きの場合)

y=ROUND(-cos)、x=ROUND(sin)とした場合、この座標平面を視界のイメージ図の赤枠の範囲に見立てると相対座標表(上向きの場合)とCS表の値が一致します。

この赤枠内の値を利用して上向きの視界内の全てのマスの座標を求めることで、向き変更時にもCS表の角度の範囲を変更するだけで変更した向きの全てのマスの座標が求まります。

2-(1)-2 正面の相対座標(近0、中0、遠0)の求め方

近0の座標は①と一致するので①の座標(-1,0)となります。

中0と遠0の座標は、それぞれ近0の2倍、3倍の距離になるので①×2(=(-2,0))、①×3(=(-3,0))で求まります。

2-(1)-3 正面以外の相対座標の求め方

正面以外の座標は、自分の位置(0,0)から右1マス分のベクトルを求めて、中0、遠0から横向きの距離を計算することで求まります。

(0,1)-(0,0)→(0,1)となります。

↓↓↓

各相対座標は以下の通り

中右1：(-2,0)+(0,1)→(-2,1)

中右2：(-2,0)+(0,1)×2→(-2,2)

中左1：(-2,0)-(0,1)→(-2,-1)

中左2：(-2,0)-(0,1)×2→(-2,-2)

遠右1：(-3,0)+(0,1)→(-3,1)

遠右2：(-3,0)+(0,1)×2→(-3,2)

遠左1：(-3,0)-(0,1)→(-3,-1)

遠左2：(-3,0)-(0,1)×2→(-3,-2)

2-(2) 上向き以外の相対座標の求め方

・右向きの相対座標

右向き(角度90°)時の視界は0°～180°の範囲になり、CS表の「①②③④⑤」の値が対象となります。

視界のイメージ図(右向きの場合)

視界内の相対座標表(右向きの場合)

CS表

CS表の①～⑤と相対座標表が一致

・正面の座標

上向きの計算と同様にそれぞれのマスの座標を求めます。

近0が③の座標(0,1)なので、中0と遠0の座標は③×2(=(0,2))、③×3(=(0,3))となります。

・正面以外の座標

自分の位置から右1マス分=(1,0)なので、各相対座標は以下の通り

中右1：(0,2)+(1,0)→(1,2)

中右2：(0,2)+(1,0)×2→(2,2)

中左1：(0,2)-(1,0)→(-1,2)

中左2：(0,2)-(1,0)×2→(-2,2)

遠右1：(0,3)+(1,0)→(1,3)

遠右2：(0,3)+(1,0)×2→(2,3)

遠左1：(0,3)-(1,0)→(-1,3)

遠左2：(0,3)-(1,0)×2→(-2,3)

となります。

下向き、左向きも同様の計算手順なので省略します。

「向き」と「視界」は以上です。(3)に続きます。

検証04-2：迷路内の擬似３Ｄ化(pyxel版)(2)：「向き」と「視界」①

※向きと視界の設定と表記について

２Ｄの迷路を３Ｄ化することで、「向き」と「視界」を考慮する必要が出てきます。

この検証プログラムの解説では、向きと視界を以下の様に設定および表記しています。

・向き：「上、右、下、左」の４方向

・視界：距離４段階、列は正面と左右２列の計５列

　→距離：遠い方から「遠距離、中距離、近距離、側」と表記。(「遠、中、近、側」と略して表記する場合もあり)

　→列：正面を「0」、右は近い方から「右1、右2」、左も同様に「左1、左2」

　※但し、「側と近距離の右2、左2」および「遠距離の側面」は視界外とします

　※正面に壁があってその先の壁が見えなくても視界とします

・視界内のマスは距離と列を繋げて表記

　例：自分の位置(赤マス)：「側0」、正面は近い方から「近0」「中0」「遠0」、遠距離左に2列目は「遠左2」

　使用例：「上向きの場合、遠左2の相対座標は-3,-2」等

視界のイメージ図(上向きの場合)

※色の着いたマスが視界

※赤マスは自分の位置、黄色マスは正面の視界、グレーマスはその他の視界範囲、青矢印は向き

１．視界内のマップ座標の取得

視界内に壁を表示するために、視界とマップ座標を関連付けて壁と通路の位置を把握します。

1-1 視界内の相対座標

自分の位置(赤マス)からの相対座標を求めて下図に(y,x)で表記します。

※相対座標の求め方は説明が長いので後でまとめて解説します(※1)。

※自分の位置を(0,0)として、上は「y」がマイナス、下は「y」がプラス、左は「x」がマイナス、右は「x」がプラスとします

この相対座標にマップ座標を合わせることで、マップの壁と通路の情報を取得します。

視界内の相対座標表(上向きの場合)

※視界内の壁を描画するためには上表で色の着いた位置のマップ座標を取得する必要があります

1-2 マップ座標の取得

以下のサンプルマップ(下図左)の(5,5)の位置(赤斜線)で上を向いた場合、(下図右)赤枠内の太線で囲われた範囲が視界となります。

※自分の位置の座標は、赤マスの位置(5,5)に視界内の相対座標(0,0)を足して(5,5)となります

例：視界内の以下のマップ座標は次の通り

遠左2：(5,5)+(-3,-2) → (2,3)

遠右2：(5,5)+(-3,2) → (2,7)

側左1：(5,5)+(0,-1) → (5,4)

側右1：(5,5)+(0,1) → (5,6)

実行画面

・向き変更時の相対座標

上向き以外も向きに応じた相対座標図を作成して上向きと同様にマップ座標を求めます。

視界内の相対座標表(右向きの場合)

例：視界内の以下のマップ座標は次の通り

遠左2：(5,5)+(-2,3) → (3,8)

遠右2：(5,5)+(2,3) → (7,8)

側左1：(5,5)+(-1,0) → (4,5)

側右1：(5,5)+(1,0) → (6,5)

実行画面

視界内の相対座標表(下向きの場合)

例：視界内の以下のマップ座標は次の通り

遠左2：(5,5)+(3,2) → (8,7)

遠右2：(5,5)+(3,-2) → (8,3)

側左1：(5,5)+(0,1) → (5,6)

側右1：(5,5)+(0,-1) → (5,4)

実行画面

視界内の相対座標表(左向きの場合)

例：視界内の以下のマップ座標は次の通り

遠左2：(5,5)+(2,-3) → (7,2)

遠右2：(5,5)+(-2,-3) → (3,2)

側左1：(5,5)+(1,0) → (6,5)

側右1：(5,5)+(-1,0) → (4,5)

実行画面

長いので分割します。「向き」と「視界」②に続きます。

検証04-1：迷路内の擬似３Ｄ化(pyxel版)(1)：擬似３Ｄの描画

迷路を作ってもただ上から眺めて左上から右下まで目で追ってなんとなくゴールした気分になっても空しいだけなので…

迷路の中を歩き回ってゴールを目指す感じになる様に、迷路をレトロゲームエンジンpyxelで擬似３Ｄ化してみました。

一点透視法を使って壁等の大きさを計算して扱いやすい数値に丸めています。

pyxelの機能でgifを作ってみました。

操作方法：

前進：↑ボタン、左旋回：←ボタン、右旋回：→ボタン、振り返り：↓ボタン

壁色変更：スペースキー、迷路リセット：Qキー

※マウスでの操作も可能です。

前進、振り返り：マウスホイール、左旋回：左クリック、右旋回：右クリック

迷路リセット：左右同時クリック(操作が少しシビアですが…)

※ゲームコントローラーでの操作も可能です。

※PS4のゲームパッドでテストしました

前進：↑、振り返り：↓、左旋回：L1ボタン、右旋回：R1ボタン、

迷路リセット：OPTIONSボタン(STARTボタン？)

ソースはGoogleドキュメントに載せてあります。

迷路内の擬似３Ｄ化

迷路自動生成クラスのソースはこちらです。

c103maze.py

※「擬似３Ｄ」というのは、

・Wizardryシリーズ

・ダンジョンマスター

・真・女神転生シリーズ

等々、のダンジョンをイメージしていただくと理解しやすいかと思います。

今回の擬似3Dを作成するにあたり、上記3シリーズを参考にしました。

擬似ではない本物の３Ｄを作るには今の自分には技術的に無理そうなので、３Ｄっぽく見える２Ｄの画像をそれっぽい位置に表示して３Ｄを表現しています。

ここでは主に実際に描画される各パーツや一点透視法による３Ｄ表現について解説します。

画面

ちなみに当初案はこちらになります。

最初はこちらの比率にしようと思ったんですが、通路上に何かを表示する際に「小さすぎる」ので現行サイズにしました。

リソース(256*256)：イメージバンク0

一段目(左から)：正面壁遠距離、正面壁中距離、正面壁近距離、謎のゴールポール

二段目：横壁中距離左右、横壁近距離左右、横壁側左右、横壁中距離左右(一列外側)

三段目：コンパス枠、コンパス向き(上、右、下、左)

四段目：移動操作表示(左折、右折、前進、振り返り)

遠近感を出すために遠くのものは小さく、近くのものは大きく見える様にサイズを変えています。

正面に壁がある直線の通路を前進した時の画面表示になります。

一歩進む度(画像の左上→右上→左下→右下の順)に正面の壁が大きく描かれます。

謎のゴールポールはただゴールに座標を合わせるだけだと達成感が薄いので、目標物として立ててみました。

謎のゴールポールも近くなると大きく描かれます。但し、ゴールの位置に立つと見えなくなります。

画面右上に表示されているコンパスは自分が向いている方向を示します。

左から、上向き、右向き、下向き、左向きとなります。

コンパスの外円の中は市松状に透過色を設定して壁と重なった時に少し透過する様にしています。

画面下の移動操作表示は、動いたことが把握しやすい様に移動操作時に0.1秒だけ表示されます。

移動操作後に表示される壁のパターンが全く同じ場合に座標表示またはコンパス以外に違いがなくなるので追加しました。

※ラグで実際は0.1秒より少し長い時間表示されている場合もありますが設定では0.1秒を超えたら表示を消しています。

※FC版Wizardryでは、移動操作時に一瞬だけ暗転することで移動操作を表現している様です。

横壁中距離左右と横壁中距離左右(一列外側)の違いですが、

一点透視法の場合、奥の一点から放射状に引いた線上に物体を描くので外側の方が角度的に開いて見えます。

正面近くの横壁(画像左)よりも正面から一列外側にある横壁(画像右)の方が開いて見える様に描いています。

見栄えの確認用に、壁色を変更出来る様にしてあります。

リソース(48*24)：イメージバンク1

壁の位置に先に色を描画して、その上から壁を透過指定で描画して色が表示される様に作ってあります。

階層違いや特殊な場所を表現するのに使えそうな気がします。

左上の座標は上段が自分の現在の座標(x,y)、下段はゴールの座標(x,y)になります。

自分がスタート座標にいる場合は"START!"、ゴール座標にいる場合は"GOAL!"と表示されます。

(1)は以上です。(2)に続きます。

迷路自動生成のクラス化

サイズを与えるとそのサイズの迷路を生成して返す関数を作ってクラス化しました。

ソースをGoogleドキュメントに載せました。

ソースファイル名：c103maze.py

クラス名：Maze
迷路自動生成(壁伸ばし法)クラス

・使い方
迷路クラスのインスタンスを作って「getmaze」関数に迷路のサイズ(横＆縦)を渡すと迷路データのリストが返されます。


迷路クラス呼び出しのサンプルプログラムを作ってみました。
こちらのソースもGoogleドキュメントに載せました。
迷路自動生成クラス呼び出しテスト

-ソース------------------------------------------------------
T105maze.py 迷路自動生成クラス呼び出しテスト
import pyxel as px

from c103maze import Maze

class App():
    def __init__(self):
        #self.h,self.wは5以上の奇数！
        self.h=131       #迷路の縦幅(外周込み)
        self.w=201       #迷路の横幅(外周込み)
        px.init(610,400,title="迷路自動生成クラス呼び出しテスト"+f"({self.w}*{self.h})",display_scale=2)
        px.mouse(True)
        self.sttflg=0   #開始フラグ
        self.lmap=[]

        px.run(self.update,self.draw)

    def update(self):
        if self.sttflg==0:                      #開始前の場合
            wk=Maze()
            self.lmap=wk.getmaze(self.w,self.h)
            self.sttflg=1                       #開始済にする
        elif px.btnp(px.MOUSE_BUTTON_RIGHT):    #開始済時に右クリックされた場合
            self.sttflg=0   #開始フラグ初期化
            self.update()   #update処理

    def draw(self):
        px.cls(0)

        #迷路描画
        for j in range(self.h):
            for i in range(self.w):
                if self.lmap[j][i]==1:
                    px.rect(3+i*3,3+j*3,3,3,7)  #壁を四角で表示

App()
-------------------------------------------------------

以上です。

検証03-2：迷路自動生成後にゴール探索追加

迷路の自動生成後に作成された迷路のゴールを探索する処理を追加してみました。

この迷路には元々スタート・ゴールという設定はないので、左上をスタート、右下をゴールとしてルート探索を行います。

実際にゴールの探索を行う際は、スタートとゴールを通路上の任意の場所に設定して使用します。

探索系のアルゴリズムには何種類かありますが、その中で「幅優先探索」を採用しました。

※Wikipedia等に載っていますので、専門的な解説が必要な場合はそちらを参照してください

理由は大体以下の通りです。

・処理が単純

・解が存在する場合、必ず解を見つけられる完全性

・重み(隣りのマスに進むコスト)の考慮は無いが、そもそも迷路の道のコストが一律(コストが常に1)なので不要

等々、迷路のゴール探索に向いていると思われるからです

どの様な探索法かと言うと「しらみつぶしに探して、途中でゴールが見つかったらそこで終了」という感じになります。

ソースはGoogleドキュメントに載せてあります。

迷路自動生成後にゴール探索追加

幅優先探索によるゴール探索の解説

1.以下のリストを作成する。

・探索座標リスト：探索座標を登録し、先頭から抜き出して使用する

・探索済み保存用リスト：探索座標から各方向の調査を行う時に調査方向の道が探索済みかチェックする

・経路保存用リスト：探索座標と調査先を関連付けてゴールに辿り着いた後にスタートに戻れる様にする

2.スタート座標を探索座標リストに入れる。

3.以下の3-1～3-5の処理を探索結果が出るまで繰り返す。

3-1.探索座標リストが空の場合、探索結果を「ゴールなし」として処理を抜ける。

3-2.探索座標リストの先頭データを抜き出す(抜き出したデータは探索座標リストから削除する(popメソッドを使用))。

3-3.探索済み保存用リストに抜き出したデータを登録する。

3-4.探索座標がゴール座標の場合、探索結果を「ゴール到達」として処理を抜ける。

3-5.探索座標の隣(上下左右)の座標を調査し、未探索かつ通路の場合は探索座標リストと経路保存用リストに追加する

4.探索結果に応じて以下の処理を行う。

4-1.ゴール到達の場合はゴール座標をマップにセットし、ゴール座標から順に経路保存用リストでスタートまで辿る。

4-2.ゴールなしの場合は経路を辿る処理をしない様にフラグを立てる。

5.探索結果がゴール到達の場合はマップに経路を描画する。

Googleドキュメントに載せてあるソースには左クリックでゴール探索および経路表示、右クリックで迷路の再作成を行う様にしてあります。

以上です。

検証03-1：迷路自動生成テスト応用編(区画と小部屋作成)

迷路自動生成の応用編として、前の記事で少し触れましたが「区画線」と「小部屋」がある迷路の自動生成について解説します。

設定上の話になりますが、右上、右下、左上に小部屋、黄色の十字を扉として固定配置し、間の迷路が書き換わることでそれぞれの小部屋や扉へのアクセスの仕方を変化させています。

ソースはGoogleドキュメントに載せてあります。

迷路自動生成テスト応用編

区画線と扉について

区画線は迷路作成前に引いておくことで、線で区切られた区画毎に隣接した別々の迷路が出来上がります。

区画線の引き方は、左上の座標を(y,x)=(0,0)としてy(またはx)が偶数の行(または列)に引きます。

区画間の行き来をするための扉は区画線上でyが奇数ならxは偶数、yが偶数ならxは奇数の座標に設置します。

ここまで設定してから迷路の自動生成を行うと、一例として以下の様な迷路が出来ます。

小部屋について

小部屋は上記の区画線と扉の応用になります。小部屋の範囲内の起点を取り除くことで小部屋内に新たな壁が発生せずに部屋になります。

↓↓↓

ここまで設定してから迷路の自動生成を行うと、一例として以下の様な迷路が出来ます。

但し、小部屋は壁と接点を作る必要があります。

上記の例の様に壁と一体化した小部屋なら問題ありませんが、以下の例の様な位置に作るとルートが一意にならなくなります。

例：壁に接点のない小部屋

↓↓↓

迷路自動生成を行うとルートが複数作られる

一か所壁とつないでおく等の工夫が必要

以上です。