パーソナルブログメモリ

a = [1, 1]
for _ in "*" * 999: a += [sum(a[-2:])]
print(a)

ボードゲームでA*(A-star)探索アルゴリズム

2021-11-21 | Python

前回 逃げのプログラム(最短で脱出するものを作ったので)今回は足場を固めるプログラム。

少しでも信頼性を高めるためにこまめに確認したり。目視で確認しやすいツールのような関数

を増やす。このゲーム最終的には相手の脱出を長引かせるための壁を設置するプログラムが

必要になる。今の所コレといったアイデアはまとまっていない。前は相手のまわりに何パターン

か置いて距離を測ってタイムアウトにならないぐらいの微調整をしていたのを思い出しました。

 

まずはパスファインディングを自分占用から相手にも使えるようにデータまわりから修正する。

A*使ったらもっと速くなるかもと使ってみることにしてみました。21〜34行目。そんなに大きく

ない迷路で使ったらソートのコストの方が大きいかもと懸念しましたが、平均で3倍ぐらいは

速そうなことがわかりました。距離の長い序盤は5倍、終盤は1倍、相手ブロックが絶妙な時、

1を切ることもあります。

 

a_lenは各ボットの対面の壁との距離です。(対面に早くたどりつくと勝ち)ノーマルのパス

ファインディング(11〜20)と A*(21〜34)にそんなに違いはなく、ゴールに近い点から先

に計算するので、ゴールとの距離を探索情報に入れ繰返しの時にソートかけています。

画面左下 time pfとtime asはそれぞれ3回ずつ計算した時間x10000です。(単位秒)


最新の画像もっと見る

コメントを投稿

ブログ作成者から承認されるまでコメントは反映されません。