Simulating separation forces amount n bodies

Question

I'm writing a simulation for little creatures that walk around the screen. One issue I'm having is that they'll get too close sometimes - I figure that one way to solve this is to have a certain threshold distance, and when any two creatures get closer than this distance, a force will push them apart.

Before I implement this, however, I was wondering if there are any known algorithms for this besides the brute force solution.

I've been researching a few different algorithms, and one of note was the Barnes-Hut algorithm, which runs in time - however, I'm not sure if this would work for this problem.

Any help is appreciated

Answer 1

Barnes-Hut and variations are the common way to do this, but I would not implement the full algorithm for your use case because it seems overkill. I would probably just divide the plane into a square grid, say 20 x 20, and maintain a set for each cell with all the creatures currently located within the cell. Then for each creature just look into its cell and the 8 (or 5 at the sides or 3 in the corners) neighboring cells and use a force that drops to zero within the length of one cell.

There is an obvious trade-off - a finer grid means less pairs of creatures to consider but you will then have to move them from cell to cell more often. A cell length smaller than the range of the force is useless because you will not only have to consider the 8 neighbors but cells beyond them that are within the range of the force.

Answer 2

Gridding out your bodies into a tree structure, use a quadtree for 2D and octree for 3D. The idea behind O(n log n) algorithms is to make log n comparisons for every body instead of n comparisons. If your bodies are clustered into groups, you can compute the average mass and position of a cluster. Rather than having a force from each of the bodies in that group acting on a body, a single combined force of an equivalent pseudo body acts on another body. I believe this is the idea behind Barnes-Hut.

You will need a fast algorithm to identify your clusters, determine when you can sacrifice simulation accuracy for speed (it may be okay to group Jupiter and its moons as a single pseudo-body to calculate the gravitational force on Earth. It probably isn't okay to group Jupiter and Saturn as a single pseudo-body to calculate the gravitational force on Earth)

The larger you let your clusters get, the less accuracy you have. However, larger clusters also means fewer body-body comparisons that need to make. You may also want to optimize clustering that can be reused for other bodies. Grouping all of the inner planets with the Sun may be okay to compute forces on all outer solar system bodies.

Start with the naive O(n^2) approach first before you venture into the complex O(n log n) implementations. When you're ready, there's a lot of great literature on the web about n-body simulations.