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 mapsFirst 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:
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:
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 mapsThe 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:
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:
coord_t[3] findID(coord_t[3] starting_point, movement_t bit_mask, int ID);
InterfaceI think, that the functions qwertyuiopas mentioned:
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:
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.