Print

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

[Impaler[WrG]]

Thanks for the help slicer, I'll be working on your code today.  BtW did you get my MP about getting in touch via Skype or other IM?

[SmileyMan]

Putting on my TOGAF hat, I think some sort of glossary would be a good idea, so we can make sure everyone is talking about the same things when they say "zone", "cell" etc.  Some are obvious, but a lot aren't.

I got halfway through drawing out a plan for a hybrid pheromone/zone map system that would be quite lightweight.  No time for it today, but maybe finish off the paper code later in the week.

A few quick questions: How are we expecting calls from the program to the pathfinder to work?  Given that some critters may be moving towards a moving target, I'm assuming that it's a series of "I am at location X and I need to get to location Y, what is the next step I should take?" and the return value will be a direction in some format (sub-question: is there a standard format for these vectors?).  The primary goal is then to return from that call as quickly as possible, without returning an impossible move and without causing "waggle dance" or other atrtfacts.

[Impaler[WrG]]

Another excellent site with a very deep yet understandable guide to pathfinding

http://theory.stanford.edu/~amitp/GameProgramming/index.html

[Starver]

A few quick questions: How are we expecting calls from the program to the pathfinder to work?  Given that some critters may be moving towards a moving target, I'm assuming that it's a series of "I am at location X and I need to get to location Y, what is the next step I should take?" and the return value will be a direction in some format (sub-question: is there a standard format for these vectors?).  The primary goal is then to return from that call as quickly as possible, without returning an impossible move and without causing "waggle dance" or other atrtfacts.

Personally, I think the return call should be the entire path from current location to intended destination, and possibly some more jiggery pokery (as noted belote).  On an trip that takes 100 steps, a mythical beyond-theoretically-possible pathfinding alorithm that takes N cycles to work out the optimally short 'N'-step journey that must be taken, and tells the agent the next step, would need 100*101/2 cycles to get them to the destination.  And, in reality, we know that it's probably somewhere between N Log N and something truly exponentional, for a single N-step, which then gets added.  So, best to calculate a single path, once, and follow it.  At least until something tells you that a recalculation is needed.

Obviously, recalculation at each step of the way handles dynamic environments exceedingly well.  And also simplifies things in an 'intuitive' system where only the next step (or two) is queried, which would involved back-reference to rule out "been there, and it's blocked off" possibilities).  To that end, the additional 'jiggery pokery' could involve waypoints where conditions should be queried, or even (at a memory-mapping level) implementing memory pointers that mean that when obstructions are created/removed they can create an 'event'/interupt to be picked up by all relevent pathing agents, to force them[1] or encourage them[2] to re-evaluate their path.

This latter would reduce re-pathing needs, length of any particular repathing need[3] and act almost as if the omniscient repathing were being reassessed after every single tick.  Not quite, because unforseen new paths from multi-tile landscape destruction are among the trickiest things to consider (and probably not worth the trouble), although an event-initiated link to currently routing agents might also be considered when a new agent plans its own path and discovers not only the new and better routing possibility, but that it shares significant waypoints with those remaining in the currently travelling agents queue of intentions.  The triggered events can then prompt the more senior router to reassess their position, with most of the required calculation already done.


Of course, this is the omniscient solution.  Some people, I know, would rather it be reduced to discovery/trial-and-error.  And I certainly think that could be factored in, but not in a pheremone-style way.  An ant's nest has a whole mass of active agents, running their own instantaneous partial-path routing, not externally controlled by a solid purpose but creating an apparent purpose from the combined 'waveforms' of purposelessness within the hive mind and hive body.  I don't see enough of those aspects being sufficiently relevent to dwarfkind.


[1] Where a blocking affects the currently intended path, but allow them to remember this for point [2]...

[2] When a path segment opens that was previously blocked, or (if you want to get complicated) by some means remember "could have, if only" shorter viable paths prevented only by a temporary style of blockage.  By adding a little extra effort/information storage, it might even streamline travel through zones such as repeater-led cyclic barriers across a path.  And if you allow natives (and possibly, by experience, long-term transient entities like a multi-season beseiging force) this skill, but leave opportunistic thieves/fauna/etc to continue their current method of pathing, it could mean that the creation of a 'dynamic labyrinth' could be a viable means of 'defence by confusion'.

