So-net無料ブログ作成
ゲーム欲 プチコン3号 ブログトップ
前の10件 | -

迷路探索シミュレーター A法その5 [ゲーム欲 プチコン3号]

前回にも書きましたが,@SHORT1,@SHORT2ルーチンは,
  マシン語などでコンパイルして使うと早くて良いのです.
  ただ,256(区画)×256(歩数)ループで計算させていて,無駄が多いです.
  ここには改良の余地があり,次回直します.

<趣味画像 3536> 歩数0から増やしていきます
3536 迷路シミュレーター527.JPG

<趣味画像 3537> 歩数MAPが,ゴールにとどけばおしまい
3537 迷路シミュレーター528.JPG

歩数MAPを作る部分と,それから手順を生成する部分に分けていて,
  普通は続けて実行することになります.
  MAP5は,二次元のMAPではなく,手順が並んだ一次元です.
  ゴール位置から,矢印のお尻をたどることで,生成されます.

<趣味画像 3538> 8歩でゴールする例
3538 迷路シミュレーター529.JPG

<趣味画像 3539> 歩数の分だけ手順があるはず
3539 迷路シミュレーター530.JPG

<趣味画像 3540> S2MODEが1ならば,一手順読みだし
3540 迷路シミュレーター531.JPG

これで終わりです.次回は,迷路の大きさを30×30にして,
  A法のルーチンも対応させて,難しい迷路を解かせてみましょうか.

<関連記事> 今回も画像は別画面で大きく表示されます(横1000ピクセル)
3530 迷路シミュレーター525.JPG 平成27年 4月27日 迷路探索シミュレーター A法その4
3504 迷路シミュレーター521.JPG 平成27年 4月19日 迷路探索シミュレーター A法その3

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (A-No.5): Private Material Life.

迷路探索シミュレーター A法その4 [ゲーム欲 プチコン3号]

さて,A法の核心部分では,2つのサブルーチンを実行します.
  S1MODE値を0にして,@SHORT1を実行します.
    これで,最短経路歩数MAP(MAP3,MAP4)ができます.
  S2MODE値を0にして,@SHORT2を実行します.
    これで,最短に進む手順がMAP5にできます.
  通過済み区画の場合,ここまでを飛ばします.

<趣味画像 3530> A法メイン部分です.
3530 迷路シミュレーター525.JPG

S2MODE値を1にして,@SHORT2を実行すると,
  返り値S2OUTに,手順が一つ読み出されます.
  その通り実行すれば,最短手順でゴールへ近づきます.

<趣味画像 3531> 0なら前進,1なら右を向けば良い
3531 迷路シミュレーター526.JPG

昔のBASICは遅かったので,このSHORT1,SHORT2ルーチンだけを,
  8bitのマシン語サブルーチンで作製して使っていました.
  BASICのほうが,bit操作やMAPが大げさだったり,
  変数文字が多くなってややこしいです.
  4月29日に,この2つのルーチンを出します.

<関連記事> 今回画像は別画面で大きく表示されます(横1000ピクセル)
3504 迷路シミュレーター521.JPG 平成27年 4月19日 迷路探索シミュレーター A法その3
3471 迷路シミュレーター504.jpg 平成27年 4月 8日 迷路探索シミュレーター A法その2

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (A-No.4): Private Material Life.

迷路探索シミュレーター A法その3 [ゲーム欲 プチコン3号]

動作確認した,A法のプログラム部分の紹介です.
  始めの設定は左手法などと同じです.

<趣味画像 3504> A法の準備部分
3504 迷路シミュレーター521.JPG

メインのサブルーチン「@A_MAIN」から,Aボタンで1手順ずつ進む.
  Yボタンを押すと,どんどん進みます.
  ゴールしたら,スタートとゴールを入れ替えるだけでなく,
  最短経路内に未通過区画がまだ残るかどうか判定します.
  S2NOCHECK変数が0ならば,最短経路確定として終了します.

