Update:This week I've been implementing A*-pathfinding for the AI -- this will allow enemies or NPCs to find a short path through the world to moonman or some other target.
Starting simple, here is a case where the target location is the top of those tiles, and the knight knows that he has to take a series of jumps on the left hand side. The planner knows how to move and jump and searches the entire nearby space for the quickest route to the top.
Here's a more complex case. The squares show the potential tiles the knight will move through, and each one is checked for collision. If a tile is blocked then the path-finder will find another way around (if there is one).
One interesting problem I had was to predict which tiles a human would move through as they jumped. To solve this I assumed the jump path was perfectly parabolic, which isn't exactly correct, but a good enough estimate for now. The problem then becomes: given start and end locations and jump height, what parabola goes through those points?
A page or two of algebra, and many mistakes later, I ended up with the equation. You can actually play with the equation
over here on Desmos. For that equation I assumed the mob was at the origin and wanted to jump to point q, with a height h.
You can then trace out the parabola in tile-space (adding the human height along the way), and if it collides with a block then you know the jump won't be successful. In terms of A*-search, this path (between p and q via a jump) would be invalid.
You can see the behaviour of the path-finder below. As I move the target around the algorithm finds a new shortest path.
It's important to note that the path is an ideal path, and assumes a perfect ability to jump between platforms, etc. Following the path is another thing altogether (especially in a physics simulation) and the success will depend on environmental factors, the physics state of the mob, and some how precise the AI-control can time things. But for the most part a mob will be able to follow a path fairly well .. and if it fails at any point then it'll simply re-plan and try again.
Here's a video of a knight following a path. He's pretty good at jumping between all those platforms, although halfway through he fails a jump and has to re-plan the route.
And here's a gif or a knight following Moonman (crunched to a few colours because of it's size):
The implementation is super simple at the moment and there are a lot of things that the pathfinding doesn't consider yet, like doors, sloped terrain, bridges, platforms, ladders, etc. These will all be brought into the system one by one until we have some semi-intelligent mobs that can't be tricked so easily.
The path-finding and path-following components are just one piece of the AI system, but I think it'll be the trickiest to implement. One necessary optimisation I need to add, for instance, is to cache the graph for the A* system. Being tile-based, Moonman has part of a graph already (just use the tiles and their neighbours), however it doesn't account for jumping to and falling from ledges, and I'll need to find and cache that info whenever the world geometry changes.
It's interesting also to consider how A*-search would work if entities are allowed to modify the world/graph. For instance, if an enemy in Moonman could mine through a wall or build a bridge, how would that effect the pathfinding system? I assume it's a very difficult problem to do well, although some basic logic for hacking through a wall could push the game in a very interesting direction! For now though, it's in the todo-later basket.
Another interesting thing I've been thinking of is path-finding or following going wrong. Consider a "dumb' enemy. Would he make a bad plan? Would he make bad assumptions about the distance he can jump? Would he cancel a plan halfway through? When coding the system I stumbled across a bug that revealed a strange, but entertaining, behaviour. Here the knight believes the shortest path to the spaceman is to bunnyhop the entire way. See you next time!
Community
