postmortem:
the open and closed lists are static arrays of structs allocated on the stack (IE local variables).
the number of open and closed nodes in each list is tracked.
init_astar_lists is simply setting num_open_nodes and num_closed_nodes to zero.
the lists use insert at end, and swap and dec count to remove.
the open list stores both x,z, and an id=z*collsion_map_size+x
the main function is:
init_astar_lists
while !quit
get_lowest_open &id
move_to_closed id
expand_neighbors id
.
extract_path
get_lowest_open does a simple for loop search of the open list array for the index with lowest f
in expand_neighbors i unrolled the nested for loops into eight explicit calls to expand_neighbor.
in expand_neighbor i combined the atomic operations such as add, remove, membership check, etc.
i left in the check for neighbor off edge of collision map, as opposed to using a border of closed nodes. it seemed to me that a border of closed nodes would increase the size of the closed list and therefore slow down membership tests. but this is only due to my implementation method. for some other method with faster membership tests, a border of closed nodes may be faster.
so expand_neighbor ended up looking like this:
if off_edge return
if in_closed_and_not_removed return
if in_open_and_not_removed return
add_to_open
in_closed_and_not_removed does the membership test. if the test succeeds and the node should be removed, it does the remove. it then returns a result, saying what it did.
in_open_and_not_removed works in a similar manner.
ints are used for f, g, and h, and h is just BBox distance to goal. i tried floats and sqrt(2) for diagonal cost and true 2d distance, its just slower.
the parents are stored in a 2d array the same size and scale as the collision map. and there's no need to initialize it.
extract_path pulls the path from the 2d array and stores it in a 1D path array, which is then copied to the entity's path array. it could be modified to extract directly to an entity's path.
the collision map system was modified to handle collision maps at arbitrary scales. collision maps are now generated at different scales, based on the diameter of the critter in question. so critters are always one square in size. obstacle radii are grown by 1 to account for critter radius when going around corners.
Astar uses the collision maps for passable/impassable node checks.
before astar actually runs, it does a number of checks:
1. if the start is in impassable terrain, it finds the closest open node and does LOS movement to there. this check may be unnecessary.
2. if the goal is in impassable, it finds the closest open node to the goal and does Astar movement to there. this can occur if the goal is a critter who seems to be in impassable terrain due to the collision map scale vs their size. IE a human of diameter 2 can move to what appears to be inside a rock on a collision map at a scale of 6.
3. it then gets the goal for the current collision map, based on the ultimate goal. this is basically a raycast to the edge, followed by an outwardly expanding edge search for open nodes on both this map's edge, and the adjacent map's edge. if the ultimate goal is in the current collision map, it simply returns the ultimate goal as the current goal.
4. if it can not find an open edge node for the current goal, it tries LOS. this case will only occur if the entire edge of a collision map is impassable. IE its ocean or impassable mountains. in such cases you're more or less screwed anyway. i mean if your target takes off on a raft across the ocean, there's not much you can do about it. especially if you're an animal that can't build a raft and give chase.
5. if the start == the current goal, either its at the ultimate goal or at the edge of a collision map, either way LOS is used to get the rest of the way, or to the next collision map.
if none of the above conditions is true, it runs astar out to a range of 50 feet. this is far enough to get the critter moving in the correct direction around large obstacles, even if it doesn't path all the way past them.
when following the path, if they are more than one node distant from node zero, they goto node zero, else they goto node 1.
optimization of real-time collision map generation at arbitrary scales may be called for.
further optimization of astar itself may be called for with a large number of active critters at once.
i'm currently running A* every update, which is probably unnecessary. it should only have to be run when the goal changes, or when they exhaust the nodes in their current path, or when they deviate drastically from the path for some reason.
notes:
1. don't forget that extracted paths are in reverse order.
2. collision maps at arbitrary scales meant i was dealing with three coordinate systems: world, collision map, and scaled collision map. this led to a bit of confusion as different parts used different coordinate systems. in the end i converted everything from world to scaled collision map coordinates, did all the astar stuff, then converted the results back to world coordinates.
3. i was quite surprised how just a few things like insert-at-end, swap and dec, unrolling the loops in expand neighbors, and especially combining the atomic calls in expand neighbor really made a big difference in performance. all my times are zero milliseconds now. i'm down to having to measure astar execution time in clock ticks.