<趣味画像 3505> ゴール区画の判定があります
3505 迷路シミュレーター522.JPG

続いてメインルーチンですが,通過済み区画では壁探査を省略します.
  最短経路も予定通りで進めますから,経路計算も省きます.
  未探索区画なら,前方と左右の壁だけ調べます.

<趣味画像 3506> メインルーチン
3506 迷路シミュレーター523.JPG

調べた壁のDATAから,MAP1に壁を記憶します.
  ついで,グラフィックスでも壁を表示します.
  Xボタンで元迷路を消せば,探索した壁だけがみえます.

<趣味画像 3507> 壁表示と壁記憶
3507 迷路シミュレーター524.JPG

ここまでは,拡張左手法などと同じです.
  次回に続きます.

<関連記事> 
3471 迷路シミュレーター504.jpg 平成27年 4月 8日 迷路探索シミュレーター A法その2
3460 迷路2015年2月.jpg 平成27年 4月 5日 迷路探索シミュレーター A法その1

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (A-No.3): Private Material Life.

迷路探索シミュレーター A法その2 [ゲーム欲 プチコン3号]

とりあえず動作確認のため,ゆっくりでも動くルーチンを作りました.
  未探索区画では,毎回最短経路を計算しています.(少し無駄です)
  実際のマウス競技では,まだ改良が必要です.
  でも,BASICのわりには処理が速く,ピコピコ軽快に進みます.

<趣味画像 3468> 3歩進んで戻る
3468 迷路シミュレーター502.jpg

3歩進んだ区画で最短経路を計算し直すと,戻って右へ進む.
  迷ったら,壁が無いものとして最短コースを求め直します.
  解ける迷路なら,必ずゴールへ到着します.
  「求心法」というアルゴリズムも別にありますが,
  ゴールの位置が中心とは限らず,探索には使えません.

<趣味画像 3469> ゴールまで1回目到着
3469 迷路シミュレーター501.jpg

ゴールに着いても,そこから目的地を切り替えて,
  最短コースでスタートを目指すことで,
  別の最短コースの可能性を探れます.
  迷路の端にあるスタートの方が,迷いにくいことが多いはずです.

<趣味画像 3470> スタートに戻ってみる
3470 迷路シミュレーター503.jpg

スタートに戻れても,まだ「最短コースが確定していない」と判定されれば,
  もう一度ゴールを目指します.
  1回の試走で,最短コースを確定させることができます.

<趣味画像 3471> 行き来しているうちに最短確定
3471 迷路シミュレーター504.jpg

迷路の全面探索をするまでも無く,
  ここまで探索すれば,最短が求まるようです.
  もちろん,実際のマウス競技では,
  斜め走行や,直線加速も考慮しての最短コースを求めます.
  マウスの走行の正確さが,勝敗を分けます.
  次回は,プログラム公開です.

<関連記事> 
3460 迷路2015年2月.jpg 平成27年 4月 5日 迷路探索シミュレーター A法その1
3441 迷路シミュレーター402.jpg 平成27年 3月27日 迷路ルーチン 拡張左手法その3

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (A-No.2): Private Material Life.

迷路探索シミュレーター A法その1 [ゲーム欲 プチコン3号]

拡張左手法で迷路を全面探索することができました.
  このあと,マイクロマウス競技では最短コースを計算して本番走になります.
  最短コースを求めるためには,全面探索することが必要でしょうか.
  そこで,「最短コースを求めるには,どこまで探索すれば良いのか.」
  これこそが,マイクロマウスの,それまでとは違う探索法の誕生につながりました.

マイクロマウス競技をよく知っている人には,
  これから記述するアルゴリズムが,○○法と呼ばれていることを,
  私はよく存じていますが,個人情報の観点から,このブログ内だけでは,
  A法と呼ばせてください.(これはお願いです.コメントも要りません)

<趣味画像 3459> 当時の研究ノート
3459 マウスノート003.jpg

