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:
(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:
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:
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.