Handling Diagonal Lines

In a previous post I added support for having drawn horizontal and vertical lines act as walls that my moving icons can't go through. This post talks about how I added support for diagonal lines.

The basic approach is to determine which cells a line goes through and then disconnect that cell from all its neighbors, making it impossible to move to those cells.

Basic Algorithm

A diagonal line starts at one lattice point and ends at another, passing through cells along the way. The algorithm I came up with was just to "walk" the line. This looks like:

1. Figure out starting cell (x₀, y₀)
2. For each x coordinate that the line goes through:
1. Calculate the y coordinate for that x coordinate (x₁, y₁)
2. Mark every cell (x₀, y₀) -> (x₀, y₁)
3. Set x₀ = x₁ and y₀ = y₁.
3. You are done.

The one caveat is handling when the line actually goes through a lattice point. In that case, you need to make sure that you only mark the two cells on the diagonal, and not three or four. (the algorithm as above with end up marking threes of them without a special case). You do need to disconnect the two non-marked cells since they no longer connect through the diagonal. The code that actually does all of this looks like:

  1 Map.prototype.breakDiagonalLine = function(line) {
  2   var p1 = line.p1; 
  3   var dy = line.slope.rise / Math.abs(line.slope.rise);
  4   var yOffset = (dy > 0) ? 0 : -1; 
  5   while (!p1.eq(line.p2)) { 
  6     var cellPoint = new Point(p1.x, p1.y + yOffset);
  7     this.breakPoint(p1); 
  8     for (var tx = 1; tx <= line.slope.run; tx++) {
  9       var nextY = Math.floor(p1.y + tx*line.slope.rise/line.slope.run);
 10       if (tx == line.slope.run) nextY -= (1 + yOffset); 
 11       while (nextY != cellPoint.y) { 
 12         this.breakWholeCell(cellPoint); 
 13         cellPoint = cellPoint.delta(0, dy);
 14       } 
 15       this.breakWholeCell(cellPoint); 
 16       cellPoint = cellPoint.delta(1, 0);
 17     } 
 18     p1 = p1.delta(line.slope.run, line.slope.rise); 
 19   } 
 20   this.breakPoint(line.p2); 
 21 }

Because of how I calculate slope, the run is guaranteed to be positive. Line 3 calculates the signum of the rise which is used for traversing the cells on line 13.  Line 4 calculates the y offset of the starting cell, relative to the starting point.  i.e. going diagonally upwards starts with a different cell than going diagonally downwards.  The loop on lines 5 - 19 handle the each segment from lattice point to lattice point along the line, iterating once for each lattice point that is reached.

Line 6 determines the first cell that is to broken, using the offset calculated on line 4.  Line 6 breaks apart the cells that are diagonally touching at this point.  The loop on lines 8 to 17 iterate over every x coordinate until the next lattice point.  Line 9 calculates the y coordinate for the given x coordinate (step 2.1 from above).  Line 10 handles the special case of the new x,y coordinates being a lattice point.  The loop one lines 11-14 mark the appropriate cells (step 2.2 from above). Line 15 ensures that we've marked the last cell needed and line 16 increments the x coordinate (step 2.3 from above).

Line 18 sets p1 to the next lattice point so it is ready for the next iteration through the loop. Line 20 breaks apart diagonally touching cells at the final point along the line. Which means we are ready for the demo.

Demo

As before, click an icon, click a destination, and watch the icons avoid the lines.

line rectangle erase line erase rectangle