Friday, July 25, 2014

(On this blog I'll sometimes go into the “making of” the game programming tutorials I post on my site.)

For my pathfinding pages I wanted to support "painting" on the map to make or erase walls. When you change the map, the pathfinding algorithm updates the paths. Here's how paint works:

Set up mousedown, mousemove, mouseup event handlers on all the tiles.

  1. When you press the mouse button, I toggle the tile you're pointing to.
  2. When you move the mouse, I set the tiles you pass over to match the tile you first clicked on.
  3. When you release the mouse, I stop tracking the mouse.

For example, if there are three tiles A B C and you are over A without a wall, then press the mouse button, I put a wall at A (toggle). If you then move the mouse over B, I make B a wall (set to whatever A has). And then if you release the mouse over C, I'll set C to a wall as well.

When I first published the Introduction to A* article two weeks ago, I still had an item on my bug list to fix map editing on a touch screen. I wasn't sure why it wasn't working. I figured the touch events touchstart, touchmove, touchend would map cleanly to mousedown, mousemove, mouseup. But they didn't. After some debugging, I figured out that the touchmove and touchend events get sent to the object that received the touchstart event. That means instead of seeing A.mousedown, A.mousemove, B.mousemove, C.mousemove, C.mouseup, I am seeing A.touchstart, A.touchmove, A.touchend. I don't receive events on B or C at all.

To fix this, for touch events I look up the x,y position of the touch and map that back onto a tile. This is sort of annoying, as I figure browsers already have a way to map pixel locations to SVG DOM objects, but I don't know how to harness that lookup. Fortunately, most of the diagrams are simple square grids, so the code to map pixels to grid locations is easy.

There are some more tweaks for the page to work well on touch screens, but it should mostly work now.


Thursday, July 24, 2014

People sometimes ask about pathfinding on isometric grids. This is the wrong way to look at it.

You're finding paths in the game world. Isometric is not part of the game world. Isometric is how you look at the game world. Consider the shortest path from New York to San Francisco. Does the shortest path depend on how you hold the map? No! The person looking at the map does not matter. The shortest path is the same no matter how you are looking at the map.

Labels: ,

Sunday, July 13, 2014

I've been working on updating my pathfinding articles with interactive diagrams. While doing so, I realized that I don't like the way I've presented information in my pathfinding articles. Instead of just updating them in-place, I'm writing new tutorials and will eventually figure out how to stitch everything together.

A big one I've been working on is the introduction to A*. I started writing these notes in 1997 and have updated them over the years. The past few months I've been working on a replacement for this page. The page compares Breadth First Search, Dijsktra's Algorithm, Greedy Best First Search, and A*. Differences from the old page:

  • All the diagrams are interactive (of course)
  • I mention non-grids a little more (still not enough)
  • I use contour lines to compare the algorithms (not sure if this will make sense to people)
  • I show working Python code for each of the algorithms
  • I have supplemental material that includes the helper functions and classes needed for the search algorithms
  • I give some guidance on which algorithm to use

There are lots of little things (smoother animations, touch screen support, better code highlighting, better contour line visualization) that remain, but I decided to publish it 90% complete instead of delaying it to polish all those little details. Take a look at the new introduction and let me know what you think. Is it understandable? Do the contour lines help? Is it enough to help you implement A* yourself?


Wednesday, July 09, 2014

I'm working on a tutorial showing how Breadth First Search, Dijkstra's Algorithm, Greedy Best-First Search, and A* are related. I'm focusing on keeping the code simple and easy to understand.

While tracking down a bug in my Dijkstra's Algorithm code, I realized I had forgotten to implement the "reprioritize" case. That led me to wonder why my code seemed to work without handling that case. It turns out that case is never triggered by the graphs I'm searching over. Let me explore this …

Labels: ,