I am working on an floorplan application where I save elements on an infinite grid in a sparse manner. Specifically, I have the following Python class representing a sparse grid (basically a dictionary mapping coordinates to elements):
from collections.abc import MutableMapping
class SparseGrid(MutableMapping):
""" An n-dimensional grid saved in a sparse format. """
def __init__(self, dimensions=2):
self._dimensions = dimensions
self._grid = {}
def __getitem__(self, coords):
return self._grid[coords]
def __setitem__(self, coords, value):
if len(coords) != self._dimensions:
self._raise(coords)
self._grid[coords] = value
def __delitem__(self, coords):
del self._grid[coords]
def __len__(self):
return len(self._grid)
def __iter__(self):
return iter(self._grid.values())
def __contains__(self, value):
return value in self._grid.values()
def _raise(self, coords):
raise ValueError(f"Expected {self._dimensions} coordinates, got {len(coords)}: {coords}")
def coordinates(self):
return self._grid.keys()
def items(self):
return self._grid.items()
The grid can contain a lot of elements, but the number of different possible elements is small. As such I was able to colour-code them and I had the idea to save the elements to a PNG image, which should help a lot with file-size (over, say, saving them to a JSON dict or some similar approach). However, since the grid can conceivably span tens/hundreds of thousands or even upwards of a million of units in any direction, creating such an image in memory would be impractical, even if the end file size would probably still be small (since PNG is pretty good at compressing large areas of the same colour -- in this case black, representing empty space). As such, I decided to split the grid into chunks and save each chunk as a separate image.
from collections import defaultdict
from enum import Enum
from pathlib import Path
class Element(Enum):
WOOD = 150, 60, 50
STONE = 150, 150, 150
GRASS = 100, 200, 0
def __init__(self, r, g, b):
self.colour = r, g, b
class Plan(SparseGrid):
""" A sparse grid of `Element`s. """
def save(self, file, chunk_size=1024): # After combining logic is implemented, should probably start with size 1 or 2 here
file = Path(file)
file = file.with_name(file.stem + '_{},{}_{}.cnk')
chunks = defaultdict(list)
for x, y in self.coordinates():
chunks[x // chunk_size, y // chunk_size].append((x, y))
#TODO: Combine neighbouring chunks:
# for each size up to let's say 2048 (doubling each step), do a horizontal and vertical pass
# if chunks are neighbours, combine them into a single chunk
# keep in mind that this way the horizontal/vertical sizes won't necessarily be the same
#
# Is this actually worth it? It will result in a lot of empty space with bigger chunks ...
# I could use logic where I only combine if the resulting chunk is at least 50% full
# Save the chunks
for chunk, elements in chunks.items():
self._save_chunk(file, elements, *chunk, chunk_size)
def _save_chunk(self, file, elements, chunk_x, chunk_y, size):
file = file.with_stem(file.stem.format(chunk_x, chunk_y, size))
# Generate the image
img = np.zeros((size, size, 3), dtype=np.uint8)
for x, y in elements:
img[y % size, x % size] = self[x, y].colour
# Save the image
img = Image.fromarray(img)
img.save(file, format='PNG', compress_level=9)
@classmethod
def load(cls, file):
plan = cls()
file = Path(file)
# Load the chunk files
for chunk_file in file.parent.glob(file.stem + '_*,*_*.cnk'):
plan._load_chunk(chunk_file)
return plan
def _load_chunk(self, file):
coords, size = file.stem.split('_')[-2:]
chunk_x, chunk_y = map(int, coords.split(','))
# Load the image
img = np.array(Image.open(file))
xs, ys = np.where(img.any(axis=2))
colours = img[img.any(axis=2)]
# Parse the Blocks
for x, y, colour in zip(xs, ys, colours):
self[chunk_x * size + x, chunk_y * size + y] = Element(*colour)
Note that this code isn't properly tested so it probably contains bugs, I'm posting it more for demonstration's sake.
My question concerns the TODO part in the above code. Splitting the image into chunks obviously decreases the efficiency of PNG compression and thus increases overall file size. This is particularly true in the case of small regions on intersections of chunks. The main idea of the process described in the TODO is to only save each distinct region on the grid as its own PNG file, where regions have a lot of empty space between them. While the grid can easily expand to dimensions upwards of a million, populated regions are expected to be at most a few thousand units large. The below image illustrates the idea of the algorithm (the colours represent elements, the chunkified regions are black and empty space is white).
I also thought of doing something BST-based but I don't think a tree would help in the case of chunks that are close in coordinate space, but far away on the tree. For instance, (0, 0) and (0, -1) are neighbours in coordinate space, but in the tree you'd have to go all the way to the root and back down the tree to get to the other one.
My question is, since I don't want to reinvent the wheel, is there some sort of existing approach to such region-searching on a grid? Or in general, a more efficient way to save such a sparse grid?