最短コースの確定が判定できるプログラムを考えました.
  MAPを用意して壁を記憶していて,スタートとゴールは決まっているとします.
  ① 通過したことのある区画のみ通って,S→Gの最短コース.
  ② 未通過の区画も含めて通って,S→Gの最短コース.
  ポイントは,壁の有無が不明なところには壁が無いとしていること.
  ①=②となれば,そのコースが最短コースであり確定する.
  別の言い方をすれば,②のコース上に未通過区画がなくなれば終わりです.

このプログラム(サブルーチン)の使い方は,
  ①のコースをたどれば,途中で探索が時間切れになっても,
  ゴールへのコースが確定しているので,本番記録が残せるということです.
  ①も②も区画の判定以外は,同様にしてコースを求めるので,
  そこだけ変数で指定すれば,共通のプログラムで済みます.

このプログラムを使用して,現在地をS,中央のゴールをGとすると,
  現在地からマウスが,次に進むべきは②のコースです.
  その中には未探索区画が含まれますから,すぐ壁に阻まれて進めなくなります.
  その時点で,再び現在地をSとして再計算すれば,いつか必ずGに到着します.

<趣味画像 3460> 迷路探索中
3460 迷路2015年2月.jpg

ゴールGに着いたら,スタートとゴールを入れ替えて,スタートSを目指す.
  行き来しているうちに,最短コースが確定するはず.
  ゴールからスタートへ向かう方が,迷路は簡単な場合がありそうですから,
  これは有利な作戦です.ゴールで止まらなければ,1回の試走で最短コースが確定します.
  途中で時間が無くなったら,探索を中止して①のコースで本番走をすれば,
  このプログラムだけで,(クラシックの)マイクロマウス競技の迷路探索は十分でした.

<趣味画像 3461> プログラムはBASICで書きます
3461 プチコン3号ガイドブック.jpg

文字ばかりになりましたが,けっこう大事なポイントを説明しました.
  今回の記事がよくわからないけど理解したい奇特な方が居ましたら,
  財団のT代さんに聞いてください.(人任せにしてすみません)
  次は,A法の走行パターンを示します.

<関連記事> プチコン3号カテゴリーで読み直してください
3441 迷路シミュレーター402.jpg 平成27年 3月27日 迷路ルーチン 拡張左手法その3
3435 迷路シミュレーター310+.JPG 平成27年 3月25日 迷路ルーチン 拡張左手法その2

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (A-No.1): Private Material Life.

迷路ルーチン 拡張左手法その3 [ゲーム欲 プチコン3号]

左手法で迷路を探索すると,迷路の外周を回って戻ります.
  この走行図のように,外周しか探索できません.

<趣味画像 3439> 左手法の走行図
3439 迷路シミュレーター400.jpg

一度通った区画へ入って,同じ探索をしないようにルールを作ると,
  だんだん内側を探索していくので,ゴールに着きます.
  これを拡張左手法といって,全面探索には基本的な方法です.
  ゴールしても同様のルールで探索を続けると,
  全面を探索してスタートに戻ります.

<趣味画像 3440> 拡張左手法でゴール
3440 迷路シミュレーター401.jpg

それにしても,「BASICは遅い」というイメージがありましたが,
  プチコンなのに処理が速くて驚いています.
  大昔30年前の8bit-CPUである,Z80マシンのクロックは2MHz.
  それでも,1MHzの2倍だと驚いていました.
  現在の3DSは,Nintendo 1048 CPUが2個とGPUも搭載があり,
  クロックは推定で266MHzとか.単純に100倍以上速いわけです.

シミュレーションなので実際の走行ではないのですが,
  探索にかかる時間を調べてみました.TIME$を表示しただけです.
  Yボタンでビューッと走らせると,全面探索でも3秒でした.
  このBASICは,「速い」です.

<趣味画像 3441> 拡張左手法の全面探索
3441 迷路シミュレーター402.jpg

さて,次回からは,拡張左手法を越える探索法について説明します.

