Print

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

[Earthquake Damage]

well, TOADY PLZ LET US CHOOSE ANY VALUE, INCLUDING NEGAITVES!!!!!

Cue infinite loop as the pathfinder keeps trying to shuffle between two tiles to continually shorten the path.

[TolyK]

yeah... well just exclude already-done tiles an it should work

[Trouserman]

Mein gott!  I just realized something:  if you set the high traffic cost to zero, wouldn't that make dwarves always use the high traffic tiles when available, no matter how silly the path?  I wonder if this could be used for dastardly purposes.  Do things other than dwarves respect traffic designations?  We could potentially force siegers to waste time zigging and zagging on their way to the fort.

The risk:  Crashing the game because pathfinding keeps trying to follow a high-traffic loop because the next tile in the loop always costs less than a step in the right direction.

This is not a good idea.  A cost of 0 would mean that the pathfinding algorithm will not be able to guarantee finding you a shortest path, and would be horribly inefficient.  Any path through 0 cost tiles will have equal "length" as far as the algorithm is concerned.  This may or may not cause loops, depending on implementation details, but would almost certainly lead to paths that go well out of their way, if it does not.  For instance (in a 3-wide high traffic hallway):

Code: [Select]

->------>------>
|..............|
<-----A..B<-----

I don't think anyone but your dwarves respect traffic designations, so you could not use it on sieges as you suggest, either.

results: DAMN IT DOESN'T WORK! I can't set it below 1 

It's just as well.  You wouldn't be happy with the results.

[rephikul]

Speak of pathing, I've found my dwarves to be unable to path over long chains of ramps. Any idea why?

[Urist Da Vinci]

Mein gott!  I just realized something:  if you set the high traffic cost to zero, wouldn't that make dwarves always use the high traffic tiles when available, no matter how silly the path?  I wonder if this could be used for dastardly purposes.  Do things other than dwarves respect traffic designations?  We could potentially force siegers to waste time zigging and zagging on their way to the fort.

The risk:  Crashing the game because pathfinding keeps trying to follow a high-traffic loop because the next tile in the loop always costs less than a step in the right direction.

results: DAMN IT DOESN'T WORK! I can't set it below 1 

well, TOADY PLZ LET US CHOOSE ANY VALUE, INCLUDING NEGAITVES!!!!!

You can't have a traffic cost less than 1, you'd break the function.

See http://en.wikipedia.org/wiki/A*_search_algorithm

Manhattan, really?  Doesn't DF use a Chebyshev distance, where the diagonals have equal cost to movement along the axes?  A Manhattan heuristic would overestimate the distances, in which case A* wouldn't necessarily find the shortest path.

Actually, you seem to be correct.

[Urist Da Vinci]

...sieges...

Only your dwarves, but not pets, enemies, neutrals, and perhaps not even children respect traffic designations. Many cat destroyers work on this principle.

Speak of pathing, I've found my dwarves to be unable to path over long chains of ramps. Any idea why?

Can they actually use the ramps? http://df.magmawiki.com/index.php/Ramp#Movement_Using_Ramps

[Xenos]

Basically my theory is that the dreaded "Infection" that arises in hospitals is partly due to the fact that most wells output "stagnant water."  I noticed that whenever wounded dwarves were given water in one of my forts that they left buckets full of stagnant water and had much unhappy thoughts from this.  One day, I remembered that pumps desalinate water when pumped into an entirely artificial cistern.  I also knew that this now desalinated water was always just "water" and never "stagnant water."  So, I proceeded to do a little test using a murky pool (which a previous well had drawn stagnant water from as a check.)  I pumped from that pool into my artificial cistern, built a well, and saw that it did indeed draw clean "water."  Now to perform tests with injured dwarves which is the more difficult portion of testing. 

To effectively test this, I will need to construct two sets of wells, one which will draw stagnant water and one which will draw water in the same fort.  Then wound a number of dwarves (I am thinking 10 wounded to 50+ healthy with at least 2 dwarves on each medical labor to allow for breaks.)  Immediately save after wounding the dwarves, then copy the save.  Allow one fort access to the stagnant water by walling off the clean well and allow the other access to the clean water by walling off the stagnant well.  Save and copy each fort again, and distribute the copied saves (so the other samples do not need to go through the process themselves.)  Now run each save for about 1-2 years.  Note how many dwarves receive infection in each fort, repeat.  Have others do the same, then try it with soap in each hospital and note the results.  My plan is to eventually get a definitive result wiht how to effectively treat wounded dwarves.  I just need to figure out how to wound dwarves reliably without fatalities...so far it seems like a fall would work nicely...

