Print

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

[Saber Cherry]

I don't know if this is relevant or if you're aware, but DF actually *does* factor in the extra time required to move diagonally.

My point with regards to XY-plane movement is mainly that:

1) In an A* heuristic, for internal areas, I suspect it would be more accurate and faster if paths were estimated as though diagonal movement was impossible, since the square-tile-based maps make diagonal paths the exception rather than the rule.  This is due to hallways and etc. being most efficient when aligned along an X or Y axis, so most paths have long axial portions and short diagonal portions in a typical fortress.

When movement is unrestricted, like outside on a flat clear map, A* pathing is efficient enough with either heuristic (a correct one or a simpler one) since the heuristics' assumption of no obstructions is true.  Thus, optimal pathing in this setting is not really an important consideration in algorithm design since it does not represent the case that actually drains CPU resources (in my highly speculative model of how the game engine works). 

As such, diagonal movement should be something present in final paths, but perhaps not present in pathfinding distance-estimation heuristics.

[Footkerchief]

DF uses Manhattan distance as its A* heuristic, apparently.  Don't know if it allows diagonals or not.  I'm not sure why we're talking about pathfinding, though.  It's known that DF uses straight-line distance for various distance checks, possibly including item selection.

I really opened up the can, didn't I.

[Dante]

I'd rather see proper pathfinding to items being used to locate items for jobs at workshops. Or at least an approximation, with floodfill or something. Even at the cost of FPS.

Currently, if you have a set up with walls like

Code: [Select]


------------
       WWW |
1      WWW | 2
       WWW |
------------

(W = workshop area)


then dwarves will still try to get item #2, even if they have to walk four circuits of your fortress, or outside into a dangerous zone, to get it. Just because item #1 is a single square further away as the crow flies.

I don't know about you guys, but this sort of thing actually happens to me a lot, especially in younger fortresses where I haven't got all my staircases and stockpiles and things sorted out yet.

[Saber Cherry]

DF uses Manhattan distance as its A* heuristic, apparently.

Thanks!

I'm not sure why we're talking about pathfinding, though.

I don't know why other people are, but I am because graph algorithms are one of my hobbies   And, of course, pathfinding (and its effect on FPS) is this huge issue that dominates my fortresses' design and operation, moreso than anything else like caravans, sieges, or food production.  You can get those wrong and survive but if you are not vigilant about pathfinding the game can become unplayable.

It's known that DF uses straight-line distance for various distance checks, possibly including item selection.

I hope item-selection gets changed to Manhattan + extra cost for Z-motion, since that's the heuristic that always causes me the most problems (aside from animal pathing).


@Dante.  It would be nice for dwarves to always get the actually closest thing.  But until that can be done at 100fps, I prefer my dwarves to do a little extra work rather than my CPU do a ton of extra work.  CPUs are expensive but you can always get more dwarves, for free.

[madman]

I don't know if this is relevant or if you're aware, but DF actually *does* factor in the extra time required to move diagonally.

Of course, it only does this for horizontal travel, not for travel between z-levels, as stated in one of the REQs.

Do you know what factor it uses for the movement cost of going diagonally rather than horizontal or vertical? sqrt(2) would be the 'correct' number to use, but that would slow down computation.

Even in that case, the horizontal distance metric should be a*max(|x₁-x₂|,|y₁-y₂|) + b*(|x₁-x₂|+|y₁-y₂|) for some constants a,b, rather than the Euclidean one (although with a sqrt(2) multiplier on the diagonal movement cost , a=2-sqrt(2), b=sqrt(2)-1 and Euclidean gives a pretty good approximation).

