Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[MaDeR Levap]

Wohoo! 

I've addressed what should be the main cause of these problems (see comments in 0000070), but I doubt I've handled every single pathing issue that's been reported. It's difficult to say what I should do with those reports now.

I would mark as resolved ALL of them - and when releasing 0.31.03, specifically ask people to try to find any other issues with pathfinding and report them on Mantis - preferably in reproductible way.

It appears that it is assigning a different connected component to every liquid floor/flow tile...

My brain turned off at this moment. WTH is "connected component"? I feel so stupid now. As I understanded whole text, something borked in advanced optimisation to pathfinding.

[sweitx]

I'm going to hazard a guess that the pathfinding treat a large area of dynamic path area (areas that get flooded and cleared relatively frequenctly) as one "connected component" and the bug arose from when two areas that are supposed to be treated as one are treated as multiple sub-area, screwing up pathfinding algorithms that assume that area is one big area.
Even more hazard guess, maybe it's something like the following.

Code: [Select]

00100
11111
01000
01022
01020
0 are unpathable, non-zero are pathable.
After flooding (or a path change).

Code: [Select]

00100
00000
03000
03022
03020
Lower path is updated to indicate a different connected area.
After path clears.

Code: [Select]

00100
44444
03000
03022
03020
The code forgot to "reconnect" the pathing areas.  So in preliminary path finding that's trying to figure out can a dwarf go from North to South, it sees there's no common connected area shared by 2 edges and assume no path from North to South in said region.

Again, this is a wild guess on what may have happened.
*Fun in reverse engineering

[Footkerchief]

That's roughly correct, although it's nothing specific to "areas that get flooded and cleared relatively frequenctly."  Each "connected component" is a group of tiles such that any two tiles in the group can be pathed between.  The game uses this to prevent pathfinding attempts that are guaranteed to fail.  Tiles only belong to one group, so the actual implementation is that each tile is assigned a "component number," a dwarf standing in a tile with component number 7 can only path to other tiles in 7, and the component numbering gets updated when the map changes.

edit: also why is this in Suggestions?

[MaDeR Levap]

why is this in Suggestions?

Because of this suggestion:

I would mark as resolved ALL of them - and when releasing 0.31.03, specifically ask people to try to find any other issues with pathfinding and report them on Mantis - preferably in reproductible way.

[sweitx]

That's roughly correct, although it's nothing specific to "areas that get flooded and cleared relatively frequenctly."  Each "connected component" is a group of tiles such that any two tiles in the group can be pathed between.  The game uses this to prevent pathfinding attempts that are guaranteed to fail.  Tiles only belong to one group, so the actual implementation is that each tile is assigned a "component number," a dwarf standing in a tile with component number 7 can only path to other tiles in 7, and the component numbering gets updated when the map changes.

edit: also why is this in Suggestions?

Ah, so technically it's not applied to a small area, but to the entire map.

Well, the initial OP's post is a suggestion to Toady as to how to handle potentially unhandled bugs.  Namely close/resolve them and ask us to repost it if it shows up in new version again.

I'm just trying to ask the second part.
Ooh, I also just found how pathfinding was implemented (in a way).
http://www.gamasutra.com/view/feature/3549/interview_the_making_of_dwarf_.php?page=8
Cool!