Print

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

[Granite26]

It appears I owe you an apology.  I was convinced that we'd had a long debate about using doors double thick to keep water out and long cooridors full of doors versus a path around with no doors, but I can't find it.

I never called out grouping contiguous area dividers as a single one, so my harrassing you about it was totally off base.

In my own defense, you did falsely accuse me of assuming everyone played like me.

[Niseg]

I'll throw my ideas about the subject and I don't think someone mentioned them but they aren't that revolutionary.

I think the easiest improvement on pathing is to put a constraint on how long each mob can hog cpu per frame on pathing. This is rather simple to implement but may cause the dwarf/mob to stand there for a while.  The dwarf or mob can also take a guess that the path they are on is good and start traveling . Because A* start at the source and not destination the dwarf can keep a back-path if he didn't travel too long . You may see the dwarf running  running around his start position until he gets on the correct path.

Adding the feature "stop and think" or "thinking on your feet " may save people with weaker CPU a lot of trouble .

I also had a similar idea to the "areas" that were mentioned here so dwarfs would go from Area to Area rather than from point to point.

[JanusTwoface]

It might help, but there is a definite cost to storing where you were in the path finding and the reloading that every frame (or however often). It might work, but I think the ideas which automatically make larger areas with stored paths will probably be more benificial.

A thought on those lines: could pathing be done in a manner similar to how network traffic is routed?
- Each boundary between zones (however those are decided) keeps a routing table for how to get to each general area of the fort.
- Each path finding dwarf gets to one of these checkpoints and tells it their destination.
- The routing table gives them the next part of their journey.
- They use A* (on a much shorter path) to get to the next routing station.

Thoughts?

[Jeoshua]

That sounds like a  hybrid of brute-force pathfinding and nodal pathfinding.

I like it.

[Granite26]

That's pretty much what we've been talking about.  The hard part is coming up with how to do the nodes in a way that will support outdoors, inside a fortress, in a cavern, etc.

[Draco18s]

That's pretty much what we've been talking about.  The hard part is coming up with how to do the nodes in a way that will support outdoors, inside a fortress, in a cavern, etc.

You need to deal with mazes,* large open spaces, spaces with 1 entry, 2, and 20.

*A "maze" is defined as 1-2 tile wide corridors that zig-zag a lot, possibly including multiple valid paths to the destination.

[JanusTwoface]

That's pretty much what we've been talking about.  The hard part is coming up with how to do the nodes in a way that will support outdoors, inside a fortress, in a cavern, etc.

Right. The node idea has been discussed quite a  bit, both here and in the Pathfinder Project. But I think the idea of routing tables is new(ish). I'm actually curious how that'd work in practice. I may throw together a proof of concept.

You need to deal with mazes,* large open spaces, spaces with 1 entry, 2, and 20.

Large open spaces seem like they're not really a problem. Set aside a tunable parameter for how large of groups actually will form and divide it into a grid of that size. Up to the (unlikely) possibility of including the entire outside as a node in a region where your fortress is entirely underground with minimal wildlife that needs pathing.

Mazes I'm not so sure about. I think it's a matter of scale again. Smallish mazes would probably be a single node. It'd be quicker to solve them with A* then storing and reading paths. Larger mazes... Hmm...

[Niseg]

bisection and powers of 2 are your friends:


1. create an data structure with  256X256 block of the map on each z level
2. for each block in the map recursively split recursively into 4s according to number of directions you can travel.
3 . after splitting zones up build a connection map between zones.
4. build a function to quickly decide which spot is in which zone.
5. add update scheme
6. you are set with many small Ns with best-case runtimes.

[JanusTwoface]

1. create an data structure with  256X256 block of the map on each z level

Why on each z-level? As NW_Kohaku was talking about, it would be nice to treat the z-axis equivalently (or at least weighted) to the x and y for people that build vertically. (And I'm sure he's not the only one).

2. for each block in the map recursively split recursively into 4s according to number of directions you can travel.

So... a quad tree.

5. add update scheme

This is the hard part. How/when does this run? This has to be more efficient then the current pathfinding we have, otherwise it's not worth changing.

[Nikov]

I'd like to be able to paint hallways similar to high traffic zones, which dwarves path to, path along ignoring side passages and even perfectly open space, then path off of once they are at the closest point to their destination. Of course I'm not a computer science person and better methods might exist, but that was the idea I had a while back to make haulers go around the dining room. Naturally painting vertically is an option.

