So this post is about how one thing leads to another. After I got my player character into the game and popped in a sword which he could pick up and throw (which is all controlled by scripting and whatnot), I thought "well, I should make him throw it at someone so I can test the collision code is working".
Which meant I had to make an enemy.
But that got me thinking about how my enemies are going to get around the world. While many of them will have simplistic behaviours, it'd still be nice if there was a really fast, non-iterative way of detecting the ends of platforms so they didn't walk off of them if I didn't want them to. That's incredibly easily done if your game doesn't have slopes, but mine does so it requires a little more computation than "is there a tile to the right of this tile?", as that would result in non-ends of platforms being flagged as ends of platforms.
So instead of doing these calculations in real time, I do it when the room is entered (or altered) and store the information in a layer of data, resulting in nice clean information which looks like this:
(Navmap flags are stored in "surface" tiles, which are directly above the topmost solid tile. That's why they appear to be floating)
And for comparison, without the guff.
But while I was doing that, I thought I may as well find locations of jumps up to platforms, jumps from platform to platform, slopes which some enemies might not be able to handle, climbable surfaces, etc, and flag those in the same manner. Which meant the data became this:
(Blue lines indicate the links between jump points)
And then I thought, well... I may as well flag walls and ceiling, too, so creatures like spiders know where they can jump to in order to get closer to the player.
Once that was done, I thought - hmm... it'd be nice if some enemies were capable of pathing towards the player. Now, for a while I did go down the route of trying to make enemies able to path via platforms, climbable areas and walls/ceiling but that soon gave me a massive headache and instead I decided to limit it to flying enemies, because I don't have to worry about terrain with them. Plus, I think that fairly simplistic behaviours for the platform-bound enemies should make them tricky enough to deal with as it is.
I've decided to go with a look-up table based pathfinding solution, rather than A*, as it makes the pathfinding effectively FREE to use, which'll be important if I have 30 wasps trying to path towards different moving targets every frame. To make the look-up table I fill all the free space in the room with rectangular areas, like so:
Yes, the patterns *are* pretty. Then I see which of these areas are adjacent to which other areas and draw up lists of connections. Finally I use that connection data to pre-calculate the shortest route to every cell in the map from every other cell, via a simple recursive function. And that gives me my look-up table.
To show it in action, the following animated gif shows the order in which an entity anywhere on the map would path through the areas in order to get to the player if they were at the bottom-left of the map. NB. the dots don't show their exact path, it just shows which area they'd aim for from any given area, so it's only a macro-level solution.
(Oh, and I still need to tweak the generation routine to deal correctly with one-way platforms, but that's a minor thing.)
And that's how digressions work.
Now, about that enemy I wanted to hit with a sword...