Repository: projectmesa/mesa
Pull request #1920 (2023-12-21 22:06:35)

space: Let move_agent choose from multiple positions
This PR enables the `move_agent` method to take a list of potential positions and offering two selection strategies: random and closest.

This allows any subset of potential positions to be inputted, like an neighborhood, list of empty cells, etc.

Furthermore, it will help with #1898 when cells are selected based on properties.

### New features

1. **Flexible Position Handling**: The `move_agent` method can now accept a single position or a list of possible positions for agent movement.

2. **Selection Strategies**: 
    - `random`: Selects a position randomly from the provided list.
    - `closest`: Chooses the position closest to the agent's current location. In case of ties, a position is selected randomly from the closest ones.

### Usage examples

1. **Moving to a Random Position**:
   ```python
   space.move_agent(agent, possible_positions, selection='random')
   ```

2. **Moving to the Closest Position**:
   ```python
   space.move_agent(agent, possible_positions, selection='closest')
   ```

### Limitations
- This currently only works for Grids, not for ContiniousSpace.

EwoutH: @jackiekazil @tpike3 @Corvince @rht @wang-boyu @quaquel please review
codecov[bot]: ## [Codecov](https://app.codecov.io/gh/projectmesa/mesa/pull/1920?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Comparison is base [(`9495a5a`)](https://app.codecov.io/gh/projectmesa/mesa/commit/9495a5acb6256104e95b02c71f6a8eecffb412f1?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) 77.53% compared to head [(`b2c9653`)](https://app.codecov.io/gh/projectmesa/mesa/pull/1920?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) 78.05%.


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


```diff
@@            Coverage Diff             @@
##             main    #1920      +/-   ##
==========================================
+ Coverage   77.53%   78.05%   +0.51%     
==========================================
  Files          15       15              
  Lines        1015     1039      +24     
  Branches      221      227       +6     
==========================================
+ Hits          787      811      +24     
  Misses        197      197              
  Partials       31       31              
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/projectmesa/mesa/pull/1920?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa).

Corvince: I definitely like this PR and this is something we should implement. 
However the first thing that comes to my mind is that this would be a breaking change and could potentially really break a lot of models, because I don't think it's uncommon to pass the coordinates as a list of x, y instead of a tuple. It's probably also used in some of the examples. Maybe there is a way to circumvent this issue. 
Corvince: One thing that could be done is to introduce this as a now function that is simply called "move" and at some time deprecate the otherk one.
EwoutH: > because I don't think it's uncommon to pass the coordinates as a list of x, y instead of a tuple.

Good point, I also notice this in testing.

What if we check if it's a sequence of numbers (sequence of int/float). That way it would catch lists coordinate input, but still allow multiple coordinates (which would be sequences of sequences).
EwoutH: Implemented in 0e8e42f. None of the test are now needed to be modified.

We should still steer to inputting tuples, it's also type hinted that way. But that can be another effort.
EwoutH: This can be quite slow for long lists of agents. Could we just check the first element?
Corvince: That sounds correct. Either the first element is just a number or another iterable. 
EwoutH: Implemented, all tests pass.

We have to think about how to process empty lists of possible positions. Either:
- Don't allow it (by crashing) (current behavior)
- Don't move the agent
Corvince: Good question. My first instinct would say don't move but issue a warning. I guess most of the time something went wrong when trying to move to an empty list of cells, but crashing the program seems a bit harsh.
EwoutH: Having thought about it a bit, let’s keep it this way for now. Before this PR, you where required to input a location and your agent would always move. Now, that’s still the case, only multiple is also allowed.

If empty lists become an issue that we can’t solve in usage, we can revisit this.
EwoutH: Still thinking about the empty lists case. Currently, if you think you might have no target locations, you have to check manually if this is the case:
```Python
possible_positions = some_selection_function()
if possible_positions >= 1:
  move_agent(agent, possible_positions)
