Distinguish Logical Index from Physical Position#3268
Conversation
fbfdd45 to
25b6882
Compare
|
Performance benchmarks:
|
| "This space may be purely topological (no physical coordinates)." | ||
| ) | ||
|
|
||
| def cell_to_pos(self, cell: T) -> np.ndarray | None: |
There was a problem hiding this comment.
why did you implement these two methods on the space instead of the cell?
There was a problem hiding this comment.
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:
...There was a problem hiding this comment.
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
There was a problem hiding this comment.
Thanks for the clarification. It makes sense now. But then naming matters as stated below.
There was a problem hiding this comment.
| 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.
There was a problem hiding this comment.
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.
There was a problem hiding this comment.
Because of this, on the visualization side, we have to map these coordinates to x,y positions.
- 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.
- 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.
There was a problem hiding this comment.
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.
- The agent position is leading in my view.
- Once it is determined that a given agent is in cell 5.3, its
agent.cellattribute can be set to that cell, and so it is added tocell.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. - 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. - 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.
There was a problem hiding this comment.
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:
- Cells only matter for lookups ("who's near my cell?")
- All physics happens agent-to-agent via agent.position
- Cell.position is rendering-only
If cells have spatial extent, then:
- Cells can have spatial properties (temperature at center, resource density)
- Physics can be agent-to-agent AND agent-to-cell
- 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
There was a problem hiding this comment.
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.
quaquel
left a comment
There was a problem hiding this comment.
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.
I partially agree with the naming but I will strongly advise to keep it on space itself |
b415f65 to
c732f89
Compare
|
Performance benchmarks:
|
fd28357 to
7147f3a
Compare
|
@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? |
|
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 Discrete space level properties like |
|
I have updated the PR to align with our discussion,
|
quaquel
left a comment
There was a problem hiding this comment.
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: |
There was a problem hiding this comment.
Should we not turn DiscreteSpace into an ABC and then handle this and the methods above as abstract methods?
There was a problem hiding this comment.
Agree. If you advice, I can do this in follow-up PR
|
Thanks for the great review as always :) 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. |
quaquel
left a comment
There was a problem hiding this comment.
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.
|
Minor tweaks done. PR description updated. |
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
Cell.position: A dedicated property for physical coordinates, distinct from the logicalcoordinatefind_nearest_cell(position): High-performance lookup of the cell containing or nearest to a physical position(using KD-Trees for Voronoi, Network and HexGrid).scipy.spatial.KDTreefor spatial lookups, to improve performance over brute-force distance checks.Breaking Changes
VoronoiGrid only:
cell.coordinateis now an integer index instead of a float tuple.Migration:
This makes
VoronoiGridconsistent with other spaces, improves performance by using integer keys for dictionary lookups, and decouples physical location from logical identity.