I already had an A* implementation, so I imported it into the project. Great post, see you next time!
Okay, so. I will need AIs in the game, and they will need path-finding. I cannot really do with straight path to player logic if I am to make any room layouts that have cool features. The AIs would just get stuck on corners, each other, props, etc. Out of all the algorithms, A* seems to be the best choice. And, as I said, I already have it written from years ago, it’s well-tested, optimized and pretty easy to integrate. There is a queue system, retry queues, search limits, callbacks, and all sorts of stuff that a game’s agents would need. So that’s what I’m using. There are lots of internal details about how it works, but that’s not really something I am working on right now for the game, so I won’t cover it.
I don’t have any AI written yet, so I tested A* by searching a path from the player to the mouse location each frame (technically, whenever previous search is done), and that works great:
And here’s some (very pretty) in-scene debug:
My world is already a grid. And, while entities can move freely within cells, I can round the location coordinates to integers and use that for my searches. I already have mouse-to-tile conversion. And I already have a way to look up tiles by their coordinates and see if they are walkable. So the whole process was very painless.
I’ll add path-finding capabilities to mobs, but first I have to separate player and enemy mobs, that is, create separate classes, definitions, etc. This way I am not mixing my AI code and whatever enemies do with my player stuff. This broke all my mob assets and their references, so I’m fixing those. I just wish Unity let me fix assets by pointing to the “new” script instead of doing this:
Long story short, I now have player- and enemy- specific implementations for logic and definitions:
The player (mob) doesn’t need to path-find; they are directly controlled by the player. So I will implement path-finding for enemies only. To avoid writing any AI framework just now, I will make them all constantly search for a path to the player and try to follow to the next closest coordinate on their found path. This does involve writing a helper class that knows how to search for, receive and then follow a path, so that the actual mob class is nice and clean. Anyway, this is the result (sped up):
I don’t actually check for anything other than tiles for path-finding. For example, my enemies are happy to get “stuck” on each other and some chests:
So I also need to add other items that can block paths, like other mobs or props. This is where it gets interesting. Firstly, I have to ignore the path seeker itself when checking valid coordinates, and I need to ignore the target (i.e. player) in this case too. My A* didn’t actually do this, so I had to add an arbitrary “extra info about pathing restrictions” that the path seekers can set to be a list of ignored entities (here, itself and player). In fact, this will get more complicated once I have stuff like flying mobs or ghosts or whatever. Or, for example, ignoring other moving entities with an assumption that they might get out of the way.
But yes, the enemies are less dumb now, as far as “blind” path-finding is concerned:
I mean, they are still quite dumb:
But that’s for AI to figure out later.
There is another feature my pathfinder doesn’t do and that is “shorten” the paths between sections of clear tiles. That is, it doesn’t go directly between two points when there are no obstacles in between, but rather always visits every point on the path. This is really obvious when things move in diagonals (which enemies will do a lot on room with clear sight):
In short, the algorithm to solve this is to go through each coordinate and try to look ahead to see if any following coordinates “can be skipped”. Now, “can be skipped” is a sub-algorithm which determines if the path between two coordinates is free. In other words, “fat” line of sight. The simplest degenerate case is if the coordinates are on a straight line in one of the eight cardinal directions; these can be skipped immediately without expensive tile checking logic:
For all other cases, however, I need custom logic that will check every tile and its neighbouring tiles for potential obstacles. In short, I can fail a path “shortening” if any of three closest neighbouring tiles have an obstruction. Here the path correctly goes through a door by not shorting any “corners” (green bubbles are tiles that were checked when shortening):
One final note on shortening is that the algorithm doesn’t iterate or backtrack. That is, it doesn’t attempt to find the shortest shortened path, only shortens the next segment greedily. For example:
vs 
And I cannot simply “reverse” it, because then the same problem happens on the “other end” of the path. In short, the algorithm would have to be recursive and keep track of the shortened path’s length to find the shortest path. But I am not writing a shortest shorter path algorithm. It’s good enough for my purposes. Besides, the player isn’t the one path-finding, enemies will not just go straight to the player, and enemies that do will be re-pathing all the time anyway.
Now let’s talk optimization for looking up stuff by coordinates/on tiles. I don’t have to profile this to know it will seriously suck when I add more entities. A* will be checking hundreds of tiles per frame for obstructions. And each check means seeing if any entity is in that coordinate and, worse yet, applying conditional rules for different entities. If I were to just naively iterate all entities (like I do now), it would quickly add up. What I need is a better way to store and cache entities and their position.
The way I am doing this is keeping 2 cached collections: one where I can look up a list of entities in any given location and one where I can look up the last cached location of any given entity. In other words, I can very quickly list all the entities at a given location. And I can very quickly modify this list when entity coordinates change. A sample snapshot of my main list looks like this:
Memory is generally not an issue for a game like this. I can waste lost of memory without any performance impact. But CPU time is precious and every microsecond counts. So I rather have many redundant specialized lists than spend time iterating an inefficient one.
Anyway, the path-finding looks good (enough). It already does more than I likely need and more than the vast majority of games like this. I doubt I will revisit it much more than a few tweaks here and there. So unless something major doesn’t work, that’s it for path-finding. Time to focus on some other stuff (hopefully, gameplay).