<関連記事> 
3433 迷路シミュレーター308+.JPG 平成27年 3月25日 迷路ルーチン 拡張左手法その2
3422 迷路シミュレーター305+.JPG 平成27年 3月22日 迷路ルーチン 拡張左手法その1

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (No.11): Private Material Life.

迷路ルーチン 拡張左手法その2 [ゲーム欲 プチコン3号]

まずは,現在区画の壁の探索です.前右左の壁を調べて,記憶して表示します.
  現在地が通過済みの区画であれば,この探索を省略します.
  MAP2の値が,0で未通過,1で通過済みです.

<趣味画像 3431> 拡張左手法メインの探索部分
3431 迷路シミュレーター306+.JPG

<趣味画像 3432> 拡張左手法メインの壁表示部分
3432 迷路シミュレーター307+.JPG

拡張左手法では,「通過済み区画」に進入できる条件が,「逆戻り」のみです.
  これから入る区画のMAP3の値が,「逆向き」でなければ進入しません.
  「その区画から出た時の頭の向き」と「これから進もうとする頭の向き」を比較する.
  こうすることで,左手法で一周してしまう迷路でも全区画が探索できます.

<趣味画像 3433> 拡張左手法メインの思考部分(左)
3433 迷路シミュレーター308+.JPG

<趣味画像 3434> 拡張左手法メインの思考部分(前右後ろ)
3434 迷路シミュレーター309+.JPG

ゴールに着いても探索を継続することで,全面を探索してスタートに戻れます.
  全面探索は,最短経路を確定させるのに必要十分な条件ですから,
  時間が許せばそれがいいはずです.実際は制限時間があります.

<趣味画像 3435> 壁探索から呼び出す,壁記憶ルーチン
3435 迷路シミュレーター310+.JPG

今日はここまで.次回は走行例の写真など.

<関連記事> 
3421 迷路シミュレーター304+.JPG 平成27年 3月22日 迷路ルーチン 拡張左手法その1
3414 迷路シミュレーター300+.JPG 平成27年 3月19日 迷路探索思考ルーチン 左手法

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (No.10): Private Material Life.

迷路ルーチン 拡張左手法その1 [ゲーム欲 プチコン3号]

スタートから1本のヒモを伸ばし,あしあとも付けながら探索すると考えてください.
  通過済み区画に戻ってきた場合,そこにヒモが通っているので気付きます.
  そこへの再侵入を許すと,同じ道をグルグル進むことになるので禁止します.
  進めなくなれば,ヒモをたどる方向にだけ,戻ることを許し,
  途中で枝分かれしていた,未探索の区画へ向かって,左手法で探索します.

これで,浮島のゴールも探しに行けます.拡張左手法と呼ばれています.
  実際にはヒモや,あしあとではなく,履歴を使いMAPに記憶します.
  通過履歴はMAP2に記憶します.0で未通過,1で通過済み.
  MAP3には,通過済み区画から出た時の頭の向き:0~3を記憶します.

<趣味画像 3421> 拡張左手法の準備部分
3421 迷路シミュレーター304+.JPG

MAP読み出しを早く処理するために,今回から迷路記憶MAPを少し変更します.
  MAP1のbit0,bit1を使い,一区画に2方向の壁のみ記憶しましたが,
  4bitで,四方の壁を記憶します.ただ,記憶時に二重に書き込む必要があります.
  これに伴い,MAPサイズは17×17が,16×16になります.

8bitマシン語で記述していた頃(30年前)は,256バイトで1単位であり,
  迷路サイズが16×16と決まっていました.このMAPが扱いやすかった.
  最近は迷路サイズも可変ですから,いずれ100×100ぐらいに対応しておきたい.

<趣味画像 3422> ボタン読み込みループです(左手法と同じ)
3422 迷路シミュレーター305+.JPG

ここまでは,前回と同じです.
  拡張左手法で探索すれば,必ずゴールに着きます.
  ゴールに着いても,そのまま探索を続けることで全面探索が可能です.
  次回がメインルーチンです.

<私的物欲生活.In Amazon> プチコンの本が届きました
 

