Selectively Displaying a Map in JavaScript

So I've now created the ability for an icon to navigate through a maze. For the next step, I think it would be interesting if the user could only see the portion of the maze that the icon could see. I am envisioning a scenario where everything that the icon can see looks as before, areas that the icon can't see and you've never seen aren't visible, and places that you can't see, but you have seen are grayed out (representing your memory).

Algorithm
The first (and arguably hardest) step is determine which cells can be seen from a given location.  Here is the algorithm that I have come up with:

• The cell with the icon is visible
• Any other cell is visible if
• the cell(s) directly closer to the icon are visible
• AND it is legal to move directly to the cell(s) closer to the icon

Also, to make sure diagonal lines that are borders can be seen, any cell with a line running through it (I'll call this a "broken" cell) that borders a visible cell is visible.

To handle "memory", when calculating what cells are visible, I first mark any cells that were visible as OLD so they can be shown in gray if they are not still visible.

Implementation
The first method that I have is the easiest - it just marks every existing visible cell as previously visible.

  1 Map.prototype.prepareVisibleCells = function(){
  2   for (var i in this.cells) {
  3     var cell = this.cells[i];
  4     if (cell.visible == Visible.VISIBLE) {
  5       cell.visible = Visible.OLD; 
  6     } else if (cell.visible == Visible.BORDER) {
  7       cell.visible = Visible.OLD_BORDER;
  8     } 
  9     cell.visited = false; 
 10   } 
 11 }

There are two things I want to point out in this method. The first is that I mark every cell as not having been visited in line 9. I'll use this property to make sure I don't process a cell twice. The second is that I have two types of cells, VISIBLE and BORDER. VISIBLE cells are what they sound like. BORDER cells correspond to the "broken" cells I talked about above that I'll show as visible, but that you can't see through.

The second method is the one where I calculate which cell(s) are between the current cell and the start cell (the one with the icon). Let me show an example to explain what I want.

	A	B
	C	D
		E

In the above example, cell A and C are visible as long as they directly connect to the icon. B is visible if it is connected to A and A is visible. Similarly E is visible if it is connected to C and C is visible. But what about D? D is between the horizontal line A-B and the diagonal line C-E. The choice I made is that D is only visible if it can be seen on both the diagonal, and the horizontal. I.e. D is connected to A and A is visible and D is connected to C and C is visible. The code that determines which direction to go looks like:

  1 Map.prototype.getClosestDirs = function(start, cell) {
  2   var dx = start.point.x - cell.point.x; 
  3   var dy = start.point.y - cell.point.y; 
  4   var sx = this.signum(dx);
  5   var sy = this.signum(dy);
  6   var dir1 = Dir.getDir(sx, sy); 
  7   if (Math.abs(dx) > Math.abs(dy)) sy = 0;
  8   if (Math.abs(dx) < Math.abs(dy)) sx = 0;
  9   var dir2 = Dir.getDir(sx, sy); 
 10   return [dir1, dir2]; 
 11 }

The signum call on lines 5 and 6 is just the signum function. I realize that the Map class is probably not an appropriate place for this function, but that is where it is for now.

If the cell is on one of the 4 cardinal directions from the start, lines 2-6 calculate that cardinal direction, otherwise it finds the diagonal that the cell is closest to. Lines 7-9 determine which of the 4 cardinal directions the cell is closest too, unless it is exactly on the diagonal. Line 10 returns these two directions that were found. Note that they are the same if the cell is exactly on one of the 8 main directions from the start cell.

Now that we have these two helper functions, we can do a breadth first search from the icon to determine what is visible.

  1 Map.prototype.setVisibleCells = function(point) {
  2   this.prepareVisibleCells(); 
  3   var start = this.getCell(point);
  4   start.visited = true; 
  5   var queue = new Queue();
  6   queue.push(start); 
  7   while (!queue.isEmpty()) { 
  8     var cell = queue.pop(); 
  9     if (cell != start) { 
 10       if (cell.isBroken) { 
 11         cell.visible = Visible.BORDER; 
 12         continue; 
 13       } 
 14       var dirs = this.getClosestDirs(start, cell);
 15       if (!cell.isVisibleDir(dirs[0]) || !cell.isVisibleDir(dirs[1]))continue;
 16     } 
 17     cell.visible = Visible.VISIBLE; 
 18     for (var i in Dir.dirs) {
 19       var dir = Dir.dirs[i]; 
 20       var nextCell = cell.getAdjacent(dir);
 21       if (!nextCell || nextCell.visited) continue;
 22       nextCell.visited = true; 
 23       queue.push(nextCell); 
 24     } 
 25   } 
 26 }

Lines 2-6 set up the state for the BFS algorithm, while lines 7-25 are the main loop. Lines 10-12 is where I determine if the cell has a line going through it (i.e. is "broken"). Since I know only cells adjacent to VISIBLE cells will ever get processed, I can mark this cell as a BORDER so it will be shown. The isVisibleDir calls made on line 15 check if the the cell in the given direction is both connected and visible. If not, then this cell is not visible, and we can continue to the next cell in the BFS queue.

If we get to line 17, then this cell is VISIBLE and we mark it as such. In lines 18-24 we iterate through all of the cells that are adjacent to this cell, and add them to the queue, if they haven't already been added to the queue (i.e. marked as visited). And with that, we have an algorithm that calculates which cells should be visible.

Hiding Cells
To actually limit the visibility I added another canvas layer that is on top of the other layers and I have a VisibleLayer class that manages this layer. Whenever the icon we are following moves into a new cell Map.setVisibleCells is called and then VisibleLayer.draw is called to hide parts of the map.

  1 VisibleLayer.prototype.coverSquare = function(point, style) {
  2   var realPoint = this.getReal(point);
  3   this.ctx.fillStyle = style; 
  4   this.ctx.fillRect(realPoint.x, realPoint.y, this.grid.size, this.grid.size);   
  5 } 
  6 VisibleLayer.prototype.draw = function(map) {
  7   this.clear(); 
  8   this.ctx.save(); 
  9   for (var i in map.cells) {
 10     var cell = map.cells[i]; 
 11     if (cell.visible == Visible.OLD || cell.visible == Visible.OLD_BORDER) {
 12       this.coverSquare(cell.point, "rgba(0, 0, 0, 0.5)");
 13     } else if (!(cell.visible == Visible.VISIBLE || cell.visible == Visible.BORDER)) {
 14       this.coverSquare(cell.point, "rgb(0, 0, 0)");
 15     } 
 16   } 
 17   this.ctx.restore(); 
 18 }

The draw method just iterates over all the cells in the map and if they are VISIBLE or a BORDER, draws a black square over the cell, and if they are OLD or OLD_BORDER then it draws a black square with the alpha set to one half, so that it can still be seen through.

The ctx is the 2d context of the canvas, gotten via the call

this.ctx = canvas.getContext('2d');

The calls to ctx.save() and ctx.restore() ensure that at the end of this method that canvas drawing context is the same as the beginning despite the setting of fillStyle on line 3. The getReal method that is called on line 2 calculates the actual x and y coordinates based on the logical coordinates of the cell, and the clear() call on line 7 clears this layer, making ever cell visible except for the ones that get covered by the calls on lines 12 and 14.

Odds and Ends

To help separate the walls from the shadows, I changed the color of the walls from black to brown and made them thicker.  I also increased the size of the grid cells that are shown on the screen to make things easier to see. The new icon was downloaded from the site http://www.wpclipart.com/money/treasure/.

Demo