Repository: projectmesa/mesa
Pull request #1890 (2023-11-27 17:06:39)

Add DiscreteEventScheduler
This PR introduces the DiscreteEventScheduler, an addition to the Mesa time module. This new scheduler is designed for discrete event simulation, where agent steps are scheduled to occur at specific simulation times, rather than at regular, step-wise intervals.

Key Features:
- The scheduler advances the simulation to the time of the next scheduled event, handling multiple events efficiently.
- If multiple events are scheduled for the same time, their execution order is randomized. This is achieved by adding a secondary sorting criterion based on a random value. This ensures fairness and reduces bias that might occur from consistent ordering.
- The `model.step()` works the same by default: It advances time by 1. The DiscreteEventScheduler has a keyword argument `time_step` (default 1) which is the period in which the model is advanced by each model.step() call. In that period, agent may execute their step function zero, one or multiple times, depending on the amount of eventa scheduled for that agent.
  - This allows easy adaption from current models, and to gather data at regular intervals.

Modifications:
- Added the DiscreteEventScheduler class with methods to schedule and process events.
- Modified the `schedule_event` method to include a random value for secondary sorting in the event queue.
- Adjusted the `step` method to handle events within a given time frame, advancing the simulation in fixed time steps.
- Modified the `add` method to have a `schedule_now` keyword, which is True by default. When True, the first event for that agent is immediately added to the schedule. 

Two example models are available, a very simple one and a slightly more complex one.

```Python
from mesa import Model, Agent
from mesa.time import DiscreteEventScheduler
import random

class MyAgent(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        # Agent initialization code here

    def step(self):
        # Agent action code here
        # For example, schedule next action after a random delay using schedule_in
        print(f"Agent {self.unique_id} executing step at time {self.model.schedule.time}")
        delay = random.uniform(1, 2)
        self.model.schedule.schedule_in(delay, self)

class MyModel(Model):
    def __init__(self, num_agents):
        self.schedule = DiscreteEventScheduler(self, time_step=1)
        # Initialize and add agents
        for i in range(num_agents):
            agent = MyAgent(i, self)
            self.schedule.add(agent, schedule_now=True)

    def step(self):
        self.schedule.step()  # Execute events for the next time step

# Create and run the model
model = MyModel(num_agents=5)
for i in range(10):  # Run for 20 steps
    model.step()
```
More complex example:

<details>

