ダイクストラ法による距離の計測

やねうらおさんに書いてもらった擬似コードを元に
ダイクストラ法をやってみました。
確かに、ゴールまで何マスで移動できるかが求まりました
iのループが反復進化で言うdeepnessという感じですが、
再帰を用いずに、距離が求まるので、
スタックが少なそうなActionScriptでは望ましいコードだと思います。
現在mapsizeが8ですが、
64x20=1280回のループ。たいしたことない回数ですね。

ただ、ゴールまでの距離はもとまりますが、上下左右、
どちらに進むほうが良いかは解らないのですが、
上下左右に関して、それぞれゴールまで距離を求めれば、
どの方向に進むのが最短か？　は分かりますね。
４回計算するより、なんか良い方法がありそうなので、
また突っ込まれるかもしれない(^^;

まだ動くとこまで行ってないですけど、
けっこう重いかもしれない(^^;
詰将棋的方法のほうがハッシュでの枝刈りが効いて
計算量は少ないかも。
距離が近くなる方向を優先して探すヒューリスティックも入れていたし
実際にゴールに近づくとほとんと計算しないで済みますが、
上記の方法は実際の距離に関係なく計算量一定だし

↑
やねさんからコメント欄で解説を受けました。
ゴールが判明しているなら、ゴールまでの距離が判明した時点で
計算は止められますね。
あと、進む方向についても、checkの更新時にどの方向が
最短化をいっしょに更新すれば、距離と方向は一度に求まります

		for(j=0;j<mapsize;j++) for(k=0;k<mapsize;k++) dij[ j*mapsize+k ] = 99;
		dij[ x+y*mapsize ]=0;

		for(i=0;i<20;i++)
		{
			for(j=0;j<mapsize;j++)
			{
				for(k=0;k<mapsize;k++)
				{
					if( dij[ k+j*mapsize ]==i )
					{
						check( k-1,j  ,i );
						check( k+1,j  ,i );
						check( k,  j-1,i );
						check( k,  j+1,i );
					}
				}
			}
		}