Dev Log: Pathfinding Fun
Like a cat chasing a laser pointer, I have some basic enemies chasing paths through the skies.
Right now I'm using A* and although I don't really know what is going on that much, I have a system that enemies can use to find paths to their destinations. Normally I wouldn't bother with any sort of path finding, but for this game I want enemies to have to intelligently navigate through obstacles that the player is deploying, so my usual "make up a path finding function that doesn't actually path find but sometimes works out" function wont cut it.
What I have currently is a pretty straight forward set up:
- One PathFinder instance in my Scene. It extends Entity so that it can be updated by the scene automatically.
- Enemies request a path from PathFinder and also register a callback Action with the request.
- The PathFinder instance adds the request to the queue.
- Every update the PathFinder will take the top item of the queue and start the path finding process.
- The actual A* algorithm and calculations are run on a BackgroundThread so that the game can continue while this is going on.
- When the path is done calculating the callback is fired, and the enemy now knows about its path.
- It chases down the nodes that were added to its path.
I made a quick change to the A* algorithm as well under the sage advice of Chevy Ray: I'm using a maximum movement value that will stop the algorithm if the move costs become too high. The result is that the algorithm will return a partial path to the final target instead of the entire path (which could take a long time to calculate in a set of nodes with a lot of open spaces.) So with this in mind the rest of my logic looks like this:
- When the enemy reaches the last node, it checks to see if its close to its intended target.
- If not it requests a new path to its target.
- If it is then it will enter its attack behavior, whatever that is.
So far this seems to be working out pretty well. I have a lot of work to do with how enemies will end up treating their path nodes in regards to their actual movement. Right now they just try to move toward each node, but with a lot of nodes together they end up having some trouble, like that wiggling in the animation above. Something like an averaged out path between a lot of nodes might work better... hmm!
4 Comments
