vittro wrote:
Sorry if this was already asked, but how does pathfinding work in DROD? Paths change constantly with doors and broken walls but it doesn't take any noticable amount of time even for a room full of brained roaches to calculate new paths.
Probably some breadth-first algorithm like this:
* Take a room-sized array of integers
* Initialize a list of tiles with the index/coordinates/whatever of the square with Beethro
Then iterate over that list twice in a loop:
* for each square that doesn't have a value yet, set it to the lowest neighbouring value plus one (or 0 if it's the initial square) in the array
* for each square that got set add the neighbouring squares that don't have a value yet to the list for the next iteration
Lather, rinse, repeat until you're out of tiles.
When moving brained enemies, choose the first surrounding square with the lowest value from the array; if that's blocked choose the second highest one and so on. If there's no numbered tile in the surrounding area do an unbrained move.
Of course, this doesn't take arrows and other stuff into account, but that's "
just"
extra checks to rule out impossible moves when assigning the numbers.
np: The Notwist - Gravity (The Devil, You + Me)
____________________________
"
I'm not anti-anything, I'm anti-everything, it fits better."
- Sole
R.I.P. Robert Feldhoff (1962-2009)