Posted on 11th Aug 2010 at 10:31 by Mode 7 with 10 comments
I'm pleased with myself today.
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, below.
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...