If anyone wants to help me with this it would be much appreciated!   (also, the hospital would be fully stocked with supplies and I intend to have enough buckets produced that the doctor wont have issues with no buckets working.  maybe the stagnant water causes issues with the reaction.  I dont know...)

[Shoku]

If you want to work out the processor drain from pathing you will need to actually look at the layout of your fort and do a lot of counting. If the tiles checked to get from a dwarf to where he wants to go are less one way then that means better FPS. This is the basis for ALL claims about pathfinding FPS from stairs or ramps but "count several thousand tiles" is not as catchy an idea as "ramps are better" or "stairs are better" so you hear those instead, usually with very altered reasons because so few people check out the pages people link for A* pathfinding, or possibly because a few couldn't understand it (it's easy.)

[Xenos]

If you want to work out the processor drain from pathing you will need to actually look at the layout of your fort and do a lot of counting. If the tiles checked to get from a dwarf to where he wants to go are less one way then that means better FPS. This is the basis for ALL claims about pathfinding FPS from stairs or ramps but "count several thousand tiles" is not as catchy an idea as "ramps are better" or "stairs are better" so you hear those instead, usually with very altered reasons because so few people check out the pages people link for A* pathfinding, or possibly because a few couldn't understand it (it's easy.)

This also explains why ramps are better in some forts and why stairs are better in others and and still others can be very efficient on one level.  (although the last one more works with burrows.

[rephikul]

Can they actually use the ramps? http://df.magmawiki.com/index.php/Ramp#Movement_Using_Ramps

Should. Mine look like this


#^__ #
# __^#
#^__ #
# __^#

[Xenos]

Can they actually use the ramps? http://df.magmawiki.com/index.php/Ramp#Movement_Using_Ramps

Should. Mine look like this


#^__ #
# __^#
#^__ #
# __^#

Those are unusable.  you need ramps to have a floor on top of the wall that acts as the base of the ramp.

[Trouserman]

Manhattan, really?  Doesn't DF use a Chebyshev distance, where the diagonals have equal cost to movement along the axes?  A Manhattan heuristic would overestimate the distances, in which case A* wouldn't necessarily find the shortest path.

Actually, you seem to be correct.

Actually, it seems I am not.  It's more complicated than that.  Test scenario:

Code: [Select]

########B#
#######..#
######.#.#
#####.##.#
####.###.#
###.####.#
##.#####.#
#.######.#
##.#####.#
###.####.#
####A....#
According to my hypothesis, dwarves should prefer the left hand path from A to B (10 diagonal steps), but they prefer the right hand path (12 orthogonal steps and one diagonal step at the corner).  Instead, they prefer the right hand path.  This holds for a designated traffic cost of either 1 or 2, so it's not due to a bugged heuristic.  So I watched the movement more carefully.  After taking an orthogonal step, my test dwarf required 10 (sometimes 9) simulation steps to recover before the next move.  After a diagonal step, he recovered for 13 simulation steps.  So the cost of a diagonal step is higher than the cost of an orthogonal step.  Manhattan would still be an inappropriate heuristic, since the factor is clearly less than 2 (though I cannot prove it is not being used from these data).  [Edit: Yes I can.]

The dwarf chose the left path when two of its tiles were designated high traffic, but not one (all other tiles being normal, at a cost of 2).  This is consistent with the observed movement cost ratio between 1.33 and 1.42.  (I didn't count out enough steps to actually narrow this down any more than that.)

[twilightdusk]

Can they actually use the ramps? http://df.magmawiki.com/index.php/Ramp#Movement_Using_Ramps

Should. Mine look like this


#^__ #
# __^#
#^__ #
# __^#

Those are unusable.  you need ramps to have a floor on top of the wall that acts as the base of the ramp.

so it should look like this from a side view?

##^__ _#
#_ __^##
##^__ _#
#_ __^##

[Trouserman]

so it should look like this from a side view?

##^__ _#
#_ __^##
##^__ _#
#_ __^##

Yes, that is one way, as long as the dwarves can go around the hole where the ramp down is.  It'll be cleaner if you offset the levels horizontally.  Top view:

######
#+++^#
#v####
######

Level below:

######
####v#
#^+++#
######

From there, you're halfway to an elaborate spiral stair.

[Urist Imiknorris]

SCIENCE

Diagonal paths take √2 times as long to traverse, and the algorithm probably accounts for that.