Skip to content

Grid

Grid generation.

To create a grid using invasion percolation:

  1. Generate an NxN grid of random numbers.
  2. Mark the center cell as "filled" by negating its value.
  3. On each iteration:
    1. Find the lowest-valued cell adjacent to the filled region.
    2. Fill that in by negating its value.
    3. If several cells tie for lowest value, pick one at random.
  4. Stop when the filled region hits the edge of the grid.

Instead of repeatedly searching for cells adjacent to the filled region, the grid keeps a value-to-coordinates dictionary. When a cell is filled in, neighbors not already recorded are added.

The grid is saved as a list of lists. 0 shows unfilled cells, while positive numbers show the original value of filled cells.

Grid dataclass

Keep track of generated grid.

Source code in src/snailz/grid.py 
37
38
39
40
41
42
@dataclass
class Grid:
    """Keep track of generated grid."""

    grid: list[list[int]]
    params: dict[str, object]

Invperc

Represent a 2D grid that supports lazy filling.

Source code in src/snailz/grid.py 
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
class Invperc:
    """Represent a 2D grid that supports lazy filling."""

    def __init__(self, depth: int, size: int) -> None:
        """Initialize the invasion percolation grid.

        Parameters:
            depth: The maximum value for grid cells
            size: The size of the grid (size x size)
        """
        self._depth = depth
        self._size = size
        self._cells = []
        for x in range(self._size):
            col = [random.randint(1, self._depth) for y in range(self._size)]
            self._cells.append(col)
        self._candidates = {}

    def __str__(self) -> str:
        """Convert to printable string representation.

        Returns:
            A string representation of the grid with '.' for unfilled cells
            and 'x' for filled cells, with each row on a separate line
        """
        rows = []
        for y in range(self._size - 1, -1, -1):
            rows.append(
                "".join(
                    "." if self._cells[x][y] == 0 else "x" for x in range(self._size)
                )
            )
        return "\n".join(rows)

    @property
    def cells(self) -> list[list[int]]:
        """Get the grid cell values.

        Returns:
            A 2D list of grid cell values
        """
        return self._cells

    def fill(self) -> None:
        """Fill the grid one cell at a time using invasion percolation.

        Starts at the center and fills outward, choosing lowest-valued adjacent cells,
        until reaching the border of the grid. After filling, inverts cell values.
        """
        x, y = self._size // 2, self._size // 2
        self._cells[x][y] = -self._cells[x][y]
        self.add_candidates(x, y)
        while True:
            x, y = self.choose_cell()
            self._cells[x][y] = -self._cells[x][y]
            if self.on_border(x, y):
                break
        self.invert()

    def invert(self) -> None:
        """Flip cell values to final form.

        Converts negative values (filled cells) to their positive values
        and leaves non-negative values as 0 (unfilled)
        """
        for row in self._cells:
            for i in range(self._size):
                row[i] = 0 if row[i] >= 0 else -row[i]

    def add_candidates(self, x: int, y: int) -> None:
        """Add unfilled cells adjacent to a filled cell as candidates for filling.

        Parameters:
            x: X-coordinate of the filled cell
            y: Y-coordinate of the filled cell
        """
        for ix in (x - 1, x + 1):
            self.add_one_candidate(ix, y)
        for iy in (y - 1, y + 1):
            self.add_one_candidate(x, iy)

    def add_one_candidate(self, x: int, y: int) -> None:
        """Add a single point to the set of candidates for filling.

        Parameters:
            x: X-coordinate of the candidate cell
            y: Y-coordinate of the candidate cell

        Note:
            Does nothing if the coordinates are outside the grid bounds
            or if the cell is already filled (negative value)
        """
        if (x < 0) or (x >= self._size) or (y < 0) or (y >= self._size):
            return
        if self._cells[x][y] < 0:
            return

        value = self._cells[x][y]
        if value not in self._candidates:
            self._candidates[value] = set()
        self._candidates[value].add((x, y))

    def choose_cell(self) -> tuple[int, int]:
        """Choose the next cell to fill using the invasion percolation algorithm.

        Returns:
            A tuple (x, y) of coordinates for the next cell to fill

        Note:
            Chooses the lowest-valued cell adjacent to already filled cells.
            If multiple cells tie for the lowest value, picks one at random.
            Updates the candidate set after selecting a cell.
        """
        min_key = min(self._candidates.keys())
        available = list(sorted(self._candidates[min_key]))
        i = random.randrange(len(available))
        choice = available[i]
        del available[i]
        if not available:
            del self._candidates[min_key]
        else:
            self._candidates[min_key] = set(available)
        self.add_candidates(*choice)
        return choice

    def on_border(self, x: int, y: int) -> bool:
        """Check if a cell is on the border of the grid.

        Parameters:
            x: X-coordinate of the cell
            y: Y-coordinate of the cell

        Returns:
            True if the cell is on any edge of the grid, False otherwise
        """
        size_1 = self._size - 1
        return (x == 0) or (x == size_1) or (y == 0) or (y == size_1)

