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.