単純な格子状のマップを想定したダイクストラ法での経路探索

最低限のサンプルなので斜め移動とか高低差なんかはないです。

経路情報作成／探索用の一式

/* ----- ノード間接続情報----------------- */
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;
	};

}

テストにはちっちゃいマップを使います

横６×縦５。

スタート地点をx:0, y:3

ゴール地点はx:5, y:3

として、移動制限は特になし。スーパーシンプルな条件でお試し

実行用のコード

	function Keiro(){
		/*-- マップサイズ 小さく６×５ --*/
		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 = 移動不可

実行結果はこう

絵にするとこう

それっぽい！