Spatial Indexing

I just spent nearly two days researching spatial indexing/partitioning. I'm trying to figure out what kind of structure I need to represent my game world.

Initially, I was trying to find a way to identify contiguous regions in my generated map. I wanted to select isolated rooms (some can be seen in the previous screenshot) so I could try to do something with them. Maybe run a tunneling algorithm to connect them up to the rest of the map, or just convert them into something decorative like pools of water. Started looking at running flood fills and counting cells but quickly abandoned that. I don't want to try to manually implement flood fill in Python, given that I'm already seeing a small slowdown in generating this tiny map. I wanted a more efficient option, and eventually got to numpy and scipy. These two libraries allow fast processing of multi-dimensional arrays, and these scipy functions (particularly label) look like exactly the kind of thing I need. It took me some time to understand how it works, and now I've got a pending task to refit my map representation to use numpy arrays.

With this, I started considering the possibility of treating the tilemap as essentially a 2D image. Each tile is pretty much just a pixel, so that should allow you to use all sorts of 2D graphics techniques to process a map. You could split a map into multiple layers, create masks, and treat them like sprites, blitting subregions onto a background. Something like that might be a way to support construction and terrain deformation in the game. What could be done with filters, shaders, and other such methods? I don't know much about those, so they're another subject to research later.

From there I went to 2D collision techniques, looking at ways to quickly find intersections among intervals and points. I found references to R-trees, kd-trees, quadtrees, segment trees, and interval and range trees. After many hours I've understood pretty much nothing of the technical aspects of how they work, but the latter three look like useful constructs. I found this series of articles which led to this Javascript library that implements streaming segment trees. At least 10 hours yesterday were spent attempting to port this library to Python, both because I wanted to experiment and because I was hoping to learn about the algorithm and the techniques used to make it efficient. I only got partway through before hitting a major roadblock, in that the library seems to make heavy use of some kind of run-time code generation which I have no idea how to translate.

Nobody seems to have written Python code that provides mutable 2D spatial trees. The best I can find seem to be the 1D intervaltree package and the insert-only pyqtree quad tree. Maybe that'll be enough. In the end, though, all of that is completely irrelevant to the roguelike. Consensus is that uniform grids and spatial hashing are generally sufficient for box intersection in a game. Constructing and maintaining a tree is only worthwhile in cases where you have objects of widely varying dimensions or if they're sparsely distributed. Still, this may be useful for a later project.

There's another significant challenge pending, namely making the map generation deterministic so that I can save its state. Even if I save the terrain layout of the map, I'm going to be using random minor variations in color and characters to texture the terrain. Modifying the terrain during gameplay will throw this off completely and result in blatant changes in appearance. I want to keep the terrain layout and appearance separate. That is, I just want to record that a cell contains grass; I don't want to store which of the 8 possible variations of grass tile the game displayed for that particular cell. And I just realized that I should be using a hash function here instead of an RNG. That'll fix the problem, assuming the function provides good distribution of values. Maybe save a random seed/salt value for each map, and then use a hash to combine that with each tile's position and terrain type to choose a variant.

...and now I've spent some hours reading about Bloom filters, cuckoo hashing, key derivation functions, etc., while looking for a suitable Python hash function. Interesting post here (links to a Youtube playlist with videos).

The step after this is going to be wilderness generation. I'll pause work on dungeon generation because I need to figure out map representation for towns and overworld terrain. I'm thinking that I'd like to have some z-level variation in surface maps, and I have an idea of how to visualize it, but that's something that needs to be prototyped. Giving it the right visual presentation will mean more trial-and-error color work, and I'll probably have to try out stuff like alpha blending and color interpolation.