```Python
from mesa import Agent, Model
from mesa.space import MultiGrid
from mesa.datacollection import DataCollector
from mesa.time import DiscreteEventScheduler
import random


class Prey(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.energy = 5

    def step(self):
        # print(f"Prey {self.unique_id} executing step at time {self.model.schedule.time}")
        if self.energy <= 0:
            self.model.schedule.remove(self)
        else:
            self.move()
            self.energy -= 1
            self.eat()
            # Schedule next move at a random time in the future
            next_event_time = self.model.schedule.time + random.uniform(1, 2)
            self.model.schedule.schedule_event(next_event_time, self)

    def eat(self):
        self.energy += random.uniform(1, 2)
    def move(self):
        # Move to a random neighboring cell
        possible_steps = self.model.grid.get_neighborhood(
            self.pos,
            moore=True,
            include_center=False
        )
        new_position = random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)

    def reproduce(self):
        # If another prey is in the same cell, reproduce
        this_cell = self.pos
        x, y = this_cell
        this_cell_agents = self.model.grid[x][y]
        for agent in this_cell_agents:
            if isinstance(agent, Prey):
                child = Prey(self.model.next_id(), self.model)
                self.model.schedule.add(child)
                self.model.grid.place_agent(child, self.pos)
                return


class Predator(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.hunger = 5

    def step(self):
        # print(f"Predator {self.unique_id} executing step at time {self.model.schedule.time}")
        if self.hunger <= 0:
            self.model.schedule.remove(self)
        else:
            self.hunt()
            self.hunger -= 1
            # Schedule next hunt at a random time in the future
            next_event_time = self.model.schedule.time + random.uniform(2, 4)
            self.model.schedule.schedule_event(next_event_time, self)

    def hunt(self):
        # If a prey is in the same cell, eat it
        this_cell = self.pos
        x, y = this_cell
        this_cell_agents = self.model.grid[x][y]
        for agent in this_cell_agents:
            if isinstance(agent, Prey):
                self.model.schedule.remove(agent)
                self.model.grid.remove_agent(agent)

                self.hunger += random.uniform(5, 10)
                return
        else:
            # Move to a neighboring cell
            self.move()

    def move(self):
        # Move to a random neighboring cell
        possible_steps = self.model.grid.get_neighborhood(
            self.pos,
            moore=True,
            include_center=False
        )
        new_position = random.choice(possible_steps)
        self.model.grid.move_agent(self, new_position)

class EcosystemModel(Model):
    def __init__(self, N, width, height):
        super().__init__()
        self.num_agents = N
        self.grid = MultiGrid(width, height, True)
        self.schedule = DiscreteEventScheduler(self)
        self.prey = []
        self.predators = []
        self.datacollector = DataCollector(
            model_reporters={
                "N": lambda m: m.schedule.time,
                "Prey": lambda m: len(m.prey),
                "Predators": lambda m: len(m.predators),
                "Prey average energy": lambda m: sum([a.energy for a in m.prey]) / len(m.prey) if len(m.prey) > 0 else 0,
                "Predator average hunger": lambda m: sum([a.hunger for a in m.predators]) / len(m.predators) if len(m.predators) > 0 else 0,
            }
        )

        # Create predators and prey
        for i in range(self.num_agents):
            if random.random() < 0.5:
                a = Prey(self.next_id(), self)
                self.prey.append(a)
            else:
                a = Predator(self.next_id(), self)
                self.predators.append(a)
            self.schedule.add(a, schedule_now=True)
            # Place the agent on the grid
            x = random.randrange(self.grid.width)
            y = random.randrange(self.grid.height)
            self.grid.place_agent(a, (x, y))

    def step(self):
        self.schedule.step()
        # Update prey and predator lists
        self.prey = [a for a in self.schedule.agents if isinstance(a, Prey)]
        self.predators = [a for a in self.schedule.agents if isinstance(a, Predator)]
        self.datacollector.collect(self)


model = EcosystemModel(N=25, width=10, height=10)
for i in range(100):  # Run for 25 steps
    model.step()
print(model.datacollector.get_model_vars_dataframe())
```

</details>

