Print

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

[shadow_slicer]

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.

If you add an extra level to represent the ceiling, then you can't support vertical diagonal movement, which is already used for things such as ramps (or later jumping off of cliffs).

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).

While it's true that the penalty is likely to be the same for each tile, keeping a second table doesn't save anything. A 32 bit pointer is just as big as a 32 bit float.

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?

Pushing the table through would not be faster. Unconditional function calls are dirt cheap. Modern CPU's can execute them without even a single cycle of extra delay. Copying and maintaining a working set that does not even fit in L3 cache is expensive. With the function call, we have less memory overhead so we displace much less of the client's working set out of cache.

And that's still not mentioning the size of the table! If you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.

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

Honestly, I can think of quite a few. But not to dismiss your point, I understand what you're saying, and I admit that the problems seem quite coupled from a certain point of view. We definitely need to take into consideration the needs of users, but I feel that if we choose a simpler interface and let the client glue together the pieces he needs, the library will be much more flexible, robust and faster.

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)

First of all, loops are not slow --especially small repeated loops such as iterating over a list -- even if they have unconditional function calls. Everything is already in L1 and branch prediction will be near perfect, so this should be rather fast.

Second, once you have your interface, how would your method solve it? Would you do a breadth first search of the entire graph until at least one of the items is found? We could just as easily do this without storing the locations of items. Just provide a method:

Code: [Select]

Path EstimateCostToNearest(Point Start, Point[] Targets)


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.

That's also not true. However much information you want the creature to have should be reflected in the map you provide to the pathfinder. If you don't provide omniscient information, then the creatures won't be omniscient. It's up to the client to decide what they want.

Edit: fix quote tags

[Footkerchief]

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?

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).

I see what you're getting at, but the scheme you described:

Code: [Select]

coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
is not going to work, if ID simply refers to "object type."  Maintaining the client-side index would be extremely messy (does a given number refer to enemy goblins, or enemy goblin archers, or all goblin archers?  do left-handed redheads get their own ID?  what about thrones decorated with platinum but not with steel?) and it would be awkward for the client to request the nearest of an inhomogeneous set of objects.

There's no reason for the pathfinding library to care about object IDs at all.  It's much cleaner for the client to simply pass in a set of candidate destination coordinates and for the library to find the nearest of those coordinates and pathfind to it.  Obviously the client should first do some trivial pruning of the coordinate set.

[CobaltKobold]

Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.cost

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.

You could....take the wordsright out of my mouth.

26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions, but I already found a corner case I'd like preserving: swimming up waterfalls. solvable if swimming is permitted to go up.

I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)

[Footkerchief]

Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.

Even if that does happen, it makes sense just from a modularity standpoint to separate the concerns of generating a set of candidate objects and finding the nearest of them.  It won't ever be practical to rely on an "object type ID" as a substitute for an arbitrary set of objects.

[tomato]

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.

If you add an extra level to represent the ceiling, then you can't support vertical diagonal movement, which is already used for things such as ramps (or later jumping off of cliffs).

Ramps don't use vertical diagonal movement, you can't have such situation:

Code: [Select]

(cross section)
__#
##↑
ramps work just like stairs

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).

While it's true that the penalty is likely to be the same for each tile, keeping a second table doesn't save anything. A 32 bit pointer is just as big as a 32 bit float.

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?

Pushing the table through would not be faster. Unconditional function calls are dirt cheap. Modern CPU's can execute them without even a single cycle of extra delay. Copying and maintaining a working set that does not even fit in L3 cache is expensive. With the function call, we have less memory overhead so we displace much less of the client's working set out of cache.

IMO you're a bit over estimating the capability of CPUs, but that's not the point.
Most of the map is static, you displace client cache once, when loading the data, not every time it's called. And the data has to be stored somewhere - if we want the library to be opaque it needs to duplicate the data