<関連記事> 
3414 迷路シミュレーター300+.JPG 平成27年 3月19日 迷路探索思考ルーチン 左手法
3392 迷路シミュレーター209+.JPG 平成27年 3月 8日 迷路探索シミュレーター その7

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (No.9): Private Material Life.

迷路探索思考ルーチン 左手法 [ゲーム欲 プチコン3号]

さて,左手法の思考ルーチンの製作です.
  手動操作ルーチンで,現在位置NX,NY,NHが独立していませんでした.
  これからは,NOWX,NOWY,NOWHで現在位置を記憶します.
  スタートすると,Aボタンを押すたびに,1区画ずつ進みます.
  自動的に周囲の壁も探索します.

<趣味画像 3414> 左手法の準備部分
3414 迷路シミュレーター300+.JPG

左手法は,左に壁がなければ左に進むので,左の壁に沿って進みます.
  Xボタンで元の迷路表示を消せば,探索がよくわかります.
  Yボタンは,押している間進み続けるので,ビューと行きます.

<趣味画像 3415> ボタン読み込みループです
3415 迷路シミュレーター301+.JPG

やってみればわかりますが,左手法では浮島のゴールに着きません.
  グルグル回り続けることがわかります.

<趣味画像 3416> 左手法メインの探索部分
3416 迷路シミュレーター302+.JPG

<趣味画像 3417> 左手法メインの思考行動部分
3417 迷路シミュレーター303+.JPG

一度通過した区画を覚えておいて,同じ探索を繰り返さないこと.
  それを考えたのが,次に説明する拡張左手法です.

<関連記事> 
3394 迷路シミュレーター211+.JPG 平成27年 3月 8日 迷路探索シミュレーター その7
3385 迷路シミュレーター206+.JPG 平成27年 3月 5日 迷路探索シミュレーター その6

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (No.8): Private Material Life.

迷路探索シミュレーター その7 [ゲーム欲 プチコン3号]

やっと,手動操作プログラムです.シミュレーターの動作確認でもあります.
  十字キーを読み込んで,「F」「R」「B」「L」の指令を送るのは簡単です.
  BUTTON(2)関数で,3DSの十字キーやABボタンの情報を得ます.
  前進,右向き,後進,左向きは,そのまま@MAINに指令します.

<趣味画像 3392> プログラム2 その9/11
3392 迷路シミュレーター209+.JPG

追加で作成した機能として,Aボタンで現在地の四方の壁を探索表示します.
  探索された壁だけの表示のために,BGスクリーン1を用意しました.
  そのままでは,BG2に隠れてしまいますから,
  Xボタンで,元の迷路表示を消すことができます.

<趣味画像 3393> プログラム2 その10/11
3393 迷路シミュレーター210+.JPG

<趣味画像 3394> プログラム2 その11/11
3394 迷路シミュレーター211+.JPG

Aボタンを押すと,探索した四方壁だけが表示されます.
  元の迷路を消すと,本当に迷子になりますね.

<趣味画像 3395> 実行画面 探索中です
3395 迷路シミュレーター212+.jpg

さて,次は左手法の思考ルーチンの製作です.
  作ってから気付きましたが,現在位置変数のNX,NY,NHが独立していません.
  次からはローカル変数にも気をつけましょう.

<関連記事> 
3387 迷路シミュレーター208+.JPG 平成27年 3月 5日 迷路探索シミュレーター その6
3376 迷路シミュレーター204+.JPG 平成27年 3月 1日 迷路探索シミュレーター その5

最後まで読んでいただいて,ありがとうございます.
ほかの記事も読んでくださると,うれしいです.

I make the maze program in Puchikon (No.7): Private Material Life.

前の10件 | - ゲーム欲 プチコン3号 ブログトップ
私的物欲生活

生活の中で,自分なりのこだわりで選んだ買い物.なぜ,これでなければならなかったのか.買い物してしまって後悔しません.無理に勧めません.お気に入りなだけです.

Private Material Life.