chrome/test/data/third_party/kraken/tests/kraken-1.1/ai-astar.js

   1 Array.prototype.each = function(f) {
   2     if(!f.apply) return;
   3     for(var i=0;i<this.length;i++) {
   4         f.apply(this[i], [i, this]);
   5     }
   6 }
   7 Array.prototype.findGraphNode = function(obj) {
   8     for(var i=0;i<this.length;i++) {
   9         if(this[i].pos == obj.pos) { return this[i]; }
  10     }
  11     return false;
  12 };
  13 Array.prototype.removeGraphNode = function(obj) {
  14     for(var i=0;i<this.length;i++) {
  15         if(this[i].pos == obj.pos) { this.splice(i,1); }
  16     }
  17     return false;
  18 };
  19
  20 function createGraphSet(gridSize, wallFrequency) {
  21   var graphSet = [];
  22   for(var x=0;x<gridSize;x++) {
  23     var row = [];
  24     for(var y=0;y<gridSize;y++) {
  25       // maybe set this node to be wall
  26       var rand = Math.floor(Math.random()*(1/wallFrequency));
  27       row.push(new GraphNode(x,y,(rand == 0)));
  28     }
  29     graphSet.push(row);
  30   }
  31   return graphSet;
  32 }
  33
  34 // astar.js
  35 // Implements the astar search algorithm in javascript
  36
  37 var astar = {
  38     init: function(grid) {
  39         for(var x = 0; x < grid.length; x++) {
  40             for(var y = 0; y < grid[x].length; y++) {
  41                 grid[x][y].f = 0;
  42                 grid[x][y].g = 0;
  43                 grid[x][y].h = 0;
  44                 grid[x][y].parent = null;
  45             }
  46         }
  47     },
  48     search: function(grid, start, end) {
  49         astar.init(grid);
  50
  51         var openList   = [];
  52         var closedList = [];
  53         openList.push(start);
  54
  55         while(openList.length > 0) {
  56
  57             // Grab the lowest f(x) to process next
  58             var lowInd = 0;
  59             for(var i=0; i<openList.length; i++) {
  60                 if(openList[i].f < openList[lowInd].f) { lowInd = i; }
  61             }
  62             var currentNode = openList[lowInd];
  63
  64             // End case -- result has been found, return the traced path
  65             if(currentNode.pos == end.pos) {
  66                 var curr = currentNode;
  67                 var ret = [];
  68                 while(curr.parent) {
  69                     ret.push(curr);
  70                     curr = curr.parent;
  71                 }
  72                 return ret.reverse();
  73             }
  74
  75             // Normal case -- move currentNode from open to closed, process each of its neighbors
  76             openList.removeGraphNode(currentNode);
  77             closedList.push(currentNode);
  78             var neighbors = astar.neighbors(grid, currentNode);
  79
  80             for(var j=0; j<neighbors.length;j++) {
  81                 var neighbor = neighbors[j];
  82                 if(closedList.findGraphNode(neighbor) || neighbor.isWall()) {
  83                     // not a valid node to process, skip to next neighbor
  84                     continue;
  85                 }
  86
  87                 // g score is the shortest distance from start to current node, we need to check if
  88                 //   the path we have arrived at this neighbor is the shortest one we have seen yet
  89                 var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
  90                 var gScoreIsBest = false;
  91
  92
  93                 if(!openList.findGraphNode(neighbor)) {
  94                     // This the the first time we have arrived at this node, it must be the best
  95                     // Also, we need to take the h (heuristic) score since we haven't done so yet
  96
  97                     gScoreIsBest = true;
  98                     neighbor.h = astar.heuristic(neighbor.pos, end.pos);
  99                     openList.push(neighbor);
 100                 }
 101                 else if(gScore < neighbor.g) {
 102                     // We have already seen the node, but last time it had a worse g (distance from start)
 103                     gScoreIsBest = true;
 104                 }
 105
 106                 if(gScoreIsBest) {
 107                     // Found an optimal (so far) path to this node.  Store info on how we got here and
 108                     //  just how good it really is...
 109                     neighbor.parent = currentNode;
 110                     neighbor.g = gScore;
 111                     neighbor.f = neighbor.g + neighbor.h;
 112                 }
 113             }
 114         }
 115
 116         // No result was found -- empty array signifies failure to find path
 117         return [];
 118     },
 119     heuristic: function(pos0, pos1) {
 120         // This is the Manhattan distance
 121         var d1 = Math.abs (pos1.x - pos0.x);
 122         var d2 = Math.abs (pos1.y - pos0.y);
 123         return d1 + d2;
 124     },
 125     neighbors: function(grid, node) {
 126         var ret = [];
 127         var x = node.pos.x;
 128         var y = node.pos.y;
 129
 130         if(grid[x-1] && grid[x-1][y]) {
 131             ret.push(grid[x-1][y]);
 132         }
 133         if(grid[x+1] && grid[x+1][y]) {
 134             ret.push(grid[x+1][y]);
 135         }
 136         if(grid[x][y-1] && grid[x][y-1]) {
 137             ret.push(grid[x][y-1]);
 138         }
 139         if(grid[x][y+1] && grid[x][y+1]) {
 140             ret.push(grid[x][y+1]);
 141         }
 142         return ret;
 143     }
 144 };
 145
 146 function go() {
 147   path = astar.search(g1, start, end);
 148 };
 149
 150 go();