[3] Imagine wandering half way round the mountain to find that the area previously impassible from a straight-through route and needing the detour was now only passable via the straight-through route.  Something you might easily get if setting up a satelite 'watchtower' or outlying habitation/cafeteria specifically for certain resource-handlers.  The overhead of recalculation (and 'dwarf energy' in this (extreme) example could have been avoided if, shortly after they set off on their way round, there had been a 'psychic summons' bringing them back again to the now-opened direct route (before or after the original indirect route was shut off[4]).

[4] Technically, a shut-off before the official short-cut actually opening should trigger relevent "cannot reach, abandoning job" events.  But it's up to the player to work out how they want to synchronise the activities of blocking masons/channellers/etc with permitting miners/bridgers/etc.

[SmileyMan]

Returning the entire path works very poorly for a moving target (e.g. a meeting), and also means that if several dwarves are following a common path (e.g. trade-depot -> stockpile) then you have multiple memory copies of the same path.

Each critter has to make a call that says "What is my next move" - whether it makes that to its own stored copy of the path or to a pathfinding engine is largely irrelevant.  I'm not suggesting that the engine recalculate every path for every call, although we can program a reference engine that does that if necessary.  But the call to the engine should be (pseudo-typed):

Code: [Select]

DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination);
and everything inside there should be a black box to the client, returning DirectionVector in as few cycles as possible (averaged over many calls).

BTW - would you ppl like to work on this in Google Wave?  I've got a bunch of invites, so PM me your email address if you want one!

[Starver]

Returning the entire path works very poorly for a moving target (e.g. a meeting), and also means that if several dwarves are following a common path (e.g. trade-depot -> stockpile) then you have multiple memory copies of the same path.

Apologies, I meant to add that to the "advantages of a single move" side.  With the caveat that if it's converging paths (at least temporarily) the two pathers could be given event-driven instructions to pop the successively nearer destination locations of of each other, and if one is chasing the other considerations might be given to adding the 'done' movements of the latter to the former's path.  Worst case scenario is when the disinterested 'target' agent is moving in a topologically 'perpendicular' manner and the changes to the seeker's path are not simple splice-on/off functions.

Each critter has to make a call that says "What is my next move" - whether it makes that to its own stored copy of the path or to a pathfinding engine is largely irrelevant.  I'm not suggesting that the engine recalculate every path for every call, although we can program a reference engine that does that if necessary.  But the call to the engine should be (pseudo-typed):

Code: [Select]

DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination);
and everything inside there should be a black box to the client, returning DirectionVector in as few cycles as possible (averaged over many calls).

I see, so pathing is initiated by the GetNextStep function if there's no acknowledged (and irrefutable) path already in existence, but the next step merely shifted from the required path store (not sure what syntax your pseudo-code would use, but some sort of hybrid of a "state %path; $path{$agentID} = GetNewPath($src,$dst) unless (defined $path{$agentID} && !PathChangeNeeded{$agentID});" command that I might use in my Perl testbed's version of the above[1]) whenever possible.  With the PathChangeNeeded() function covering a variety of relevent sins...


[1] I've forgotten how I'd do this in the mainstream C-family of languages, to my shame.  Might also be "state", but it's so long since I've employed this particular trick of the trade.  Apologies if Perl syntax is similarly strange to you.

[shadow_slicer]

I'm beginning to agree with SmileyMan. An interface where only the next step is returned is more general than one which returns the entire path.

As for the interface, I think there would be more state required than simply the current location and destination.
Perhaps instead of returning the next step in the path, it should return a "path iterator" which it can use to find the next step.

If a method such as A* is used, the path can be completely calculated, and an iterator to that path can be returned. If a more dynamic or adaptive method is used, the iterator could actually calculate the next step. Further the iterator could implement Starver's jiggery pokery without the client needing to have any knowledge of the actual jiggery pokery involved.

If the destination changes, we could call something like "changeDestination(iterator, newdestination)" and get a new iterator for the new path. This would allow dynamic or adaptive algorithms to be used efficiently.

[SmileyMan]

