Performance via Chunks

[lumi-a]

Currently, a lot of objects interact pairwise:

• Each planet interects with each {Asteroid, Ship}
• Each bullet interacts with each {Planet, Asteroid, some ships}

If we eventually expand the map to be much larger, containing many more objects, these interactions will kill performance. A solution to this:

Chunks are squares that tile the whole universe. Each object is assigned to a chunk, and when it moves outside of its current chunk, it gets assigned to a new one.

An object A interacts (gravity, intersection-checks) only with objects B that are in "close" chunks. In pseudocode, this might mean that, instead of the current interactions:

for A in planents:
    for b in ships:
        a.interact(b)

we would have something like:

ADJACENT = [(-1,-1),(0,-1),(1,-1), (-1,0),(0,0),(1,0), (-1,1),(0,1),(1,1)]
for A in planets:
    adjacent_chunks = [A.chunk + v for v in ADJACENT]
    for b in get_ships_in_chunks(adjacent_chunks):
        a.interact(b)

The size of the chunks would have to be chosen appropriately, of course.

Chunks would change the way gravity acts: Originally, gravity does always act between two objects, no matter how far apart. With chunks, it'd only act between two objects that aren't too far apart. The effect should be negligible, though, because gravity is proportional to the inverse of squared distance.

[Tim2othy]

I guess I'd only add this once there is some lag. Maybe we can implement everything we want without there being any problems in which case it seems like we don't have to bother with chunks.

A different idea is, just for gravity, if we had a simple conditional that checks how close two objects are and only calculates gravity if they are close enough? Would this increase performance? There would still be as many interactions as before, but with this feature sometimes only the distance has to be calculated instead of also calculating the gravitational force? If this would increase performance it seems super easy to implement.

[lumi-a]

Yes. In fact, we'd only calculate the square of the distance, and check if that is small (the same trick is already implemented in bouncing). Calculating the square of the distance is faster, as it doesn't involve a sqrt-operation. When gravitational-force is calculated in the end, we do need the distance, though.