One thing that annoys me about my own A* pages is that they use grids for the examples. A* is not restricted to grids. A* works on any directed graph. A* on uniform grids is often slow, so people have come up with various ways to make the algorithm faster. I feel like the "right" thing to do is not to change the algorithm but to change the data.

Graph search is used when you want to make "global" decisions that involve potentially analyzing large parts of the map. You look ahead all the way to the end before you can decide anything. It's a waste to use it on "local" decisions that you can make without looking far ahead. Suppose you have this game map (from Baldur's Gate):

What's the easiest thing to do? Make each tile into a graph node:

This is a fine solution, but A* will take a while to find the paths. There are a lot of nodes to visit. Some algorithms will make A* faster by using a cheaper way to visit the nodes. However, it's even faster if you skip most nodes altogether. For any path on this map, almost all of steps can be decided locally, by just following a straight line. There's no need to give those nodes to A*. Instead of making every tile into a pathfinding graph node, give a smaller graph to A*:

You'll need to annotate the map with this graph, either manually in a level editor or automatically with a preprocessing algorithm. A* will run much faster on the tiny graph than the dense grid graph. If you're looking to optimize A* on a grid, consider changing the data before you consider changing the algorithm. Navigation meshes, visibility graphs, and hierarchical approaches are all worth a look.

I have a little more written here and here, but one of these days I will update my pages to put less emphasis on grids.

Labels: ,

I’ve been updating my hexagonal grid reference and noticed how bad the pseudocode is. I took a few days to clean it up.

Here’s a loop that was setting variables and also calling graphics commands.

for each 0 ≤ i < 6:
    angle = 2 * PI / 6 * i
    x[i] = center_x + size * cos(angle)
    y[i] = center_y + size * sin(angle)
    if i == 0:
        moveTo(x[i], y[i])
    else:
        lineTo(x[i], y[i])

I replaced that with a function that be used independently of the line drawing code:

function hex_corner(center, size, i):
    angle = 2 * PI / 6 * (i + 0.5)
    return Point(center.x + size * cos(angle),
                 center.y + size * sin(angle))

I’ve also switched from separately tracking x and y to using a Point class/struct/record with x and y fields. This more closely matches what most people will be doing.

Here’s another example of a code snippet without any clear indication of how to use it:

neighbors = [
    [+1, -1,  0], [+1,  0, -1], [ 0, +1, -1],
    [-1, +1,  0], [-1,  0, +1], [ 0, -1, +1]
]
d = neighbors[direction]
return Cube(x + d[0], y + d[1], z + d[2])

What’s wrong with this?

  1. neighbors is a constant and doesn’t need to be initialized every time you need a neighbor.
  2. The return statement makes it clear this is part of a function, but the function is nowhere to be seen.
  3. The inputs to the function are apparently x, y, z, direction but it’s not stated.
  4. The output is a Cube object, but the input is three separate numbers x, y, z instead of another object.
  5. The elements of the neighbors array are arrays of integers, but they should also be Cube objects.

Later on the page I call a directionmethod on a Cube object, but I never define that. The direction method is related to the neighbors function.

I rewrote it like this:

directions = [
   Cube(+1, -1,  0), Cube(+1,  0, -1), Cube( 0, +1, -1),
   Cube(-1, +1,  0), Cube(-1,  0, +1), Cube( 0, -1, +1)
]

function cube_direction(direction):
    return directions[direction]

function cube_neighbor(hex, direction):
    return cube_add(hex, cube_direction(direction))
  1. The array is now defined outside the function, and the elements are cube objects.
  2. The logic is separated into cube_direction, cube_neighbor, and the helper function cube_add. I can now use cube_add because the array contains cube elements instead of arrays of ints.
  3. The input to the function is a cube object, although I don’t list the types in the pseudocode. This is something I want to address later.

Here’s another example of potentially confusing pseudocode:

function hex_distance(Cube(x1, y1, z1), Cube(x2, y2, z2)):
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

What’s wrong with this? It’s mostly ok, except that I use destructuring bind (pattern matching) in the function arguments. I think most readers will prefer this:

function cube_distance(a, b):
    return (abs(a.x - b.x) + abs(a.y - b.y) + abs(a.z - b.z)) / 2

I’m also removing some of the inlining. Here’s an example of hex-to-cube inlined:

function hex_distance(Hex(q1, r1), Hex(q2, r2)):
    var x1 = q1
    var z1 = r1
    var x2 = q2
    var z2 = r2
    var y1 = -(x1 + z1)
    var y2 = -(x2 + z2)
    return (abs(x1 - x2) + abs(y1 - y2) + abs(z1 - z2)) / 2

If you’re just skimming the page, you’ll have no idea where or why all those variables are there. I hope the new version is clearer:

