On: The Powder Toy

[vortico]

Most powder models have O(n^2) interactions per step, so it's nontrivial to approximate it in O(n log n) while keeping it just as fun, especially when pushing the models to their limits.

[rhn_mk1 → vortico]

Where does the O(n²) come from? Is the number of neighbors unlimited? I was always under the impression that only a constant number of immediate neighbours counts.

[sdflhasjd → rhn_mk1]

Yes, it is linear, with a few small exceptions. The vast majority of element types in the game only check a fixed number of neighbours. Neighbour checking uses a 2-D map so it's constant-time.

[sandos → sdflhasjd]

Just randomly selected neighbours then I assume?

[sdflhasjd → sandos]

Most elements check the entire immediate neighbourhood at a taxicab distance of 1 or 2 (between 8 and 24 neighbours).

Not all elements check neighbours, An A+B interaction may have A checking for B or B checking for A.

[wyager → vortico]

Isn’t it automatically O(n log n) if you don’t have accurate gravity and you use some sort of special tree to find neighbors?

[tozder → vortico]

it is mostly linear and there are lots of optimisation opportunities. rapid movements like explosions are the exception. then again you have the gpu and the other cores, i rarely see below 60fps on my sand game and map size is the only limitation.