And that's still not mentioning the size of the table! If you decide to devote 8 bits for each tile (not for each edge, each tile!) just to determine is this tile passable by movement type x, a 256x256x16 map would require 1MB of memory. If we add ceilings, it goes to 2MB. Note that this is a really small map. A 6x6 I am currently using is 288x288x32, which is 2.5 or 5 MB. Note that this does not include any cost information, and only supports 8 movement types. If you add terrain types or other features then this only gets worse. And, as you said the number of tiles on the map is only going to increase. If you get up to hundreds of z-levels with larger embark sizes, things get nasty very quickly.

since when 5MiB of memory for such huge tool is much?! We're trying to trade in memory for cycles, 200MiB would be nothing!

and a 200x400x200 map with 32 movement types and 2 non standard penalty values per tile on average would take only about 244MiB, and first: that's a huge map, second: the amount of other game info that's needed will still dwarf it.

Remember, I told that the pathfinding world doesn't need to be uniform, the engine has to push to the lib only the fragments that have known resources or pathfinding creatures

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

Honestly, I can think of quite a few. But not to dismiss your point, I understand what you're saying, and I admit that the problems seem quite coupled from a certain point of view. We definitely need to take into consideration the needs of users, but I feel that if we choose a simpler interface and let the client glue together the pieces he needs, the library will be much more flexible, robust and faster.

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)

First of all, loops are not slow --especially small repeated loops such as iterating over a list -- even if they have unconditional function calls. Everything is already in L1 and branch prediction will be near perfect, so this should be rather fast.

i said nothing of such sort, i know that loop is faster than unrolled loop on current CPUs, that was not the point
the point is repetitive calling of non tryvial function. As I demonstrated, for a 50 tile cube a legendary mason will cause 1 million calls per second to the function, if the function returns in 100 cycles (that's fast) we get a 10% CPU usage on a 2GHz CPU. And that's a single mason, for a non-optimal algorithm

Second, once you have your interface, how would your method solve it? Would you do a breadth first search of the entire graph until at least one of the items is found? We could just as easily do this without storing the locations of items. Just provide a method:

Code: [Select]

Path EstimateCostToNearest(Point Start, Point[] Targets)


For starters it would search the item on accessible areas, simple 3D floodfill would be better than the current DF implementation.

Then we could optimise for stuff that's in abundance - by storing additional info whatever an item of such and such ID is in reduced movement graph of the map.

Besides I'm suggesting an interface, not a solution. When the library has full picture of the situation, we can optimise the whole situation, not just find local minima.

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.

That's also not true. However much information you want the creature to have should be reflected in the map you provide to the pathfinder. If you don't provide omniscient information, then the creatures won't be omniscient. It's up to the client to decide what they want.

Edit: fix quote tags

it was just a simple use case of the API, not the only way to use it.

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?

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).

I see what you're getting at, but the scheme you described:

Code: [Select]

coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
is not going to work, if ID simply refers to "object type."  Maintaining the client-side index would be extremely messy (does a given number refer to enemy goblins, or enemy goblin archers, or all goblin archers?  do left-handed redheads get their own ID?  what about thrones decorated with platinum but not with steel?) and it would be awkward for the client to request the nearest of an inhomogeneous set of objects.

There's no reason for the pathfinding library to care about object IDs at all.  It's much cleaner for the client to simply pass in a set of candidate destination coordinates and for the library to find the nearest of those coordinates and pathfind to it.  Obviously the client should first do some trivial pruning of the coordinate set.

As I suggested - that's the interface for stuff that's in the hundreds or thousands, not single items.

For items that are uncommon, a function that takes all coordinates of them and returns the closest one would be better.

[CobaltKobold]

I suppose you're right. It'd be useful if you bstracted creatures to things like "ENEMY_MELEE" "ENEMY_RANGED" "OBJECTIVE" "MISC_CREATURE" (for obstacle/crawl purposes)by then you're probably going to need to check your dorf's preferences for hated/liked critters, so yeah.

[Footkerchief]

As I suggested - that's the interface for stuff that's in the hundreds or thousands, not single items.

For items that are uncommon, a function that takes all coordinates of them and returns the closest one would be better.

Ah, okay.  That makes more sense.

