Spent all week working on pathfinding stuff. This is, realistically, probably something I shouldn’t be spending this much time on. I’m getting sidetracked. Still, getting sidetracked like this on difficult but interesting problems is good for me, at least in small portions. It helps me keep on learning instead of settle into the same grooves, makes me in general a better artist even if, in specific, a bit worse at producing this specific piece of art. So I don’t begrudge myself the time.
As I understand this problem now, it’s basically split into three parts: First, mapping the terrain. Though the terrain is already in a format easily read and perfectly suitable for simple interactions, understanding the layout of a whole bunch of undifferentiated tiles is something that’s difficult to teach a computer to do. This is mostly what I’ve been spending the last week on, putting together the best map of the terrain I can, as detailed as necessary without any false or extraneous information. This is what it looks like now for a simple level:
The lines show where each node is looking for possible connections for where to move next. Note that the nodes underneath the platform don’t try to connect directly to it, since it would be impossible to reach there with the solid platform in the way. Unfortunately, for a more complex level this map takes about a second to generate, which is too long to do in real-time every time a level is loaded. Thus, I’m probably going to have to make these nav maps get saved alongside the map tile data, and just get generated whenever the level is modified or loaded.
So that’s the first part. The second part is finding a path through that map, getting from the start tile to the goal tile. This is what I’m working on now. To start with it’s simple enough, just chain through the connected nodes and find the closest to the start and the goal, and continue until you either reach the goal or fail to do so. That’s the part I have done. The tricky part is that in between each connection I need to make sure that the path isn’t blocked, which means projecting the character movement as they walk or jump from one block to the next, make sure their jump is powerful enough to bridge any gaps, make sure that when attempting to jump across they won’t be blocked by the terrain. That parts a bit complex, and is what I’ll be tackling tomorrow.
The third part I haven’t tackled at all yet, and that’s converting the path through the level into a set of instructions for the entity to move through, and making sure it executes them perfectly enough that it doesn’t, say, miss a jump and fall into a completely different part of the level and generally muck things up. I don’t think that part will be too hard, but I’ve certainly been surprised by that sort of thing before.
I’m hoping that within the next few days I can have a simple case of this running, a basic enemy that just follows the character around using this pathfinding algorithm, before I built it out into something a bit more nuanced. Either way, once I have this, if I do it right it’s something I should be able to use for years to come, for basically any game built on this same kind of 2d platformer movement system. Implementing enemies in general will become much easier in the future, since I can just pass all level navigation tasks down to this algorithm.