Monday, October 25, 2010

Navigating a Maze

My goal with my drawing program and moving icon programs is to be able to combine them so that the icons will treat the drawn lines as walls. This is my initial pass at that.

I started with the icon mover from last time which already had a Map class.  I added helper methods that will disconnect adjacent cells. breakCells to disconnect a cell from its neighbor and breakPoint to disconnect the two pairs of points that are diagonally touching at a point. breakCells takes a grid cell point, and breakPoint takes a lattice point. The relationship is that a grid cell has the same coordinates as the lattice point at its upper left corner.
  1 Map.prototype.breakCells = function(point, dir) {
  2   var cell = this.getCell(point);
  3   if (cell) cell.eraseEdge(dir); 
  4   cell = this.getAdjacentCell(point, dir);
  5   if (cell) cell.eraseEdge(dir.opposite());
  6 } 
  7 Map.prototype.breakPoint = function(point) {
  8   this.breakCells(point, Dir.NORTHWEST); 
  9   this.breakCells(, 0), Dir.NORTHEAST); 
 10 }
The cell.eraseEdge just marks that edge as non-traversable so that it won't be included when the cell.getNeighbors call is made.

For this initial implementation I am sticking to the simpler case of just handling horizontal and vertical lines. I want to break apart any two cells that has a line that crosses between them and break any point that a line touches. I added a method breakGridLine which does this.
  1 Map.prototype.breakGridLine = function(line, dir, dx, dy){
  2   var p1 = line.p1; 
  3   while (!p1.eq(line.p2)) { 
  4     this.breakPoint(p1); 
  5     this.breakCells(p1, dir); 
  6     p1 =, dy); 
  7   } 
  8   this.breakPoint(line.p2); 
  9 }
dx and dy are the deltas that describe how to traverse the line and dir is the direction of the cells that are on the other side of the line.

Now I just added another method that loops over all the lines and breaks them apart.
  1 Map.prototype.breakLines = function(lines) {
  2   for (var i in lines) {
  3     var line = lines[i]; 
  4     if (line.slope.rise == 0) {
  5       this.breakGridLine(line, Dir.NORTH, 1, 0);
  6     } else if ( == 0) {
  7       this.breakGridLine(line, Dir.WEST, 0, 1);
  8     } else { 
  9       // ignore diagonal lines for now 
 10     } 
 11   } 
 12 }
If we call this method with the lines from a drawn map, our existing BFS searching algorithm will now cause our icons to traverse the grid. Now its just a matter of calling the breakLines method when we start to move icons.
  1 IconControls.prototype.setLines = function(lines) {
  2 = new Map(this.iconLayer.grid.width, this.iconLayer.grid.height);
  4 }
And of course the HTML to add the buttons, etc, which I won't bore you with today. Anyway, here is the demo.



No comments: