Go home A*, you're drunk.





The figure on the right is what A* looks like when it's working properly.
The figure on the left is what A* looks like when it's been bludgeoned over the head with a dead racoon whilst intoxicated.

As shown by the different colours in the level editor shot (right), parts of tiles are marked as either:

  • unwalkable (red)
  • walkable (yellow)
  • preferred (green)

This means that while a pedestrian CAN walk across a road, they shouldn't always use roads to walk on when there's a (theoretically) safer place to do so: the pavement/sidewalk all y'all.
In order to get this right I simply make unwalkable surfaces an obstacle as usual, but allocate a heigher weighting-scale to the walkable areas than the weight-scale of a preferred tile area.
When I say "weight-scale", I mean that the weight a tile is normally assigned (say 10 for horizontal/vertical movement, 14 for diagonal movement) is multiplied by the scale assigned to the tile area.
open tile.H = distance from end * movement weight * tile area scale

Of course, if you mess that up a little bit ("obstacles? oh, you mean *10000 scale factor right? overflows? no, not heard of them, why?"), you get the image on the left. I don't claim to know why it ended up doing what it was doing, but it found its way eventually, and might come in handy for drunk pedestrians.
Not that they'd ever make it that far without being hit by a car, muh har har!

Oh, the square texture on the level shows the granularity of the path-finding.
It also turns out that it makes it easier to get a sense of perspective with it on, so I may keep it.

Navigation Meshes.



Recast is a lovely looking tool. It takes 3D geometry and calculates walkable areas depending on a large, large variety of factors.
Recast does not have awesome documentation.
Recast only comes with one demo code sample, an incredibly scary looking project with many complicated GUI things that -as someone just looking for how it works- I don't care about.
Where is my "hello world, walk over me" example? Eeee!

So instead of, you know, having patience and doing things "the right way" and figuring it all out, I simply implemented OBJ export in my level editor.
10 minutes later and I had this lovely test up and running using a build of the aforementioned scary-looking-project:



It all looked peachier than James and his giant produce, until I started looking closer.
No matter what settings I used, I could not get the mesh to produce a walkway between two buildings that are far enough apart for a tiny block to walk through.



Not only that though, I don't know how I would differentiate between "walkable" and "preferred" areas. It just generates one large polygon for the pavements and street, which is not really what I want.

That all said, this is by no means a fault of Recast. This is all just me being stupid.
I went back to the scary GUI project and found a single file that you can basically see how everything works, and it's not toooo bad.
But for right now, I'm just too keen to prototype to mess around with this too much.

permalink print article