And +1 for defining rooms with vertical space. I want my greathall's vaulted and engraved 5z ceiling to count for something.

[Granite26]

As far as value and dwarf perception go, multi-z level rooms make sense.  It doeen't make sense to consider high ceilings from a pathfinding perspective.  Hell, you should be able to define your grand dining hall with a ramp to the king's table, a 5 z level ceiling, and a balcony area overlooking the whole thing with stairs in each corner, all as one room from the dwarfs' perspective.  That doesn't mean the pathfinder can't cut it up into 3 rooms from it's perspective.

[Niseg]

2. for each block in the map recursively split recursively into 4s according to number of directions you can travel.

So... a quad tree.

Cool ,it has a name - so i guess it's not as hard to implement if someone else thought about it.. I noticed there is a 3d version of it called octtree

5. add update scheme

This is the hard part. How/when does this run? This has to be more efficient then the current pathfinding we have, otherwise it's not worth changing.

it's not really hard if you go through the rules of how you make eache zone like a zone has to have 7  (open area ) or more dirrections or 3 or less  (path ,intersection,dead end). you can either update as dwarves go along it or run zone updates in the background.

The general idea is to reduce the number of nodes  while also segmenting pathing in a way that the size of the map would not affect the game . performance. if for example you got a map size

small example get from O to X current  pathing would  take 9 steps and won't gain much other than dividing the movement into smaller steps

Code: [Select]

#########
###+X+++#
O##+###+#
+##+###+#
++++++++#
#########


Code: [Select]

A . B .
##.###.####
##.#+X.+++#
O#.#+#.##+#
.......   C
+#.#+#.##+#
++.+++.+++#
##.###.####
 D. E .

. separator
O start position
X end position
# wall
+ floor

Weights 
A 1 (can be merged with D)
D 2
E 3
C 6
B 2

path  we are looking for is A to B and best path is A->D ->E ->B and A * will find it pretty fast . the number of steps are 4 while we do have the intermidiate steps inside the small zone which usual have very short runtime. If we merge A and D we would reduce main search making it  length  3 . This will change the execution (from 9 step search then 9 steps) to
frame 1 : search for path from A ->B , returns A-> D ->E->B then search for path to A->D then move 1 step south
frame 2:  when reaching D search for a path to E then move south east
frame 3: move east
frame 4: search for a path from E to B then move step north east
frame 5: move north
frame 6 : search for a path to destination move ne

Due to the fact this  example is very small the gains would be very minor but if instead of 9 steps you need to move 100 steps You will gain a lot.  If this 100 step path would be divide it into 10 step initial search (smallneighbor list ),  then 9 steps  walk then another 10 step search  etc it would be a lot less CPU than doing a 100 step search and then going on the path. This will also save the big penalty on  path recalculation  . The cache penalty on long paths is also pretty bad especially when changing Z levels.

 
I can probably implement some kind of javascript simulator to do this on map data . I like JS cause it runs on every platform and it's easy to access.

[Starver]

So, this article on memristors and maze solving came across my feeds a few days ago. The paper it reports on is a surprisingly easy read (and the pictures at the end are enlightening), so consider reading it.[...]

Sorry, coming late to this particular thread, and still working through, but... as said immediately afterwards (and I don't think disproved, later on, otherwise I'm going to look silly) this is a real-world parallelisation that doesn't map well to a computational environment.  It can be emulated (in a multi-core situation, even, which might speed it up, minus overheads) but an arbitrarily large array in simulation would need an arbitrary amount of parallelisation to do much the same 'instantaneous' solving as the real-world construct does.

Quantities of various End-Encoded DNA single-strands can be mixed up to make a massively parallel 'calculator', from which all 'valid paths' (sets of suitably attached DNA strands that feature any required intermediate points, and both required end-points) can be extracted and then the best path (the shortest composite strand) can be itself be extracted from these solutions (doubly-so) to 'read' the solution.

And there's another good way of solving various pathfinding problems, with string.  Lay out a 'net' (in several senses of the word) composed of suitable lengths of string knotted together with the others at the correct node.  Grab your start point with one hand.  Grab your end point with the other hand.  Lift and pull tight.  The taught length of en-knotted string-lengths is your best path.  Set back down on the floor (avoiding tangling) and you can repeat the process for any other path.  Or, if you haven't inter-twined disconnected sections, discover if a path is impossible by having two (or more) nets separate out when you lift and pull.

