Space partitioning

[olofson]

Problem

The 0.7.x engine still uses the original XKobo design; all objects are kept in arrays (one for enemies, and one for player bullets) with no space partitioning or other optimizations. This means every object needs to be checked when rendering, and more importantly, we rely completely on the fact that there is no enemy-to-enemy collision checking, which would require all-to-all tests.

Solution

Since we're dealing with small and/or wrapping maps, the most straightforward solution is probably to subdivide the map into suitably sized tiles, and keep objects in per-tile doubly linked lists.

Z-order - The non-trivial trivial problem

To preserve Z order when rendering, so they don't "pop" randomly when moving across tiles, we need some extra logic. They can either be sorted on the fly when rendering (potentially expensive, though we can probably arrange it so we don't have completely unsorted input), or we keep objects in a global linked list.

Hybrid: Maintain a Z-order sorted list or array of on-screen objects. Objects insert themselves in the right spot when the go onscreen, and remove themselves as they go offscreen.

Regardless of solution, we should probably guarantee unique Z-order for each object. For example, we can encode priority or layer in the upper N bits of a priority field, and reserve the lower bits for the engine to assign unique Z-orders within the respective group.

Another solution might be to organize objects in per-group lists, and just rely on position in the group list for group local Z-order. Simple and fast, but does not provide explicit control of Z-order within groups.