Monday, February 22, 2016

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: ,

4 comments:

MG wrote at March 03, 2016 3:35 AM

How do you determine the points inside the polygons? Manually?

Amit wrote at March 03, 2016 9:57 AM

The abstract graph structure doesn't actually have a location inside the polygon. The polygon itself is the node. For the visualizations on the page, I pick a point manually, but A* doesn't actually see that.

MG wrote at March 04, 2016 12:28 AM

Then how are the polygons used for pathfinding? Sorry if the question seems too basic, I am guessing you probably wrote about this somewhere.

Amit wrote at March 04, 2016 6:37 AM

Not at all! It's *not* obvious, and my diagrams don't make it completely clear. :(

What A* sees is the abstract "graph" data -- nodes and the connections ("edges") between nodes. It doesn't actually know that the nodes represent polygons, or that the nodes "mean" a location on a map. To graph search (including A*), the nodes could be anything. For example, you might make nodes for moods like "happy" and "sad", and then you could have an edge from sad-->happy that is labeled "eat ice cream". Then if you ask graph search how to get from "sad" to "happy" it would say the shortest path is to eat ice cream. Graph search is quite useful for lots of things.

For game maps we use places for nodes. What A* needs to know is what the possible places are and what's connected to what. So we could use a polygon for each graph node, and then adjacent polygons (you can walk from one to the other) would get a graph edge. Or we could use a grid coordinate for each graph node, and then adjacent grid tiles would get a graph edge.

The way the graphs are drawn in the visualizations is mostly separate, and not something A* actually sees.

(This brings up another topic I should add to the page — when people say A* finds the "shortest" or "optimal" path, that's only on the *graph* and not necessarily the shortest path on the map! Another topic…)