so i've finally begun the A* implementation for Caveman 3.0. i first played around with A* almost a decade ago. this time around, with my typical outside the box approach to things, i decided to try things a little differently.
to begin with, i'm working with a 300x300 grid type search area. once the code is complete this will most likely be changed to a variable sized search area.
instead of open and closed lists, i keep an A* map: a 300x300 array with f,g,h, and state: open | closed | neither.
for the moment, a separate 300x300 collision map has the obstacle data in it. but the two maps might be combined.
the only slow part is getting lowest f, which requires searching the entire grid.
so the idea to speed up that is to use an index system.
when a node is marked as open (added to the open list), it would be bucket sorted on f into the index system.
with a 300x300 area, the longest straight path is only 420, and a convoluted path might max out at 600 or so. so you would need perhaps 600 buckets. since multiple open nodes can have the same f value (working with ints here), each bucket would be a list.
for the lists i was thinking an un-ordered list with active fields. i figured insert a first inactive and set active to false to remove would be faster than insert at end and copy higher array elements down on remove.
when adding a node to the open list, you'd have to iterate thru that bucket's list to insert at first inactive.
when getting lowest f, you'd have to iterate through the buckets to the first non-empty one, then iterate though its list of nodes to the first active one.
storing the number of nodes in each bucket will speed up determining empty buckets. same idea might apply for first active and inactive node in a bucket, but maybe not. you have to sort or search at some point. same might also be true for first non-empty bucket.
nodes in the a* map and the index system would be doubly linked, IE a map node would have a reference to its index system entry, and its index system entry would have the coordinates of the node in the A* map. this would make operations like removal very fast.
if i can track first non-empty bucket instead of searching for it, then search for first active node in the bucket list is about the only slow part left.
its my understanding that the open list is the "frontier" nodes, and the closed list is the "interior" nodes.
the max number of frontier nodes would be the max size for a bucket list (worst case).
might take a bit of ram. i'm thinking have one A* map and index system, and just keep using them over and over for each entity. entities would store the paths that were the output of the A* system.
thoughts? comments? suggestions?