Print

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

[Granite26]

I don't honestly think either of these are particularly good ideas for DF, but they could be in some form.

Reverse Breadcrumb Pathing : When a dwarf decides to go someplace, he places a breadcrumb, or in this case, a +1 pt cost field, on the squares of his path.  Other dwarves will try not to path along his path (unless they are following him to a destination, which I assume is a pathing shortcut in the system).  This means less traffic jams as dwarves naturally path around each other.  (This is most useful for dwarves running down those one wide exploratory tunnels to pick up stuff.)  This could be combined with a flow indicator to create a tendancy for one way traffic down a hall (Or right/left lanes in two wide hallways).  

Waypoints : Allow (Players to request) dwarves to build signs.  Whenever a dwarf at a defined location (I'm thinking piles or rooms here) is engaged in pathfinding and it finds a waypoint, it records that distance (but maybe not the actual path).  Each waypoint retains a path cost (and maybe path definition) to each other waypoint.  (I'm thinking 5-6 would be ideal, your front gate/trade depot, the stairs from the 'depths', the well, the apartment complex, and maybe the workshop area).  This information is maintained at the same time the dwarves re-path.  (Basically pathing signs(signs-1)/2 extra paths, which is 15 for 6 signs)

OK, so when the dwarf finds the path to a waypoint, it then knows how far all the other waypoints are from it, and, if another unit has pathed to the waypoint from the spot the dwarf is going, it also puts an upper bound on the length of the path between the points.  This isn't particularly useful if your waypoints are bad/close together, but if you've got your zones widely spaced, it could be a big help.

Some code possibilities:
Compare the path known to the as the crow flies distance.  If it's reasonably efficient, just use it.  (I.E. if the linear distance is only 80% of the pathed distance, just use it.  Since the path between disparate waypoints is going to be calculated once, you are saving that cost each turn by the number of units that actually take that path-1.  Minor deviations to get out of the way could be supported.

I'm not sure how the pathing works.  The simple solution would be breadth first of all the available points with a bias for moving towards the finish line.  (or a depth first with a bias towards the finish line) However, having a guaranteed max distance based on the waypoints could give you some optimization here.  (If you want all mathy, it would be an ellipse looking thing saying how far you could path from the straight and narrow and still hit your target).  This would allow some more 'risky' pathing solutions to be tried, because you'd have a guaranteed cutoff point.

All of that is based on my experience of having a few areas of dwarf concentration seperated by big distances.  (Crafts and Trade upstairs, apartments to the right, farming to the left and the Smithies downstairs, with the mining down in the underdark)

Again, don't know if they'd work for DF, but it's the fruits of my thinking about optimization and it interests me  

[Draco18s]

Breadcrumb won't work.  When you've got one entrance to your fort and 100 dwarves, that means that those popularly used tiles have a pathcost of, oh, say, 50 on average, which makes them even less preferred that restricted tiles, causing the A* algorithm work harder to find a better path, causing MORE lag, not less.

[Neonivek]

Let me see... 3rd post. (My brain hurts from thinking)

Well this one is shorter

Reverse Breadcrumb Pathing: I think the poster above me summed it up

Waypoints: I don't understand... what is the point exactly? While I do agree that a measurement tool for distance could be helpful.

Code Possibilities
-A lot of this is already in the game... The problem comes when there are TONS of dwarves (and their pets). making you require large hallways.

[Granite26]

quote:Originally posted by Draco18s:
<STRONG>Breadcrumb won't work.  When you've got one entrance to your fort and 100 dwarves, that means that those popularly used tiles have a pathcost of, oh, say, 50 on average, which makes them even less preferred that restricted tiles, causing the A* algorithm work harder to find a better path, causing MORE lag, not less.</STRONG>

Not intended to fix lag, intended to fix having 50 dwarves trying to move through one corridor when there's a two step longer path that's empty.

[Normandy]

That could simply be achieved by using traffic zones. Sure it's not automatic, but it provides better control.

[Draco18s]

quote:Originally posted by Granite26:
<STRONG>Not intended to fix lag, intended to fix having 50 dwarves trying to move through one corridor when there's a two step longer path that's empty.</STRONG>

The game takes this into account already.  An unavoidably path-through-a-dwarf is worth about 30 on the A* algorithm (dwarves would rather go around than through, and will go through restricted zones to do so).  Thing is, there might not be a dwarf there when the dwarf gets his path through there.  But if it is unbelievably crowded, dwarves will go around.

[Derakon]

Waypoints would be useful for optimizing pathing, as follows: the game computes paths between the waypoints, and then caches those paths. When a dwarf needs to go somewhere, he paths to the nearest waypoint, and from there to the waypoint nearest where he wants to go. Assuming intelligent placement of waypoints, the extra cost of going to the waypoint before going where you need to go is minimal.

The big problem with this is that paths between waypoints may be disrupted or become improvable as the game's terrain changes.