Indefinitely move objects around randomly without collision

Question 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.

Question 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.

Question 3

Look at this and this Which described an AI program to auto - play Mario game.

So in this link, what the author did was using a A* star algorithm to guide Mario Get to the right border of the screen as fast as possible. Avoid being hurt.

So the idea is for each time frame, he will have an Environment which described the current position of other objects in the scene and for each action (up, down left, right and do nothing) , he calculate its cost function and made a decision of the next movement based on this.

Source: http://www.quora.com/What-are-the-coolest-algorithms

Question 4

For A* you would need a 2D-Grid even if it is not visible. If I get your idea right you could do the following.

Implement a pathfinding (e.g. A*) then just generate random destination points on the screen and calculate the path. Once your insect reaches the destination, generate another destination point/grid-cell and proceed until the insect dies.

As I see it A* would only make sence if you have obstacles on the screen the insect should navigate around, otherwise it would be enough to just calculate a straight vector path and maybe handle collision with other insects/objects.

Note: I implemented A* once, later I found out that Lee's Algorithm pretty much does the same but was easier to implement.

Question 5

Consider a Hamiltonian cycle - the idea is a route that visits all the positions on a grid once (and only once). If you construct the cycle in advance (i.e. precalculate it), and set your insects off with some offset between them, they will never collide, simply because the path never intersects itself.

Also, for bonus points, Hamiltonian paths tend to 'wiggle about', and because it's a loop you can predict (and precalculate) the path into the indefinite future.

You can always use the nodes of the grid as knot points for a spline to smooth the movement, or even randomly shift all the points away from their strict 2d grid positions, until you have the desired motion.

Example Hamiltonian cycle from Wikimedia:

On a side note, if you want to generate such a path, consider constructing a loop through many points and just moving the points around in such a manner that they never intersect an existing edge. With some encouragement to move into gaps and away from each other, they should settle into some long, never-intersecting path. Store the result and use for your loop.