... so I don't know what optimizations you are using that would get screwed with.
Actually, none yet. There's an Annotated A*, and an Annotated (Greedy) Best First, this could work quite well with them both... while I've made the path finder much faster, it still isn't fast enough to lift the node limit high enough to make it actually good (in terms of path quality), so abstraction is going to be needed.
Or maybe not... Whilst half way through writing the abstract map class, I had a brainwave, and completely rewrote the A* and Annotated Map. It uses more memory, but still very reasonable (if I did my sums right, 1.2 MB for a 256*256 cell map (a 128*128 Tile map (oh, I've renamed SurfaceCell to Tile btw)). I haven't timed it yet, the A* is debugged and works but the new annotated map it searches on is a bit screwy, and I haven't yet implemented the interface I need to get my debugging textures for it. The new annotated map replaces virtually ALL of the new stuff, the 'node pool' object and it's helper structures, the double marker array, pointer array, and the binary heap are all gone.
This hasn't been committed yet, I want to get the annotated map fixed first, so if you're going to look at any of the new stuff, just look at the AnnotatedMap, and ignore the A* in it. The initialisation method is the only thing that has changed greatly, and there's a comment in the old code explaining exactly what should be done, I finally got around to doing it
Add in some 'local repair' to existing paths, so once you have a long path, you keep it! if you get blocked, trim off the next 10 (or whatever) steps, and get a new path to there, and splice that into your old path. This should make it 'fast' enough for the size maps we currently deal with. Abstraction ultimately is still a must, I want bigger maps (and/or larger cell scale, which is effectively the same thing only it would make all current maps bigger too).
Too bad, otherwise, you could tell the pathfinder what your travel restrictions are (altitude limits, etc.).
I'm going to assume you've heard of influence maps, I was thinking it would be nice to have a 'generic' influence map, which could be the typical 'military strength' type, or anything else you cared to construct one for (favour high ground, not near buildings, etc). These could then be passed to the pathfinder with a search request, of course the hierarchical thing does make it a bit awkward, but I think we should try to figure something out...
... Among the things I did come up with, none of them were simple. It mostly involved the division of the map into hierarchical areas of increasingly smaller sizes, with 4 areas at the top, 16 below that, 32 (EDIT: I mean 64) below that, etc to some depth that was appropriate. ...
This is a bit like Hierarchical A*, the 'original' abstracted A*. You're controlling the division much more tightly but it's basically the same idea. I don't like the excessive layering myself, and suspect it wouldn't be much faster than standard A*, searching through all those hierarchies.
I have however decided to adapt HAA* to be more like this. I'm just using the abstraction technique from HAA* and using the result to guide the low level A* (ie, to provide better heuristics) in the same way HA* does. But I only want one abstract level, maybe two if we get really huge maps going, and the 'cluster' of low level cells would probably be 32*32, which I think will be fine, even that can be searched very quickly.
I guess the more I think about it, each node in such a tree would have to have an array of open paths that lead to another side described by the border cells (for the bottom nodes) or the border sibling nodes (for all upper nodes). I really need to look at your code to make sure I'm not duplicating any effort (at least in analysis, as I'm not planning on coding any of this any time soon), but here's the general idea:
Well, kind of... but I haven't committed that code yet... read on...
class AbstractNode {
// omitted
}
Now you're talking my language
Ok, here's what I have, you'll have to excuse me.. I figured this all out on graph paper and notepads while my computer was away, there was no prototyping, this is 'production' code....
// This will actually be 'packed' using bitfields...
struct Entrance {
int clearance;
int position;
};
struct Border {
// Entrances of max clearance for each field
Entrance transitions[FieldCount];
/* intra cluster edge weights
for vertical borders... for horizontal borders...
2 3 1
+------+------+ +------+ [0] = NW
| | | | | [1] = N
1 | C1 | C2 | 4 0 | C1 | 2 [2] = NE
| | | | | [3] = SE
+------+------+ +------+ [4] = S
0 5 | | [5] = SW
[0] == SW 5 | C2 | 3
[1] == W | |
[2] == NW +------+
[3] == NE 4
[4] == E
[5] == SE
*/
float weights [FieldCount][6];
};
class AbstractMap {
Border *vertBorders, *horizBorders, sentinel;
int w, h; // width and height, in clusters
AnnotatedMap *aMap;
public:
AbstractMap ( AnnotatedMap *aMap );
~AbstractMap ();
// 'Initialise' a cluster (evaluates north and west borders)
void initCluster ( Vec2i cluster );
// Update a cluster, evaluates all borders
void updateCluster ( Vec2i cluster );
// compute intra-cluster path lengths
void evalCluster ( Vec2i cluster );
bool search ( SearchParams params, list<Vec2i> &apath );
void getBorders ( Vec2i cluster, vector<Border*> &borders, Border *exclude = NULL );
// Border getters
Border* getNorthBorder ( Vec2i cluster );
Border* getEastBorder ( Vec2i cluster );
Border* getSouthBorder ( Vec2i cluster );
Border* getWestBorder ( Vec2i cluster );
};
So we have had essentially the same idea. I have no abstract node, I only store the borders, the maximum clearance value for each field along the border, what position along the border that is, and the edge weights to it's neighbour borders. I will also be caching results from searches in the abstract map, haven't given to much consideration to the exact nature of this, you've given me a bit to think about there actually
(ie, 'dirtiness' of those results).
The above is only partially implemented, the initialisation and evaluation functions... the search I haven't bothered with, as again, I need debugging textures so I can see what's going on, in this case I need entirely new ones, and a new interface, code in the renderer, etc etc etc....
Yikes... I'll be taking a break now
