幅優先検索JavaScript（アルゴリズムまたは入力）

Question

これはちょうど幅優先の検索であると考えられています。それが終わると、それらの両親を出発点に戻って道を辿る。

マップは、それが私のアルゴリズムや私の出発データであれば、私は私の人生のために把握することはできませんこれらのタイルの配列だけ

function Tile(x, y){ 

    this.x = x; 
    this.y = y; 

    //for BFS 
    this.px = 0; 
    this.py = 0; 
    this.visited = false; 

    this.is = " "; 

    this.n = null; 
    this.e = null; 
    this.s = null; 
    this.w = null; 
} 

です。

誰かがこのオブジェクトのトラブルシューティングを手伝ったり、正しいものとして解決してくれたら大変感謝しています。

function FakeBFS(){ 
    var me = this; 

    this.get_path = function(sx, sy, ex, ey, map){ 
     var x = sx; 
     var y = sy; 
     var unfinished = [{"x":sx, "y":sy}]; 

     //walk until we can't or we reach our destination 
     while(unfinished.length && x != ex && y != ey){ 

      var new_location = unfinished.shift(); 

      x = new_location.x; 
      y = new_location.y; 

      //if we haven't been here... 
      if(map.tiles[x][y].visited == false){ 

       console.log("\n\nlooking for path from:"+x+","+y+" to:"+ex+","+ey); 
       var nesw_array = new Array(
              [x,y+1], //n 
              [x+1,y], //e 
              [x,y-1], //s 
              [x-1,y]);//w 
              console.log(nesw_array); 

       //add all the vertices we care about to unfinished 
       for(var nesw=0; nesw<4; nesw++){ 
        var vx = nesw_array[nesw][0]; 
        var vy = nesw_array[nesw][1]; 
        console.log(nesw_array[nesw]); 
        if((map.tiles[vx][vy].is == " " 
        || map.tiles[vx][vy].is == "H") 
        && map.tiles[vx][vy].visited == false){ 
         console.log("parenting["+nesw+"]"+map.tiles[vx][vy].x+","+map.tiles[vx][vy].y+" to:"+x+","+y); 
         //set the route we took to get here 
         map.tiles[vx][vy].px = x; 
         map.tiles[vx][vy].py = y; 
         unfinished.push({"x":map.tiles[vx][vy].x, "y":map.tiles[vx][vy].y}); 
        } 
       } 
       //visit this vertex 
       map.tiles[x][y].visited = true; 
      } 

      console.log("END LOOP looking for path from:"+x+","+y+" to:"+ex+","+ey); 
     } 

     //walk back to start for our path 
     var path = Array(); 
     if(x == ex && y == ey){ 
      while(x != sx && y != sy){ 
       path.push({"x":x,"y":y}); 
       console.log(x+","+y); 
       x = map.tiles[x][y].px; 
       y = map.tiles[x][y].py; 
      } 
      path.push({"x":x,"y":y}); 
      console.log("Path:"+util.inspect(path)); 
      return path; 
     } 
     return false; 
    } 
} 

私はいくつかのサンプルデータを作成しましたが、基本的に同じ問題があります。これはピン止めしにくいです。 以下のコードでは、 "me"はMap（）オブジェクトを参照しています。

function TestMap(){ 
    var me = this; 
    this.paths = new Array(); 
    //width and height 
    this.size = 10; 
    this.num_tiles = this.size*this.size; 
    //we can't build on the edge 
    this.start = 1; 
    this.end = this.size-this.start; 

    // 
    // 
    //tiles 
    //////////////////////////////////////// 
    this.tiles = new Array(); 

    // 
    // 
    //print 
    ////////////////////////////////////////// 
    this.print = function(){ 
     var mapscii = ""; 
     for(var y=this.end; y>-1; y--){ 
      for(var x=0; x<this.size; x++){ 

        mapscii += this.tiles[x][y].is; 

      } 
      mapscii += "\n"; 
     } 
     console.log(mapscii); 
    } 

    // 
    // 
    //setup the tile array and the associations 
    ///////////////////////////////////////////////// 
    this.init_map = function(){ 
     for(var x=0; x<me.size; x++){ 
      me.tiles[x] = new Array(); 
      for(var y=0; y<me.size; y++){ 
       var t = new Tile(x, y); 

       //draw bounds 
       if(x==0 || y==0 || x==me.size-1 || y==me.size-1){ 
        t.is = "#"; 
       } 
       me.tiles[x][y] = t; 
      } 
     } 
    } 

    // 
    // 
    //setup the tile array and the associations 
    ///////////////////////////////////////////////// 
    this.fake_map = function(){ 
     var fake_rooms = [  [2,2] 
          , [2,3] 
          , [3,2] 
          //, [3,3] 

          //, [5,2] 
          , [5,3] 
          , [6,2] 
          , [6,3] 
         ]; 

     var fake_doors = [ 
           [3,3] 
          , [5,2] 
         ]; 

     for(var x=0; x<fake_rooms.length; x++){ 
      me.tiles[fake_rooms[x][0]][fake_rooms[x][1]].is = "."; 
     } 
     for(var x=0; x<fake_doors.length; x++){ 
      me.tiles[fake_doors[x][0]][fake_doors[x][1]].is = "H"; 
     } 
    } 

    this.fake_place_paths = function(){ 
     var bfs = new BFS(); 

     me.paths[0] = bfs.get_path(
         3,3, 
         5,2, 
         me 
      ); 
    } 

    this.mark_paths = function(){ 
     for(var i=0; i<me.paths.length; i++){ 
      console.log(me.paths); 
      var thispath = me.paths[i]; 
      console.log("["+i+"]"+thispath.x+","+thispath.y); 
      me.tiles[thispath.x][thispath.y].is = "+"; 
     } 
    } 

    this.init_map(); 
    this.fake_map(); 
    this.fake_place_paths(); 
    this.print(); 
    this.mark_paths(); 
} 

