First of all, apologies if this idea has been proposed before. I did use the search function but there have been a lot of long threads about pathfinding over the years and it's hard to find good search terms.
There are currently various issues with pathfinding for more exotic creatures. As far as I'm aware the game maintains some kind of path cache and/or connectivity map for dwarves and other similar creatures, but that data is only valid for creatures which can't fly, can't swim, and can't handle extreme temperatures. If an FB is standing in the middle of a flooded cavern then it won't be aware that it can reach the fortress. Similarly creatures made of fire can get stuck if they stand still for too long, since all the tiles around them heat up to such a temperature that they're no longer considered pathable.
Most of the proposed solutions to this sort of pathfinding issue involve either maintaining additional pathing caches (one for each type of movement, as is already done for wagons), or adding extra data to the existing cache so it can support more movement types. Those solutions have their own advantages and disadvantages, but what I'm proposing is much simpler and should require much less development time while also achieving almost arbitrarily good performance.
If performance wasn't a concern then the easiest solution would just be to run a full A* search from scratch for each creature every time it wants to find a path. In practice that would do horrible things to your FPS, but it would be able to accommodate every conceivable constraint on movement. My proposal is to simply spread the FPS cost out over time. Instead of trying to find a path every tick or every 100 ticks, only do the full A* search once every ingame week or month. Also, instead of blocking the main game loop until the search completes, spread the cost out over multiple ticks.
Under this proposed system creatures would still use the existing dwarf-like pathing cache for 99% of their queries. Dragons would still try to walk into your fortress instead of flying, assuming you left the front gate open, and FBs made of fire could still temporarily get trapped by their own heat. The difference is that after a few days of being stuck they would randomly enter a "thinking" state where they stop moving and run a full CPU-intensive A* search taking into account all of their capabilities. This could even include more exotic options like climbing walls, jumping over gaps, or holding their breath and using their swimming skill to enter via your well. The scheduling of these searches should be random so that the chances of any two creatures doing it simultaneously are low.
It wouldn't cause significant lag because the high computational cost would be spread out over time, but it would completely solve the issue of creatures getting stuck indefinitely. It's even realistic that a creature shouldn't instantly know the best way to sneak into your fortress so the time delay can be thought of as a feature rather than a compromise for performance.
Additionally, most of the creatures on the map would never need to do it. Any creature which isn't actively trying to attack your fort should just follow the normal wandering behaviour, and the existing pathfinding code works perfectly well for your own dwarves (leaving aside modded amphibious/flying races). The main problem currently is with invaders who have non-standard movement capabilities.
I guess the worst case scenario would be an undead explosion in a reanimating biome since undead are amphibious and you could have hundreds of creatures all doing these kind of searches, but even that could be solved. Simply make the frequency of checks inversely proportional to the number of creatures. The game engine only allows, say, 30 full A* searches per month, and those get allocated randomly among the eligible creatures. Then it doesn't matter if you have 1 zombie or 10,000. There could even be a priority system where creatures which have just entered the map are put at the front of the queue while ones which have been trapped for years in your dungeon (many repeated unsuccessful pathing attempts) are very unlikely to be picked. Add a config option so that people can adjust the maximum number of tiles processed per tick and the maximum frequency of A* searches.
Author
Topic: Better pathfinding for flying/amphibious/heatproof invaders (Read 911 times)