Print

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

[Draco18s]

I apologize for not having read the thread, but has anyone tried something like ant trails, at least for civilian dwarfs?

Was discussed, yes.

[Pie]

I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).

Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).

[Nadaka]

I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).

Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).

You can already somewhat do this with traffic zoning.

[PencilinHand]

I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).

Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).

You can already somewhat do this with traffic zoning.

The idea will be expanded upon somewhat by the burrows concept.  Which will prevent dwarfs from taking jobs etc. outside their assigned burrows thus limiting the destination possibilities.  However, pathfinding will not take burrow boundary's into account.

[tigrex]

That might lead to some exasperating situations, such as a dwarf entering a burrow with the aim to go through it and into the burrow next door and then to its destination, only to find that the second burrow is forbidden to it.  It reverses, and then sees burrow 1 again, turns around and walks through it, leading to what people will soon call burrow dancing.

[PencilinHand]

That might lead to some exasperating situations, such as a dwarf entering a burrow with the aim to go through it and into the burrow next door and then to its destination, only to find that the second burrow is forbidden to it.  It reverses, and then sees burrow 1 again, turns around and walks through it, leading to what people will soon call burrow dancing.

Dwarfs ignore burrows when pathing.

[jaked122]

we should take neurons from a rat to learn how to path through the most efficient way, then we just jam a rat into the CPU.
or you *could* have embedded pathing nodes that players can place in important areas that would link to nearby reasources(much like the unreal engine does) and the doors could easily function as conditional nodes (if connected to a lever)

[Mel_Vixen]

A rat? Heck use an evolutionary algorithm some thousand maps and many hours of time. The fastest near optimal algo with the lowest memory and time impact wins.

edit:

Anyway btt: The first post says:

Create a flexible BSD licensed C++ path-finding library specialized  for grid based systems like that of Dwarf Fortress and able to  efficiently handle rapidly changing map geometry and other challenges  such as but not limited too multiple travel domains, multi-tile  creatures, variable movement cost terrain and path caching.

Algorithms for multitile creatures could be extend to "Swarms" (Boids etc.). The only difference is that a swarm is flexible in form. I dont know how hard it would be (its just a fix idea) but i think much of the code for multi-tile creatures could work for swarms too. Thus you could safe much time by calculating a path for one swarm then a path for every single member.

The "Swarm" concept could apply to things like Herds of animals, squads, armys, working-groups, etc. 

Anyway that is only suggestion based on a educated guess.

[ggeezz]

I realise that this is not within the scope of this project (as it involves feature implementation by Toady), but in terms of Dwarf Fortress Pathfinding in general, if there was some option for the user to paint a rough route from point A to point B, would this make Pathfinding faster? The "brush" would be several tiles large, to give the system some flexibility. The basic idea would be that there would be far fewer tiles to search through, and even some of the most sub-optimal routes would be acceptable for most players (since they painted them). If the route was sliced in half (say by some deadly magma), it would simply revert to the standard Pathfinding method. Another advantage of this method is that you don't have to calculate total distances with objects many z-levels above. The main disadvantage is of course the lack of automation to this and the fact that you'd still need a much better Pathfinder for situations not involving stockpiles and workshops (or other specific start/end points).