[numerobis]

if we want the library to be opaque it needs to duplicate the data

What data would need to be replicated?

[shadow_slicer]

Ramps don't use vertical diagonal movement, you can't have such situation:

Code: [Select]

(cross section)
__#
##↑
ramps work just like stairs

Are you sure about that? Because I've tested this on 40d15. No creature is ever on the top floor of a ramp. They all travel horizontally as well as vertically. Even wagons from trade caravans skip the top floor. If you put a dog on a chain next to a ramp, he can be on the top floor diagonal from the ramp, but never on the top floor of a ramp. If this is an item of dispute, I can take a screen cap.

IMO you're a bit over estimating the capability of CPUs, but that's not the point.
Most of the map is static, you displace client cache once, when loading the data, not every time it's called. And the data has to be stored somewhere - if we want the library to be opaque it needs to duplicate the data.

I think you're overestimating the memory/cache system of modern CPUs. If something is not in the cache, you're talking about a stall of hundreds of clock cycles. If you read any recent works on optimizing program execution speed, it's all about reducing the size of the working set and increasing locality.

Have you considered what sort of interface Toady currently uses for pathfinding? That's an important consideration if we ever hope he will ever consider adopting our library. I guarantee you he calculates the connectivity and path costs on demand. Separating that out to a function call from our library is one just additional instruction. Duplicating the data is tens to hundreds of megabytes.

Further, duplicating the data is entirely unnecessary, even for an opaque library. There are lots of opaque libraries that allow you to register callback functions. And that is all the getEdgeCost function is. Further this design adds significant flexibility: All we need is the costs from tile A to tile B. The client already stores this data and can calculate it easily. Why not let them decide whether they want to calculate it each time or store it. If you want, you can even write a wrapper around this API that stores its own copy of that data (and we could even include it in the library).

since when 5MiB of memory for such huge tool is much?! We're trying to trade in memory for cycles, 200MiB would be nothing!

and a 200x400x200 map with 32 movement types and 2 non standard penalty values per tile on average would take only about 244MiB, and first: that's a huge map, second: the amount of other game info that's needed will still dwarf it.

5MiB is a huge amount when it's sacrificed for no perceivable gain. I wouldn't mind using 200MiB of path caches if it was able to significantly speed things up, but that's a ridiculous amount just to obtain basic functionality. If you read the literature and look at other pathfinding implementations, none of them duplicate the connectivity map. Some (modern ones) even talk about pushing the path-finding footprint below 500kiB! On that 200x400x200 map you mentioned, the other method would only require 32 bytes(!) to achieve the same thing. Your design just doesn't scale.

The point is exactly that there is such a large amount of game information already, that we can't afford to add more. Each byte of memory in use by the pathing library is one that can't be used to improve the game.

Remember, I told that the pathfinding world doesn't need to be uniform, the engine has to push to the lib only the fragments that have known resources or pathfinding creatures

And how will the engine know which portions of the map are relevant to pathfinding? The library is supposed to be opaque.

Second, once you have your interface, how would your method solve it? Would you do a breadth first search of the entire graph until at least one of the items is found? We could just as easily do this without storing the locations of items. Just provide a method:

Code: [Select]

Path EstimateCostToNearest(Point Start, Point[] Targets)


For starters it would search the item on accessible areas, simple 3D floodfill would be better than the current DF implementation.

Then we could optimise for stuff that's in abundance - by storing additional info whatever an item of such and such ID is in reduced movement graph of the map.

Besides I'm suggesting an interface, not a solution. When the library has full picture of the situation, we can optimise the whole situation, not just find local minima.

