Rogue Likeか Tower Defense か何かで使おうとしてA*をつくっていたけど
これってdiffだよね〜と思ってたらやっぱりdiffだったので
diffにも使えるように改造していた。
ランダムに問題を生成してedit graph をA*でたどったもの
A*のパラメータとしては
- S: スタートは左上隅
- G: ゴールは右下隅
- ノード展開は、3方向(→↘↓) か 2方向(→↓)
- h(n) は d←n-G で |dx| と |dy| の大きい方
- f値が同じときのタイブレークは Gまでのユークリッド距離で小さい方を選ぶ
- COST(n,m)は1
で、だいたいこんなかんじ