```
Advantages:
- Explicit
- You can do a `else` if no location if found
- Maybe easier to debug

Disatvantages:
- Added boilerplate code

We could add a `allow_no_move` boolean to `move_agent`, which if true allows to input an empty list, which results in the agent not moving (either with or without warning).

However, then we fundamentally change the behavior of `move_agent`: Instead of always moving, we now maybe move the agent.

Another solution could be just to create a new method for these cases, and leave `move_agent` as it originally was. Then `move_agent` requires a single position and you can be sure your agents moves there, while `move_agent_to_one_of` moves an agent to one of a list. If the list if empty, it doesn't move (and we could add a bool for a warning if that happens).
quaquel: > Another solution could be just to create a new method for these cases, and leave `move_agent` as it originally was. Then `move_agent` requires a single position and you can be sure your agents moves there, while `move_agent_to_one_of` moves an agent to one of a list. If the list if empty, it doesn't move (and we could add a bool for a warning if that happens).

I like the clarity of `move_agent_to_one_off` and keeping it separate from `move`. In this case, you can keep the default behavior as `random`, like you want. I am unsure about the behavior of the following two cases.

1. Empty list; I am inclined to raise an error in this case. You cannot move, so it is an error, and errors should not be passed over silently. It is up to the user to catch the exception and handle it properly.  Clearly, this must be documented well. 
2. list with one item; in principle, you can simply handle this identically to a list larger than one. 
EwoutH: Fully refactored the PR. There is now a new method `move_agent_to_one_of` (suggestions for other names are welcome), and the `move_agent` method is unchanged. Docs are updated and tests pass.

Random is the default selection method and by default, empty lists are allowed. You can optionally enable warnings or errors on empty list input.

Curious what everybody thinks!

Patch:
diff --git a/mesa/space.py b/mesa/space.py
index 18cf7314..987afaf9 100644
--- a/mesa/space.py
+++ b/mesa/space.py
@@ -431,6 +431,69 @@ class _Grid:
         self.remove_agent(agent)
         self.place_agent(agent, pos)
 
+    def move_agent_to_one_of(
+        self,
+        agent: Agent,
+        pos: list[Coordinate],
+        selection: str = "random",
+        handle_empty: str | None = None,
+    ) -> None:
+        """
+        Move an agent to one of the given positions.
+
+        Args:
+            agent: Agent object to move. Assumed to have its current location stored in a 'pos' tuple.
+            pos: List of possible positions.
+            selection: String, either "random" (default) or "closest". If "closest" is selected and multiple
+                       cells are the same distance, one is chosen randomly.
+            handle_empty: String, either "warning", "error" or None (default). If "warning" or "error" is selected
+                          and no positions are given (an empty list), a warning or error is raised respectively.
+        """
+        # Only move agent if there are positions given (non-empty list)
+        if pos:
+            if selection == "random":
+                chosen_pos = agent.random.choice(pos)
+            elif selection == "closest":
+                current_pos = agent.pos
+                # Find the closest position without sorting all positions
+                closest_pos = None
+                min_distance = float("inf")
+                for p in pos:
+                    distance = self._distance_squared(p, current_pos)
+                    if distance < min_distance:
+                        min_distance = distance
+                        closest_pos = p
+                chosen_pos = closest_pos
+            else:
+                raise ValueError(
+                    f"Invalid selection method {selection}. Choose 'random' or 'closest'."
+                )
+            #  Move agent to chosen position
+            self.move_agent(agent, chosen_pos)
+
+        # If no positions are given, throw warning/error if selected
+        elif handle_empty == "warning":
+            warn(
+                f"No positions given, could not move agent {agent.unique_id}.",
+                RuntimeWarning,
+                stacklevel=2,
+            )
+        elif handle_empty == "error":
+            raise ValueError(
+                f"No positions given, could not move agent {agent.unique_id}."
+            )
+
+    def _distance_squared(self, pos1: Coordinate, pos2: Coordinate) -> float:
+        """
+        Calculate the squared Euclidean distance between two points for performance.
+        """
+        # Use squared Euclidean distance to avoid sqrt operation
+        dx, dy = abs(pos1[0] - pos2[0]), abs(pos1[1] - pos2[1])
+        if self.torus:
+            dx = min(dx, self.width - dx)
+            dy = min(dy, self.height - dy)
+        return dx**2 + dy**2
+
     def swap_pos(self, agent_a: Agent, agent_b: Agent) -> None:
         """Swap agents positions"""
         agents_no_pos = []


Test patch:
diff --git a/tests/test_space.py b/tests/test_space.py
index f8f2cc94..ab0e0da3 100644
--- a/tests/test_space.py
+++ b/tests/test_space.py
@@ -327,6 +327,33 @@ class TestSingleGrid(unittest.TestCase):
         assert self.space[initial_pos[0]][initial_pos[1]] is None
         assert self.space[final_pos[0]][final_pos[1]] == _agent
 
+    def test_move_agent_random_selection(self):
+        agent = self.agents[0]
+        possible_positions = [(10, 10), (20, 20), (30, 30)]
+        self.space.move_agent_to_one_of(agent, possible_positions, selection="random")
+        assert agent.pos in possible_positions
+
+    def test_move_agent_closest_selection(self):
+        agent = self.agents[0]
+        agent.pos = (5, 5)
+        possible_positions = [(6, 6), (10, 10), (20, 20)]
+        self.space.move_agent_to_one_of(agent, possible_positions, selection="closest")
+        assert agent.pos == (6, 6)
+
+    def test_move_agent_invalid_selection(self):
+        agent = self.agents[0]
+        possible_positions = [(10, 10), (20, 20), (30, 30)]
+        with self.assertRaises(ValueError):
+            self.space.move_agent_to_one_of(
+                agent, possible_positions, selection="invalid_option"
+            )
+
+    def test_distance_squared(self):
+        pos1 = (3, 4)
+        pos2 = (0, 0)
+        expected_distance_squared = 3**2 + 4**2
+        assert self.space._distance_squared(pos1, pos2) == expected_distance_squared
+
     def test_iter_cell_list_contents(self):
         """
         Test neighborhood retrieval
@@ -350,6 +377,68 @@ class TestSingleGrid(unittest.TestCase):
         assert len(cell_list_4) == 1
 
 
+class TestSingleGridTorus(unittest.TestCase):
+    def setUp(self):
+        self.space = SingleGrid(50, 50, True)  # Torus is True here
+        self.agents = []
+        for i, pos in enumerate(TEST_AGENTS_GRID):
+            a = MockAgent(i, None)
+            self.agents.append(a)
+            self.space.place_agent(a, pos)
+
+    def test_move_agent_random_selection(self):
+        agent = self.agents[0]
+        possible_positions = [(49, 49), (1, 1), (25, 25)]
+        self.space.move_agent_to_one_of(agent, possible_positions, selection="random")
+        assert agent.pos in possible_positions
+
+    def test_move_agent_closest_selection(self):
+        agent = self.agents[0]
+        agent.pos = (0, 0)
+        possible_positions = [(3, 3), (49, 49), (25, 25)]
+        self.space.move_agent_to_one_of(agent, possible_positions, selection="closest")
+        # Expecting (49, 49) to be the closest in a torus grid
+        assert agent.pos == (49, 49)
+
+    def test_move_agent_invalid_selection(self):
+        agent = self.agents[0]
+        possible_positions = [(10, 10), (20, 20), (30, 30)]
+        with self.assertRaises(ValueError):
+            self.space.move_agent_to_one_of(
+                agent, possible_positions, selection="invalid_option"
+            )
+
+    def test_move_agent_empty_list(self):
+        agent = self.agents[0]
+        possible_positions = []
+        agent.pos = (3, 3)
+        self.space.move_agent_to_one_of(agent, possible_positions, selection="random")
+        assert agent.pos == (3, 3)
+
+    def test_move_agent_empty_list_warning(self):
+        agent = self.agents[0]
+        possible_positions = []
+        # Should assert RuntimeWarning
+        with self.assertWarns(RuntimeWarning):
+            self.space.move_agent_to_one_of(
+                agent, possible_positions, selection="random", handle_empty="warning"
+            )
+
+    def test_move_agent_empty_list_error(self):
+        agent = self.agents[0]
+        possible_positions = []
+        with self.assertRaises(ValueError):
+            self.space.move_agent_to_one_of(
+                agent, possible_positions, selection="random", handle_empty="error"
+            )
+
+    def test_distance_squared_torus(self):
+        pos1 = (0, 0)
+        pos2 = (49, 49)
+        expected_distance_squared = 1**2 + 1**2  # In torus, these points are close
+        assert self.space._distance_squared(pos1, pos2) == expected_distance_squared
+
+
 class TestSingleNetworkGrid(unittest.TestCase):
     GRAPH_SIZE = 10