c# - Optimal High-Density Binary Space Partition for Grids

Question

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?

Answer 1

I am thinking of implementing something similar in my game that I am working on. I'm going to create a custom class that can be accessed like a 2D array ex. map[x][y] but the underlying datatype would be closer to a hashtable. Something like data[x.Value.ToString() + "," + y.Value.ToString()]

My game is fairly basic as my tiles will only ever be walkable, deadly, or unwalkable.

I'm interested in a more elegant solution though :D