pacman AI について私が提案するのは、フラッド フィル アルゴリズムを使用して、グリッド上のすべてのタイルへの最短経路と合計距離を計算することです。これは A* よりもはるかに単純なアルゴリズムであり、実際には A* よりも最悪のケースが優れています。
パフォーマンスの比較をもう少し詳しく説明するために、A* の最悪のケースを想像してみてください。行き止まりのため、最終目的地に到達する前に、グリッド上のすべてのタイルを探索する必要があります。この理論的なケースは、ボード上に多くの行き止まりがある場合に発生する可能性がありますが、実際のパックマン ボードではほとんどありません。フラッド フィルの最悪のケースは、最良のケースと同じで、マップ上のすべてのタイルを 1 回だけ訪れます。違いは、フラッド フィルの反復ステップは A* 反復の場合よりも単純であるため (ヒューリスティックやノード ヒープがないなど)、すべてのノードへのアクセスは A* よりもフラッド フィルの方が高速です。
実装は非常に簡単です。グリッドをグラフとして想像すると、各タイルがノードであり、隣接するタイル間に壁のない各エッジがグラフのエッジである場合、グラフの幅優先トラバーサルを実行して、どのノードに到達したかを追跡します。から、そこにたどり着くまでに探索したノードの数。ノードを訪問したときにそのノードを訪問済みとしてマークし、ノードを 2 回訪問することはありません。
開始するための疑似コードを次に示します。
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if not child.has_been_visited
child.has_been_visited = true
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
pacman をどこかに移動させる方法を理解するには、目的のノードから開始し、.previous ポインターを先頭までたどり、リストを逆順にします。
これの良いところは、マップ上の任意のタイルに到達するためのコストについて一定時間クエリを実行できることです。たとえば、各パワー ペレットをループして、どれが最も近く、どのようにそこに到達するかを計算できます。
ゴーストが「攻撃」モードのときにパックマンに戻るための最速の方法を知るために、これを使用することもできます!
また、各ゴーストからのフラッド フィルを考慮して、最も近いゴーストとの距離を各タイルに格納することもできます。ノードが最大コスト (8 マス?) より大きい場合は、ノードをオープン リストに追加せずに、探索する最大距離を制限できます。次に、後で A* を実行した場合、ゴーストがどれだけ近いかに基づいて、各タイルのコストにバイアスをかけることができます。しかし、それはあなたが質問で求めていたものを少し超えています。
フレームごとにインラインで実行したり、必要に応じてマルチスレッドで実行したりできるほど高速である必要があります。簡単にするために、メインのゲーム シミュレーション スレッド (UI スレッドではないことに注意) で実行することをお勧めします。
パフォーマンスに関する 1 つのヒント: フレームごとに「has_been_visited」フラグを調べてクリアするのではなく、フレームごとにインクリメントする検索カウンターを単純に持つことができます。そのようなもの：
openlist = [ start_node ]
do
node = openlist.remove_first()
for each edge in node.edges
child = node.follow_edge(edge)
if child.last_search_visit != FRAME_NUMBER
child.last_search_visit = FRAME_NUMBER
child.cost = node.cost + 1
child.previous = node
openlist.add(child)
while openlist is not empty
そして、フレームごとに FRAME_NUMBER をインクリメントします。
幸運を！