cells property

Get the grid cell values.

Returns:

Type Description
list[list[int]]

A 2D list of grid cell values

__init__(depth, size)

Initialize the invasion percolation grid.

Parameters:

Name Type Description Default
depth int

The maximum value for grid cells

 required
size int

The size of the grid (size x size)

 required
Source code in src/snailz/grid.py 
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
def __init__(self, depth: int, size: int) -> None:
    """Initialize the invasion percolation grid.

    Parameters:
        depth: The maximum value for grid cells
        size: The size of the grid (size x size)
    """
    self._depth = depth
    self._size = size
    self._cells = []
    for x in range(self._size):
        col = [random.randint(1, self._depth) for y in range(self._size)]
        self._cells.append(col)
    self._candidates = {}

__str__()

Convert to printable string representation.

Returns:

Type Description
str

A string representation of the grid with '.' for unfilled cells
str

and 'x' for filled cells, with each row on a separate line
Source code in src/snailz/grid.py 
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
def __str__(self) -> str:
    """Convert to printable string representation.

    Returns:
        A string representation of the grid with '.' for unfilled cells
        and 'x' for filled cells, with each row on a separate line
    """
    rows = []
    for y in range(self._size - 1, -1, -1):
        rows.append(
            "".join(
                "." if self._cells[x][y] == 0 else "x" for x in range(self._size)
            )
        )
    return "\n".join(rows)

fill()

Fill the grid one cell at a time using invasion percolation.

Starts at the center and fills outward, choosing lowest-valued adjacent cells, until reaching the border of the grid. After filling, inverts cell values.

Source code in src/snailz/grid.py 
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
def fill(self) -> None:
    """Fill the grid one cell at a time using invasion percolation.

    Starts at the center and fills outward, choosing lowest-valued adjacent cells,
    until reaching the border of the grid. After filling, inverts cell values.
    """
    x, y = self._size // 2, self._size // 2
    self._cells[x][y] = -self._cells[x][y]
    self.add_candidates(x, y)
    while True:
        x, y = self.choose_cell()
        self._cells[x][y] = -self._cells[x][y]
        if self.on_border(x, y):
            break
    self.invert()

invert()

Flip cell values to final form.

Converts negative values (filled cells) to their positive values and leaves non-negative values as 0 (unfilled)

Source code in src/snailz/grid.py 
151
152
153
154
155
156
157
158
159
def invert(self) -> None:
    """Flip cell values to final form.

    Converts negative values (filled cells) to their positive values
    and leaves non-negative values as 0 (unfilled)
    """
    for row in self._cells:
        for i in range(self._size):
            row[i] = 0 if row[i] >= 0 else -row[i]

add_candidates(x, y)

Add unfilled cells adjacent to a filled cell as candidates for filling.

Parameters:

Name Type Description Default
x int

X-coordinate of the filled cell

 required
y int

Y-coordinate of the filled cell

 required
Source code in src/snailz/grid.py 
161
162
163
164
165
166
167
168
169
170
171
def add_candidates(self, x: int, y: int) -> None:
    """Add unfilled cells adjacent to a filled cell as candidates for filling.

    Parameters:
        x: X-coordinate of the filled cell
        y: Y-coordinate of the filled cell
    """
    for ix in (x - 1, x + 1):
        self.add_one_candidate(ix, y)
    for iy in (y - 1, y + 1):
        self.add_one_candidate(x, iy)

add_one_candidate(x, y)

Add a single point to the set of candidates for filling.

Parameters:

Name Type Description Default
x int

X-coordinate of the candidate cell

 required
y int

Y-coordinate of the candidate cell

 required
Note

Does nothing if the coordinates are outside the grid bounds or if the cell is already filled (negative value)

Source code in src/snailz/grid.py 
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
def add_one_candidate(self, x: int, y: int) -> None:
    """Add a single point to the set of candidates for filling.

    Parameters:
        x: X-coordinate of the candidate cell
        y: Y-coordinate of the candidate cell

    Note:
        Does nothing if the coordinates are outside the grid bounds
        or if the cell is already filled (negative value)
    """
    if (x < 0) or (x >= self._size) or (y < 0) or (y >= self._size):
        return
    if self._cells[x][y] < 0:
        return

    value = self._cells[x][y]
    if value not in self._candidates:
        self._candidates[value] = set()
    self._candidates[value].add((x, y))

