Skip to content

Distinguish Logical Index from Physical Position#3268

Merged
quaquel merged 19 commits intomesa:mainfrom
codebreaker32:add_pos
Feb 14, 2026
Merged

Distinguish Logical Index from Physical Position#3268
quaquel merged 19 commits intomesa:mainfrom
codebreaker32:add_pos

Conversation

@codebreaker32
Copy link
Copy Markdown
Collaborator

@codebreaker32 codebreaker32 commented Feb 9, 2026

Summary

This PR adds the ability to convert between logical coordinates (cell indices) and physical positions (spatial coordinates) across all discrete space types. This lays the foundation for stacked spaces as discussed in #2585 (reply in thread)

Changes

  1. Cell.position: A dedicated property for physical coordinates, distinct from the logical coordinate
  2. find_nearest_cell(position): High-performance lookup of the cell containing or nearest to a physical position(using KD-Trees for Voronoi, Network and HexGrid).
  3. HexGrid, VoronoiGrid & Network: Implemented scipy.spatial.KDTree for spatial lookups, to improve performance over brute-force distance checks.

Breaking Changes

VoronoiGrid only: cell.coordinate is now an integer index instead of a float tuple.
Migration:

# Before
centroid = cell.coordinate  # Was (55.2, 12.1)

# After  
centroid = cell.position    # np.array([55.2, 12.1])
cell_id = cell.coordinate   # 5 (Integer index)

This makes VoronoiGrid consistent with other spaces, improves performance by using integer keys for dictionary lookups, and decouples physical location from logical identity.

@codebreaker32 codebreaker32 marked this pull request as draft February 9, 2026 19:37
@github-actions
Copy link
Copy Markdown

github-actions bot commented Feb 9, 2026

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 -1.3% [-2.4%, -0.1%] 🟢 -3.8% [-4.1%, -3.6%]
BoltzmannWealth large 🔵 -0.1% [-0.6%, +0.5%] 🟢 -7.3% [-8.9%, -5.7%]
Schelling small 🔵 +1.5% [+1.1%, +2.0%] 🔵 -1.7% [-1.9%, -1.6%]
Schelling large 🔵 -0.2% [-0.9%, +0.6%] 🔵 -3.8% [-5.4%, -2.3%]
WolfSheep small 🔵 +0.2% [-0.5%, +0.8%] 🔵 -0.9% [-1.1%, -0.7%]
WolfSheep large 🔵 -0.5% [-1.5%, +0.4%] 🔵 -1.1% [-2.1%, -0.2%]
BoidFlockers small 🔵 -2.1% [-2.5%, -1.6%] 🔵 -1.5% [-1.7%, -1.2%]
BoidFlockers large 🔵 -2.2% [-2.9%, -1.6%] 🔵 -1.2% [-1.5%, -1.0%]

"This space may be purely topological (no physical coordinates)."
)

def cell_to_pos(self, cell: T) -> np.ndarray | None:
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

why did you implement these two methods on the space instead of the cell?

Copy link
Copy Markdown
Collaborator Author

@codebreaker32 codebreaker32 Feb 10, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

A Cell usually only knows its own coordinate and its contents. It does not know about the boundaries of the world, whether the world wraps around (torus), or the dimensions of the grid.
To convert a physical position (x, y) to a cell, you need to know the Space Dimensions.

Looking at the logic you will see, It relies heavily on self.torus and self.dimensions, which exist on the Grid, not the Cell.

def pos_to_cell(self, position):
    # Needs Grid Dimensions to know if pos is out of bounds
    if not 0 <= position[0] < self.width:
        # Needs Torus setting to know if we should wrap or raise error
        if self.torus:
            coord = position % self.dimensions 
        else:
            raise ValueError("Out of bounds")
            
    return self._cells[coord]

Hypothetical Alternative: If we moved this to Cell, we would have to inject the Grid into every function call, which is clumsy and circular.