これは、印刷時の「偽のマップ」の外観です。

＃=境界

です。 =ルーム

H =ドア

########## 
#  # 
#  # 
#  # 
#  # 
#  # 
# .H .. # 
# .. H. # 
#  # 
########## 

は、ここに私のデバッグ出力です。

C:\Users\trans\Documents\JS>node test_bfs.js 


looking for path from:3,3 to:5,2 
[ [ 3, 4 ], [ 4, 3 ], [ 3, 2 ], [ 2, 3 ] ] 
[ 3, 4 ] 
parenting[0]3,4 to:3,3 
[ 4, 3 ] 
parenting[1]4,3 to:3,3 
[ 3, 2 ] 
[ 2, 3 ] 
END LOOP looking for path from:3,3 to:5,2 


looking for path from:3,4 to:5,2 
[ [ 3, 5 ], [ 4, 4 ], [ 3, 3 ], [ 2, 4 ] ] 
[ 3, 5 ] 
parenting[0]3,5 to:3,4 
[ 4, 4 ] 
parenting[1]4,4 to:3,4 
[ 3, 3 ] 
[ 2, 4 ] 
parenting[3]2,4 to:3,4 
END LOOP looking for path from:3,4 to:5,2 


looking for path from:4,3 to:5,2 
[ [ 4, 4 ], [ 5, 3 ], [ 4, 2 ], [ 3, 3 ] ] 
[ 4, 4 ] 
parenting[0]4,4 to:4,3 
[ 5, 3 ] 
[ 4, 2 ] 
parenting[2]4,2 to:4,3 
[ 3, 3 ] 
END LOOP looking for path from:4,3 to:5,2 


looking for path from:3,5 to:5,2 
[ [ 3, 6 ], [ 4, 5 ], [ 3, 4 ], [ 2, 5 ] ] 
[ 3, 6 ] 
parenting[0]3,6 to:3,5 
[ 4, 5 ] 
parenting[1]4,5 to:3,5 
[ 3, 4 ] 
[ 2, 5 ] 
parenting[3]2,5 to:3,5 
END LOOP looking for path from:3,5 to:5,2 


looking for path from:4,4 to:5,2 
[ [ 4, 5 ], [ 5, 4 ], [ 4, 3 ], [ 3, 4 ] ] 
[ 4, 5 ] 
parenting[0]4,5 to:4,4 
[ 5, 4 ] 
parenting[1]5,4 to:4,4 
[ 4, 3 ] 
[ 3, 4 ] 
END LOOP looking for path from:4,4 to:5,2 


looking for path from:2,4 to:5,2 
[ [ 2, 5 ], [ 3, 4 ], [ 2, 3 ], [ 1, 4 ] ] 
[ 2, 5 ] 
parenting[0]2,5 to:2,4 
[ 3, 4 ] 
[ 2, 3 ] 
[ 1, 4 ] 
parenting[3]1,4 to:2,4 
END LOOP looking for path from:2,4 to:5,2 
END LOOP looking for path from:4,4 to:5,2 


looking for path from:4,2 to:5,2 
[ [ 4, 3 ], [ 5, 2 ], [ 4, 1 ], [ 3, 2 ] ] 
[ 4, 3 ] 
[ 5, 2 ] 
parenting[1]5,2 to:4,2 
[ 4, 1 ] 
parenting[2]4,1 to:4,2 
[ 3, 2 ] 
END LOOP looking for path from:4,2 to:5,2 
########## 
#  # 
#  # 
#  # 
#  # 
#  # 
# .H .. # 
# .. H. # 
#  # 
########## 

[ false ] 
[0]undefined,undefined 
C:\Users\trans\Documents\JS\testmap.js:102 
         me.tiles[thispath.x][thispath.y].is = "+"; 
              ^

TypeError: Cannot read property 'undefined' of undefined 
    at TestMap.mark_paths (C:\Users\trans\Documents\JS\testmap.js:102:24) 
    at new TestMap (C:\Users\trans\Documents\JS\testmap.js:110:7) 
    at Object.<anonymous> (C:\Users\trans\Documents\JS\test_bfs.js:2:11) 
    at Module._compile (module.js:570:32) 
    at Object.Module._extensions..js (module.js:579:10) 
    at Module.load (module.js:487:32) 
    at tryModuleLoad (module.js:446:12) 
    at Function.Module._load (module.js:438:3) 
    at Module.runMain (module.js:604:10) 
    at run (bootstrap_node.js:390:7) 

Answer 1

主な問題は、私がそのデータを取得する前にループを去り、私が何かを参照するために使用していた変数を変更するという私の条件でした。

  ....................... 

    //walk until we can't or we reach our destination 
    while(unfinished.length){ 

     var new_location = unfinished.shift(); 

     x = new_location.x; 
     y = new_location.y; 

     if(x == ex && y == ey){ 
      unfinished.length = 0; 
      continue; 
     } 

    .......................... 

    //walk back to start for our path 
    var path = Array(); 
    if(x == ex && y == ey){ 
     console.log("here"); 
     while(!(x == sx && y == sy)){ 
      path.push({"x":x,"y":y}); 
      console.log(x+","+y); 
      //temporary to not screw up reference 
      var tempx = map.tiles[x][y].px; 
      tempx = map.tiles[x][y].px; 
      y = map.tiles[x][y].py; 
      x = tempx; 
      console.log(x+","+y); 
     } 
     path.push({"x":x,"y":y}); 
     return path; 
    } 
    return false;