Gaming Your Way

May contain nuts.

Node based pathfinding

So the refactoring has turned more into re-coding with regards the baddies.

Due to the collisions being a lot ( Lot ) more robust than in the previous two games, it's highlighted a large issue with the baddie AI. Basically it was cheating badly. Now it can no longer cheat the baddies are too dumb. Joy. So lets make those bad boys a bit smarter, with some pathfinding.

That's a section from level 2 ( It's pretty ugly designing levels ). Those brown circles are our nodes which we're going to use to path find. Luckily this is about as complex a layout as we're going to have in the game, so I won't be killing myself putting a million nodes down every where.

What we do at present is a line of sight check from the baddie to the player. If there is one then he'll head off towards the player as before. Every couple of frames I check to see if that line of sight is still present. If not, then the baddie has to find a different way to the player, and the path finding kicks in ( Before they'd just pick a random direction and walk off towards it ).

It works using a form of Dijkstra's algorithm. When the level is created all the nodes are stored away. Each node is then told about all the other ones and then calculates the distance from itself to the others. The idea is to pre-calculate everything as much as possible before hand, so the actual pathfinding runs as quickly as possible.

Every frame the game works out which node is closest to the player, and sorts an array based on that ( So array[0] is the closest ). I'm slightly concerned about the impact that will have on performance, but it's a pre-sorted list which doesn't change that much ( Relative to the game running at 35 fps ) and it's not showing up as taking that much time, so I can live with it ( Plus I imagine I could skip the check every 5 frames or so without it causing any harm ).

When the baddie needs to find a path it calculates which node it's closest to. I don't check all the possible nodes on a level as that's a waste, if it's more than 10 nodes to get the player then the baddie is more than likely well off screen and we can just pause it. Now we know the nearest node, and we know that the destination node is always closest to the player ( array[0] ) we just run a simple check to find out a path from the baddies node to the players based on the pre-stored distances. This is stored in a Vector of x,y coords for each node, and sent back to the baddie. It then walks from node to node until he gets to the end and then he'll start again.

As you can see there, node 0 is the one which was nearest to the baddie, he's already got there, and he's moving down the path.

Now it's not fool proof, he won't always find the shortest path, but to be honest I'm not worried. The baddies aren't meant to be super smart, and compared to how they were before they've had a hell of an IQ boost. In a perfect world when there are a couple of baddies following slightly different paths it'll feel like they're flanking you.

There's still more stuff to add to the baddie code, it's been a major upheaval, but hopefully it'll be finished in the next couple of days and then I can retro fit all these amends into all the other baddie types.

And that's how we do things at the start of Feb.

Squize.

Comments (1) -

  • Zedacus

    2/12/2013 5:17:58 AM |

    I've been checking this every single day and decided not to say anything until now. Any way, keep up the good work. I'de love to test O:2 when it's ready for testing. Also, have a fantastic day and a good valentines day (When it comes on Thursday).

Comments are closed