#+TITLE: Line drawing on a grid #+OPTIONS: toc:nil Graphics libraries provide line-drawing routines, sometimes with [[https://en.wikipedia.org/wiki/Xiaolin_Wu%27s_line_algorithm][antialiasing]] and variable width. On a grid map, line drawing is useful for for visibility, the path of an arrow/bullet, and enemy AI. I sometimes see people adapting the Bresenham line drawing algorithm to draw lines on a grid (especially for roguelike games), but I prefer a /much/ simpler algorithms that runs just as fast. I'll show the algorithms I use. This is the code. The first section will explain how it works and the helper functions =round_point= and =lerp_point= and =diagonal_distance= (these are all short), and then the other sections will describe variants of the algorithm. #+begin_src js :tangle no function line(p0, p1) { let points = []; let N = diagonal_distance(p0, p1); for (let step = 0; step <= N; step++) { let t = N === 0? 0.0 : step / N; points.push(round_point(lerp_point(p0, p1, t))); } return points; } #+end_src * Linear interpolation :PROPERTIES: :CUSTOM_ID: interpolation :END: This demo shows what grid locations should be marked if you're drawing a line between two points. *Try moving the endpoints around*. #+begin_export html
#+end_export I find the easiest way to find these points is to use /linear interpolation/. Let's see how that works. ** Interpolating numbers :PROPERTIES: :CUSTOM_ID: interpolation-numbers :END: Here's a simple (Javascript) helper function I'll use: #+begin_src js :tangle yes :exports code function lerp(start, end, t) { return start * (1.0 - t) + end * t; } #+end_src @@html:Linear interpolation@@ (“lerp”) gives you a number between two other numbers. When =t= = 0.0 you get the start point; when =t= = 1.0 you get the end point. *Try setting t*, the third parameter to lerp(): #+begin_export html
```lerp(  0,   1, ) =
lerp(  0, 100, ) =
lerp(  3,   5, ) =
lerp(  5,   3, ) =
```
#+end_export #+begin_src js :tangle yes :exports none var t0 = make_scrubbable('t0', 0.3, [0.0, 1.0], 0.01); t0.trigger(function() { function set(id, fmt, lo, hi) { d3.select(id).text(d3.format(fmt)(lerp(lo, hi, t0.value))); } set("#lerp1", ".2f", 0, 1); set("#lerp2", ".0f", 0, 100); set("#lerp3", ".1f", 3, 5); set("#lerp4", ".1f", 5, 3); }); #+end_src ** Interpolating points :PROPERTIES: :CUSTOM_ID: interpolation-points :END: We can extend the idea of interpolation to work on points, by interpolating both the x and y coordinates. *Try varying t* = @@html:@@: #+begin_export html
#+end_export Here's the code to find point x,y between point p_{0} = (x_{0},y_{0}) and point p_{1} = (x_{1},y_{1}): #+begin_src js :tangle yes function lerp_point(p0, p1, t) { return new Point(lerp(p0.x, p1.x, t), lerp(p0.y, p1.y, t)); } #+end_src Let's divide the line into @@html:@@ equal line segments: #+begin_export html
#+end_export Here's the code to find those points: #+begin_src js :tangle yes :exports none function Point(x, y) { this.x = x; this.y = y; } #+end_src #+begin_src js :tangle yes :exports none // This will make it easier to use with d3+svg Point.prototype.toString = function() { return this.x + "," + this.y; }; #+end_src #+begin_src js let points = []; for (let step = 0; step <= N; step++) { let t = step / N; points.push(lerp_point(p0, p1, t)); } #+end_src Variant: we can start ~let step = 1~, and stop at ~step < N~ if we want to exclude the two endpoints. Variant: we can replace ~step <= N~ with another condition, such as stopping at a wall or at the edge of the map. ** Snap to grid :PROPERTIES: :CUSTOM_ID: snap-to-grid :END: Next we need to figure out which /grid squares/ those points are in. We can round x and y to the nearest integer to find the grid tile: #+begin_export html
#+end_export We also need to decide how many points to include. Too few and the line has holes. Too many and the line has overdraw. How many do we need? The right number is the /diagonal distance/ between the endpoints, which in this case is @@html:@@. *Adjust N* = @@html:@@ to @@html:@@ to see how the line fills in. @@html:@@ That's it! 1. Set N to the diagonal distance between the start and end point. 2. Pick N+1 interpolation points, evenly spaced. 3. Round those points to the nearest grid tile. Here's the final code: #+begin_src js :tangle yes function line(p0, p1) { let points = []; let N = diagonal_distance(p0, p1); for (let step = 0; step <= N; step++) { let t = N === 0? 0.0 : step / N; points.push(round_point(lerp_point(p0, p1, t))); } return points; } #+end_src This is the simplest line drawing algorithm I know of. Here are the helper functions, which you may have already implemented: #+begin_src js :tangle yes function diagonal_distance(p0, p1) { let dx = p1.x - p0.x, dy = p1.y - p0.y; return Math.max(Math.abs(dx), Math.abs(dy)); } function round_point(p) { return new Point(Math.round(p.x), Math.round(p.y)); } function lerp_point(p0, p1, t) { return new Point(lerp(p0.x, p1.x, t), lerp(p0.y, p1.y, t)); } function lerp(start, end, t) { return start * (1.0 - t) + t * end; } #+end_src #+begin_src js :tangle yes :exports none // You should use the line() function presented in the article. // However, for the interactive illustrations I want to show the // unrounded points, and I also want the reader to choose N, so this // is a variant of the line() function. function line_N_unrounded(p0, p1, N) { let points = []; for (let step = 0; step <= N; step++) { let t = N === 0? 0.0 : step / N; // special case: N=0 when p0==p1 points.push(lerp_point(p0, p1, t)); } return points; } #+end_src #+begin_src js :tangle yes :exports none // Make a line-drawing diagram // // #\$id will get a new
#+end_export #+begin_src js :tangle yes :exports none let diagram_grid_movement = new Diagram('diagram-grid-movement') .add_track() .add_line_draw() .add_endpoints(); diagram_grid_movement.find_line = function() { this.points = walk_grid(this.endpoints, this.endpoints); }; diagram_grid_movement.redraw(); #+end_src The strategy here is to think about the /grid edges/ being crossed, both vertical and horizontal. At every step we either cross a vertical edge (horizontal step) or cross a horizontal edge (vertical step). The way we can tell which way to go is by looking to see which of =(0.5+ix) / nx= and =(0.5+iy) / ny= is smaller. The smaller one is where we want to take the next step. #+begin_src js :tangle yes function walk_grid(p0, p1) { let dx = p1.x-p0.x, dy = p1.y-p0.y; let nx = Math.abs(dx), ny = Math.abs(dy); let sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1; let p = new Point(p0.x, p0.y); let points = [new Point(p.x, p.y)]; for (let ix = 0, iy = 0; ix < nx || iy < ny;) { if ((0.5+ix) / nx < (0.5+iy) / ny) { // next step is horizontal p.x += sign_x; ix++; } else { // next step is vertical p.y += sign_y; iy++; } points.push(new Point(p.x, p.y)); } return points; } #+end_src To avoid the division, including a potential divide by zero, we can rewrite the comparison from =(0.5+ix) / nx < (0.5+iy) / ny= to =(0.5+ix) * ny < (0.5+iy) * nx=. Then to avoid the floating point we can rewrite that to =(1 + 2*ix) * ny < (1 + 2*iy) * nx=. It's more work to make it symmetric. Also, sometimes you'll want more control over whether you pick a horizontal step or a vertical step, especially if the choice is close, and there's a wall in one direction but not the other. ** Supercover lines :PROPERTIES: :CUSTOM_ID: supercover :END: "Supercover" lines catch all the grid squares that a line passes through. I believe (but am not sure) that it is somewhere in between regular line drawing and grid movement line drawing. Unlike grid movement line drawing, we can take a diagonal step /only/ if the line passes exactly through the corner. This looks like the grid movement line drawing, except when the line goes through a grid corner. #+begin_export html