It's C++, with CoOrdinate and DirectionVector being as-yet-unidentified types.

The iterator idea gives us the advantage that it gives a hint to the engine as to which paths are currently in use, so shouldn't be dropped from the cache.  The iterator should be valid as long as the destination didn't change.

That doesn't help us for moving targets, and if we just used the single function, it would involve the constant creation and destruction of iterators, which might be expensive.

However, we could have different functions so that we can optimise the calling code depending on whether we are aiming for a moving or a static target:

Code: [Select]

PathIterator GetFirstStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to static destinations
DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to mobile destinations
where PathIterator has an "increment" operator, and is convertible to a DirectionVector.

If we code that properly, the path finding engine can keep a register of the current PathIterators, and make sure that the nothing in the path cache will be dropped if it is on a current iterated path.

That might be quite an overhead to maintain though - you could achieve the same effect just by having the GetNextStep function and a sufficiently large path cache.  The tradeoff is memory optimisation versus performance optimisation, always a fun debate 

One other bonus of just having the GetNextStep function is that you can be vague at the beginning of a long path - how you implement this in code is up to you, but for instance if you are outside in the far south and you know you need to get to the far north, then you can tell the critter to start moving north, and get more specific the closer you get.  See my heirarchical coordinate system for details of why this might be useful, also moving targets again.

