BFS Path Finder

A pathfinding visualizer that uses the Breadth-First Search (BFS) algorithm to compute the shortest path on a grid. The application outputs the path from a start position to a target while avoiding obstacles.

---

Overview

This project implements a grid-based pathfinding system and a Qt/QML graphical interface to visualize the shortest path between two points discovered by BFS.

The screenshots folder contains images demonstrating the debugging cases (path length = 10 breakpoint and a null pointer dereference), the project directory structure, and examples of sample input maps and their corresponding output visualizations.

The application allows users to load maps, generate random maps, and visualize shortest paths interactively.

---

Features

Battlefield Visualization

The UI displays a dynamic 64 × 64 battlefield grid where each cell is color-coded:

Tile Type	Color	Description
Free	White	Traversable terrain
Start	Green	Unit starting position
Target	Red	Destination
Elevated	Gray	Unreachable terrain
Path	Blue	Shortest path discovered by BFS

Cells can be hovered to inspect their row and column coordinates.

---

BFS Pathfinding

The backend implements a Breadth-First Search (BFS) algorithm to compute the shortest path between start and target cells.

Properties of the algorithm:

• Explores neighbors in four directions
  • Up
  • Down
  • Left
  • Right
• Avoids elevated terrain
• Guarantees the shortest path in an unweighted grid
• Uses backtracking to reconstruct the path

---

UI Functionalities

The interface provides several interactive controls.

Load Default Map

Loads a predefined battlematrix stored as a JSON file where Path Length = 10. Debugger screenshot is attached for this map configuartion.

---

Import Map

Allows the user to select a JSON map file from disk.

The imported file must represent a 64 × 64 battlefield grid. Sample map data files are present in 'data' folder.

When a new map is loaded:

• the previous grid is cleared
• internal data structures are reset
• the UI grid updates automatically

---

Randomize Map

Generates a random battlefield:

• random obstacles
• random start location
• random target location

This is useful for quickly testing the robustness of the pathfinding algorithm.

---

Visualize Path

Runs the BFS algorithm on the current battlefield and displays the resulting shortest path.

The discovered path is animated step-by-step across the grid to visualize traversal.

---

Clear Map

Resets the Grid:

• removes path visualization
• clears start and target
• clears all grid data
• resets the application state

---

Animation Toggle

Users can enable or disable path animation using a checkbox.

When disabled, the shortest path appears instantly.

---

Architecture

The project follows a Qt Model-View structure.

Frontend (QML)

The UI is built using Qt Quick / QML and provides:

• battlefield grid visualization
• animation control
• map loading
• user interaction

The grid dynamically reflects data exposed by the backend.

---

Backend (C++)

The core logic is implemented in C++.

Main Components

BattleMatrix

Represents the battlefield grid.

Responsibilities:

• store grid data
• convert between index and row/column
• retrieve cell types
• find neighboring cells

---

ShortestPath

Implements the BFS algorithm.

Responsibilities:

• search start and target positions
• perform BFS traversal
• track visited nodes
• reconstruct the shortest path

---

AppController

Acts as the bridge between QML UI and the C++ backend.

Responsibilities:

• load JSON maps
• generate random maps
• trigger BFS execution
• expose grid data to the UI
• expose path information to the UI

Setup and Installation

To run this project on your own machine, you need a Qt development environment with CMake support.

Requirements

• Qt Creator
• Qt 6 with the following modules:
  • Qt Quick
  • QML
  • Core
• CMake 3.16 or later
• A compatible C++ compiler:
  • MinGW 64-bit on Windows, or
  • another compiler supported by your Qt installation

Clone the Repository

Clone the repository to your local machine:

git clone https://github.com/insp7/path_finder_bfs.git
cd path_finder_bfs

Alternatively, download the repository as a ZIP file and extract it.

Open the Project in Qt Creator

1. Open Qt Creator
2. Select File → Open File or Project
3. Navigate to the repository folder
4. Open the CMakeLists.txt file
5. Choose a valid Qt kit such as Desktop Qt 6.x MinGW 64-bit
6. Allow Qt Creator to configure the project

Build the Project

After configuration:

• Click Build
• Or press Ctrl + B

Qt Creator will compile the C++ backend and prepare the QML UI.

Run the Application

Once the build completes successfully:

• Click Run
• Or press Ctrl + R

The BFS Path Finder application window should open.

Using the Application

After launching the application, you can:

• Load Default Map to test a predefined map where the path length equals 10
• Import Map to load a JSON map file from the data folder or another location
• Randomize Map to generate a random battlefield
• Visualize Path to run the BFS algorithm and display the shortest path
• Clear Map to reset the battlematrix
• Enable or disable animations using the checkbox in the control pane

Notes

• Sample JSON map files are located in the data folder
• Debugging screenshots and sample outputs are available in the screenshots folder
• If Qt Creator retains an old build configuration after renaming the project folder, delete the existing build folder and reopen the project using CMakeLists.txt

Acknowledgements

I've used AI assistance to improve the visual look and feel of the application and also referred to the official Qt documentation whenever I faced any implementation issues.