Print

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

[Draco18s]

but then, it's been frequently complained upon that pathfinding to items doesn't take z-levels and stairs into account, so it really is 2D in DF

Wrong.  I takes stairs/ramps into account all the time.  Haven't you ever watched dwarves go over a hill rather than around?

What it doesn't do is take THE ENTIRE Z AXIS into account when CALCULATING DISTANCES BETWEEN OBJECTS.

Is rock A closer to me than rock B?  Rock A at is X+4, Y-1, Z+30.  Rock B is X+10, Y+5, Z+0.  Rock A must be closer, it's only 4.1 tiles away!

[Footkerchief]

^^^ Bingo.  Has there ever actually been a thread about that issue?  It seems like such a small and easily fixed thing, so maybe he just doesn't know about it.

[texmith]

Ponder the possibilities:

Urist needs a rock. There's 500000 rocks lying around, so he does a quick dx+dy+dz test on each to find out which is closest. Rock a is the closest, he can get to it, so he calls the pathfinding routine, finds the best path and goes to get it.

Urist needs a rock. There 's 500000 rocks lying around so he calls the pathfinding routine for each rock to find the closest... the cpu melts and Urist is drowned in lava.

[Silverionmox]

Alternatively, there could be a floodfill from the place of the dwarf, and the first item encountered that fits the requirements is taken.

Or there could be a bias for the x,y plane when searching for items, since dwarves can more easily move on that one than the z-axis.

[Granite26]

Alternatively, there could be a floodfill from the place of the dwarf, and the first item encountered that fits the requirements is taken.

Win!

Or there could be a bias for the x,y plane when searching for items, since dwarves can more easily move on that one than the z-axis.

Lose! (Special case based on how you et al build your fort.)

[Silverionmox]

I know, the first one would work more reliably. The second is more of a quick and dirty fix, even though items can only lie on a mined out surface if it's facing up.

[Align]

There must be a reason floodfill isn't already used.

[Silverionmox]

There must be a reason floodfill isn't already used.

It potentially needs to flood almost the whole map. I don't know whether that would cause a major, minor or no lag, ...  sometimes or most of the time.. Most likely it's just a quirk inherited from 2d, waiting to be cleaned up.

[Random832]

There must be a reason floodfill isn't already used.

It potentially needs to flood almost the whole map. I don't know whether that would cause a major, minor or no lag, ...  sometimes or most of the time.. Most likely it's just a quirk inherited from 2d, waiting to be cleaned up.

Flood fill is also not guaranteed to reach near tiles before far tiles. Note that the animation at http://en.wikipedia.org/wiki/Flood_fill reaches the far lower left corner before it hits any of the other adjacent cells.

[Silverionmox]

There must be a reason floodfill isn't already used.

It potentially needs to flood almost the whole map. I don't know whether that would cause a major, minor or no lag, ...  sometimes or most of the time.. Most likely it's just a quirk inherited from 2d, waiting to be cleaned up.

Flood fill is also not guaranteed to reach near tiles before far tiles. Note that the animation at http://en.wikipedia.org/wiki/Flood_fill reaches the far lower left corner before it hits any of the other adjacent cells.

I had this kind of flood fill in mind:
http://en.wikipedia.org/wiki/File:Wfm_floodfill_animation_queue.gif

[Footkerchief]

Flood fill could also be useful for lighting arc stuff.

[Mikademus]

That algorithm has moved from simple flood filling into basic ray casting...

[Andir]

That algorithm has moved from simple flood filling into basic ray casting...

More than one way to skin a cat.