単純な格子状のマップを想定したダイクストラ法での経路探索
最低限のサンプルなので斜め移動とか高低差なんかはないです。
経路情報作成/探索用の一式
/* ----- ノード間接続情報----------------- */ var Edge = function( link_index, cost ){ this.link = link_index; this.cost = cost; }; /* ----- ノード情報 ----------------- */ var RouteNode = function( id, x, y, edges ){ this.id = id; this.x = x; this.y = y; this.edges = edges; this.checked = 0; this.cost = 0xFFFF; this.next = -1; }; var RouteSearch = function(){ this.nodes = []; /*** * * ノード情報作成 * * ary_map_data : マップデータ * map_size_x, map_size_y : マップサイズ(X方向、Y方向) */ this.create = function( ary_map_data, map_size_x, map_size_y ){ let x, y; this.nodes = new Array( map_size_y * map_size_x ); for( y = 0; y < map_size_y; y++ ){ for( x = 0; x < map_size_x; x++ ){ let cost = 0, e = []; pos = 0 /*-- 上下左右の方向に移動できるか調べる(マップデータが0だったら移動可) --*/ //上 if ( y - 1 >= 0 ){ pos = (y - 1) * map_size_x + x; if( ary_map_data[ pos ] == 0 ){ cost = 1; }else{ cost = 0xFFFF; } e.push( new Edge( pos, cost ) ); } //下 if ( y + 1 < map_size_y ){ pos = (y + 1) * map_size_x + x; if( ary_map_data[ pos ] == 0 ){ cost = 1; }else{ cost = 0xFFFF; } e.push( new Edge( pos, cost ) ); } //左 if (x - 1 >= 0) { pos = y * map_size_x + (x - 1); if( ary_map_data[ pos ] == 0 ){ cost = 1; }else{ cost = 0xFFFF; } e.push( new Edge( pos, cost ) ); } //右 if ( x + 1 < map_size_x){ pos = y * map_size_x + (x + 1); if( ary_map_data[ pos ] == 0 ){ cost = 1; }else{ cost = 0xFFFF; } e.push( new Edge( pos, cost ) ); } pos = y * map_size_x + x; this.nodes[ pos ] = new RouteNode( pos, x, y, e ); } } }; /*** * * 探索実行 * * sx, sy : 出発座標 * ex, ey : 目標座標 * map_size_x, map_size_y : マップサイズ(X方向、Y方向) * */ this.execute = function( sx, sy, ex, ey, map_size_x, map_size_y ){ let result = []; let i, node_count, edge_count, index; let endIndex = ey * map_size_x + ex; let startIndex = sy * map_size_x + sx; node_count = this.nodes.length; for( i = 0; i < node_count; i++ ){ this.nodes[ i ].checked = 0; this.nodes[ i ].cost = 0xFFFF; this.nodes[ i ].next = -1; } this.nodes[ endIndex ].cost = 0; this.nodes[ endIndex ].next = endIndex; while( 1 ){ let current_node = null; let min = 0xFFFF; for( i = 0; i < node_count; i++ ){ if ( this.nodes[i].checked == 0 && min > this.nodes[i].cost){ min = this.nodes[i].cost; current_node = this.nodes[i]; if( current_node.edges == null ){ edge_count = 0; }else{ edge_count = current_node.edges.length; } } } if( current_node == null ){ break; } current_node.checked = 1; //チェック(同じ個所を二度通らないように) if( current_node.edges != null ){ for( i = 0; i < edge_count; i++ ){ let link_index = current_node.edges[ i ].link; if (link_index < 0 || current_node.edges[i].cost == 0xFFFF ){ continue; } if ( this.nodes[ link_index ].cost > current_node.cost + current_node.edges[i].cost){ this.nodes[ link_index ].cost = current_node.cost + current_node.edges[i].cost; this.nodes[ link_index ].next = current_node.id; // 次のノード } } } } index = startIndex; result.push( [ this.nodes[ index ].x, this.nodes[ index ].y ] ); //開始地点もセットしておく while ( 1 ){ index = this.nodes[ index ].next; if( index < 0 ){ break; //たどり着くのはむり } result.push( [ this.nodes[ index ].x, this.nodes[ index ].y ] ); if (index == endIndex){ //到着 break; } } return result; }; }
テストにはちっちゃいマップを使います

横6×縦5。
スタート地点をx:0, y:3
ゴール地点はx:5, y:3
として、移動制限は特になし。スーパーシンプルな条件でお試し
実行用のコード
function Keiro(){ /*-- マップサイズ 小さく6×5 --*/ let map_x = 6; let map_y = 5; let x, y; /*-- マップデータ用配列 0=移動可、1=移動不可 --*/ let map_data = []; // マップデータを一次配列で作成 // (x:0 y:0), (x:1 y:0), (x:2 y:0), ~ (x:5 y:0), (x:0 y:1), (x:1 y:1), ~ の順序でセット for( y = 0; y < map_y; y++ ){ for( x = 0; x < map_x; x++ ){ map_data[ y * map_x + x ] = 0; // 0 = 移動可 } } let tansaku = new RouteSearch(); tansaku.create( map_data, map_x, map_y ); let start_x = 0, start_y = 3, goal_x = 5, goal_y = 3, route = [], i; console.log("スタート: " + start_x + ", " + start_y); console.log("ゴール : " + goal_x + ", " + goal_y); route = tansaku.execute( start_x, start_y, goal_x, goal_y, map_x, map_y ); //探索結果の経路(スタート地点からゴール地点までの座標) for( i = 0; i < route.length; i++ ){ console.log( (i+1) + " : " +route[ i ][ 0 ] + ", " +route[ i ][ 1 ] ); } }
実行結果のログ

一直線だからわかるといえばわかるけど、可視化するとこう

赤文字が移動順序です。
次は移動できない場所を設定したとき。
マップデータ作成後に移動できない箇所を作ります。
// マップデータを一次配列で作成 // (x:0 y:0), (x:1 y:0), (x:2 y:0), ~ (x:5 y:0), (x:0 y:1), (x:1 y:1), ~ の順序でセット for( y = 0; y < map_y; y++ ){ for( x = 0; x < map_x; x++ ){ map_data[ y * map_x + x ] = 0; // 0 = 移動可 } } //移動できない場所を作っておく map_data[ 3 * map_x + 3 ] = 1; // 1 = 移動不可 map_data[ 3 * map_x + 4 ] = 1; // 1 = 移動不可
実行結果はこう

絵にするとこう

それっぽい!