Determinance screenshot

Pathfinding

Pathfinding

I’m rather pleased with myself this morning.

The pathfinding in FS has always been atrocious – experienced players pretty much have to use shift all the time to bypass it.  It’s a pain in the ass.  Here’s a great example of it going wrong:

The reason pathfinding sucks so much is that my algorithm for it is terrible – it splits the levels up into a grid, each square about the size of a unit.  It then checks each square for obstacles.  It’s a really innaccurate representation of the level.

This weekend I was reading up on advanced pathfinding stuff, and considering using some kind of Navmesh with movement polygons.  Then I was hit by a flash of inspiration – the only thing that matters in FS is corners.  If you ever want to make a path in FS, you only ever use the corners to get there – the only points I need in my nav-graph are the corners!  Here’s my code for identifying the corners in action:

As you’ll know if you’ve written A* before, the algorithm needs to know how all the navigation nodes are connected.  Here’s the same level with that info:

The nav-graph for this level is pretty simple – here’s a more normal one:

Yikes.  Lucky computers are fast at this sort of thing!  Here’s the same level that the initial algorithm got wrong, but with the new algo I knocked up this morning:

Perfect.  You guys can play around with this pathfinding right now – the download is here.

Lots more UI improvements to come.

This entry was posted on Monday, August 9th, 2010 at 1:06 pm and is filed under News. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

2 Responses to “Pathfinding”

  1. Alex Vostrov:

    § August 11th, 2010 at 4:31 am

    Congratulations on your re-discovery of POV pathfinding! =)

    I went through the same steps in my RTS. Squares -> Corners. Of course, my map was grid based at one point.

    Still, the thought of ray-casting to each nav-point scares me a little even though I know it works. Just shows you that computers are faster than you imagine.

  2. Basic Frozen Synapse Level Editing : Henry Cipolla:

    § November 2nd, 2010 at 6:41 am

    [...] map I have seen so far is made up only of corners. After reading Mode 7′s blog post on path finding I would highly recommend avoiding anything other than corners in your maps because as you can tell [...]