Further optimization of ComboZones

[mkafrin]

Dynamic waits, grid system (not to confuse with PolyZones grid), etc. What other ways can we trade off some memory for performance, since we have such low memory usage? Can we hit 1000 zones at 0.01ms?

[mkafrin]

Can the operation to determine what zones collide with a grid cell be improved by sorting the zones by their y coordinate at the start, and then using binary search to find the starting point to start testing zones based on their "minimum y", which would be their y - radius and stopping at their "maximum y" which would be y + radius?

[mkafrin]

The binary search, while smart, didn't work out because of something I missed when originally thinking about it. Sorting by the Y position then using binary search to the "minimum y" or "maximum y" doesn't work, because zones can have different radii. Therefore you could get to a zone that is outside the grid row, even if the zone after it is inside the row, or vice versa.

So instead, I just precompute and cache the zones in each row by doing the check at ComboZone creation, or whenever the AddZone method is called. This actually runs about as quickly as the sort necessary to do the binary search method, but removes the runtime cost of the search.

This cache turns the grid into basically a multi-layer spatial partitioning system. The first time the player/point enters a new grid cell, the zones inside of it have to be calculated. To do this, first the grid rows cache is accessed to get all the zones in that row. Then for each zone in the row, a circle to rectangle collision test is done to determine if the zone is in the cell. If it is, it's added to the grid cells table. After the grid cell generation is done, you can then return those zones in the cell to be used by isPointInside().

I chose a grid over a more flexible data structure like a quadtree because it's significantly simpler, avoids lots of table lookups (expensive in Lua), and can be generated on the fly when the user enters a grid cell, rather than all at once. The speedup this offers is roughly the amount of grid cells, minus some overhead. The default grid layout is 34 columns and 50 rows, meaning a speedup of roughly 1700. This assumes your zones are relatively well spaced out, and in reality will likely be cut down a bit due to zones clustering more than the purely even spread that this theoretical maximum speedup assumes. But even if we assume it's only 1000, it's still three orders of magnitude faster.

Commits: 22dca26a2e7123127c1f91e72f97c6b2b25424e3 6769b81e0dbf3141d69974894e543bd8eced3629 ae1c3f70817f89057fba6e828f971a6889af4bc7 e32dab9c49516089ee2ce3ed8b903b46e8f343f6