But the process of emulating these in a computational environment isn't trivial.  The quickest solutions might indeed abstract the process back into the non-trivial pathfinding solution (rather than try to model each and every catenary and dangling thread under gravity, or going through a whole Brownian Motion thing for the DNA example).

But I've still got to read more thread, so I shall see how the conversation progresses.

[Starver]

This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.

I'd just like to s/bug/condition/ in this statement.

While it may not be the absolute optimal method (as often argued) it's a consequence of the current condition of the DF universe.  You might as well say that the Creator[1] created a 'bug' that one cannot travel faster than light in our own universe.

Of course, there's something to be said about the analogy that the dwarfs might still be running on chemical reaction rockets instead of some kind of future-tech which would allow us to more easily approach c in interstellar travel.  And perhaps there is an optimisation available within the constraints of the physical universe that would allow us to make FTL/instantaneous travel, much as there might be a trivial (e.g. constant-time, and short at that) function available to pathing Dwarfs so that they don't have to think so long (in player-time) before finding their best path.  But in both cases there needs to be some great new insight about the nature of space/information before such solutions can be considered.

And despite my machine being not particularly the best (worldgen and fort-save times are far longer than I'd like) I can't honestly talk about "crippling".  I tend to run complex forts (without any particular nod towards meta-gaming the known pathing optimisations that are possible) and the number of free stones (not locked away) is often large in my various midi-projects (verging on mega-).  Perhaps my expectations aren't high enough.  Perhaps the general slowness of other aspects (unnoticed by me, as I'm used to it) means that I'm happy with the slowness of path-recalculation.

About the only time I properly notice pathing-lag is the significant pause when traders or immigrants arrive.  (Which also usefully can clue me in on more sneaky invaders, and perhaps might let me meta-game a preparation for such nasties visible arrival, if I let myself.)  But that pause is far less than the seasonal-save pauses, even then.


This is not to say that I'm not interested in finding a more optimal solution (note my contributions in that other thread).  And apologies if all I've put towards this thread, so far, is objections.  I don't want to repeat various bits (of my own, or of others) of the other thread that I consider constructive, because that would indeed just be repetition.



[1] If any, and I've stated my beliefs on that enough times not to want to divert this thread in that direction.

[Artanis00]

This isn't game play or meta, but proper game design. The only reason butchering cats and building doors everywhere is necessary right now is because it's a workaround for a bug that cripples game play.

I'd just like to s/bug/condition/ in this statement.

While it may not be the absolute optimal method (as often argued) it's a consequence of the current condition of the DF universe.  You might as well say that the Creator created a 'bug' that one cannot travel faster than light in our own universe.

I don't think that sed is appropriate. This is definitely a bug.

To play a more accurate analogy, it would be as though time itself slowed down when too many people gathered in a city. Unlike the speed of light issue, which we can definitely measure in-universe, such an effect would be as unmeasurable to us as the pathfinding slowdown would be for our simulated dwarves.

Alternatively, I should be able to mod my dwarves to have [SPEED:-1], which would cause them to appear at their destination before they left. In fact, in the time prior to this event, you should see before-images of the dwarf walking backwards towards the dwarf, and upon merging both disappear (the dwarf having arrived at the destination several seconds ago (That's right, tachyon dwarves (But I digress))). I'm not entirely sure what this thinking does to crafting. I'm having flashbacks to the backwards time episode of Red Dwarf, though.

And despite my machine being not particularly the best (worldgen and fort-save times are far longer than I'd like) I can't honestly talk about "crippling".  I tend to run complex forts (without any particular nod towards meta-gaming the known pathing optimisations that are possible) and the number of free stones (not locked away) is often large in my various midi-projects (verging on mega-).  Perhaps my expectations aren't high enough.  Perhaps the general slowness of other aspects (unnoticed by me, as I'm used to it) means that I'm happy with the slowness of path-recalculation.

To be completely honest myself, I tend grow bored of a fort shortly after initial setup; right when I start plotting out the MOST EPIC FORTRESS EVER CONCEIVED™ and remember that building large (complex and therefore interesting) structures is still a PITA, and thus am rarely affected by this myself.