Kandria

I'm almost done

... with the fixes. Before I can release a new version though, there's a few more things that need to be addressed.

The most important thing that's still broken is the movement AI. I've touched on this very briefly before, but I'll go a bit more in-depth this time, so this update is going to be a fair amount more technical than what I usually write. I hope you don't mind!

Movement AI in this case refers to the problem of having an entity automatically traverse a 2D level as if it were an actual player, meaning that the AI should be constrained to the same rules as the player: can walk left or right, jump up to a certain height, might be able to crawl or climb.

This problem is non-trivial, as the primitive approach of simply moving the entity in the direction of its goal will not always lead to a path that can actually reach the goal under these constraints. Similarly 'greedy' strategies will fail for the same reasons. To illustrate this a bit better, here's a sample level:

https://courier.tymoon.eu/api/courier/file/view?id=k7tWwLrfVsZxnmhssj60zw%3D%3D

The green point is your starting location, and the red points are your goals. Your character can jump in a range of four blocks upwards and six blocks sideways. To simplify the problem here we'll disregard crawling and climbing. Try to act out an algorithm on how to reach one of the goals. The goals have been made such that each goal should be a bit more difficult than the last. Ideally you'll find an algorithm that can reach every goal.

Once you've convinced yourself that the problem is a bit tricky, feel free to read on.


The algorithm employed in Leaf proceeds in three steps, one of which is done ahead of time, when the level is created. We'll start with that. This first step will basically crunch the level geometry into something that we can apply standard procedures to to solve. What we do is we move over the level tiles line by line and first search out all blocks that are horizontally adjacent and don't have anything above them. For each of those, we know that an entity can walk left or right on them, so we create a virtual line there.

After that, we look at the edges of these 'walk lines'. If the edge is not connected to another walk line, we know that we are at a corner here, so we scan downwards from there until we find another solid block. We then create a 'fall line' between the edge and the bottom block.

Finally for each block that has a line connected to it we cast several jump arcs and see whether the jump arc would hit anything that isn't already reachable from our current position. When we do, we create a 'jump line' with the correct jump arc properties. Once we've done all that we'll end up with something similar to this:

https://courier.tymoon.eu/api/courier/file/view?id=8zputri2DANOEZy4RrlCFw%3D%3D

The blue edges are 'walk lines', the cyan edges are 'fall lines', and the purple edges are 'jump lines'. From here you should be able to see how to add crawling and climbing to this relatively easily.

This new navigation mesh is a much simplified description of all the possible legal movements in the level. When we actually need to search for a path, we can now apply a standard minimal distance graph search algorithm like A*. This algorithm will give us a plan of lines that we need to follow in order to reach our destination.

For the final step, we just need to execute this plan in real time by moving the entity as described by the individual line segments. We can do this with a very primitive system that simply moves the entity until it is exactly on the edge of a line, then execute that line's intended action (move more left/right or jump).

The biggest hassle by far here is getting this navigation mesh built in the first place. Especially computing and testing the jump arcs correctly can be tricky, as we need to ensure the character doesn't bonk their head on something or would have to phase through platforms somehow to reach the jump destination.

This system has been in Kandria for almost a year now, but it is implemented in a severely flawed way that's both inefficient and suboptimal in many cases. And so, the task left for me is to fix this up and make it faster and correcter. I'm not sure exactly how to fix it yet, so I'm afraid I can't really say much more about the particulars in Kandria. If you want, you can take a look at the code, though.

There's some stuff that I'm not quite sure how to deal with yet, though. For instance, if the level geometry changes due to a dynamic event such as a block falling or an elevator moving, there needs to be a way to encode this change, too, or otherwise enemies won't be able to react properly. Recomputing the navmesh every time would be far too expensive, so there has to be some incremental way of doing this. Anyway, food for thought.

Once I'm a bit happier with the movement AI I can move on (ha ha) to rewriting the wolf's AI to be more interesting. Once that's done, and the combat is a bit tuned, I'll have another demo ready for you. There's other things that desperately need fixing too, but they're less interesting than this. I'm not sure when I'll have it all done, so I hope you'll be patient with me.

What are some of the strategies you came up with for the movement AI? I'd love to hear it, it's a fun little challenge!