# Method on the Cell class
class Cell:
    def pos_to_cell(self, position, grid_instance): # Must pass grid!
        # The cell itself doesn't know the grid's width/height
        if grid_instance.torus:
            ...

Copy link
Copy Markdown
Collaborator Author

@codebreaker32 codebreaker32 Feb 10, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think we also did something like this in mesa/mesa-geo#299, where RasterLayer(eq. to Grid) owns the global context(transform etc.) and Cell only holds their positions

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks for the clarification. It makes sense now. But then naming matters as stated below.

Copy link
Copy Markdown
Member

@quaquel quaquel Feb 10, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
def cell_to_pos(self, cell: T) -> np.ndarray | None:
def cell_index_to_pos(self, cell: T) -> np.ndarray | None:

Should this ever return None?

Also, if you have the cell already, what's the point of this method? You can just check cell.position yourself.

In my view, when instantiating a discrete space, we generate the indices and the positions a give these to the cell. Afterwards, there is no need to interact much with a space at all.

In case of stacked spaces, we still might need find nearest cell which returns the cell for a given position.

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Honestly, I don't see it as an ideal choice for obvious reasons

Not sure what you mean here. To me, it makes more sense that the cell.coordinate is the cell.position in the case of OrthogonalGrids. And then, for finding the nearest cell for a coordinate in case of orthogonal grids, you just round to the nearest integer.

Copy link
Copy Markdown
Collaborator Author

@codebreaker32 codebreaker32 Feb 12, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Because of this, on the visualization side, we have to map these coordinates to x,y positions.

  1. Looking at the long term, this function will essentially act as the coordinate provider for our visualization modules. If get_position returns the raw index (the corner), agents will be rendered sitting on the grid intersections (vertices) rather than inside the cells, which visually implies a physics bug. If we attempt to fix this 'downstream' by having the visualization layer manually normalize the coordinates (e.g., adding 0.5), we force the renderer to understand the specific geometry rules of the grid. That reintroduces the exact tight coupling we are trying to eliminate

Given a way of declaring the relationship between spaces, the next thing is to automatically make an agent show up in all "stacked" spaces. This is an implementation detail. But, whenever agent.position, this should be propagated to all relevant spaces. We also need an API for an agent or perhaps even an agent type to "opt out" of any given space.

  1. I interpret this as:
  • Continuous agent has agent.position (e.g., [5.7, 3.2])
  • Agent registers in stacked Grid space
  • Grid automatically determines which cell: find_nearest_cell([5.7, 3.2]) → cell (5, 3)
  • Agent appears in cell (5, 3) for grid-based operations

But: When the agent needs to reference the cell's position (for physics, movement, attraction), what should cell.position return?

Another weak argument is if we look at it through lens of pure physics, agents at center of cell looks more intuitive to me...

Curious to know your thoughts or please correct if I am assuming anything wrong.

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If get_position returns the raw index (the corner), agents will be rendered sitting on the grid intersections (vertices) rather than inside the cells, which visually implies a physics bug.

I don't follow. The grid line drawing is an implementation detail that should be derived from how we handle the position of the cell. If we put the cell on 1,1, then grid lines should be drawn on 0.5 and 1.5. So what is considered the corner is a choice we can make while implementing this.

I interpret this as:

Good questions, and part of implementing all this is to flesh out the answers to these questions.

  1. The agent position is leading in my view.
  2. Once it is determined that a given agent is in cell 5.3, its agent.cell attribute can be set to that cell, and so it is added to cell.agents. This means, if other agents want to use cell-based lookups, they can easily find them. For example, what are the agents that live in the same postcode area as me? Here, postcode areas could be implemented using a DiscreteSpace.
  3. I don't know of a use case where the physical position of the cell should matter inside a discrete space itself. Through the connections, we already specify the topology of a discrete space. If you want to know neighboring cells, you can just do a cell.neighborhood.
  4. Of course, in the case of the postcode example, an agent might want to know the nearest neighboring postcode to itself. But then, it could just ask the postcode space for k nearest neighbors via agent.position.

