Midgard, Recursive Bitfield
(2020-01-20)
Next up, providing the basis for an interesting world. Currently, the “grass” acts like a liquid, spreading out from its initial position. What I’d like is to have a field of grass that can grow outward from whatever location it is in. Machine learning agents in the world can eat the grass, deplenishing it the location of the agent.
I would like to have each tile of field be much smaller than the machine learning agents that wander around the world. This way, bulk statistics about the amount of food nearby will be accurate representations of the world, and can be sent to the agents as summary statistics. The problem with this technique is memory. If I store each tiles grassy/barren state as a single bit, a grid with 2^20 tiles on a side would take 128 GB to store.
Grass grows outward, resulting in large swaths that are covered by grass. Similarly, agents eat grass near them, resulting in large areas that have no grass in them at all. Therefore, we should be able to have a data structure that specifies large swaths where possible, and only stores the values of individual tiles where necessary. This will be similar to adaptive mesh refinement, used in many physics simulations. It is useful where the level of detail varies over several orders of magnitude, but full detail isn’t needed at all locations.
Each grid will be an 8x8 array of bits. This can be efficiently
packed either as an integer std::uint64_t or as a wrapper around an
integer std::bitset<64>. I choose the latter, to improve
readability of bitwise operations. Each grid also needs to have a
scale factor, indicating how many tiles are represented by it. At the
lowest level, each boolean value represents one tile. At the next
level up, each boolean value represents an 8x8 space. At the second
level up, each boolean value represents an entire 64x64 space, and so
on.
There are two mental models that I have been using to picture this. In a bottom-up approach, each (x,y) coordinate pair points to a single tile. That tile’s value is found in the smallest grid that contains that value, and exists. If a grid doesn’t exist, it means that that detailed level is not needed, and that the value exists in a larger scale grid. This model is useful when looking up the value of a particular point.
In a top-down approach, each grid is a view to paint onto a canvas. Grids with smaller scale are then painted on top of the existing grids, in order to create the final shape. This model will be useful when displaying the bitfield.
Each grid is 8x8 and therefore requires 6 bits to index, 3 for each coordinate. An address for a given tile can be generated by concatenating the address within each grid. This allows a grid address to be determined by selecting the appropriate 6 bits. Each grid can also be given a key from the value of all higher bits. To make this a unique key, grids with the same higher bits can be differentiated by the layer at which they exist. For example, it is possible for a grid with bottom-left coordinate (64,64) to exist at the lowest level, covering (64-81, 64-81) and at the next level up, covering (64-127, 64-127).
Each grid is stored in a std::map, addressed by this unique key. To
determine the value of any cell, each successively larger grid can be
checked until one is found that exists. The unique key can be
determined from the (x,y) coordinate of any tile that is contained
inside the grid, allowing easy lookups.
Setting a value is a little more complicated, because it needs to remove unnecessary details as it goes. First, the value is set on the lowest-level grid. If setting a value causes a grid to be entirely true or entirely false, then it is removed, and the value is passed to the next level up. If the lowest-level grid doesn’t exist, then it can be generated and added to the map.
Unfortunately, no animations this time, as the display portion of the code isn’t written yet. This is also the first section where unit tests were added, as they were essential in working out the kinks of the addressing system.