A 3D flood-fill, also known as a breadth first search. You could also use a multi-destination version of A* (though you'd need to be careful to keep the fringe from getting too large). You could even use the cache to estimate the distance and only path the shortest ones. The point is that, for the vast majority of potential optimizations,  *what* the item is, is irrelevant. I agree with you (and a basic tenant of Information Theory) that the more information you have, the better and faster your estimates are. The problem is that speed is not the only goal, and if you're going to spend your memory on caches to help speed up pathing, you're better off storing partial paths or connections between zones than you are storing the location of all blue socks on the map.

[qwertyuiopas]

Here is an idea: Cache a single passability bitfield for each tile. Thus, it can discard impassable tiles completely in a few cycles, and only then use the more expensive edge test/callback.

That WOULD be a meaningful trade between memory and CPU usage.

[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

I guess people are also thinking we want:
- compute a path from s to the nearest node in T, where T is a small set
- compute a path from s to the nearest node that matches the predicate p
The last one doesn't support A*, but we can still do Dijkstra's algorithm (or BFS, but I'm not convinced that's really any better).

There's gnashing of teeth about function call overhead.  If it's a template library that we're building, the use of a function object is usually inlined, so it's not a problem.

[PencilinHand]

Footkerchief: So long as it's a 'pure' pf thing, yeah. But, eventually, pf = ai.
And remember the dwarven pathfinding truism: sock.value>>elephant.cost

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.

You could....take the wordsright out of my mouth.

26 directions though. When is it ever impermissible for a creature to move to where it already is? Also...I am fairly sure that flying or swimming are required to make a move to up-and-direction (without ramp, natch)
I'd suggest some manner of preclusions, but I already found a corner case I'd like preserving: swimming up waterfalls. solvable if swimming is permitted to go up.

I see why DF is loath to path fliers/swimmers right, now...for walkers, it's dead easy to see where you can go- up if on(up stair || up/down stair) && up(down stair || up/down stair) up+direction if on(ramp) && direction(wall), direction if directionIsFloored, and the downs are inverse of the ups (...actually, it won't check for the wall, as you're standing on it, leading to one-way ramps.)

I could think of one or two but they are fringe cases that are closer to a game mechanic than pathfinding.

EDIT: Here is a hint.

[Impaler[WrG]]

We know that DF itself has some major flaws in how it searches for items and while I think it would be good to eventually do some kind of search for items it would probably be best done by passing a 'success' function to the library.  Using a breath-first search outward from the start using the success function on each tile to see if the desired object has been found.  This would provide a good generic search.

If we wanted to get more sophisticated I'd go with a zone tagging scheme, the client (main game) can tag zones as having some abstract quality and the server will do a hierarchical search for the closest such zone.  If the placement of things like items sets a value in the zone then you can get a rough idea of ware the desired items are, even if the categories are broad and further checks need to be made it still rules out the vast majority of the map.

The idea of using a global list for rare items is also an excellent idea, a heuristic can be run on each one and the best one selected.  Its not as efficient when a great number of items are present in which case the breath-first search would be faster.  Doing the right kind of search for each request will be key.

[numerobis]

The idea of using a global list for rare items is also an excellent idea, a heuristic can be run on each one and the best one selected.  Its not as efficient when a great number of items are present in which case the breath-first search would be faster.  Doing the right kind of search for each request will be key.

Actually, I don't see why the pathfinder should be in the business of keeping that list.  I suggest two possibilities:
1. let the caller designate a range (begin and end iterators).  In each step, when computing the heuristic, A* will take the min over all destinations.

2. Or let the caller designate a heuristic function and a success function.  A* will call the heuristic, not knowing the destination; the game will take min over the destinations if it has a set of destinations, or just compute the single heuristic for one destination, or return 0 if it has no destination in mind.

Formulation 2 means we can implement a single A* routine and have it handle the case of not knowing where we actually want to go (in other words, we'd be running Dijkstra's algorithm).

BFS is a bit faster than Dijkstra's, but I feel that Dijkstra's is more the answer that people would expect.  Sure, we can provide BFS as another routine.

[Impaler[WrG]]

Actually you can turn A* into Dijikstra by simply using a heuristic and tiebreaker that returns zero so all you need is to write a one line rather then a whole new algorithm.  Yes we waste a little time adding zero over and over but its quick and easy.

As for ware a global item list would be stored, a client side store would probably be better and is indeed what I had in mind.  The client loops over it and calls to the the server to get the distance.