Copy link
Copy Markdown
Collaborator Author

@codebreaker32 codebreaker32 Feb 12, 2026

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don't follow. The grid line drawing is an implementation detail that should be derived from how we handle the position of the cell. If we put the cell on 1,1, then grid lines should be drawn on 0.5 and 1.5. So what is considered the corner is a choice we can make while implementing this.

Understood.

I don't know of a use case where the physical position of the cell should matter inside a discrete space itself. Through the connections, we already specify the topology of a discrete space. If you want to know neighboring cells, you can just do a cell.neighborhood

Should cells have SPATIAL EXTENT (position in space) or only TOPOLOGICAL EXTENT (connections)?

If cells are purely topological, then:

  1. Cells only matter for lookups ("who's near my cell?")
  2. All physics happens agent-to-agent via agent.position
  3. Cell.position is rendering-only

If cells have spatial extent, then:

  1. Cells can have spatial properties (temperature at center, resource density)
  2. Physics can be agent-to-agent AND agent-to-cell
  3. Cell.position is needed for physics calculations

For now, I think we can agree over cell to be purely topological but as we move closer to implementation of stacked spaces, it might be worth exploring the second alternative and its use-cases. Also, Thanks for detailed clarification

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should cells have SPATIAL EXTENT (position in space) or only TOPOLOGICAL EXTENT (connections)?

That is a very good question. I don't know. For simple spaces like hexes and orthogonal grids, the spatial extent is simple (assuming a given size for a cell). For Voronoi, we can generate it by construction. For networks, there is no natural answer to the question.

Copy link
Copy Markdown
Member

@quaquel quaquel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I am wondering whether pos_to_cell and cell_to_pos might not be better of on the Cell itself and be renamed to pos_to_index and index_to_pos.

Also, on the network side, I would suggest using networks lay outing instead of rolling our own.

@codebreaker32
Copy link
Copy Markdown
Collaborator Author

I am wondering whether pos_to_cell and cell_to_pos might not be better of on the Cell itself and be renamed to pos_to_index and index_to_pos.

I partially agree with the naming but I will strongly advise to keep it on space itself

@codebreaker32 codebreaker32 marked this pull request as ready for review February 10, 2026 08:51
@github-actions
Copy link
Copy Markdown

Performance benchmarks:

Model Size Init time [95% CI] Run time [95% CI]
BoltzmannWealth small 🔵 +0.1% [-0.3%, +0.5%] 🟢 -4.0% [-4.3%, -3.8%]
BoltzmannWealth large 🔵 -0.2% [-0.6%, +0.1%] 🟢 -3.5% [-3.9%, -3.1%]
Schelling small 🔵 +0.5% [+0.3%, +0.6%] 🔵 -1.1% [-1.2%, -1.0%]
Schelling large 🔵 -0.4% [-1.0%, +0.2%] 🔵 -1.7% [-2.5%, -1.0%]
WolfSheep small 🔵 -1.0% [-1.2%, -0.8%] 🔵 -1.9% [-2.0%, -1.7%]
WolfSheep large 🔵 -2.6% [-3.1%, -2.1%] 🔵 -2.7% [-3.2%, -2.3%]
BoidFlockers small 🔵 -0.3% [-0.7%, +0.1%] 🔵 -0.2% [-0.3%, -0.1%]
BoidFlockers large 🔵 -0.1% [-0.5%, +0.3%] 🔵 -0.5% [-0.6%, -0.3%]

@quaquel quaquel added the feature Release notes label label Feb 10, 2026
@EwoutH
Copy link
Copy Markdown
Member

EwoutH commented Feb 11, 2026

@codebreaker32 can we set properties on the cell that calls the methods from the space?

@codebreaker32
Copy link
Copy Markdown
Collaborator Author

@codebreaker32 can we set properties on the cell that calls the methods from the space?

Yes, we can do something like this