Unless of course Dwarf Fortress does something really nuts with hidden fractional position offsets rather than just traveling directly from square to square in order to make the Euclidean distance accurate (which given Toady's attention to detail would not entirely surprise me).

Edit: and just to be clear, I'd still rather see accurate closest object finding than any approximation. (if the speed hit is not too big).

[G-Flex]

I don't know if this is relevant or if you're aware, but DF actually *does* factor in the extra time required to move diagonally.

Of course, it only does this for horizontal travel, not for travel between z-levels, as stated in one of the REQs.

Do you know what factor it uses for the movement cost of going diagonally rather than horizontal or vertical? sqrt(2) would be the 'correct' number to use, but that would slow down computation.

It's some approximation of that, of course. I want to say it's just 1.41, which is probably good enough at the distances we're talking about.

Of course, there's no reason to evaluate the square root of 2 every time you need it anyway; that's a constant, so just make it a constant.

[madman]

@Dante.  It would be nice for dwarves to always get the actually closest thing.  But until that can be done at 100fps, I prefer my dwarves to do a little extra work rather than my CPU do a ton of extra work.  CPUs are expensive but you can always get more dwarves, for free.

That surely depends on the relative amount of extra work? More dwarves also drop the FPS.

If, at any given time, half your dwarves are using an accurate algorithm where they weren't before, the algorithm gets an average of 10% shorter paths while dropping the FPS by 5%, then it comes out about even in terms of dwarf work done per second doesn't it? Actually slightly better - dwarves will consume food and booze slightly slower with a slower FPS (or less dwarves at the same FPS), and are less likely to drop shorter jobs in the middle to go sleep or something.

It would depend on what the performance numbers actually are of course.

[madman]

It's some approximation of that, of course. I want to say it's just 1.41, which is probably good enough at the distances we're talking about.

Of course, there's no reason to evaluate the square root of 2 every time you need it anyway; that's a constant, so just make it a constant.

The slowing down computation is not because of evaluating the square root of 2 every time (that would be crazy), it's because of having to mix integer and floating point arithmetic all the time - that's a real CPU killer. If I was doing it, I would keep everything possible in integer arithmetic (keeping everything as floating point is not really feasible), and I might say the cost was something like 5 for a horizontal/vertical space and 7 for a diagonal, making the constant 1.4 .

It's also of interest to me: I've been designing my fortress on the basis that diagonal movement is the same cost as horizontal/vertical. Perhaps this is not a good idea.

And yes, Footkerchief, you really did open up the can.

[G-Flex]

It's some approximation of that, of course. I want to say it's just 1.41, which is probably good enough at the distances we're talking about.

Of course, there's no reason to evaluate the square root of 2 every time you need it anyway; that's a constant, so just make it a constant.

The slowing down computation is not because of evaluating the square root of 2 every time (that would be crazy), it's because of having to mix integer and floating point arithmetic all the time - that's a real CPU killer.

Sorry, wasn't giving you enough credit there. Looking around the rest of the forum (not you specifically), I'm not sure I blame myself.

[Footkerchief]

Probably too late, but we do have an active thread discussing performance stuff (started out talking about parallelization, but it's open for whatever now).  There's also another pathfinding thread where some people are working on implementing and testing a variety of algorithms on maps exported from DF.

[AbacusWizard]

I don't know if this is relevant or if you're aware, but DF actually *does* factor in the extra time required to move diagonally.

Of course, it only does this for horizontal travel, not for travel between z-levels, as stated in one of the REQs.

Do you know what factor it uses for the movement cost of going diagonally rather than horizontal or vertical? sqrt(2) would be the 'correct' number to use, but that would slow down computation.

Even in that case, the horizontal distance metric should be a*max(|x₁-x₂|,|y₁-y₂|) + b*(|x₁-x₂|+|y₁-y₂|) for some constants a,b, rather than the Euclidean one (although with a sqrt(2) multiplier on the diagonal movement cost , a=2-sqrt(2), b=sqrt(2)-1 and Euclidean gives a pretty good approximation).

Unless of course Dwarf Fortress does something really nuts with hidden fractional position offsets rather than just traveling directly from square to square in order to make the Euclidean distance accurate (which given Toady's attention to detail would not entirely surprise me).

Edit: and just to be clear, I'd still rather see accurate closest object finding than any approximation. (if the speed hit is not too big).

I'd like to see R'lyeh Fortress with non-Euclidean distance metrics.

[madman]

I'd like to see R'lyeh Fortress with non-Euclidean distance metrics.

Go for a non-metric space. The triangle inequality - who needs it?

[Chthonic]

Maybe workshops could have multiple behaviors?  Suppose at every season-change or once a "day" or whenever would be appropriate, each workshop does the elaborate pathfinding check to every individual stockpile set to use workshop-appropriate materials, and records the stockpiles in order of preference.

Then, when a job requires a material, the workshop checks each stockpile in order of proper distance for the material it needs without calculating any paths or running any algorithms beyond "what's the first suitable material in this stockpile?".  If there's nothing in the stockpiles, then it goes hunting the map using a more intensive method.

/not a computer scientist

[Neonivek]

Well one problem is that Dwarf Fortress doesn't store things very well either.

[LordZorintrhox]

Maybe workshops could have multiple behaviors?  Suppose at every season-change or once a "day" or whenever would be appropriate, each workshop does the elaborate pathfinding check to every individual stockpile set to use workshop-appropriate materials, and records the stockpiles in order of preference.

Then, when a job requires a material, the workshop checks each stockpile in order of proper distance for the material it needs without calculating any paths or running any algorithms beyond "what's the first suitable material in this stockpile?".  If there's nothing in the stockpiles, then it goes hunting the map using a more intensive method.

/not a computer scientist

...actually, not a bad idea.  When a dwarf does a job, and it is to a stockpile not already accessed by that workshop, the workshop stores a pointer to the pathing object.  Then subsequent dwarves can access the path to the stockpile they want from the workshop that they are doing the job for.  You can then make an optimized algorithm for searching stockpiles, since there are some general assumptions you can make about them (usually comparatively large and obstruction free).

If the list of stockpiles is stored in a binary tree, you can find out if the stockpile has been accessed in O(log(n)) time, and if it has, the pathing step takes O(1).  Say that the rate of new path calculations follows an exponential decay with the age of your fortress, and over time the pathing time becomes more or less constant. Huh.

And back to the game.  Yeah!  SO CLOSE!

Edit: Oops, I did my math a little wrong; over time pathing would approach O(log(n)), not a constant since you still must look up stored paths in the workshop.