ﾍｯｸｽﾏｯﾌﾟで､最短距離の経路を自動作成してみる[ﾌﾟﾛｸﾞﾗﾐﾝｸﾞ]
(2014-12-19 19:01:26) by shinoda
< ﾍﾟｰｼﾞ移動: 1 2 >
今回は､ﾍｯｸｽﾏｯﾌﾟ上のｽﾀｰﾄ地点とｺﾞｰﾙ地点を与えてやって､自動で最短距離の経路を取得する方法を考えてみよう｡
↑こういうﾏｯﾌﾟをﾃｽﾄで使う｡
青い線が X 軸､ｵﾚﾝｼﾞの線が Y軸､緑の線が Z 軸で､この軸の値を X-Y-Z のように並べてﾍｯｸｽIDとする｡
経路を決める方法としては､
･全ての経路を算出して､その中から最短のものを採用する(あるいは､人に選択させる)
･最短の(あるいは任意の条件の)経路のみを算出する
という2ﾊﾟﾀｰﾝがあると思うが､全ての経路(あるいは任意の数の経路)を算出するのは大変なので､今回は最短経路を求めてみる｡
で､最短経路をどうやって求めればいいかだが､とりあえず｢目的地の方向へひたすら進む｣という戦略を取ってみることにする｡
上の画像のような形で X,Y,Z 軸を決めると､ある任意のﾍｯｸｽから見た目的地の方向は下の図のようになる｡
要は､一歩一歩(1ﾍｯｸｽ進む毎に)目的地の方向を調べその方向へ進むということを繰り返すのだ｡単純かつ確実｡
ちなみに､進める方向によって､元の X,Y,Z 軸の値に､下の表のように加減を行なう｡
例えば､2-3-5 から 2-4-4 に移動するには右横に進めばいいので､2-3-5 の X 軸の値はそのままに､Y 軸の値に 1を足し､Z軸の値から 1を引けば 2-4-4 になるというわけ｡
この間のｴﾝﾄﾘｰに載せていた Perl ｽｸﾘﾌﾟﾄに､
# 経路選択
$i = 0;
for (;;) {
# 方向を見極める
$xd = $x2 - $x1; # X軸差
$yd = $y2 - $y1; # Y軸差
$zd = $z2 - $z1; # Z軸差
$i++;