Breadth First Search for Moving Icons

While I can move icons around on a grid, they aren't really moving the way I want. For the app that I am envisioning, icons should only be allowed to move in the four cardinal directions and the four diagonals. This post is about how I enforce that, and about setting some things in place for future enhancements.

To help I've created a Map class and a Cell class. A map consists of a bunch of cells that are connected. The cells correspond to the squares in a grid that the icons are allowed to be and they are connected along the paths that they are allowed to move. Until I've added support for drawing walls, each cell is connected along the 8 directions around it. The exception, of course, are along the 4 edges where the cells are only connect to the cells that exist.

To calculate distance, I follow the D & D convention and round the diagonal from √2 to 1.5. But since I like integer arithmetic I make the four cardinal directions have a distance of 2 and the diagonals have a distance of 3. Now that I have a map, rather than just drawing a straight line from the start to the finish, I calculate the shortest legal path and make these moves.

  1 IconControls.prototype.click = function(x, y){
  2   var point = this.iconLayer.getGridPoint(x, y);
  3   var cell = this.map.getCell(point);
  4   var icon = this.iconLayer.findIcon(point);
  5   if (icon) { 
  6     this.activeIcon = icon; 
  7     this.lastCell = cell; 
  8   } else if (this.activeIcon) {
  9     var path = this.map.shortestPath(this.lastCell, cell);
 10     if (path) { 
 11       for (var i in path) {
 12         this.activeIcon.moveTo(path[i].point);
 13       } 
 14       this.lastCell = cell; 
 15     } else { 
 16       alert("destination is unreachable.");
 17     } 
 18   } 
 19 }

In the above code, lines 6-7 handle the case where you click on an icon and lines 9-17 move the icon. The shortestPath method call on line 9 returns a contiguous set of cells that comprise a path from start to finish, if one exists.  The loop in lines11-13 then moves the icon to each of these cells in turn.  Line 16 warns the user if no path exists.  This isn't possible yet, but will be once we start adding walls to our grid.

To calculate the shortest path, I set the destination cell as having a cost of 0 and all of the other cells as having a large cost. I now do a breadth first search from the destination to the source, recording the distance in each cell along the way.  I can now calculate the path from source to destination with a greedy algorithm.  Note that since the triangle inequality holds, the shortest path will have as few or few steps than any other path, and so a breadth first search is good enough and I don't need to use Djikstra's algorithm.  If, in the future, this condition does not hold, I will have to rewrite this code.

  1 Map.prototype.shortestPath = function(src, dest){
  2   for (var i in this.cells) {
  3     this.cells[i].cost = this.MAX_COST;
  4   } 
  5   dest.cost = 0; 
  6   var queue = new PriorityQueue();
  7   queue.push(dest, 0); 
  8   while (!queue.isEmpty()) { 
  9     var cell = queue.pop(); 
 10     if (cell == src) return this.createPath(src, dest);
 11     var choices = cell.getNeighbors(); 
 12     for (var i in choices) {
 13       var move = choices[i]; 
 14       var cost = cell.cost + move.cost; 
 15       if (cost >= move.cell.cost) continue;
 16       move.cell.cost = cost; 
 17       queue.push(move.cell, cost); 
 18     } 
 19   } 
 20   return null; // no such path
 21 }

Lines 2-7 initialize our state while line 8-19 is the main loop of the search. getNeighbors returns the list of valid neighbors of this cell and the cost to move there (2 for the cardinal directions, and 3 for the diagonals) and this list is sorted by cost.  On line 15 we check if the cost of moving to a cell from the current location is lower than any previously considered path.  If it is, we set the cost on line 16 so we won't try another path with the same cost and on line 17 we push that node into our priority queue of nodes to consider.  The createPath call on line 10 calculates the path using the stored cost in each cell.

  1 Map.prototype.createPath = function(src, dest){
  2   var list = [src]; 
  3   while (src != dest) { 
  4     var cost = this.MAX_COST;
  5     var next; 
  6     var moves = src.getNeighbors(); 
  7     for (var i in moves) {
  8       var cell = moves[i].cell; 
  9       if (cell.cost < cost) { 
 10         next = cell; 
 11         cost = cell.cost; 
 12       } 
 13     } 
 14     list.push(next); 
 15     src = next; 
 16   } 
 17   return list; 
 18 }

As describe above, this algorithm just greedily chooses nodes closer to the destination until it reaches the destination.  The loop in lines 7-13 makes the greedy calculation and it is added to the path on line 14.

Demo

This demo is just like the previous demo, except the icons will move only along the 8 main directions.  As before click an icon, click a destination, lather, rinse, and repeat.