There are some big things I want to change on my pages, but there are lots of little things too. The big things I keep delaying because they're "big projects" that need a chunk of time. But the small things I've been delaying too, because I keep telling myself I'll do them when I do the big one.

Right now I'm not working on any big projects so I'm tackling some small improvements. This week I improved the path reconstruction diagram on my A* introduction. It looked like this:

Low contrast diagram without end marker

What's wrong with this?

  1. The contrast is too low between the arrows and the background. I had been using a lighter background for "unvisited" nodes and a darker background for "visited" nodes, and I also separately had chosen an arrow color that matched the came_from variable in the example code.
  2. The start node shows the blob icon but the goal node shows no icon. This is inconsistent with other diagrams on the page that show both a start and goal icon.
  3. The tricky bit here is that the arrows point backwards from the goal to the start. It's easy to miss this.

I made some quick changes; it now looks like this:

Higher contrast diagram with start/end markers

  1. I stopped using the darker background to distinguish visited/unvisited because in this diagram everything is visited.
  2. I added a goal icon that matches the other diagrams.
  3. I added goal/start icons to the code to remind the reader that the loop starts from the goal, not the start point, and works backwards.

I think it'd be even better with an arrowhead along the path to show the direction, but I was unable to get something I liked, and I didn't want to spend a lot of time on it, so I abandoned the arrow. Another thing to try would be a small animated dot  •  following the path from the end to the start, color matched with the current variable in the code. That's something I'll consider later.

There are lots of little improvements I'd like to make to my pages, and I would probably be better off making them now instead of waiting until I have time to make bigger updates.


One of the things that's bothered me about my Introduction to A* page and also my older A* pages is that I use grids everywhere. I fear that some of my readers will think that A* is only for grids or that it's best with grids. In my opinion it's worst when it is given grids, especially grids where every step has the same movement cost.

I decided the simplest thing I could do would be to change the grid map at the top of the page. That's the first impression a reader gets. Instead of showing non-grid maps halfway down the page, I should show a map that's not a grid. That way the reader immediately sees that we're not solving a grid problem. This was the first map on the page:

original-map with grid

I took some graph paper and came up with a polygon version of this map. I hand-coded it and got the A* page to show it:

new-map with polygons

Although making the initial version of this map with pen and graph paper wasn't too bad, iterating was quite a pain. I decided to make a quick & dirty tool to edit the shapes. I wanted to edit the graph connectivity too but didn't want to spend more than an hour writing the tool, so I didn't implement that. I put the connectivity in manually.

map-tool I used to edit the polygon shapes

The tool helped a lot! I made it output JSON, and then I copied-and-pasted that JSON into my A* page, where I wrote some code to turn that into the diagram. I spent a few hours on that map and also several others. The tool made it so much easier to edit maps that I ended up making more maps for the page.

After I had this new map up, the next step was to add a section to the page that described graphs. Although I have a link to another page that describes graphs, I think the input and output to an algorithm are too important to not explain on the main page.

I had implemented the A* diagrams with layers (see this); I was able to easily add new layers to show graph nodes and graph edges. With this I made a new diagram:

graph with room centers as nodes

I wanted to demonstrate two things with pathfinding graphs:

Completely different game maps might have similar pathfinding graphs. I drew a game map based on StarRaven's cartography brushes that shared the same pathfinding map as the main example.

same pathfinding graph but different game map

The same game map can be represented by different pathfinding graphs. I added two more pathfinding graphs for the same game map:

graph with doorways as nodes

graph with grid nodes

Comparing these, you can see how A* has to do a lot more work when the pathfinding graph is a grid than when the pathfinding graph is a navmesh or waypoint graph. If you're looking to optimize pathfinding on a grid, the first thing to try is to construct a non-grid pathfinding map.

With all of the new content on the page, I also wanted to simplify some of the other parts of the page. I decided that the contour maps were the least valuable concept, and removed most of the contour map diagrams. I think it's an interesting way of looking at things, but I was never quite happy with them, and they probably belong on an advanced level page, not on this introductory page.

While testing on iPhone and Android, I realized that I had never finished a touch version of the drag-and-drop maps. Until now, it didn't matter, because the diagrams were grid-based, and I had a touch version of the grid code. I had to fill in the non-grid touch event handlers. It doesn't work that well but it's good enough for now.

I'm much happier with the page now, although I still have some work to do on the wording. Take a look! There's still more I want to improve on this page.

Labels: ,

It’s been a while since I wrote a blog post. What did I do in 2015? The first part of the year started out good. I worked on hexes:

  • I updated my Hexagonal Grid Reference with better explanations, better diagrams, and better sample code.
  • I worked on a procedural code generator (1, 2, 3) that generates hexagonal grid libraries in C++, Python, Javascript, C#, Haxe, Java, Typescript, and Lua.
  • I also procedurally generated the unit tests for those libraries, and ran the generated unit tests on the generated code.
  • I also used the generated Javascript code for a new page, a guide to implementing hex grids. My tutorials are typically about the algorithms and not the code, but for this topic I made an exception.

After that, I lost my way. I became interested in pathfinding optimizations, and wrote some things that I didn’t finish:

  • L1-Clarkson based A*, with a super fast implementation from 0fps. People often want to optimize the algorithm but a lot of the time, it’s better to focus on the data. Unweighted grids are a waste of A*’s capabilities; you can greatly speed up A* by not feeding it such inefficiently structured data. The algorithm demoed on this page implements one such possible transformation. Try the demo — it takes only milliseconds, in javascript, to find paths on a large grid map. For references and code, see this page.
  • Differential heuristics demo and article. This is something 0fps recommended I explore. It turns out to be pretty awesome, with huge speed improvements with only a few lines of code. Unfortunately I lost interest partway through.
  • Visibility graph construction to turn unweighted grids (tons of nodes for A*) into lightweight graphs. This can both speed up A* and make the paths on a grid look “straighter”. Unfortunately with this topic too I lost interest partway through.

The problem, I think, is that in my own games I’ve not needed these optimizations. So I was exploring a set of potential optimizations that I haven’t actually needed. In practice, a lot of optimizations are specific to a project, and without having worked on a real project that needed these, I didn’t have the confidence that they were good recommendations. Also, knowing that I haven’t actually needed these reduced my motivation to explore them.

The pathfinding optimization part of the year mostly fizzled, so I stepped away from that topic and worked on other topics:

  • I improved one of my older tutorials, on Probability / damage rolls. I wrote a blog post about why I was unhappy with the original version and what I did to improve the tutorial.
  • Some people see my tutorial on polygonal map generation and walk away saying it’s too complicated. Well, it is. That’s not where I started. I started with something much simpler and worked my way up to the complicated one. I wrote a tutorial on the simple map generator I often start with. It’s limited, but it’s simple.

Realizing that my tutorials are better when they come from experience with real projects, I decided to take a break from tutorials and instead try some small game projects. In the last few months of the year I worked with Jetbolt Games learning about browser-based MMOs. We used Emscripten so that we could write both the server and client in C++. I played with SDL and OpenGL shaders, as well as network synchronization. This was a fun few months. It was nice to do something different. I didn’t write any of this up.

I also worked on a bunch of small projects throughout the year:

The next step for me is to get back into writing. I’ll start with some small projects and then I’d like to explore some algorithms that are useful in simulation games like SimCity, Dwarf Fortress, Rimworld, Prison Architect, Cities Skylines. For example, I learned about Munkres-Kuhn from Goblin Camp, an open source game inspired by Dwarf Fortress, but haven’t yet explored this algorithm.

Oh, and I’ve also been spending time in nature.

Popular Posts