I’ve recently been playing with CoffeeScript, a neat little language that compiles to JavaScript. It’s a lot more concise than plain old javascript and can be organised much more tightly, so I’m really having a blast with it. That said, its conventions are a bit different to what I’m used to working with, so more bit of practice is in order.
One of the practice scripts I wrote is a very basic 2d pathfinder, hooked up to an html5 canvas element. The original idea was to get a good feel for the CoffeeScript syntax and then write a bit about it, but a screenshot of the finder on Facebook generated a bit of curiosity among some friends, so this post will be about the pathfinding algorithm instead; the CoffeeScript post will just have to wait a bit longer.
Since the point of this script was not to write a perfect pathfinder, please keep in mind that it’s not 100% complete. There are a few issues which I didn’t bother to work out; this post is purely for the benefit of the curious.
You can play with the pathfinder here.
The Algorithm
This pathfinder implementation uses a rather clever “stumble home drunk” approach to navigating around obstacles. Given a point of origin and a destination, it will start looking for a path as follows:
Step 1: Can I walk to my target in a straight line, without bumping into a wall?
– If yes: I’m home. Yay!
– If no: go to step 2.
Step 2: Walk to the wall
Step 3: Look at each corner of the wall. Have I been through there before?
– If yes: ignore that corner
– If no: Walk to that corner. Return to step 1.
(Feel free to assume our script stops to mark each corner it visits in whatever way you believe fit)
In pictures:
While I’ve only shown one path being followed for clarity, the algorithm follows both paths – see the blue lines in the first image. Once we have a few candidate paths, we can pick the shortest one to use.
In order to avoid the script pottering around aimlessly forever, we’ll also tell it that it can repeat steps 2 and 3 a limited number of times. The police would pick it up if it trashes around the streets too long.
Now, the above will give us a number of options, from which we can choose the shortest path. These paths, however, will still contain a few unnecessary jumps. For example, you may be able to go directly to a corner from your current location, without having to walk up to the wall first. To optimize that path, we can drop unnecessary points – if point 3 can be reached directly from point 1, then we don’t need point 2. Besides being shorter, this gives us a more realistic path.
In the example above, the path went through two points before finding the target. Since point 3 is directly reachable from point 1, we can drop point 2.
A small tweak
If we follow the walls exactly, we’ll end up walking pretty close to the walls. Suppose my position is described by a point in my centre mass. If that point was following the wall exactly, then half my body would be moving through the wall. Since I’m not The Hulk, that’s not very practical; my preferred way of following a wall is to be some small distance away from it, so my location will be travelling in a line parallel to the wall and my body will avoid strange endomural experiences.
To model this, we just translate the point of impact with the wall back by a few units. Think of it as stopping just short of a wall before you leave your teeth in it. Similarly, instead of pointing directly at a corner, we go to a point which is slightly away from the corner. We get this point by following the normal of the angle.
Known issues
As I said, this script is quite incomplete and buggy as hell. Among other things, it has issues with sharp corners, and can’t handle concave surfaces. It also doesn’t consider thickness, so it will happily plot a path through very narrow gaps. Since I have not tested it exhaustively, there will probably be a few more places where things go horribly wrong.
It probably doesn’t work in Internet Explorer but as far as I’m concerned, that’s a feature, not a bug.