Cell.get_neighborhood() crashes with RecursionError for large radius values #3105
Description
The Cell.get_neighborhood() method in mesa/discrete_space/cell.py uses a recursive implementation to find neighboring cells. When the radius parameter exceeds Python's default recursion limit (~1000), the method crashes with a RecursionError: maximum recursion depth exceeded.
- It crashes the entire Python process - not a recoverable exception in most cases
- It limits the scalability of discrete space models to interaction ranges < 1000
- It affects NetworkGrid, VoronoiGrid, and any custom graph-based spaces where "radius" represents hop distance
Expected behavior
get_neighborhood(radius=N) should return all cells within N connections/hops from the starting cell, regardless of how large N is (limited only by available memory, not by the recursion stack).
To Reproduce
Minimal Reproducible Example
from mesa.discrete_space import Cell
# Create a linear chain of 2000 cells (e.g., a highway, pipeline, or network path)
cells = [Cell((i,)) for i in range(2000)]
# Connect them in a chain
for i in range(len(cells) - 1):
cells[i].connect(cells[i+1], key=(1,))
cells[i+1].connect(cells[i], key=(-1,))
# Try to find neighbors within radius 1500
# This CRASHES with RecursionError
neighbors = cells[0].get_neighborhood(radius=1500)Output
Traceback (most recent call last):
File "example.py", line 12, in <module>
neighbors = cells[0].get_neighborhood(radius=1500)
File "mesa/discrete_space/cell.py", line 177, in get_neighborhood
self._neighborhood(radius=radius, include_center=include_center),
File "mesa/discrete_space/cell.py", line 203, in _neighborhood
neighbor._neighborhood(radius - 1, include_center=True)
File "mesa/discrete_space/cell.py", line 203, in _neighborhood
neighbor._neighborhood(radius - 1, include_center=True)
File "mesa/discrete_space/cell.py", line 203, in _neighborhood
neighbor._neighborhood(radius - 1, include_center=True)
[Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded
Root Cause
The _neighborhood method (lines 183-207 in cell.py) uses recursion:
def _neighborhood(self, radius: int = 1, include_center: bool = False):
# ...
else:
neighborhood: dict[Cell, list[Agent]] = {}
for neighbor in self.connections.values():
neighborhood.update(
neighbor._neighborhood(radius - 1, include_center=True) # RECURSIVE CALL
)
# ...Each call to _neighborhood(radius) makes calls to _neighborhood(radius-1), creating radius stack frames. When radius > sys.getrecursionlimit() (default ~1000), Python crashes.
Proposed Fix
Replace the recursive implementation with an iterative Breadth-First Search (BFS):
@cache
def _neighborhood(self, radius: int = 1, include_center: bool = False) -> dict[Cell, list[Agent]]:
"""Return cells within given radius using iterative BFS."""
if radius < 1:
raise ValueError("radius must be larger than one")
# Use iterative BFS to avoid RecursionError for large radius
visited: set[Cell] = {self}
current_layer: list[Cell] = list(self.connections.values())
neighborhood: dict[Cell, list[Agent]] = {}
# Add immediate neighbors (radius=1)
for neighbor in current_layer:
if neighbor not in visited:
visited.add(neighbor)
neighborhood[neighbor] = neighbor._agents
# Expand outward for remaining radius levels
for _ in range(radius - 1):
next_layer: list[Cell] = []
for cell in current_layer:
for neighbor in cell.connections.values():
if neighbor not in visited:
visited.add(neighbor)
next_layer.append(neighbor)
neighborhood[neighbor] = neighbor._agents
current_layer = next_layer
if not current_layer:
break # No more cells to explore
# Handle center inclusion
if include_center:
neighborhood[self] = self._agents
else:
neighborhood.pop(self, None)
return neighborhoodBenefits of this fix:
- No recursion = No stack overflow, regardless of radius
- Same time complexity O(number of cells in radius)
Additional context
- Default Recursion Limit:
sys.getrecursionlimit()= 1000
Verification
I have tested the proposed fix and confirmed:
radius=10worksradius=100worksradius=500worksradius=1000worksradius=1500works (previously crashed)radius=1999works (previously crashed)- All 34 existing discrete_space tests pass