class Cell:
    """Cell with position property that delegates to space."""
    
    __slots__ = [
        "_agents",
        "_empty",
        "capacity",
        "connections",
        "coordinate",
        "properties",
        "random",
        "_space",  # NEW
    ]
    
    def __init__(
        self,
        coordinate: Coordinate,
        capacity: int | None = None,
        random: Random | None = None,
        space: DiscreteSpace | None = None,  # NEW
    ):
        self.coordinate = coordinate
        self._space = space  # Store reference to parent space
        ...
    
    @property
    def position(self) -> np.ndarray:
        """Physical position of the cell."""
        if self._space is None:
            # Fallback: use coordinate as position
            return np.asarray(self.coordinate, dtype=float)
        
        # Delegate to space (space knows its geometry)
        return self._space._get_cell_position(self)

@quaquel What do you think of this approach?

@quaquel
Copy link
Copy Markdown
Member

quaquel commented Feb 12, 2026

I still don't understand why this would be needed. In my view, we either pass the position at cell construction to the cell. This is needed for networks (if provided) for Voronoi (where we already have it), and for hexgrids (I guess). Or we don't pass it, and the cell constructs it on the fly to the best of its ability. So if cell.position is None, it will try to create a 2D np array using its coordinate.

Discrete space level properties like torus don't matter as far as I can see in this. Only for finding the nearest cell for a given x,y position might the torus property matter. But of that, I am not sure. For orthogonal grids, you can just round or floor the x,y positions (depending on how we handle the coordinate position translation). Again, for hexgrids, I would need to take a closer look.

@codebreaker32
Copy link
Copy Markdown
Collaborator Author

codebreaker32 commented Feb 13, 2026

I have updated the PR to align with our discussion,

  1. Implemented space.find_nearest_cell(position) and the Cell.position property.
  2. I completely refactored HexGrid to cleanly inherit from Grid.__init__, intitalising its geometry using a dedicated method _init_hex_geometry and using scipy.spatial.KDTree indexing.
  3. This same KD-Tree optimization has been used across all non-orthogonal spaces, including spatial Networks (which now dynamically rebuild their trees upon node changes) and VoronoiGrid.
  4. Finally, Test Suit updated

Copy link
Copy Markdown
Member

@quaquel quaquel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks a lot for your work on this. I have a bunch of minor questions and suggestions, but I think this is almost ready to go.

def _connect_cells(self): ...
def _connect_single_cell(self, cell: T): ...

def find_nearest_cell(self, position: np.ndarray) -> T:
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should we not turn DiscreteSpace into an ABC and then handle this and the methods above as abstract methods?

Copy link
Copy Markdown
Collaborator Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Agree. If you advice, I can do this in follow-up PR

@codebreaker32
Copy link
Copy Markdown
Collaborator Author

codebreaker32 commented Feb 14, 2026

Thanks for the great review as always :)
I have addressed all your major suggestions, particularly eliminating the redundant graph traversals in network.py by fusing the initialization and KD-Tree array construction into a single pass. I also refactored the layout argument to accept Mapping or Callable

For the remaining structural ideas (making DiscreteSpace an ABC and introducing a configurable size attribute on Grid and modify space_drawer), I think those would be best suited for a follow-up PR to keep this one atomic.

Copy link
Copy Markdown
Member

@quaquel quaquel left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This looks good to me. If you have any further minor tweaks you want to make, let me know. Otherwise, I'll merge this tomorrow.

@codebreaker32
Copy link
Copy Markdown
Collaborator Author

Minor tweaks done. PR description updated.
Good to go from my end

@quaquel quaquel merged commit 5e0a90a into mesa:main Feb 14, 2026
14 checks passed
codebyNJ added a commit to codebyNJ/mesa that referenced this pull request Feb 15, 2026
@EwoutH EwoutH added enhancement Release notes label and removed feature Release notes label labels Feb 15, 2026
@codebreaker32 codebreaker32 deleted the add_pos branch February 26, 2026 12:50
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

enhancement Release notes label

Projects

None yet

Development

Successfully merging this pull request may close these issues.

3 participants