Project Overview

This project, maze_path_finder, implements multiple algorithms for pathfinding. The project includes two implementations: one for pathfinding in 2D on a square grid, and one for pathfinding in 3D on a cubical grid. The 2D visualization is done using the curses library, while the 3D visualization is done using the ursina library.

Project Structure

  • pathfinding/path_finder.py: Implements 2D pathfinding algorithms and visualization.
  • pathfinding/maze.csv: Contains maze data in CSV format.
  • pathfinding_3d/main.py: The main script for 3D pathfinding algorithms.
  • pathfinding_3d/pathfinding.py: Implements 3D pathfinding methods and cell relationships across cube faces.
  • requirements.txt: Lists the required dependencies for the project.

Features

  • 2D Pathfinding: Pathfinding algorithms with visualization using curses.
  • 3D Pathfinding: Pathfinding algorithms with visualization using ursina, offering interactive 3D views with user-controlled cameras.

2D Path Finding Visualized

The 2D visualization of the maze and pathfinding process is displayed using the curses library, providing a terminal-based interface.

Example 1

Maze Type 0

Example 2

Maze Type 4

3D Path Finding Visualized

The 3D visualization of the maze and pathfinding process is displayed using the ursina library, allowing an interactive user-controlled camera view.

3D Maze Example

3D Maze

Algorithms Implemented

  1. Breadth-First Search (BFS)
  2. Depth-First Search (DFS)
  3. A* Search (with four heuristics: Manhattan, Euclidean, Chebyshev, and Octile)
  4. Greedy Best-First Search
  5. Dijkstra
  6. Bidirectional Search

Algorithms Explained

1. Breadth-First Search (BFS)

Breadth-First Search is an algorithm that explores all the nodes at the present depth level before moving on to the nodes at the next depth level. It uses a queue to keep track of the nodes to be explored next. The implementation can be found in the bfs function.

2. Depth-First Search (DFS)

Depth-First Search is an algorithm that explores as far as possible along each branch before backtracking. It uses a stack (or recursion) to keep track of the nodes to be explored next. The implementation can be found in the dfs function.

3. A* Search

A* Search is an algorithm that finds the shortest path by combining the cost to reach the current node and a heuristic estimate of the cost to reach the goal. It uses a priority queue to expand the node with the lowest combined cost. The implementation can be found in the a_star function.

4. Greedy Best-First Search (GBFS)

GBFS is an algorithm that expands the most promising node chosen according to a specified rule. It uses a heuristic to estimate the cost to reach the goal from the current node and always expands the node with the lowest estimated cost. The implementation can be found in the gbfs function.

5. Dijkstra's Algorithm

Dijkstra's Algorithm finds the shortest path from the start position to the end position in a weighted graph. It uses a priority queue to explore the node with the lowest cost first and updates the cost of reaching its neighbors. The implementation can be found in the dijkstra function.

6. Bidirectional Search

Bidirectional Search is an algorithm that simultaneously searches from the start and end positions until the two searches meet. This can significantly reduce the search space and time compared to unidirectional search. The implementation can be found in the bidirectional function.

Heuristics

1. Manhattan Distance

The Manhattan distance between two points is the sum of the absolute differences of their Cartesian coordinates. It is used in grid-based path finding where movement is restricted to horizontal and vertical directions. The implementation can be found in the heuristic function with the type "manhattan".

2. Euclidean Distance

The Euclidean distance between two points is the straight-line distance between them. It is used in scenarios where movement can occur in any direction. The implementation can be found in the heuristic function with the type "euclidean".

3. Chebyshev Distance

The Chebyshev distance between two points is the maximum of the absolute differences of their Cartesian coordinates. It is used in grid-based path finding where movement can occur in any direction, including diagonally. The implementation can be found in the heuristic function with the type "chebyshev".

4. Octile Distance

The Octile distance is a combination of Manhattan and diagonal distances. It is used in grid-based path finding where diagonal movement is allowed but has a different cost than horizontal and vertical movement. The implementation can be found in the heuristic function with the type "octile".

Usage

2D Pathfinding

  1. Ensure Python is installed on your system.
  2. Install the required dependencies: 
    pip install -r requirements.txt
    Note: On Windows, install windows-curses for the curses library.
  3. Run the 2D pathfinder script: 
    python pathfinding/path_finder.py

Command Line Arguments

path_finder.py [-h] [--rows ROWS] [--cols COLS] [--maze_type MAZE_TYPE]
  • -h, --help: Show help message and exit
  • --rows ROWS: Number of rows in the maze
  • --cols COLS: Number of columns in the maze
  • --maze_type MAZE_TYPE: Type of maze to generate. Options: 0 (small), 1 (large), 2 (CSV), 3 (random grid), 4 (random).

3D Pathfinding

  1. Ensure Python is installed on your system.
  2. Install the required dependencies: 
    pip install -r requirements.txt
  3. Run the 3D pathfinder script: 
    python pathfinding_3d/main.py