Print

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

[Draco18s]

quote:Originally posted by Fedor:
<STRONG>That's not a good reason.  If a dwarf is trapped, the game should pause, center on the dwarf, and alert the player.</STRONG>

See the thread where traffic designations were requested and Toady's reponses.

[Eagle of Fire]

I can't find the thread, but I'm sure I've read something Toady wrote in a thread to make this assumption. However, if it doesn't recalculate with high traffic designation, how would you explain the lag in "If you make the last numbers too large, pathfinding might lag"?

I was thinking about it since a little while myself, and it does make sense that the path_cost add up when the game try to calculate a viable route.

Best thing would be that Toady come here and explain how it works in person. There would be no speculation then.  

[Fedor]

quote:Originally posted by Eagle of Fire:
<STRONG>I can't find the thread, but I'm sure I've read something Toady wrote in a thread to make this assumption. However, if it doesn't recalculate with high traffic designation, how would you explain the lag in "If you make the last numbers too large, pathfinding might lag"?</STRONG>

Again, I could easily be talking out of my ass here, but it's fun to play "guess the algorithm".  And even more fun to find out just how wrongly speculation has led one!  

So I will propose that this can be explained by noting that, the higher the total path cost from A to B compared to the distance as the bird flies, the more alternatives the code must consider before it knows that that path really is (despite appearances) the best route.

[Tahin]

quote:Originally posted by Draco18s:
<STRONG>

The reason it isn't is due to the "if a dwarf can't walk there at all, and that area is the only path for him to travel he'd never get out."  Hence why restricted: travel here as little as possible.

The pathing values are how many times it searches for a better path, and a forbid is just a restricted with a value of about 500 (search every single path ever, pick best).  And you'd still get dwarves walking through it.  And lag.</STRONG>

It could let them access "Forbidden" tile if they were already standing on a forbidden tile. I can't imagine that would be too terribly hard. I'd also like the ability to toggle these "Forbidden" tiles on and off through the "o"ptions menu, to create custom "Stay Inside"-type "safe zones"

[Draco18s]

quote:Originally posted by Tahin:
<STRONG>

It could let them access "Forbidden" tile if they were already standing on a forbidden tile. I can't imagine that would be too terribly hard. I'd also like the ability to toggle these "Forbidden" tiles on and off through the "o"ptions menu, to create custom "Stay Inside"-type "safe zones"</STRONG>

I see...I see...

code:

######
....D#
######
traffic:
######
FFFFN#
######

He can't get out, and he could have gotten there by falling.  Which is more towards the point I was making.

[Squeegy]

Why would a dragon care about your zones?

[Asehujiko]

What does a dragon have to do with pathing bugs in the first place?

[Idles]

Toady posted a while back that he's using an algorithm roughly similar to the A* algorithm.  If anyone wants more details on how that works, and why path costs do what they do, try reading this wikipedia page.  The "path cost" numbers factor into the pathfinding heuristic.  Toady also mentioned that, rather than crawling along whenever a dwarf encounters some other creature in its path, the dwarf will try to find a path around the other creature, and crawl only if it can't.  This part of the code *possibly* results/resulted in some problems, such as framerate slowdowns when many dwarves attempt to move through a narrow corridor (the dwarves are all using up computing cycles asking the pathfinder if there's a better way to go around everyone else).  This could also potentially result in this currently described problem, where dwarves will (my assumption, since the OP didn't answer my question) sooner walk over restricted-cost tiles than crawl under another dwarf.

I hope this explains everything.  And anyone who knows more (0x517A5D ?), feel free to correct me if I'm wrong.

[Quintin Stone]

quote:Originally posted by Eagle of Fire:
<STRONG>I can't find the thread, but I'm sure I've read something Toady wrote in a thread to make this assumption. However, if it doesn't recalculate with high traffic designation, how would you explain the lag in "If you make the last numbers too large, pathfinding might lag"?</STRONG>

When you see a graphical representation of a pathfinding algorithm in progress, you get an idea of the kinds of things that can hurt or hinder it.  Sparse use of really high path costs probably won't hurt.  But if the only path is through a really high path cost area, the algorithm will spend a whole lot of memory and CPU cycles to trying rapidly expanding and multiplying paths that can consume nearly the whole map.

[Draco18s]

quote:Originally posted by Squeegy:
<STRONG>Why would a dragon care about your zones?</STRONG>

quote:Originally posted by Asehujiko:
<STRONG>What does a dragon have to do with pathing bugs in the first place?</STRONG>

Jesus Christ on a crutch!  IT'S A DWARF!

[Zurai]

quote:Originally posted by Idles:
<STRONG>I hope this explains everything.  And anyone who knows more (0x517A5D ?), feel free to correct me if I'm wrong.</STRONG>

I've used A* before. It works pretty much as you describe it. From what I recall of discussion in older versions, the pathfinding that Toady uses goes in sections rather than setting the entire path in stone from the start. It'll run an A* to be sure that a path exists, but once it's determined that much it runs shorter pathfinding loops repeatedly along the path. That's how dwarves can step aside without having to run a completely new path search. Presumably, the "step aside to let someone else pass" code either ignores heuristics or assigns a value to the currently occupied square that is greater than 25.

[TheSilverHammer]

I have had an issue with this too.  Over and over I find dwarvs building a wall from the wrong side, or removing a floor from the wrong side.  If I designate an area as restricted, even if I crank the cost up to 100, it never prevents them from standing on the wrong side of the wall when finishing it.

I also have a food stockpile I do not want dwaves to use, so I made the entire thing restricted, including the door to the room the pile is in.   They totally ignore it and go in and eat all the time.

[Eagle of Fire]

You didn't read much of what been discussed in this thread, isn't?

Restricted only nudge dwarves to better area. It is not a forbidden command, and won't stop them from entering the tile if they have no choice or have a good reason to.