Probably has been looked at before (but I hadnt seen it)... (idea came from garbage collectors using generation sets to minimize overall cost) A* Candidates are usually thrown into a sorted 'open list' (BTree or HeapQ can be used..) and then best is pulled for next cycles candidate -- one big tree with some possibly having the worst falling of the bottom of a fixed depth tree. My proposed mechanism : Is it possible to use a generational 'cheap' sort O(1) to toss out those above a certain threshold into equally spaced buckets (each probably just a link list). With a fixed interval for the 'cost' the bucket would be an array. And a simple division would tell you which bucket to drop it in ( O(1) ) and a first interval result gets sorted immediately. Any nodes within the first cost interval are sorted into a 'best' BTree/HeapQ (with the usual sort processing cost log2(n) and as the first bucket empties the next bucke up is sorted and then the process continues (with all nodes fitting within the first 2 intervals now being sorted). If necessary a cheap function could make the interval pattern geometricly expand instead of linearly...) The mechanism is fairly simple but the problem is selecting the cost interval (and of course the bucket array would have to be some size adaquate to handle the worst case.) When the search pattern runs into a costly wall/blockage and starts moving laterally the cost increases without getting much nearer the target node. Depending on the ratio between node edge cost and move distance value the cost might stay the same as you move directly at the target in a largely unobstructed path. ( a starting point to chose the bucket interval may be a simple distance to target multiple.) Does the typical map search pattern allow this mechanism to save any significant amount of processing ??? Or do most of the new open list nodes stay mostly within the first interval (where they are sorted as normal A*) ??? Again the interval chosen is a problem (assuming there IS any potential for saving by doing a lazy sort on some portion of the nodes -- and having most of those never reached for tree sorting.)

An added thought considering current talk about multicores and multi thread usage :

Those buckets could be pre-sorted in background to be ready should the first 'best' interval set run out and the next generation need to have candidated picked from. The backgound bucket sorting would have minimal interlocking (the insert pointer being the one point).



That brings up the more general discussion of how can sorts (A* and others ) be (fine) parallelized effectively ----versus the obvious having different sort problems running in parrallel with only one thread per path search problem process (coarse parallelism).

Quote:Original post by losethos
Ummm. you talking about a radix sort?

No Im talking about some cheap way to sideline poor candidates, putting new ones with an evaluation value outside some quantum value into a bunch of buckets (bypassing a more costly sort for candidates which may never be picked).
The quantum value is related to the evaluation number range and thus doesnt often fit nicely into intergers. The buckets ranges may not even be linear - might be some power series.

Its somewhat the same idea but its tied more complexly into the primary sort (Tree or HeapQ) of the first quantum -- which can encompass more quantums as the path difficulty gets higher/indirect.

I have been looking at HeapQs and its likely simpler to increase the HeapQ size
(the nodes of bucket chains use more memory for the links). Some mechanism for handling node which fall out of a filled HeapQ would probably be used.

Im still investigation how you would predetermine a good bucket quantum -- too small and you quickly have to grab bucket sets, too large and you never use the buckets.

Just curious to see what your results were if you have been able to implement this.

Quote:Original post by Theoreticalstudios
Just curious to see what your results were if you have been able to implement this.

I spent time reimplementing the straigh A* with the HeapQ mechanism which is now working and decided whether to handle overflow off the fixed size heapQ.
Running sample maps (256x256) with random start/end points, its not unusual to have 2k-3K nodes in the open list, which memory-wise isnt that big (so if you make the heap large enough the overflow generally wont happen).

The problem remains with the quantum level generational system of finding the quantum value and then making the buckets work with the least amount of overhead. I havent found a systematic way to preanalyse the map to come up with a good value yet.

My HeapQ is only an array of pointers to the map array where the path cost data is also maintained, so when you sort-swap the HeapQ nodes you only swap a single data item. HeapQ size is N * 4bytes, so a 4K node HeapQ is only 16kB. Node data is in the map data array (which serves as the closed list) 64K nodes.


Link lists make for more data per node saved in a quantum bucket -- unless I do some trick like haveing a fixed sized data block of only 2 quantum buckets and having one grow up and the other grow down with no extra pointers required. Only 2 buckets kind of hamstrings the whole idea of the buckets.
The bucket 'sort' itself is trivial, so that part I will finish next.


So as I expected, getting the quantum value would be the major problem . I will try hand tuning a value to see how the data patterns run (to see if any appreciable numbers of open nodes really get excessive costs enough for them to be dumbed in the buckets. Map cost range and patterns of course effect the value of a useful quantum.