I am writing a game in which a character moves on a randomly generated map in real time (as it turned out.) This leads me to an interesting problem of data structures. The map is created as it appears in the circle around the symbol (maybe 20-60 tiles), so where there is data, it is very dense, and that's all in the grid. Where there is no data, there can be huge, non-degenerate spaces. The character could walk in a huge circle, for example, creating a ring of plates around a huge empty space.
A simple matrix would create a huge amount of unnecessary overhead and waste a lot of space. Typical BSPs, however, appear to be such that they can lead to a huge drop in performance due to the dense, meshy nature of the data.
What are you offering? Matrices - quadrants - some hybrids of two?
source
share