Aah, I see! Obviously the asteroids in your game are static obstacles. Sorry, I missed that in the beginning and thought they were moving around, too.

I know the problem you've described in your rescent post. Most techniques only consider individual obstacles, but are not able to detect clusters that should be avoided as a whole. So an entity could be steered into a gap between two obstacles, even if there is not enough space between them.

An easy way to overcome this would be to always let an entity turn into the same direction as soon as an obstacle is found in front of it. This would be comparable with wall following behaviour. However, it will probably make the obstacle avoidance look less natural and intelligent. So presumably it's not an option for you.


Some mobile robots use vector field histograms for detecting obstacles around them. I don't really now whether this method could be utilized in a game environment, but an implementation could look like this:



The obstacles are projected onto the entities field of view (the black thingy). The FOV could be represented by an array. Each array index could be considered a sensor. By weighting and evaluating all sensors the most desired movement direction can be determinded. In theory at least. ; ) This method benefits from being able to handle clusters of obstacles.


A method I'm interested in for a while bases on projecting bounding boxes on a 2d plane. I'm not sure whether you could make any use of it, as it was designed to be used for moving entities on the ground. Basically you would project the asteroids' bounding boxes on an imaginary plane (as you don't have any floor to project on). You then would expand the bounding box projections by the hull radius of the avoiding entity. The overlapping projections form a graph. By following the most outer edges a path around an obstacle cluster can be found.



This technique can be used with arbitrary entity sizes. However, IMO its not that easy to implement. Probably something like a sweep line algorithm is required to handle all the line segment intersections in an acceptable time.

Ok, one last thing for today.
You've abandoned the A* algorithm because of the varying sizes of your space ships. However, you could use clearance based A* which takes account of entity sizes. Actually it's pretty simple:



This would also work in a 3d space of course. It should be noted, that the image above is only a simple example. Ships with a size value of 2 were not be able to fly through this cluster.


Well, no time left, sorry. : )