Print

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

[qwertyuiopas]

How about

-GetShortestPathLength  (for stockpile distances and stuff)
-GetFullPath (should be rarely used, but still exist)
-GetStep (As mentioned before)
-GetNSteps (Allows program to cache a few steps at a time)
-GetLOSSteps (Gets the steps between the unit and where the path leaves LOS. This would be closest to real life, since I doubt you think "Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. " When all 4 are in the sime direction)

[Starver]

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

What I meant was "not sure how I'd do this Perlish statement in C-Code".  See "Persistent Private Variables" in the appropriate PerlSub perldoc for the mechanism I was employing.  In leiu of making it a global (i.e. ($main::<foo>) implementation or needlessly package/object-wide.  Sorry, minor distraction, that.

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.

Actually, I'd take some of that idea and think about the possibility of globally using "Just In Time" techniques.  For the origin in the far south, the mere hint of the destination in the far north should prompt the topmost layer of routing hierarchy to spew "move through zone immediately to north" as the lowest-definition necessity of routing.  If using a hierarchical zone (and meta^N-zone?) structure to the algorithm, one could easily buffer the detail of the journey until (at the latest) entry to the zone[1].  In a true 'real time' game, consideration would need to be given to using 'slack ticks' to get the backlog of future necessary workings precalculated so as not to pile up JIT requisitions, but minor lag-hiccups could be absorbed by DF, I'm sure, should things get complicated.  (Though "every tick, do a given proportion of queued pathfinding details" could be implemented without excessive management overheads, and could clear the still-to-do queues long before the JIT philosophy rquires it.)

But.  Whatever the system, it should be able to check its assumptions and not say "wander north, don't worry about the detail for now" when you get something like the typical 'megaprojecty' conditions where the map is cleaved by impassible terrain (Dwarfmade, natural or from player-led/hostile-presenced travel restrictions/reprioritisations) and a straight-mined tunnel has been helpfully comissioned by the player (and completed by the workforce) especially for this eventuality.  A meta-hierarchical system should handle that with grace, of course.


[1] Or, where zone transitions are N tiles wide, N tiles prior to the zone transition, in order to allow the foresight to to handle optimal zone transitioning.  This may be hwolly contained within the predecessor area, or leach into ones further back.

[Starver]

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?

Personally, I'm working on a testbed system of my own, having not yet grappled the published testbed system (also standalone, merely simulating[1] the general conditions of DF, not tapping into its code.  But this is to address one particular design feature of a pathing algorithm.

For the rest, I am theorising (some might say "pontificating") about various pathing issues being discussed.  Some of which apply to 'my' personal project, and some don't even apply to the collaborative work at hand.

(The trouble is, my brain works far faster than my hands can type code/explanations.  And, if I say so myself, I can type code and explanations very quickly.  If occasionally inaccurately.



[1] Simulating a simulation!  Ha!  I suddenly find my approach even more amusing...

[SmileyMan]

How about

-GetShortestPathLength  (for stockpile distances and stuff)
-GetFullPath (should be rarely used, but still exist)
-GetStep (As mentioned before)
-GetNSteps (Allows program to cache a few steps at a time)
-GetLOSSteps (Gets the steps between the unit and where the path leaves LOS. This would be closest to real life, since I doubt you think "Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. " When all 4 are in the sime direction)

Most of those things are just moving the GetNextStep call to various points in the algorithm by making assumptions about algorithm behaviour that the implementor may not wish to conform to.

However, the PathLength you mention is an important function for the engine.  It could be a method of the PathIterator concept.

[tomato]

How about

-GetShortestPathLength  (for stockpile distances and stuff)
-GetFullPath (should be rarely used, but still exist)
-GetStep (As mentioned before)
-GetNSteps (Allows program to cache a few steps at a time)
-GetLOSSteps (Gets the steps between the unit and where the path leaves LOS. This would be closest to real life, since I doubt you think "Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. Okay, next I must go that way for a step. " When all 4 are in the sime direction)

Most of those things are just moving the GetNextStep call to various points in the algorithm by making assumptions about algorithm behaviour that the implementor may not wish to conform to.

However, the PathLength you mention is an important function for the engine.  It could be a method of the PathIterator concept.

We're talking about interface and DF needs if someone wants to implement an algorithm for pathfinding they have to implement such and such functions, wants and whims have nothing to do with it.

Now, I've been thinking about the interface a bit lately, taking into consideration the way that DF stores its map internally and what it needs from the PF.

Movement maps
First thing, I don't think that the callback mechanism for detecting passability for tiles is a good idea - remember, the very paths we look for are directly influenced by it and to calculate it we would have to run it thousands of times. As such IMO the single tile in the map data that the library gets should be a bit field with each bit setting passability for certain type of transport, for example:

Code: [Select]

pool:
00000100
least significant bit - dwarfs
2nd - flyer
3rd - swimmer - water
4th - swimmer - salt water (do fresh water fish die in salt water?)
5th - building destroyer
6th - digger
etc.
up to 32 or 64 bits with dedicated bits for traders and siegers, pets, etc.

workshop: (hexadecimal)
30 30 30
33 33 33
33 33 30
the 2nd row and first 2 bottom fields are passable for dwarfs, flyers, building destroyers and diggers,
the top row and bottom right corner is passable only for building destroyers
we can use 64bit ints for 64 different kinds of movement. Now, if we want to get a path, we set a single bit in the bit mask and tell what kind of transport the creature wants and from where to where it wants to go.

To optimise, we can additionaly set cost of movement for creature type, in the above example, we could get a additional cost maps looking like this:

Code: [Select]

dwarf:
 2  2  2  2  2
 2  0  0  0  2
 2  5  5  5  2
 2  5  5  0  2
 2  2  2  2  2

flyer:
 2  2  2  2  2
 2  0  0  0  2
 2  2  2  2  2
 2  2  2  0  2
 2  2  2  2  2

building destroyer:
 2  2  2  2  2
 2 10 10 10  2
 2  2  2  2  2
 2  2  2 10  2
 2  2  2  2  2

the upside of this approach is that the algorithm doesn't know that 0x01 is dwarf and 0x02 are flyers, it's completely arbitral and thus portable. By using bitfields instead of ints we can get unlimited number of movement types.

miasma and shallow water may be represented by higher path cost.

Resource maps
The second thing is finding nearest x-thing, to do this, we need to know which square contains which resources.
To do this, we can get ID-s (32bit ints should be enough) and squares they are on.

For updates simple add() and substract() should suffice:

Code: [Select]

typedef coord_t int32_t;
add(coord_t[3] square, int ID, int count);
substract(coord_t[3] square, int ID, int count);
optionally functions for mass adding and removing

again, we not need to know that ID=10 are obsidian rocks, ID=14 are plump helmets and ID=20 are goblin axemen.

so, to find closest stuff the interface would look something like this:

Code: [Select]

coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);

Interface

I think, that the functions qwertyuiopas mentioned:

Code: [Select]

movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
have to be included.

GetLOSSteps() is optional, GetShortestPathLength() is findID()

Beside them, we need:

Code: [Select]

setDefaultMovementPenalty(movement_cost[32]) - sets default movement cost for different movement types
updateMapData(cubestartxzy, movement_mask[][][]) - takes cube of space, it's starting field and puts it to the movement graph with fields being movement masks
updateMapMovementPenalty(cubestartxyz, cost_type, movement_costs[][][]) - takes movement type and cube of space with movement cost as filelds in the cube

all coordinates should be signed to enable update only of parts of world and non uniform world.

[bartavelle]

I just discovered this thread, and like everybody I have suggestions and will not provide much work :p :
* this seem like a great idea
* it would be cool to have the first post link to something where the current work is. It looks that there is already stuff done (i just read the last 2 pages), but i'm not willing to parse 20 pages just to find it :/
* did anyone think about penalties for path going through creatures ? this is really important in DF

And for a not so great contribution : for the people who wonder how to cut the map in zones that would reduce the quantity of nodes to take into account, there are already others who solved this.

http://en.wikipedia.org/wiki/Binary_space_partitioning

[Starver]

* did anyone think about penalties for path going through creatures ? this is really important in DF

Yesno* (*delete as inapplicable).  When planning an arbitrarily long route, any creature you might want to penalise moving through (over/under/charge through with battleaxe whirring like a rotary mower blade) is almost certainly not going to be there when you get there.

It may be in the same length of tunnel, of course, and I suppose it could be factored in as a 'smeared-out' movement penalty if chained down in a tunnel (1/3rd penalty over each of three adjacent tiles, or 3x1/9th penalty if a 3-wide tunnel with it in the centre, etc) but that's a more complex thing to deal with than potential presence/absence of bridge/barrier by the time your agent finds its way to a transient pinch-point/dynamic landscape feature of some other kind.


OTOH, factoring in the level of traffic a corridor currently has (not tying down to any particular creature, but using the current creature occupation/transit details through a zone to discourage use of that zone) might result in intelligent (and 'SatNav with realtime updates'-like) traffic re-routing options that reduces such congestion.


And (of course) hostiles, the presence of least-favourite-vermin and miasmic outbreaks could modify the decision tree while searching for a path, to weight against certain pathing areas.  That may already be a considered point.  (Certainly a lot of the external links have this mentioned, so I suppose those working on this more actively/collaboratively have it in mind, even if it's missing from my own testbed, which currently is 'agent and landscape only'.)

[shadow_slicer]

First thing, I don't think that the callback mechanism for detecting passability for tiles is a good idea - remember, the very paths we look for are directly influenced by it and to calculate it we would have to run it thousands of times. As such IMO the single tile in the map data that the library gets should be a bit field with each bit setting passability for certain type of transport

The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).

I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.

Resource maps

I don't think something like this belongs in a general purpose pathing library. I think it should be enough if we have something like

Code: [Select]

cost_t estimatePathCost(Point source, Point destination)
which finds a reasonable estimate of the cost of traveling between two points without actually calculating the path. This could be implemented by finding the path cost between the zones containing the source and destination (which is cached).

Then the client can loop over all the items they want to consider and choose the shortest themselves.

Interface
I think, that the functions qwertyuiopas mentioned:

Code: [Select]

movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
have to be included.

GetLOSSteps() is optional, GetShortestPathLength() is findID()

I don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS!

[numerobis]

What A* needs of the graph is:
- iterate over the edges out of a vertex
- cost of an edge
- admissable heuristic for the distance between two vertices
At the moment, it doesn't seem like we need anything more for any of the extensions we've come up with.

It shouldn't be our job to determine how the graph is stored internally; anything that supports the interface should be acceptable.

What a game needs of our pathfinder is probably just:
- compute a path from s to t, returning a forward iterator over edges

[tomato]

First thing, I don't think that the callback mechanism for detecting passability for tiles is a good idea - remember, the very paths we look for are directly influenced by it and to calculate it we would have to run it thousands of times. As such IMO the single tile in the map data that the library gets should be a bit field with each bit setting passability for certain type of transport

The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).

