map=new string[10]; map[0]="#####"; map[1]="#G..#"; map[2]="#.###"; map[3]="#...#"; map[4]="#.#.#"; map[5]="###.#"; map[6]="#...#"; map[7]="##.##"; map[8]="#S..#"; map[9]="#####"; #は壁 Gはゴール Sはスタート位置
Gからコストどれだけで移動できるかを再帰的に探索
SearchMap()で求めた表がこれ
(上下が逆なので注意)
いま、どこにいるかを指定すれば、そこからゴールまでの最短経路は、
8方向の値が小さいマスを選べばいい
スタートからゴールに移動中
はいゴール
ターン制RPGなら1マスつづ移動でもいいけど
そういうわけにもいかないので、スムーズな移動を実現
探索は超単純で
(map3は初期値はすべて-1が入っている)
void SearchMap(int x,int y,float cost) { if(x<0) return; if(y<0) return; if(x>5) return; if(y>9) return; if(map2[x,y]==1) return; if(map3[x,y]==-1) map3[x,y]=cost; else if(map3[x,y]>cost) map3[x,y]=cost; else return; SearchMap(x-1,y,cost+1f); SearchMap(x+1,y,cost+1f); SearchMap(x,y-1,cost+1f); SearchMap(x,y+1,cost+1f); SearchMap(x-1,y-1,cost+1.4f); SearchMap(x-1,y+1,cost+1.4f); SearchMap(x+1,y-1,cost+1.4f); SearchMap(x+1,y+1,cost+1.4f); }
すでにコストが入っている場合も、自分がより低いなら書き換える
壁や、コストが自分と同じ、または高いなら、戻る
斜めコストを1.4=√2として設定している
面倒くさいのが座標合わせ(´・ω・`)
もっとはじめにやっておくべきだった。
ある程度作ってしまってるのに、経路探索で距離を判断するように修正するのは
かなり面倒でバグまみれになりそうな予感。