Back to the interface, I think the engine needs a "MapDataChange" function, which (ideally) the game could call when map data changes (would obviously require Toady's input), but in the meantime, critters could call when the direction specified in the return from GetNextStep was impassable.  You could use this as a very inefficient (in the beginning) way of building up the map data without having to read memory at all, or alternatively have a sub process which scans the map at intervals and checks for changes:

Code: [Select]

void MapDataChange(const CoOrdinate& Location, const bool IsPassable, const Cost& = 0);
or similar.

By just having two functions in the interface, the barrier to entry is very low (a raw A* uncached engine would be pretty easy to write as a "worst case performance" reference model), and a test program could be run up quickly; it also makes it easier for Toady to integrate into his code later on.

For something I've got no time to spend on, I seem to be spending quite a lot of time on this!   More fun than work though......

[shadow_slicer]

That doesn't help us for moving targets, and if we just used the single function, it would involve the constant creation and destruction of iterators, which might be expensive.

However, we could have different functions so that we can optimise the calling code depending on whether we are aiming for a moving or a static target:

Code: [Select]

PathIterator GetFirstStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to static destinations
DirectionVector GetNextStep(const CoOrdinate& CurrentLocation, const CoOrdinate& Destination); // for paths to mobile destinations
where PathIterator has an "increment" operator, and is convertible to a DirectionVector.

I was thinking something more like:

Code: [Select]

PathIterator path(const point& CurrentLocation, const point& Destination); //for all pathfinding
PathIterator changeDestination(Pathiterator currentIterator, const point& newDestination); //only used when destination changes
I think we will definitely need state for each active path. Otherwise it becomes impossible to use A* or other methods that need to calculate the entire path in one step.

If we code that properly, the path finding engine can keep a register of the current PathIterators, and make sure that the nothing in the path cache will be dropped if it is on a current iterated path.

It appears you are thinking of having a path cache that stores the entire path for all active paths. I don't think that storing entire paths would be very useful. While dwarves tend to go to and from nearby places, they almost never go to/from the exact same tile. The odds are the path would be broken by a topology change before it could ever be reused. And while we could use these full paths for path splicing, this becomes very complicated very quickly.

One other bonus of just having the GetNextStep function is that you can be vague at the beginning of a long path - how you implement this in code is up to you, but for instance if you are outside in the far south and you know you need to get to the far north, then you can tell the critter to start moving north, and get more specific the closer you get.  See my heirarchical coordinate system for details of why this might be useful, also moving targets again.

This can also be done quite easily with the iterator.

Back to the interface, I think the engine needs a "MapDataChange" function, which (ideally) the game could call when map data changes (would obviously require Toady's input), but in the meantime, critters could call when the direction specified in the return from GetNextStep was impassable.  You could use this as a very inefficient (in the beginning) way of building up the map data without having to read memory at all, or alternatively have a sub process which scans the map at intervals and checks for changes:

Code: [Select]

void MapDataChange(const CoOrdinate& Location, const bool IsPassable, const Cost& = 0);
or similar.

In the current code base the client creates a "grid" class which implements two functions:

Code: [Select]

cost_t edgeCost(const point& a, const point&b);
unsigned max(unsigned dim);
where max returns the size of the grid along dimension dim and edgeCost returns the cost to travel from point a to an adjacent point b. A cost of -1 is used to represent disconnection. You can use edgeCost(a,a)!= -1 to determine if point a is passable.

Then the client passes this grid to the library, which does stuff based on that.
For the cached pathing methods there is another function "registerChanged(const point &p)" which needs to be called for every tile that has changed.

[Impaler[WrG]]

I like the idea of creating a generic interface object that each agent would follow, it would maintain a link with the centralized manager which has the map representation and provides what ever sort of internal path searching or path representation is needed.  It would even allow more sophisticated orders, like fleeing and flocking.

[Nadaka]

You guys are planning on using A* or a variation right? For a moving goal where the goal is moving slowly (within a trivial number of tiles from its previously computed location), you can use the previously calculated path to seed the algorithm as its best first guess.

This will:
A: eliminate the cost of finding a valid path to optimize.
B: seed h(estimated distance function) with an accurate approximation of the remaining distance to reduce the amount of branching required to optimize the already known path.

You could even use the same method when recalculating paths to static goals after sanity checking to ensure the previous path is not blocked in order to find new paths that are shorter if desirable.

[dyze]

half of the stuff in this thread goes way over my head. the other half goes way way over.
are you guys working on actual df code, or are you just theorizing as of now?

[SmileyMan]

I was thinking something more like:

Code: [Select]

PathIterator path(const point& CurrentLocation, const point& Destination); //for all pathfinding
PathIterator changeDestination(Pathiterator currentIterator, const point& newDestination); //only used when destination changes
I think we will definitely need state for each active path. Otherwise it becomes impossible to use A* or other methods that need to calculate the entire path in one step.

In the current code base the client creates a "grid" class which implements two functions:

Code: [Select]

cost_t edgeCost(const point& a, const point&b);
unsigned max(unsigned dim);
where max returns the size of the grid along dimension dim and edgeCost returns the cost to travel from point a to an adjacent point b. A cost of -1 is used to represent disconnection. You can use edgeCost(a,a)!= -1 to determine if point a is passable.

Then the client passes this grid to the library, which does stuff based on that.
For the cached pathing methods there is another function "registerChanged(const point &p)" which needs to be called for every tile that has changed.

OK, the PathIterator with the ChangeDestination method is good, that's a clean single interface.

Should ChangeDestination be a method of the iterator class or should it be a method of the engine?  If it's an engine method, should it take and return a reference, allowing the engine to re-use the iterator (or create a new one), for maximum flexibility?

[Impaler[WrG]]

I'm writing up an interface to do just this.  I'm calling it MovementController, and it would act as the 'brain' of the unit with respect to all movement.  The Controller will know the units capabilities with respect to terrain and size and current location.  It can be set to different behavior states like following another agent, fleeing an agent, wandering aimlessly or going to a destination.  Each call to getMovementDirection call then returns the appropriate direction consistent with the behavior.

As for the system it will use a central PathManager which will store the Map graph/s.  It will act as a factory for MovementControllers and keep a link with all of them.  The PathManager will receive map-change updates and can then signal certain Controllers to change paths if desired.  It will also perform caching of paths.  The Controllers will request new paths from the Manager when their in need, though it will also be possible to request paths directly from the Manager.

[peterix]

Guys: I haven't read the whole thread, but I think you should consider some stuff.

1. the ant approach.
2. network routing protocols (real-world pathfinding)
3. space subdivision

So, you have agents (ants, packets... blah) running around, doing space subdivision as they go. One sub-part is equivalent to a router in a network. The network is a graph of nodes (routers) and connecting paths.
The obvious + here is that you don't have to recalculate the whole thing when a tile changes. It will get recalculated when the agents discover the changes, and the changes will be only local at first, propagating through the network as they become known.

Would make an interesting experiment I think