Repository: projectmesa/mesa
Pull request #1508 (2022-11-06 00:38:46)

Make MultiGrid.place_agent faster
The condition tested now is a constant time operation while before it was a linear time operation in relation to the size of the list of agents

codecov[bot]: # [Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1508?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) Report
Base: **91.32**% // Head: **91.32**% // No change to project coverage :thumbsup:
> Coverage data is based on head [(`4081541`)](https://codecov.io/gh/projectmesa/mesa/pull/1508?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) compared to base [(`c201bcb`)](https://codecov.io/gh/projectmesa/mesa/commit/c201bcb2a61e29ed03c0c04ac0a64bddb201fa10?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).
> Patch coverage: 66.66% of modified lines in pull request are covered.

<details><summary>Additional details and impacted files</summary>


```diff
@@           Coverage Diff           @@
##             main    #1508   +/-   ##
=======================================
  Coverage   91.32%   91.32%           
=======================================
  Files          15       15           
  Lines        1303     1303           
  Branches      223      223           
=======================================
  Hits         1190     1190           
  Misses         80       80           
  Partials       33       33           
```


| [Impacted Files](https://codecov.io/gh/projectmesa/mesa/pull/1508?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) | Coverage Δ | |
|---|---|---|
| [mesa/space.py](https://codecov.io/gh/projectmesa/mesa/pull/1508/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS9zcGFjZS5weQ==) | `96.21% <66.66%> (ø)` | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa)

</details>

[:umbrella: View full report at Codecov](https://codecov.io/gh/projectmesa/mesa/pull/1508?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).   
:loudspeaker: Do you have feedback about the report comment? [Let us know in this issue](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).

Tortar: Need to resort to a somewhat in between implementation :any time the agent.pos position is not preassigned to where you want to place the agent in the grid it takes a constant amount of time, otherwise it goes to scan the list

Patch:
diff --git a/examples/schelling/model.py b/examples/schelling/model.py
index 52cfafa2..821b68af 100644
--- a/examples/schelling/model.py
+++ b/examples/schelling/model.py
@@ -70,7 +70,7 @@ class Schelling(mesa.Model):
                     agent_type = 0
 
                 agent = SchellingAgent((x, y), self, agent_type)
-                self.grid.position_agent(agent, (x, y))
+                self.grid.place_agent(agent, (x, y))
                 self.schedule.add(agent)
 
         self.running = True
diff --git a/mesa/space.py b/mesa/space.py
index c0081f74..48979763 100644
--- a/mesa/space.py
+++ b/mesa/space.py
@@ -4,9 +4,13 @@ Mesa Space Module
 
 Objects used to add a spatial component to a model.
 
-Grid: base grid, a simple list-of-lists.
-SingleGrid: grid which strictly enforces one object per cell.
-MultiGrid: extension to Grid where each cell is a set of objects.
+Grid: base grid, which creates a rectangular grid.
+SingleGrid: extension to Grid which strictly enforces one agent per cell.
+MultiGrid: extension to Grid where each cell can contain a set of agents.
+HexGrid: extension to Grid to handle hexagonal neighbors.
+ContinuousSpace: a two-dimensional space where each agent has an arbitrary
+                 position of `float`'s.
+NetworkGrid: a network where each node contains zero or more agents.
 """
 # Instruction for PyLint to suppress variable name errors, since we have a
 # good reason to use one-character variable names for x and y.
@@ -75,7 +79,7 @@ def is_integer(x: Real) -> bool:
 
 
 class Grid:
-    """Base class for a square grid.
+    """Base class for a rectangular grid.
 
     Grid cells are indexed by [x][y], where [0][0] is assumed to be the
     bottom-left and [width-1][height-1] is the top-right. If a grid is
@@ -251,29 +255,37 @@ class Grid:
         if neighborhood is not None:
             return neighborhood
 
-        coordinates: set[Coordinate] = set()
+        neighborhood = []
 
         x, y = pos
-        for dy in range(-radius, radius + 1):
-            for dx in range(-radius, radius + 1):
-                # Skip coordinates that are outside manhattan distance
-                if not moore and abs(dx) + abs(dy) > radius:
-                    continue
+        if self.torus:
+            x_radius = min(radius, self.width // 2)
+            y_radius = min(radius, self.height // 2)
 
-                coord = (x + dx, y + dy)
+            for dx in range(-x_radius, x_radius + 1):
+                for dy in range(-y_radius, y_radius + 1):
 
-                if self.out_of_bounds(coord):
-                    # Skip if not a torus and new coords out of bounds.
-                    if not self.torus:
+                    if not moore and abs(dx) + abs(dy) > radius:
                         continue
-                    coord = self.torus_adj(coord)
 
-                coordinates.add(coord)
+                    nx, ny = (x + dx) % self.width, (y + dy) % self.height
+                    neighborhood.append((nx, ny))
 
-        if not include_center:
-            coordinates.discard(pos)
+        else:
+            x_range = range(max(0, x - radius), min(self.width, x + radius + 1))
+            y_range = range(max(0, y - radius), min(self.height, y + radius + 1))
+
+            for nx in x_range:
+                for ny in y_range:
+
+                    if not moore and abs(nx - x) + abs(ny - y) > radius:
+                        continue
+
+                    neighborhood.append((nx, ny))
+
+        if not include_center and neighborhood:
+            neighborhood.remove(pos)
 
-        neighborhood = sorted(coordinates)
         self._neighborhood_cache[cache_key] = neighborhood
 
         return neighborhood
@@ -504,6 +516,27 @@ class SingleGrid(Grid):
         If x or y are positive, they are used.
         Use 'swap_pos()' to swap agents positions.
         """
+        warn(
+            (
+                "`position_agent` is being deprecated; use instead "
+                "`place_agent` to place an agent at a specified "
+                "location or `move_to_empty` to place an agent "
+                "at a random empty cell."
+            ),
+            DeprecationWarning,
+        )
+
+        if not (isinstance(x, int) or x == "random"):
+            raise Exception(
+                "x must be an integer or a string 'random'."
+                f" Actual type: {type(x)}. Actual value: {x}."
+            )
+        if not (isinstance(y, int) or y == "random"):
+            raise Exception(
+                "y must be an integer or a string 'random'."
+                f" Actual type: {type(y)}. Actual value: {y}."
+            )
+
         if x == "random" or y == "random":
             if len(self.empties) == 0:
                 raise Exception("ERROR: Grid full")
@@ -549,10 +582,10 @@ class MultiGrid(Grid):
     def place_agent(self, agent: Agent, pos: Coordinate) -> None:
         """Place the agent at the specified location, and set its pos variable."""
         x, y = pos
-        if agent not in self.grid[x][y]:
+        if agent.pos is None or agent not in self.grid[x][y]:
             self.grid[x][y].append(agent)
-        self.empties.discard(pos)
-        agent.pos = pos
+            agent.pos = pos
+            self.empties.discard(pos)
 
     def remove_agent(self, agent: Agent) -> None:
         """Remove the agent from the given location and set its pos attribute to None."""
@@ -953,6 +986,11 @@ class NetworkGrid:
     """Network Grid where each node contains zero or more agents."""
 
     def __init__(self, G: Any) -> None:
+        """Create a new network.
+
+        Args:
+            G: a NetworkX graph instance.
+        """
         self.G = G
         for node_id in self.G.nodes:
             G.nodes[node_id]["agent"] = self.default_val()
diff --git a/mesa/time.py b/mesa/time.py
index f9c84acf..54f6e25a 100644
--- a/mesa/time.py
+++ b/mesa/time.py
@@ -28,7 +28,7 @@ from __future__ import annotations
 from collections import defaultdict
 
 # mypy
-from typing import Iterator, Union, Iterable
+from typing import Iterator, Union
 from mesa.agent import Agent
 from mesa.model import Model
 
@@ -96,9 +96,10 @@ class BaseScheduler:
         """Simple generator that yields the agents while letting the user
         remove and/or add agents during stepping.
         """
-        agent_keys = self._agents.keys()
+        # To be able to remove and/or add agents during stepping
+        # it's necessary to cast the keys view to a list.
+        agent_keys = list(self._agents.keys())
         if shuffled:
-            agent_keys = list(agent_keys)
             self.model.random.shuffle(agent_keys)
 
         for key in agent_keys:
@@ -137,12 +138,16 @@ class SimultaneousActivation(BaseScheduler):
 
     def step(self) -> None:
         """Step all agents, then advance them."""
-        for agent in self._agents.values():
-            agent.step()
-        # the previous steps might remove some agents, but
-        # this loop will go over the remaining existing agents
-        for agent in self._agents.values():
-            agent.advance()
+        # To be able to remove and/or add agents during stepping
+        # it's necessary to cast the keys view to a list.
+        agent_keys = list(self._agents.keys())
+        for agent_key in agent_keys:
+            self._agents[agent_key].step()
+        # We recompute the keys because some agents might have been removed in
+        # the previous loop.
+        agent_keys = list(self._agents.keys())
+        for agent_key in agent_keys:
+            self._agents[agent_key].advance()
         self.steps += 1
         self.time += 1
 
@@ -185,18 +190,18 @@ class StagedActivation(BaseScheduler):
 
     def step(self) -> None:
         """Executes all the stages for all agents."""
-        agent_keys = self._agents.keys()
+        # To be able to remove and/or add agents during stepping
+        # it's necessary to cast the keys view to a list.
+        agent_keys = list(self._agents.keys())
         if self.shuffle:
-            agent_keys = list(agent_keys)
             self.model.random.shuffle(agent_keys)
         for stage in self.stage_list:
             for agent_key in agent_keys:
                 getattr(self._agents[agent_key], stage)()  # Run stage
             # We recompute the keys because some agents might have been removed
             # in the previous loop.
-            agent_keys = self._agents.keys()
+            agent_keys = list(self._agents.keys())
             if self.shuffle_between_stages:
-                agent_keys = list(agent_keys)
                 self.model.random.shuffle(agent_keys)
             self.time += self.stage_time
 
@@ -259,9 +264,10 @@ class RandomActivationByType(BaseScheduler):
             shuffle_agents: If True, the order of execution of each agents in a
                             type group is shuffled.
         """
-        type_keys: Iterable[type[Agent]] = self.agents_by_type.keys()
+        # To be able to remove and/or add agents during stepping
+        # it's necessary to cast the keys view to a list.
+        type_keys: list[type[Agent]] = list(self.agents_by_type.keys())
         if shuffle_types:
-            type_keys = list(type_keys)
             self.model.random.shuffle(type_keys)
         for agent_class in type_keys:
             self.step_type(agent_class, shuffle_agents=shuffle_agents)
@@ -276,9 +282,8 @@ class RandomActivationByType(BaseScheduler):
         Args:
             type_class: Class object of the type to run.
         """
-        agent_keys: Iterable[int] = self.agents_by_type[type_class].keys()
+        agent_keys: list[int] = list(self.agents_by_type[type_class].keys())
         if shuffle_agents:
-            agent_keys = list(agent_keys)
             self.model.random.shuffle(agent_keys)
         for agent_key in agent_keys:
             self.agents_by_type[type_class][agent_key].step()


Test patch:
diff --git a/tests/test_grid.py b/tests/test_grid.py
index 245a5c35..7a706198 100644
--- a/tests/test_grid.py
+++ b/tests/test_grid.py
@@ -262,6 +262,25 @@ class TestSingleGrid(unittest.TestCase):
                 self.grid.place_agent(a, (x, y))
         self.num_agents = len(self.agents)
 
+    @patch.object(MockAgent, "model", create=True)
+    def test_position_agent(self, mock_model):
+        a = MockAgent(100, None)
+        with self.assertRaises(Exception) as exc_info:
+            self.grid.position_agent(a, (1, 1))
+        expected = (
+            "x must be an integer or a string 'random'."
+            " Actual type: <class 'tuple'>. Actual value: (1, 1)."
+        )
+        assert str(exc_info.exception) == expected
+        with self.assertRaises(Exception) as exc_info:
+            self.grid.position_agent(a, "(1, 1)")
+        expected = (
+            "x must be an integer or a string 'random'."
+            " Actual type: <class 'str'>. Actual value: (1, 1)."
+        )
+        assert str(exc_info.exception) == expected
+        self.grid.position_agent(a, "random")
+
     @patch.object(MockAgent, "model", create=True)
     def test_enforcement(self, mock_model):
         """