Was thinking some more, and while the traditional "pheromone per task" design would seem obvious, the massive number of tasks would likely make this pointless.
But, if we re-imagine the map as a series of subdivisions, then we could make the pheromone data universally applicable, based on subdivision heirarchy.
A Small 2D exampleFirst, a standard Cartesian coordinate map
11 12 13 14 15 16 17 18
21 22 23 24 25 26 27 28
31 32 33 34 35 36 37 38
41 42 43 44 45 46 47 48
51 52 53 54 55 56 57 58
61 62 63 64 65 66 67 68
71 72 73 74 75 76 77 78
81 82 83 84 85 86 87 88
And here it is, as a binary subdivision map, divided xyxyxy
000000 000010 001000 001010 100000 100010 101000 101010
000001 000011 001001 001011 100001 100011 101001 101011
000100 000110 001100 001110 100100 100110 101100 101110
000101 000111 001101 001111 100101 100111 101101 101111
010000 010010 011000 011010 110000 110010 111000 111010
010001 010011 011001 011011 110001 110011 111001 111011
010100 010110 011100 011110 110100 110110 111100 111110
010101 010111 011101 011111 110101 110111 111101 111111
Critter 1, starting at (7,7) wants to move to (2,2). There are no pheromones
stored at (7,7), so it gets a path from the standard pathfinder, which will
trivially be 77->66->55->44->33->22
At each of those tiles, it places a marker, containing the final destination,
and the direction of travel. The destination is stored as the most significant
different bit pair from the current coordinate:
(7,7) -> 111100
(2,2) -> 000011
Stored: 110000 = (-1,-1)
(6,6) -> 110011
Stored: 110000 = (-1,-1)
(5,5) -> 110000
Stored: 110000 = (-1,-1)
(4,4) -> 001111
Stored: 001100 = (-1,-1)
(3,3) -> 001100
Stored: 001100 = (-1,-1)
(2,2) = Destination
Critter 2, starting at (6,6) wants to move to (3,1). The subdivision coordinate
for (3,1) is 001000, and therefore the most significant bit pair from (6,6) is
110000. There is already a marker on (6,6) telling us how to move to 110000, so
we don't need to go to our expensive pathfinder. The movement goes as follows:
(6,6) -> 110011
(3,1) -> 001000
Search: 110000
Found: 110000 = (-1,-1)
(5,5) -> 110000
(3,1) -> 001000
Search: 110000
Found: 110000 = (-1,-1)
(4,4) -> 001111
(3,1) -> 001000
Search: 000100
Not found!
So we go to the pathfinder for a path from (4,4) to (3,1), which will be something
like twice as fast as finding a full path from (6,6) to (3,1). The path returned will be
44->33->32->31, so we place markers as before:
(4,4) -> 001111
(3,1) -> 001000
Stored: 000100 = (-1,-1)
(3,3) -> 001100
Stored: 000100 = (0,-1)
(3,2) -> 001001
Stored: 000010 = (0,-1)
(3,1) = Destination.
Critter 3, wanting to travel from (7,7) to (3,1) will now follow markers all the way, and will make no pathfinder calls at all.
For each tile, it makes sense to store a limited number of markers in a cache,
depending on memory usage.
The nice thing about this is that while there is a chance of a sub-optimal path,
it will create quite naturalistic behaviour in that dwarves follow the paths other
dwarves make.
I hope the above makes sense. Given that it's obviously optimal in square areas
of power-of-two edge length, it might be best as a sub-routine for final delivery
within the (existing?) 64x64 regions, and then a macro path-finder can find routes
for the inter-region transport.
I'm sorry I don't have the time to stick some code behind this.
PS - I never did formal Computer Science, but if any compscis out there can tell me if this has been done before, that would be nice! If not, I henceforth name it the SmileyMan Algorithm!!!!!!