I have a game world which is 1000 x 1000 units (2D only) and each entity in the world is 1 unit in size. There are going to be lots of entities having to navigate around this world avoiding obstacles and finding their ways to targets. I have been debating which movement method I should use. Options I have thought of so far: Steering behaviours I like steering behaviours but also think they are little black-boxish and require a lot of fine tuning. On a related note I was thinking of using a Leonard-Jones potential function for obstacle avoidance. A* Definately going to be memory intensive but what about computationally? I have thought about schemes where only a certain amount of entities are updated each frame with a queue system to detirmine the next one to be updated. Anybody got any thoughts on these and any other recommendations?

A* will work better if the environment is complex. If you have to occasionally move AWAY from targets to get to where you want to go, steering behaviors will not work.

Usually, the best combo is to use A* on the macro level, break that path up into segments of waypoints and then use steering on the micro level to get around things that may interfere with you getting from one waypoint to the next. Again, so much depends on how cluttered your environment is.

Same as InnocuousFox said.

If you plan that your unit move along long paths (say, from (0,0) to (999,999)) think of deviding your grid into sectors and compute a rough path using sectors and then a finer path as soon as you reach a sector.

Hope this helps

Eric

Quote: Leonard-Jones potential

You must be a chemist.

Apart from the other units... are the obstacles static? I definitely agree that with many entities, you'll need a local avoidance behaviour that overrides any path following solution you implement. If you do implement a path following solution, then the question remains how to generate that path. Ultimately you have a tradeoff between offline computation + high storage versus online computation + minimal storage.

A* is useful for online computation of single source, single target paths and it can be extended to handle multi-agent pathing to different destinations, but it doesn't scale well with the number of sources and desinations.

Dijkstra's algorithm is optimal for finding all shortest paths between all pairs in a graph, but requires that you store this information if you want to use it as a basis for pathfinding.

You might want to consider using a hybrid roadmap method such as Rapidly-exploring Random Trees. Steve LaValle has a good book covering this (and there might even be an online draft copy still available, although it did go into print in '06 iirc so it might not be online still).

You might consider trying several different solutions and seeing which one works best on your specific problem... but of course that would depend on your time available.

Cheers,

Timkin