Every direction, for every movement type!? What for!? If two adjectant tiles are passable for creature of type 0x01, then it can move there. Add ceiling as an additional level (with whatever cost for movement - or 0 for DF) and we have all directions covered. It would be nice to have a path finder this complicated, but for a game like DF, where maps have thousands of tiles already (and we will get additional z-levels in couple of weeks/months making it tens/houdreds of thousands) with houndreds of pathfinding entities and we simply can't allow ourselfs the privilege of such compexity.

Spoiler (click to show/hide)

so you'll get movement map like this:

Code: [Select]

33 33 33  - level
20 33 20  - ceil/stairs
33 33 33  - level below

with movement cost for a dwarf like this:
2 2 2
0 0 0
2 2 2


As for movement/cost - in 90% of cases the penalty will be exacly the same for each and every tile, movement cost different than default will be the exception, I see no problem with that (you just keep second 3d table with pointers for data about non default values - pointer=NULL - defaults).

I don't see a way of storing all that information without using gobs of memory. But if we simply use a call-back function, the client can calculate that information procedurally. This function doesn't have to be slow. Odds are if Toady implemented one for DF it would probably only consist of some modulo arithmetic, bit tests, and table lookups -- all of which is pretty fast.

still, pushing a 3D table through a single function call will be much faster, and this doesn't inform the pathfinder when the passability is invalidated. So we would have to run it over each and every field when map change occures. So if we have to get this data one way or another, why not force the programmer to give it to us in the first place?

