Firefighter Problem Simulator

School project completed in pairs between October 2019 and March 2020.
Inspired by the “Firefighter Problem” introduced by B. Hartnell (1995), this project aims to create an interactive simulator of the fire spread process and its defence by firefighters on a graph – modelled here as a grid.

❓ Issue

How to test different defence strategies against a fire spreading through a network, while maximising the saved vertices?
➡️ The challenge is to dynamically represent a NP-complete combinatorial phenomenon and make it visual and interactive.

🛠️ Implemented solution

• 🔥 Representation of the graph as a grid (NxN matrix)

• 🚒 Ability to place initial fires and one or more firefighters

• 🔁 Iterative simulation: at each turn, the fire spreads to unprotected neighbours and the firefighters protect squares

• 👁️ Graphical interface developed with Tkinter allowing the user to:

  • manually place the elements

  • visualise the turn-by-turn evolution

  • change the rules (speed, number of firefighters, initial position, etc.)

⚙️ Technical stack

• Language: Python

• Interface library: Tkinter

• Modelling: Graph theory · Grids (matrices)

• Algorithmic concepts: propagation · heuristics · NP complexity

• Diagrams: class diagrams for object modelling

• Environment: Jupyter Notebook / local IDE