Both are also available in this ZIP, and below: [discrete_event_example_models.zip](https://github.com/projectmesa/mesa/files/13479627/discrete_event_example_models.zip)

#### Todo:
- [x] Check if manually needing to schedule first event can be integrated (yes!)
- [x] Add tests

Ready for review!

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) Report
Attention: `18 lines` in your changes are missing coverage. Please review.
> Comparison is base [(`70b2902`)](https://app.codecov.io/gh/projectmesa/mesa/commit/70b2902d10a7c6a1bc3f90156a29b7a5216b585c?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) 77.10% compared to head [(`09b517f`)](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) 75.90%.
> Report is 1 commits behind head on main.

| [Files](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) | Patch % | Lines |
|---|---|---|
| [mesa/time.py](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa#diff-bWVzYS90aW1lLnB5) | 30.76% | [18 Missing :warning: ](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=projectmesa) |

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


```diff
@@            Coverage Diff             @@
##             main    #1890      +/-   ##
==========================================
- Coverage   77.10%   75.90%   -1.21%     
==========================================
  Files          15       15              
  Lines         974     1000      +26     
  Branches      214      217       +3     
==========================================
+ Hits          751      759       +8     
- Misses        195      213      +18     
  Partials       28       28              
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/projectmesa/mesa/pull/1890?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).


Patch:
diff --git a/README.md b/README.md
index a1f617b8..ca2da39e 100644
--- a/README.md
+++ b/README.md
@@ -32,7 +32,7 @@ Getting started quickly:
 pip install mesa
 ```
 
-You can also use [pip]{.title-ref} to install the github version:
+You can also use `pip` to install the github version:
 
 ``` bash
 pip install -U -e git+https://github.com/projectmesa/mesa@main#egg=mesa
@@ -91,7 +91,7 @@ to:
     the path of your model
 -   make sure that the model folder contains an app.py file
 
-Then, you just need to run [docker compose up -d]{.title-ref} to have it
+Then, you just need to run `docker compose up -d` to have it
 accessible from `localhost:8765`.
 
 ## Contributing to Mesa
diff --git a/mesa/space.py b/mesa/space.py
index 6ed7c096..18cf7314 100644
--- a/mesa/space.py
+++ b/mesa/space.py
@@ -492,9 +492,18 @@ class SingleGrid(_Grid):
     bottom-left and [width-1, height-1] is the top-right. If a grid is
     toroidal, the top and bottom, and left and right, edges wrap to each other.
 
+    This class provides a property `empties` that returns a set of coordinates
+    for all empty cells in the grid. It is automatically updated whenever
+    agents are added or removed from the grid. The `empties` property should be
+    used for efficient access to current empty cells rather than manually
+    iterating over the grid to check for emptiness.
+
     Properties:
         width, height: The grid's width and height.
         torus: Boolean which determines whether to treat the grid as a torus.
+        empties: Returns a set of (x, y) tuples for all empty cells. This set is
+                 maintained internally and provides a performant way to query
+                 the grid for empty spaces.
     """
 
     def place_agent(self, agent: Agent, pos: Coordinate) -> None:
@@ -526,9 +535,14 @@ class MultiGrid(_Grid):
     bottom-left and [width-1, height-1] is the top-right. If a grid is
     toroidal, the top and bottom, and left and right, edges wrap to each other.
 
+    This class maintains an `empties` property, which is a set of coordinates
+    for all cells that currently contain no agents. This property is updated
+    automatically as agents are added to or removed from the grid.
+
     Properties:
         width, height: The grid's width and height.
         torus: Boolean which determines whether to treat the grid as a torus.
+        empties: Returns a set of (x, y) tuples for all empty cells.
     """
 
     grid: list[list[MultiGridContent]]
@@ -745,9 +759,13 @@ class HexSingleGrid(_HexGrid, SingleGrid):
     Functions according to odd-q rules.
     See http://www.redblobgames.com/grids/hexagons/#coordinates for more.
 
+    This class also maintains an `empties` property, similar to SingleGrid,
+    which provides a set of coordinates for all empty hexagonal cells.
+
     Properties:
         width, height: The grid's width and height.
         torus: Boolean which determines whether to treat the grid as a torus.
+        empties: Returns a set of hexagonal coordinates for all empty cells.
     """
 
 
@@ -758,9 +776,15 @@ class HexMultiGrid(_HexGrid, MultiGrid):
     Functions according to odd-q rules.
     See http://www.redblobgames.com/grids/hexagons/#coordinates for more.
 
+    Similar to the standard MultiGrid, this class maintains an `empties` property,
+    which is a set of coordinates for all hexagonal cells that currently contain
+    no agents. This property is updated automatically as agents are added to or
+    removed from the grid.
+
     Properties:
         width, height: The grid's width and height.
         torus: Boolean which determines whether to treat the grid as a torus.
+        empties: Returns a set of hexagonal coordinates for all empty cells.
     """
 
 
@@ -797,6 +821,9 @@ class ContinuousSpace:
     This class uses a numpy array internally to store agents in order to speed
     up neighborhood lookups. This array is calculated on the first neighborhood
     lookup, and is updated if agents are added or removed.
+
+    The concept of 'empty cells' is not directly applicable in continuous space,
+    as positions are not discretized.
     """
 
     def __init__(
diff --git a/mesa/time.py b/mesa/time.py
index 1b5c2bb1..ca54bab7 100644
--- a/mesa/time.py
+++ b/mesa/time.py
@@ -25,6 +25,7 @@ Key concepts:
 # Remove this __future__ import once the oldest supported Python is 3.10
 from __future__ import annotations
 
+import heapq
 from collections import defaultdict
 
 # mypy
@@ -327,3 +328,108 @@ class RandomActivationByType(BaseScheduler):
         Returns the current number of agents of certain type in the queue.
         """
         return len(self.agents_by_type[type_class])
+
+
+class DiscreteEventScheduler(BaseScheduler):
+    """
+    A scheduler for discrete event simulation in Mesa.
+
+    This scheduler manages events where each event is associated with a
+    specific time and agent. The scheduler advances time not in fixed
+    increments, but to the moment the next event is scheduled to occur.
+
+    This implementation uses a priority queue (heapq) to manage events. Each
+    event is a tuple of the form (time, random_value, agent), where:
+        - time (float): The scheduled time for the event.
+        - random_value (float): A secondary sorting criterion to randomize
+          the order of events that are scheduled for the same time.
+        - agent (Agent): The agent associated with the event.
+
+    The random value for secondary sorting ensures that when two events are
+    scheduled for the same time, their execution order is randomized, thus
+    preventing direct comparison issues between different types of agents and
+    maintaining the integrity of the simulation's randomness.
+
+    Attributes:
+        model (Model): The model instance associated with the scheduler.
+        event_queue (list): A priority queue of scheduled events.
+        time_step (int or float): The fixed time period by which the model advances
+                                  on each step. Defaults to 1.
+
+    Methods:
+        schedule_event(time, agent): Schedule an event for a specific time.
+        schedule_in(delay, agent): Schedule an event after a specified delay.
+        step(): Execute all events within the next time_step period.
+        get_next_event_time(): Returns the time of the next scheduled event.
+
+    Usage:
+        1. Instantiate the DiscreteEventScheduler with a model instance and a time_step period.
+        2. Add agents to the scheduler using schedule.add(). With schedule_now=True (default),
+              the first event for the agent will be scheduled immediately.
+        3. In the Agent step() method, schedule the next event for the agent
+              (using schedule_in or schedule_event).
+        3. Add self.schedule.step() to the model's step() method, as usual.
+
+    Now, with each model step, the scheduler will execute all events within the
+    next time_step period, and advance time one time_step forward.
+    """
+
+    def __init__(self, model: Model, time_step: TimeT = 1) -> None:
+        super().__init__(model)
+        self.event_queue: list[tuple[TimeT, float, Agent]] = []
+        self.time_step: TimeT = time_step  # Fixed time period for each step
+
+    def schedule_event(self, time: TimeT, agent: Agent) -> None:
+        """Schedule an event for an agent at a specific time."""
+        if time < self.time:
+            raise ValueError(
+                f"Scheduled time ({time}) must be >= the current time ({self.time})"
+            )
+        # Create an event, sorted first on time, secondary on a random value
+        event = (time, self.model.random.random(), agent)
+        heapq.heappush(self.event_queue, event)
+
+    def schedule_in(self, delay: TimeT, agent: Agent) -> None:
+        """Schedule an event for an agent after a specified delay."""
+        if delay < 0:
+            raise ValueError("Delay must be non-negative")
+        event_time = self.time + delay
+        self.schedule_event(event_time, agent)
+
+    def step(self) -> None:
+        """Execute the next event and advance the time."""
+        end_time = self.time + self.time_step
+
+        while self.event_queue and self.event_queue[0][0] <= end_time:
+            # Get the next event (ignore the random value during unpacking)
+            time, _, agent = heapq.heappop(self.event_queue)
+
+            # Advance time to the event's time
+            self.time = time
+
+            # Execute the event
+            if agent.unique_id in self._agents:
+                agent.step()
+
+        # After processing events, advance time by the time_step
+        self.time = end_time
+        self.steps += 1
+
+    def get_next_event_time(self) -> TimeT | None:
+        """Returns the time of the next scheduled event."""
+        if not self.event_queue:
+            return None
+        return self.event_queue[0][0]
+
+    def add(self, agent: Agent, schedule_now: bool = True) -> None:
+        """Add an Agent object to the schedule and optionally schedule its first event.
+
+        Args:
+            agent: An Agent to be added to the schedule. Must have a step() method.
+            schedule_now: If True, schedules the first event for the agent immediately.
+        """
+        super().add(agent)  # Call the add method from BaseScheduler
+
+        if schedule_now:
+            # Schedule the first event immediately
+            self.schedule_event(self.time, agent)


Test patch:
diff --git a/tests/test_time.py b/tests/test_time.py
index 60dbf506..dda68032 100644
--- a/tests/test_time.py
+++ b/tests/test_time.py
@@ -8,6 +8,7 @@ from unittest import TestCase, mock
 from mesa import Agent, Model
 from mesa.time import (
     BaseScheduler,
+    DiscreteEventScheduler,
     RandomActivation,
     RandomActivationByType,
     SimultaneousActivation,
@@ -274,5 +275,114 @@ class TestRandomActivationByType(TestCase):
             model.schedule.add(b)
 
 
+class TestDiscreteEventScheduler(TestCase):
+    def setUp(self):
+        self.model = MockModel()
+        self.scheduler = DiscreteEventScheduler(self.model, time_step=1)
+        self.model.schedule = self.scheduler
+        self.agent1 = MockAgent(1, self.model)
+        self.agent2 = MockAgent(2, self.model)
+        self.model.schedule.add(self.agent1, schedule_now=False)
+        self.model.schedule.add(self.agent2, schedule_now=False)
+
+    # Testing Initialization and Attributes
+    def test_initialization(self):
+        self.assertIsInstance(self.scheduler.event_queue, list)
+        self.assertEqual(self.scheduler.time_step, 1)
+
+    # Testing Event Scheduling
+    def test_schedule_event(self):
+        self.scheduler.schedule_event(5, self.agent1)
+        self.assertEqual(len(self.scheduler.event_queue), 1)
+        event_time, _, event_agent = self.scheduler.event_queue[0]
+        self.assertEqual(event_time, 5)
+        self.assertEqual(event_agent, self.agent1)
+
+    def test_schedule_event_with_float_time(self):
+        self.scheduler.schedule_event(5.5, self.agent1)
+        self.assertEqual(len(self.scheduler.event_queue), 1)
+        event_time, _, event_agent = self.scheduler.event_queue[0]
+        self.assertEqual(event_time, 5.5)
+        self.assertEqual(event_agent, self.agent1)
+
+    def test_schedule_in(self):
+        self.scheduler.schedule_in(3, self.agent2)
+        _, _, event_agent = self.scheduler.event_queue[0]
+        self.assertEqual(event_agent, self.agent2)
+        self.assertEqual(self.scheduler.get_next_event_time(), self.scheduler.time + 3)
+
+    # Testing Event Execution and Time Advancement
+    def test_step_function(self):
+        self.scheduler.schedule_event(1, self.agent1)
+        self.scheduler.schedule_event(2, self.agent2)
+        self.scheduler.step()
+        self.assertEqual(self.scheduler.time, 1)
+        self.assertEqual(self.agent1.steps, 1)
+        self.assertEqual(self.agent2.steps, 0)
+
+    def test_time_advancement(self):
+        self.scheduler.schedule_event(5, self.agent1)
+        self.scheduler.step()
+        self.assertEqual(self.scheduler.time, 1)
+        self.scheduler.step()
+        self.assertEqual(self.scheduler.time, 2)
+
+    def test_no_events(self):
+        self.scheduler.step()
+        self.assertEqual(self.scheduler.time, 1)
+
+    # Testing Edge Cases and Error Handling
+    def test_invalid_event_time(self):
+        with self.assertRaises(ValueError):
+            self.scheduler.schedule_event(-1, self.agent1)
+
+    def test_immediate_event_execution(self):
+        # Current time of the scheduler
+        current_time = self.scheduler.time
+
+        # Schedule an event at the current time
+        self.scheduler.schedule_event(current_time, self.agent1)
+
+        # Step the scheduler and check if the event is executed immediately
+        self.scheduler.step()
+        self.assertEqual(self.agent1.steps, 1)
+
+        # The time should advance to the next time step after execution
+        self.assertEqual(self.scheduler.time, current_time + 1)
+
+    # Testing Utility Functions
+    def test_get_next_event_time(self):
+        self.scheduler.schedule_event(10, self.agent1)
+        self.assertEqual(self.scheduler.get_next_event_time(), 10)
+
+    # Test add() method with and without immediate scheduling
+    def test_add_with_immediate_scheduling(self):
+        # Add an agent with schedule_now set to True (default behavior)
+        new_agent = MockAgent(3, self.model)
+        self.scheduler.add(new_agent)
+
+        # Check if the agent's first event is scheduled immediately
+        self.assertEqual(len(self.scheduler.event_queue), 1)
+        event_time, _, event_agent = self.scheduler.event_queue[0]
+        self.assertEqual(event_time, self.scheduler.time)
+        self.assertEqual(event_agent, new_agent)
+
+        # Step the scheduler and check if the agent's step method is executed
+        self.scheduler.step()
+        self.assertEqual(new_agent.steps, 1)
+
+    def test_add_without_immediate_scheduling(self):
+        # Add an agent with schedule_now set to False
+        new_agent = MockAgent(4, self.model)
+        self.scheduler.add(new_agent, schedule_now=False)
+
+        # Check if the event queue is not updated
+        self.assertEqual(len(self.scheduler.event_queue), 0)
+
+        # Step the scheduler and verify that the agent's step method is not executed
+        self.scheduler.step()
+        self.assertEqual(new_agent.steps, 0)
+
+
 if __name__ == "__main__":
     unittest.main()