ヘビゲーム: 探索アルゴリズムの比較

このシミュレーションでは、BFS、DFS、ダイクストラ、最良優先探索、A*などのさまざまな探索アルゴリズムによって制御されるクラシックなヘビゲームを紹介します。

通常のヘビゲームでは、プレイヤーがヘビを制御してリンゴに到達します。しかし、このシミュレーションでは役割が逆転し、リンゴを配置し、異なるアルゴリズムに従ってヘビが配置されたリンゴに到達しようとします。

理解すべき重要な用語は「コスト」と「フレーム」です。この文脈では、「フレーム」はヘビを見つけて移動させるために使用されるアニメーションフレームの総数を指します。これは探査されたセルの数とヘビを移動させるためのステップ数を反映しています。

コストはグリッド上の数値の差に1を加えて計算され、総コストはこれらの個々のコストの合計です。このメトリックは、ダイクストラとA*アルゴリズムで使用されます。また、A*と最良優先探索のヒューリスティックにはマンハッタン距離が使用されます。