I'm writing a game in which a character moves around on a randomly generated map in real time (as it's revealed.) This leads me an interesting data structures problem. The map is generated as it comes into view, in a circle around the character (probably 20-60 tiles) so where there is data, it is very dense, and all in a grid. Where there's not data, though, there could be huge, ungenerated spaces. The character could walk in a huge circle, for example, creating a ring of tiles around vast empty space.
A simple matrix would create massive amounts of unneeded overhead, and waste a lot of space. Typical BSPs, though, seem like they would cause a huge performance drop because of the dense, grid-like nature of the data.
What do you suggest? Matrixes - quadtrees - some hybrid of the two?
See Question&Answers more detail:
os 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…