choose_cell()

Choose the next cell to fill using the invasion percolation algorithm.

Returns:

Type Description
tuple[int, int]

A tuple (x, y) of coordinates for the next cell to fill
Note

Chooses the lowest-valued cell adjacent to already filled cells. If multiple cells tie for the lowest value, picks one at random. Updates the candidate set after selecting a cell.

Source code in src/snailz/grid.py 
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
def choose_cell(self) -> tuple[int, int]:
    """Choose the next cell to fill using the invasion percolation algorithm.

    Returns:
        A tuple (x, y) of coordinates for the next cell to fill

    Note:
        Chooses the lowest-valued cell adjacent to already filled cells.
        If multiple cells tie for the lowest value, picks one at random.
        Updates the candidate set after selecting a cell.
    """
    min_key = min(self._candidates.keys())
    available = list(sorted(self._candidates[min_key]))
    i = random.randrange(len(available))
    choice = available[i]
    del available[i]
    if not available:
        del self._candidates[min_key]
    else:
        self._candidates[min_key] = set(available)
    self.add_candidates(*choice)
    return choice

on_border(x, y)

Check if a cell is on the border of the grid.

Parameters:

Name Type Description Default
x int

X-coordinate of the cell

 required
y int

Y-coordinate of the cell

 required

Returns:

Type Description
bool

True if the cell is on any edge of the grid, False otherwise
Source code in src/snailz/grid.py 
217
218
219
220
221
222
223
224
225
226
227
228
def on_border(self, x: int, y: int) -> bool:
    """Check if a cell is on the border of the grid.

    Parameters:
        x: X-coordinate of the cell
        y: Y-coordinate of the cell

    Returns:
        True if the cell is on any edge of the grid, False otherwise
    """
    size_1 = self._size - 1
    return (x == 0) or (x == size_1) or (y == 0) or (y == size_1)

grid_check(params)

Check grid generation parameters.

Parameters:

Name Type Description Default
params dict[str, object]

Dictionary containing grid generation parameters

 required

Raises:

Type Description
ValueError

If parameters are missing, have wrong types, or have invalid values
Source code in src/snailz/grid.py 
45
46
47
48
49
50
51
52
53
54
55
56
def grid_check(params: dict[str, object]) -> None:
    """Check grid generation parameters.

    Parameters:
        params: Dictionary containing grid generation parameters

    Raises:
        ValueError: If parameters are missing, have wrong types, or have invalid values
    """
    utils.check_keys_and_types(GRID_PARAMS, params)
    for name in ["depth", "size"]:
        utils.require(0 < params[name], f"{name} must be positive")

grid_generate(params)

Generate grid using invasion percolation.

Parameters:

Name Type Description Default
params dict[str, object]

Dictionary containing grid generation parameters (depth, seed, size)

 required

Returns:

Type Description
Grid

Grid object containing the generated grid and parameters
Source code in src/snailz/grid.py 
59
60
61
62
63
64
65
66
67
68
69
70
71
def grid_generate(params: dict[str, object]) -> Grid:
    """Generate grid using invasion percolation.

    Parameters:
        params: Dictionary containing grid generation parameters (depth, seed, size)

    Returns:
        Grid object containing the generated grid and parameters
    """
    grid_check(params)
    invperc = Invperc(params["depth"], params["size"])
    invperc.fill()
    return Grid(grid=invperc.cells, params=params)

grid_to_csv(grid, filename)

Write grid values as CSV without a header.

Parameters:

Name Type Description Default
grid Grid

Grid object containing the grid data to write

 required
filename str | None

Path to output file, or None to write to standard output

 required
Side effects

Either writes to the specified output file or prints to stdout

Source code in src/snailz/grid.py 
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
def grid_to_csv(grid: Grid, filename: str | None) -> None:
    """Write grid values as CSV without a header.

    Parameters:
        grid: Grid object containing the grid data to write
        filename: Path to output file, or None to write to standard output

    Side effects:
        Either writes to the specified output file or prints to stdout
    """
    stream = sys.stdout if filename is None else open(filename, "w", newline="")
    writer = csv.writer(stream)
    for row in grid.grid:
        writer.writerow(row)
    if stream is not sys.stdout:
        stream.close()