9 ms·
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 t
by vortico 5y ago
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.
- wyager 5y agoIsn’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?
- rhn_mk1 5y agoWhere 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 5y agoYes, 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.
- tozder 5y agoit 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.