Print

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

[Jurph]

I was just informed in this thread that diagonal travel cost is not well-characterized, or at least not with any definite proof.  I am a little surprised that this result -- or lack of result -- isn't better understood.  I searched the forums for "manhattan" and "Chebyshev" and did not see any rigorous answer to the question.  Unfortunately, I can't figure out how to definitively pose the question using DF.

So far, the test case I envision goes something like this: a dwarf is caged or locked into a 1x1 cell behind a floodgate.  Two single-tile-wide tunnels are dug: one extends 21 tiles orthogonally; one runs 21 tiles diagonally.  A single tile of food storage is placed at the end of each tunnel and a plump helmet is placed on each stockpile.  The Enrichment Center is sealed off from the rest of the fortress.  When the dwarf indicates hunger, the lever is pulled and the dwarf is released, presumably to seek out the nearest food.

The experiment results may be documented and repeated by moving either of the stockpiles closer to the origin; for example, if a true Pythagorean distance is implemented, we'd expect 10 diagonal tiles to be roughly equidistant with 14 orthogonal tiles.

Has anyone already tried this?  Is my core assumption (dwarves always seek the nearest food) correct, or is there a better thing for a dwarf to seek?

[Vattic]

• I can't remember if goblins differ from each other like dwarves do in their stats if so mod that out.
  
• Capture some goblins in cages.
• Disarm them and place the cages at the ends of two corridors as you describe but leading to a clear exit of the map.
• Open both cages simultaneously with a lever.
• See who wins.

[Funburns]

It's distractingly hot and humid here, and I'm not exactly an expert, so I hope this post makes sense.

You may want to try your tests across several different pairs of diagonal and orthogonal directions over multiple tests for each set of length and direction combinations. If two goals are judged to be identically distant the algorithm might take whichever goal was created more recently or some other hidden tiebreaking factor that might mess with the data. It's also possible the game might prefer certain directions over others if they're identical distances; dwarves do have annoying positioning preferences for construction, after all.

Vattic's modded goblin idea might simplify the secret tiebreaker issue since they (probably) only want to reach the map edge, though my guess is it's better to increase the number of tests instead of timing multiple pathfinding agents simultaneously. If you have the patience, you could do any of these tests frame by frame to figure out if diagonal movement speed is different, as well as if the pathing cost is different.

It might also be the case that object finding is implemented by a different algorithm from that of path finding. The object finder might evaluate the apparently Euclidean distance of every object to the dwarf to find the closest object the Pythagorean way (the squares-are-squares hypothesis), while the path finder might use a simple version of Manhattan pathing which considers diagonals to cost 1.0 dwarf-efforts instead of ~1.4 (the squares-are-circles hypothesis). That would be a very... interesting... design decision, but to my novice understanding, it's plausible that object finding algorithm would be faster than using the terrain-sensitive pathing algorithm, since the latter needs to be 100% obedient to terrain restrictions.

[Lectorog]

Preliminary testing shows that a motivated* dwarf takes 14-15 steps to move one tile diagonally, while a similar dwarf takes 10-11. I'll return later with better data.

(*faced with an enemy they want to kill at the end of a hallway)

[Lectorog]

OK, I did a full round of testing. Here are the results:

Code: [Select]

ROUND I
Out-In
W:12-12,10-11,11-11,11-11
N:11-12,11-11,11-11,10-11
E:11-11,10-10,11-10,11-11
S:11-11,10-11,11-11,11-11
----
NW:11-11,14-15,15-14,14-15
NE:11-11,14-14,14-14,15-14
SE:12-11,15-15,15-14,14-15
SW:12-12,14-15,15-14,14-14
In this arena configuration:

Spoiler (click to show/hide)

Those were the '.' steps it took for each dwarf to move one tile, listed by the outer dwarf (team 2) to the inner dwarf (team 1). As each hallway was 11 long, only 4 steps from each could be reliably counted.

This seems to confirm that it takes longer to move diagonally than orthogonally.

It also confirms that arenas are hard to configure in text. Took me well over an hour to make the arena, after figuring out Paint won't let you work with this program correctly. If anyone want the arena, ask and I'll upload it.

[Jurph]

Lectorog, this is awesome stuff.  I can see that you did two rounds of tests, with dwarves going out-then-in, and I can see that you broke down the results by direction.  I'm a little puzzled by the fact that the first orthogonal round took the longest, and the first diagonal round was the shortest.  Can you think of anything that would explain that?  Maybe observation bias? 

If we assume some sort of measurement bias in the first round -- even a fencepost or counting error could account for it -- then it seems reasonable to conclude that dwarves take about 1.4 (probably √2) steps to move diagonally.  I'm hosting my weekly D&D table tonight, and I've got to do some hardware work on my wife's PC, but I'll try to reproduce your results soon using your arena file. 

If enough of us can reproduce your results, I think we should post them on the Wiki somewhere for all to see, e.g.

"Dwarves take about √2 times longer to traverse a diagonal tile than an orthogonal tile (Lectorog, 2011) which means that -- just as in our universe -- the corners of a square room are 41% further than the midpoint of its walls from the center point."

OK, I did a full round of testing. Here are the results:

Code: [Select]

ROUND I
Out-In
W:12-12,10-11,11-11,11-11
N:11-12,11-11,11-11,10-11
E:11-11,10-10,11-10,11-11
S:11-11,10-11,11-11,11-11
----
NW:11-11,14-15,15-14,14-15
NE:11-11,14-14,14-14,15-14
SE:12-11,15-15,15-14,14-15
SW:12-12,14-15,15-14,14-14

[Lectorog]

It was actually just one round of tests; I put enemy dwarves at each end of the hall and they immediately ran at each other. The first number is the steps the first dwarf (outermost tile of the array) took to move one tile; the number after the dash is the inner dwarf's steps to move the same ammount. After the comma is the second step, and so on, until the fourth step, after which there was only one tile between them. These were counted at the same time, but with respect to the previous steps taken for each dwarf. (Meaning, I counted correctly, probably)

I don't know what was up with the first tile of movement. It seems that's always the same, but I don't know why. Might have something to do with specific pathing quantities. Perhaps the spawning placed them somewhere differently in the tile than moving into the tile did.

I uploaded the arena to DFFD. It's just the text file. Hallways are on the bottom level. Just note that there's a small cave-in and some minor lava flow when you start it up. I think I have an extra or missing couple lines of code. It doesn't interfere with testing, though.

[Toady One]

It could be that, as seen most easily in adventure mode, movement is instantaneous when it is your turn.  So it doesn't take extra time to do your first diagonal step, because it is your turn and you can do whatever you want, but you are hit with a timer afterward according to how far you moved.  The reason there's an initial delay is probably just the time it takes to get to the AI routine before their first instantaneous moves.  I could have misread the results though.

[Jurph]

I like the explanation of the constant-duration first step being "on credit" so that the time costs are assessed after travel... that makes good sense.  Now that we have a reasonable explanation for that phenomenon, it looks like the steady-state results confirm the Pythagorean worldview.

(Out of curiosity, Toady, are you using a true SQRT function for the Euclidean distance, or did you use an approximation like this one to save CPU cycles?)

[Toady One]

There are two sides of it.  I don't think many or any of the distance calculators care about the root 2 stuff (so I think your original experiment might not have noticed the diagonal).  The travel delay uses something like 362/256, but there isn't that much resolution in the system so it has to randomly apply the remainder.