Interactive Multi-Agent Parallel Pathfinding Simulator (IMAPPS)

An interactive multi-agent pathfinding simulator in Python using Pygame, and multi-processing modules for parallel A* path computations and optimizations. This repository contains both the serial and parallel implementations of the simulator.

Table of Contents:

1. Key Features
2. Pathfinding Algorithm
3. System Requirements
4. Installation
5. Project Structure
6. How to Run
7. Simulator Controls
8. Contributors

Key Features:

• A* based pathfinding for each agent
• Parallelized execution using Python’s multiprocessing
• Configurable grid size and number of agents
• Agents move orthogonally (4-ways) in a 2D grid space.
• Place agents, goals and obstacles with easy mouse controls.
• Agents can dynamically replan their paths if blocked by other agents.
• Measure time performance of A* path calculations.

Pathfinding Algorithm:

A* Algorithm

Each agent computes the shortest path to its goal using the A* algorithm.

• Heuristic used: Manhattan distance
  
• Cost Function: f(n) = g(n) + h(n)
  
• Neighbors: 4-directional (up, down, left, right)
  
• Obstacles: Cells marked as blocked are ignored during path expansion.
  

System Requirements:

• Python version: 3.13 or newer
• OS: Windows 10/11, macOS, or Linux
• RAM: 4GB or more
• CPU:
  • Minimum: Dual-core processor (e.g., Intel Core i3 or AMD Ryzen 3)
  • Recommended: Quad-core or higher (e.g., Intel Core i5/i7, AMD Ryzen 5/7)

Installation:

# Clone the repository
git clone https://github.com/ElectroCubic/Multi-Agent-Pathfinding-Sim.git
cd Multi-Agent-Pathfinding-Sim

# Install dependencies
pip install -r requirements.txt

Project Structure:

Serial_version contains –

• astar.py
• config.py
• main.py
• node.py
• renderer.py
• sim.py

Parallel_version contains –

• astar.py
• config.py
• main.py
• multi_processing_worker.py
• node.py
• renderer.py
• sim.py

How To Run:

Navigate to the root folder of the project and open the terminal:

For Serial Version:

python serial_version/main.py

For Parallel Version:

python parallel_version/main.py

Both commands will open a Pygame window where you can see the version name currently running in the Title bar (Serial/Parallel). The simulation results can be reproduced by just placing the exact same positions of the elements and running them manually. Timings of the result may vary depending upon system configuration.

Simulator Controls:

• Press T to toggle Wall Mode. Then use Left Click to place/remove walls.
• Press Right Mouse Button to place Agents.
• Press Middle Mouse Button to place Goals.
• Press Space bar to run the simualation.
• Press R to Reset the agents and goals.

Contributors:

• Anush Bundel - 2023BCS0005

• Ankush Sharma - 2023BCS0131