Resource maps

I don't think something like this belongs in a general purpose pathing library.

In what game that needs pathfinding you don't need to search for nearest enemy or resource?

I think it should be enough if we have something like

Code: [Select]

cost_t estimatePathCost(Point source, Point destination)
which finds a reasonable estimate of the cost of traveling between two points without actually calculating the path. This could be implemented by finding the path cost between the zones containing the source and destination (which is cached).

Then the client can loop over all the items they want to consider and choose the shortest themselves.

And that's the problem: the application has to loop, if it has no idea which, for example - a stone, is closest, it may run our function thousand times and it still won't find really the nearest one (or one even close to). There are many situations when stones that are near in cartesian space may well be most remote ones. (even the ones that are in a 20x20x20 cube) and for a 50x50x50 cube you get 125000 calls. "oops!" (simple situation - each and every level mined, mason on a level with a stair case in far corner, with stones near it, you get 50x50x49 stones to check and you still don't find the closest one - the one 26 fields south and you get exacly the same situation as now, only a bit later with much bigger computational cost)

add to this the ability for player to select which exact materials the goods have to be made from and you get situation where a stupid legendary mason is a cause of milion of calls a second to our function

Interface
I think, that the functions qwertyuiopas mentioned:

Code: [Select]

movementVectors* GetFullPath(movement_type, beginningxyz, endxyz);
movementVector GetStep(movement_type, beginningxyz, endxyz);
movementVectors* GetNSteps(movement_type, beginningxyz, endxyz);
have to be included.

GetLOSSteps() is optional, GetShortestPathLength() is findID()

I don't think that these are really necessary at all. They can all be implemented by successive calls to GetStep or whatever. In fact if we implement GetStep as an STL-compatible iterator instead of as a function, we can use STL methods to implement each of them in a single function call. This means that they don't really add anything useful and complicate the interface. Remember KISS!

But this doesn't allow for the programmer to not make the creatures onmniscient - creature gets a path (it is saved in the creature), it tries to follow it, if it can't return to it in, let's say 4 steps (to allow passing other creatures in corridors) using simple A*(because a door it just got to is closed or cavern collapsed), it only then asks for another one.
But this is not as important as the way the map data is imported to the library and later updated

[Impaler[WrG]]

The problem is that you don't have to have a single bitvector for each tile, you have to have a bitvector for all 27 possible directions from the tile! This is necessary to implement stairways, adjacent floors, ramps, etc. without nasty special cases. Then we also need separate costs for each movement type, creature size and everything else (possibly for each direction!).

Yes we can have a terrain type bitvector for each tile AND a separate bitvector for connectivity to adjacent tiles.  To establish that their is an edge between two tiles first check the terrains are both compatible with the movement type which should be a simple &.  Then determine the direction type for one tile relative to the other, north for example and & that with the connectivity, then do the same for the other tile.

This will work for anything except movement that can pass though walls and floors, people have long theorized such a digger type ability.  This would probably be best handled with a different system.

As for edge costs, because were assuming a grid system the costs are going to be attached to the tiles and the edge cost is either the value from the tile being moved into or the sum of half the in and out tiles.  It should be a simple switch to change the behavior as well.

[tomato]

This will work for anything except movement that can pass though walls and floors, people have long theorized such a digger type ability.  This would probably be best handled with a different system.

My system solves it - a tile can be passable for a digger and be impassable for every other creature type (still using the bits I showed earlier) a tile with passability mask of 0x20

[Footkerchief]

Resource maps

I don't think something like this belongs in a general purpose pathing library.

In what game that needs pathfinding you don't need to search for nearest enemy or resource?

1. Determining a destination is a separate task from finding a path, and should be treated as such.
2. A general purpose pathfinding library can't determine the destination on its own, because it's not necessarily just "nearest."  It can involve lots of game logic, creature preferences, weird item requirements for jobs, anything.

[Impaler[WrG]]

Add ceiling as an additional level (with whatever cost for movement - or 0 for DF) and we have all directions covered.

I wouldn't want to treat the z axis differently but applying the same logic to each axis it would simply things a good deal, and I already have a very similar system in Khazad, but I'm not sure if it would handle diagonal movement well.

[tomato]

Resource maps

I don't think something like this belongs in a general purpose pathing library.

In what game that needs pathfinding you don't need to search for nearest enemy or resource?

1. Determining a destination is a separate task from finding a path, and should be treated as such.

Then what would be your solution for a lone stonecrafter on a level with stones that are as far as a ladder to higher and lower levels that are full of stone?

2. A general purpose pathfinding library can't determine the destination on its own, because it's not necessarily just "nearest."  It can involve lots of game logic, creature preferences, weird item requirements for jobs, anything.

if you have only few items that are very specific then you can easly iterate over them, ask for path length to each and every one of them and this way find the nearest one.

Problem starts when you have hundreds or thousands of items that are exacly the same - then the engine can't easly decide which is nearest (as with our lone stonecrafter).