格子世界の鬼ごっこ

追跡者(Chaserのアルゴリズム)

逃亡者からのマンハッタン距離を全てのマス分求め,追跡者周辺の4マスの中で最も小さい値のマスに移動する(幅優先探索で三体距離の移動).

逃亡者(Fugitiveのアルゴリズム)

追跡者からのマンハッタン距離を全てのマス分求め,追跡者から最も遠いマスを見つける. 追跡者から最も遠いマスに最短距離で移動する(追跡者→逃亡者と同じ手順). 経路が複数存在する場合,次の移動先のマスが追跡者から遠くなる方を選択.

mainプログラム

• デフォルトで5分の1の確率で逃亡者が動けなくなる
• Usage: ./main [-n filename] [-t turn] [-p probability]

逃亡者側の問題点

追跡者の最遠マスへ最短で移動するというアルゴリズムに問題あり.

./main -n world.dat -p 0の11ターン目の挙動のように,逃亡者が自滅する場合がある.また,行き止まりの場合にも最適な動作を選ばない.

自滅の可能性がある時の処理と,行き止まりの空間に入り込まないようにするために移動先の空間の広さを把握する必要がある.

改善予定の手法として,移動後に捕獲される可能性があるかどうかの判定をいれ,候補を再検討する.