Indefinitely move objects around randomly without collision

Question

I have an application where I need to move a number of objects around on the screen in a random fashion and they can not bump into each other. I'm looking for an algorithm that will allow me to generate the paths that don't create collisions and can continue for an indefinite time (i.e.: the objects keep moving around until a user driven event removes them from the program).

I'm not a game programmer but I think this looks like an AI problem and you guys probably solve it with your eyes closed. From what I've read A* seems to be the recommended 'basic idea' but I don't really want to invest a lot of time into it without some confirmation.

Can anyone shed some light on an approach? Anti-gravity movement maybe?

1. This is to be implemented on iOS, if that is important
2. New paths need to be generated at the end of each path
3. There is no visible 'grid'. Movement is completely free in 2D space
4. The objects are insects that walk around the screen until they are killed

Answer 1

A* is an algorithm to find the shortest path between a start and a goal configuration (in terms of whatever you define as short: common are e.g. euclidean distance, cost or time, angular distance...). Your insects seem not to have a specific goal, they don't even need a shortest path. I would certainly not go for A*. (By the way, since you are having a dynamic environment, D* would have been an idea - still it's meant to find a path from A to B).

I would tackle the problem as follows:

Random Paths and following them

For the random paths I see two methods. The first would be a simple random walk (click here to see a nice 2D animation with explanations), which can suffer from jittering and doesn't look too nice. The second one needs a little bit more detailed explanations.

For each insect generate four random points around them, maybe starting on a sinusoid. With a spline interpolation generate a smooth curve between those points. Take care of having C1 (in 2D) or C2 (in 3D) continuity. (Suggestion: Hermite splines) With Catmull-Rom splines you can find your configurations while moving along the curve.

An application of a similar approach can be found in this blog post about procedural racetracks, also a more technical (but still not too technical) explanation can be found in these old slides (pdf) from a computer animations course.

When an insect starts moving, it can constantly move between the second and third point, when you always remove the first and append a new point when the insect reaches the third, thus making that the second point.

If third point is reached     Remove first     Append new point     Recalculate spline End if 

For a smoother curve add more points in total and move somewhere in the middle, the principle stays the same. (Personally I only used this in fixed environments, it should work in dynamic ones as well though.)

This can, if your random point generation is good (maybe you can use an approach similar to the one provided in the above linked blog post, or have a look at algorithms on the PCG Wiki), lead to smooth paths all over the screen.

Avoid other insects

To avoid other insects, three different methods come to my mind.

• Bug algorithms
• Braitenberg vehicles
• An application of potential fields

For the potential fields I recommend reading this paper about dynamic motion planning (pdf). It's from robotics, but fairly easy to apply to your problem as well. You can just use the robots next spline point as the goal and set its velocity to 0 to apply this approach. However, it might be a bit too much for your simple game.

A discussion of Braitenberg vehicles can be found here (pdf). The original idea was more of a technical method (drive towards or away from a light source depending on how your motor is coupled with the photo receptor) and is often used to show how we apply emotional concepts like fear and attraction to other objects. The "fear" behaviour is an approach used for obstacle avoidance in robotics as well.

The third and probably simplest method are bug algorithms (pdf). I always have problems with the boundary following, which is a bit tricky. But to avoid another insect, these algorithms - no matter which one you use (I suggest Bug 1 or Tangent Bug) - should do the trick. They are very simple: Move towards your goal (in this application with the catmull-rom splines) until you have an obstacle in front. If the obstacle is close, change the insect's state to "obstacle avoidance" and run your bug algorithm. If you give both "colliding" insects the same turn direction, they will automatically go around each other and follow their original path.
As a variation you could just let them turn and recalculate a new spline from that point on.

Conclusion

Path finding and random path generation are different things. You have to experiment around what looks best for your insects. A* is definitely meant for finding shortest paths, not for creating random paths and following them.

Answer 2

You cannot plan the trajectories ahead of time for an indefinite duration !

I suggest a simpler approach where you just predict the next collision (knowing the positions and speeds of the objects allows you to tell if they will collide and when), and resolve it by changing the speed or direction of either objects (bounce before objects touch).

Make sure to redo a check for collisions in case you created an even earlier collision !

The real challenge in your case is to efficiently predict collisions among numerous objects, a priori an O(N²) task. You will accelerate that by superimposing a coarse grid on the play field and look at objects in neighboring cells only.

It may also be possible to maintain a list of object pairs that "might interfere in some future" (i.e. considering their distance and relative speed) and keep it updated. Checking that a pair may leave the list is relatively easy; efficiently checking for new pairs needing to enter the list is not.