function hex_distance(a, b):
    var ac = hex_to_cube(a)
    var bc = hex_to_cube(b)
    return cube_distance(ac, bc)

Throughout the page I had a mix of top level code, functions, and methods, and the reader would have no idea where they came from. I’m trying to be consistent in using functions everywhere. I’m also trying to consistently name these functions hex_* and cube_* depending on whether they work on hex (axial or offset) or cube coordinates. I’ve also added implementation notes in various places where there might be something tricky. I hope these changes will make it easier for the reader to understand how to turn the pseudocode into actual code.

I'm not a fan of Bresenham's line drawing algorithm. I know, it's fast, and sometimes you want to complicate the code for speed. But these days, fast line drawing is going to be done by the graphics library. I only need line drawing for analyzing grid maps in my game. Line drawing performance isn't critical anymore for me, so I prefer using a much simpler algorithm. I decided to write up my notes about that.

I don't like that Bresenham's algorithm has separate cases for 8 octants. You can collapse some of these with a series of if statements, but I prefer interpolation, where there aren't different cases. I don't like that some presentations of Bresenham's algorithm handle only one octant and leave the rest as an exercise to the reader. I don't like that some implementations of Bresenham's swap the endpoints, which is fine for drawing lines, but not as good for game algorithms such as moving an arrow from the player's bow to the enemy orc.

I like that the linear interpolation algorithm reuses concepts that are useful for other parts of my games. I also like that the same line drawing algorithm works on 3d grids and hex grids. I like that interpolation as a concept can be extended to angles, times, spherical rotations, and other things. I like that linear interpolation leads to non-linear interpolation, often used for animation.

Interpolation is both more general and simpler than Bresenham's algorithm. I use it for lots of other things, so I use it for line drawing too, instead of using a different specialized algorithm for line drawing.


I wrote up my notes about line drawing using linear interpolation

What went right?

  1. Org-mode

    I've been trying out emacs org-mode for some of my smaller articles. It worked really well in this case. I used org-babel, which lets me embed source code along with the article text. For each block I can choose whether it gets output as javascript, in the html, or both. The code I present is the same code used to power the diagrams (for the most part).

    You can see the org-mode source here.

  2. Diagram class

    I wrote a small diagram class that let me turn on various optional features. I then instantiated it for each of the diagrams on the page, enabling different features for each.

    • All the diagrams show a grid.
    • Some diagrams show a single interpolation point, controlled through a number control on the page.
    • Some diagrams show many interpolation points. The number of points is either calculated automatically or controlled through a number control on the page.
    • Some diagrams show a "track" that contains the interpolation points
    • Some diagrams show draggable endpoints. In the end, all of them did, but during development I wasn't sure if I'd do that.

    I also have various hacks that aren't cleanly put into the diagram class. That's ok. I'm trying to make a pretty page, not make pretty code. I make pretty code only if it helps me make the pretty page more quickly. Unlike most software projects, there's not much maintenance over time, so that up-front investment usually doesn't pay off.

  3. Draggable numbers

    I have a draggable number library that I haven't shared yet, but I've used for a few unfinished projects. I used it here. It's like Bret Victor's Tangle but uses D3 instead of MooTools.

  4. Draggable markers

    I used draggable markers that I explained here and they worked pretty well.

What went wrong?

Scope creep was the biggest problem. It's just line drawing. I thought it'd be quick to write up. But I kept thinking of more things I wanted to add.

  1. Scope - algorithms

    My original plan was to explain two line drawing algorithms, but the more I worked on those, the more variants I started finding. I added the supercover line drawing, but I had several more I wanted to add when I realized … I should just stop and publish the article.

  2. Scope - topics

    As I got into interpolation for 2d grid lines, I realized that other aspects of interpolation are pretty cool too: non-linear interpolation (used in animation "tweens"), hex grid lines, 3d grid lines, interpolation in color space.

    I even had written interactive demos for interpolation in different color spaces, comparing RGB, HSL, HCL, Lab, but I ripped it all out when I realized I was going way outside the scope of the page.

  3. Scope - interactivity

    Bret Victor had talked about how the technology of the printing press led us to separate images and text, and we keep doing that on the web even though we don't use moveable type anymore. That made me wonder what kinds of things I'd like to do for explanations that break out of my standard format of text separated from diagrams.

    What first came to mind was what I do on paper: I make arrows that point from one thing to another thing, even if it's not in the same "box".

    I started implementing this, and was quite happy with what I had, but decided it wasn't worth the effort for this article. I ripped it out, and will try it again for another article. It was a neat effect that I don't see people using. Try mousing over this paragraph, and you'll see an arrow pointing back to the section heading:

In the end…

I needed this small project. I've been sort of stuck since September, so this got me going again. I often find that when I'm stuck, I need to do something simpler, and then work my way up again.

Labels: ,

Popular Posts