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

Answer 2

I've been tackling this for the past month, and have come up with what I believe is a fairly good solution. It's not as fast as a pure matrix, but has the benefit of being infinitely extensible (within the limits of an int.)

Basically, it's a binary space partition which builds upwards (instead of downwards, like a quadtree.) If you write to a point outside of the currently allocated matrix space, it generates a larger node and expands. If a majority of a node's children nodes are allocated matrices, it will aggregate them into itself and remove their references. This means that the more well-defined boundaries you use, the better performance you get, as the more this structure acts like a matrix.

I've posted my code here, and will try and write some sort of demo in the future, and move to a better hosting site.

Don't hesitate to let me know what you think, or if you have any questions about it.