0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ We're not a coding site. Questions about chunks of code are generally considered off-topic here. Our general advice is to avoid using code; if you need to show an algorithm, you can use concise pseudo-code. $\endgroup$
    – D.W.
    Commented Aug 30, 2023 at 20:50
  • $\begingroup$ What exactly is your question? Can you state it in a self-contained way? You say "such region-searching", but can you give a concise self-contained specification of the problem? What are the inputs, and what is the desired output? Or, what are the operations you want to be able to perform on your data structure? What are the requirements or criteria you will use for evaluating any candidate solution? $\endgroup$
    – D.W.
    Commented Aug 30, 2023 at 20:51

1 Answer 1

1
$\begingroup$

I think you've gotten yourself on the wrong path by trying to use PNG, splitting up into multiple chunks so the PNG files aren't too big, etc.

Instead, store your data using any sparse matrix datastructure. There are many simple schemes. As you suggest, "a dictionary mapping coordinates to elements" is a reasonable data structure. I suggest storing that directly. There are many ways you could serialize it to disk efficiently. There is no reason to go through PNG or via splitting into chunks.

$\endgroup$
1
  • $\begingroup$ I've started working on a solution with clustering so I'll probably finish that, but I'll try to just use a sparse method too, so I can compare the file sizes. scipy already has ready methods for sparse matrix handling and saving so I can probably just use those. $\endgroup$ Commented Aug 31, 2023 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.