Now I'm sure I'm missing something obvious due to my total lack of competence in this area, but I just thought that it might be worth thinking about (if it hasn't already been thought of).

You can already somewhat do this with traffic zoning.

The idea will be expanded upon somewhat by the burrows concept.  Which will prevent dwarfs from taking jobs etc. outside their assigned burrows thus limiting the destination possibilities.  However, pathfinding will not take burrow boundary's into account.

There's a difference in intent here of using less CPU cycles vs. telling dwarves where to walk.

You can already tell your dwarves where to walk, somewhat, but you can't already save CPU cycles by doing manual pathfinding.

[Shades]

There's a difference in intent here of using less CPU cycles vs. telling dwarves where to walk.

You can already tell your dwarves where to walk, somewhat, but you can't already save CPU cycles by doing manual pathfinding.

Actually that is what your doing when you 'tell your dwarves where to walk', the high traffic zones are a lower weighting to normal traffic and so will be searched in preference to other areas. Assuming your traffic zones connect that start and end of the path then the solution is found with fewer steps and so saves CPU cycles.

You could enhance this affect by increasing the weight of 'normal' in the ini file however this will slightly increase the search space in other situations so probably isn't worth it.

[Draco18s]

*Game cancels run (now paused): Urist McMason needs path to masonry shop

 

[ggeezz]

There's a difference in intent here of using less CPU cycles vs. telling dwarves where to walk.

You can already tell your dwarves where to walk, somewhat, but you can't already save CPU cycles by doing manual pathfinding.

Actually that is what your doing when you 'tell your dwarves where to walk', the high traffic zones are a lower weighting to normal traffic and so will be searched in preference to other areas. Assuming your traffic zones connect that start and end of the path then the solution is found with fewer steps and so saves CPU cycles.

You could enhance this affect by increasing the weight of 'normal' in the ini file however this will slightly increase the search space in other situations so probably isn't worth it.

Ahh, I hadn't thought about that.

Still though, there's a rather large difference between making the pathfinding somewhat faster in some situations vs. eliminating it altogether.

But I guess saying "you can already do this somewhat" is still technically accurate and moreso than I realized.

[CobaltKobold]

*Game cancels run (now paused): Urist McMason needs path to masonry shop

 

Sounds like a game genre!

[qwertyuiopas]

Well, if I understand the pathing system correctly, it tries all least-cost unexplored tiles first(If that tile has, assuming the most optimal path starting at that tile to the destination, the least cost of all other tiles that the pather hasn't explored yet), that using restricted pathing zones where you don't want dwarves going often means that the path must be much longer before it will check that route for a connection, so if it would have taken another route entirely anyway, it will ignore that section for longer, and save cycles.

By putting restricted zoning all over the external areas that dwarves shouldn't access anyway, the pathing would be less likely to spill out into the external areas and flood-fill the map during an attempt to navigate a massive maze.

Of course, if it already does minor pathing on the macro-grid level, such a waste of CPU might be discounted anyway...

[KillHour]

Well, if I understand the pathing system correctly, it tries all least-cost unexplored tiles first(If that tile has, assuming the most optimal path starting at that tile to the destination, the least cost of all other tiles that the pather hasn't explored yet), that using restricted pathing zones where you don't want dwarves going often means that the path must be much longer before it will check that route for a connection, so if it would have taken another route entirely anyway, it will ignore that section for longer, and save cycles.

By putting restricted zoning all over the external areas that dwarves shouldn't access anyway, the pathing would be less likely to spill out into the external areas and flood-fill the map during an attempt to navigate a massive maze.

Of course, if it already does minor pathing on the macro-grid level, such a waste of CPU might be discounted anyway...

Basically, it works like this:

Say we have a fort:

Code: [Select]

██████████████████████
█++++++█θ+█θ+█θ+█++++█
█+y++++█++█++█++█+x++█
█++++++█+██+██+██++++█
█++++++++++++++++++++█
█++++++██████████++++█
██████████████████████

You want to get from X to Y.

Each square in the fort is labeled with high traffic (1)

Code: [Select]

██████████████████████
█111111█11█11█11█1111█
█111111█11█11█11█1111█
█111111█1██1██1██1111█
█11111111111111111111█
█111111██████████1111█
██████████████████████

Each 'tick', the path is flooded 1 square outwards.

The numbers and letters represent the number of ticks the pathfinder takes to get to each specific square.  (after the 10 digits, I switch to letters, so a=10, b=11, etc.)

It stops when it reaches its destination.

*'s are squares the computer doesn't have to calculate.

Code: [Select]

██████████████████████
█*gfeee█cc█99█66█1112█
█*gfedd█bb█88█55█1012█
█*gfedc█a██7██4██1112█
█*gfedcba987654322222█
█*gfedc██████████3333█
██████████████████████

Lets say the bedrooms are forbidden (10)

Each forbidden square waits 10 ticks before being checked.

Code: [Select]

██████████████████████
█*gfeee█**█**█**█1112█
█*gfedd█**█**█**█1012█
█*gfedc█*██g██d██1112█
█*gfedcba987654322222█
█*gfedc██████████3333█
██████████████████████

Because of this, the bedrooms don't need to be checked, saving cycles.  However, actually trying to go to a bedroom takes more cycles to calculate a path.