I'm curious as to if this has been suggested before. I've seen other level-of-detail and tree-based pathfinding suggested here before, but not in the way I'm suggesting it.
Normally, the A* algorithm that the dwarves use involves checking large numbers of possible paths on the scale of individual tiles. This number of paths increases the more tiles it needs to check (I believe worst case scenario is distance^3?). If this can be reduced, pathfinding will require much less processing power. Due to just how processor-intensive pathfinding is, especially with large numbers of dwarves moving over large distances, a significantly faster pathfinding method would make the game run much better.
Suppose we have a fortress in an area that is 256x256 tiles (1. I know Dwarf Fortress uses larger areas, but it really doesn't matter. 2. I'm disregarding z-levels at the moment). Split it into 16x16 tile sections. The grid we end up with has significantly fewer tiles, and therefore the computer would be required to check far fewer paths. However, this lacks the detail we need. We can't just define a dwarf's movement by which 16x16 tile sections it walks through. Instead of pathing only on a large scale, the game can calculate paths on a low-detail level first, and then as the dwarf is actually going through the path, it calculates high-detail paths (level of individual tiles) one at a time and as they are needed.
Let's add some heuristics into this. Let's add a set of variables to each section that store data regarding pathing between these sections; basically variables that store how easy it is for a dwarf to get from one section to another nearby section via a third one in between. This wouldn't require an enormous number of variables; if there we take the 4 directions that a dwarf can travel through a section (6 with z-levels), then multiply it by the 3 other surrounding sections it can pass into (5 with z levels), then divide it by 2 to get rid of bi-directional cases, we end up with 6 variables to store (15 with z-levels). This isn't a lot of data and is very easily dwarfed by the quantity of data used in storing tile data. Each variable stores how frequently dwarves have been able to path through this section in each direction, and can be used to easily determine whether or not a dwarf can actually path in this direction while performing the high-level pathing. When a dwarf is running a low-level path (individual tiles rather than sections), whether or not it is actually able to get to the next section is taken into account and is used to modify this data. Data can also be stored in regards to whether or not things like doors and bridges have been opened/closed or raised/lowered in the region (perhaps large physics events like cave-ins and floods as well), which might temporarily affect high-level pathing.
Of course, none of this data will exist before you embark, and none will exist for newly dug tunnels. In this case, these sections might be labelled with a specific tag indicating that their effectiveness is unknown, and could even be marked as being freely pathable in every direction. Though this would not be accurate, it would certainly be quickly changed as dwarves attempted to path through the section. Plus, it might make the game seem a little more realistic when the dwarves appear to go check out newly constructed portions of their fortress. It might not even need to be purely based on pathing, and perhaps dwarves could even check out new portions of the fortress during their breaks with a little "Urist felt delight exploring a new area of the fortress" note in their thoughts and preferences screen or something. It certainly doesn't make sense that a dwarf that's not smart enough to get itself to water after being set on fire is somehow capable of enough omniscience to be fully aware of the structure of a portion of their fortress they've never been in.
Any thoughts? Anything I should clarify? I'm not great at explaining things all the time.
tl;dr : Split the region into sections and use heuristics to do efficient large scale pathfinding, then do tile-by-tile pathfinding as the dwarf is going through the new path. Heuristics of pathing between sections is managed by the tile-by-tile pathfinding, as well as other things. Fixing problems with newly discovered/constructed parts of the fortress might make it possible for dwarves to be made to be interested in exploring new parts of the fortress. This could also make the game run significantly faster.
Author
Topic: A Better Method for Pathfinding (Read 2579 times)