Building a Dynamic Pathfinding Agent with A* and Greedy Best-First Search

🚀 Introduction

Pathfinding is one of the most fundamental problems in Artificial Intelligence. From robot navigation and GPS systems to video games and autonomous vehicles, intelligent agents must constantly find optimal paths in complex and changing environments.

In this project, I built a Dynamic Pathfinding Agent capable of navigating a grid-based environment using two informed search algorithms:

• **A*** Search
• Greedy Best-First Search (GBFS)

The system includes:

• Interactive GUI
• Real-time visualization
• Dynamic obstacle spawning
• Automatic re-planning
• Performance metrics tracking

Let’s explore how it works.

🧠 The Problem

We want an agent that:

1. Starts from a fixed start node.
2. Reaches a fixed goal node.
3. Navigates around obstacles.
4. Adapts if new obstacles appear during movement.
5. This simulates real-world scenarios like:

• A delivery robot encounter unexpected objects.
• A vehicle rerouting due to road-block
• A game character avoiding dynamically placed traps.

🏗 System Overview

The project is implemented in Python using Tkinter for GUI visualization.

Key Components:

• Grid Environment
• Search Algorithms
• Heuristic Functions
• Dynamic Obstacle System
• Re-planning Mechanism
• Metrics Dashboard

🟦 Grid Environment

The world is represented as a 2D grid.

Each cell can be:

Value Meaning0 Empty1 Obstacle2 Start3 Goal

Features

• User-defined grid size (rows × columns)
• Random obstacle generation
• Interactive obstacle placement (mouse clicks)
• Fixed start and goal positions
• No static map files (fully dynamic)

🔍 Algorithms Implemented

1️⃣ Greedy Best-First Search (GBFS)

Evaluation Function

f(n)=h(n)

GBFS selects the node closest to the goal based only on heuristic distance.

Characteristics

• Very fast in open environments
• Does not consider path cost
• Not guaranteed optimal
• Can get trapped in complex maps

When It Works Well

• Straight paths
• Low obstacle density
• Simple environments

2️⃣ A* Search Algorithm

Evaluation Function

f(n) = g(n) + h(n)

Where:

• g(n) = cost from start
• h(n) = estimated cost to goal

Why A* Is Powerful

• Considers both actual cost and estimated cost
• Guarantees optimal path (with admissible heuristic)
• More stable in complex environments

Tradeoff

• Slightly more memory usage
• Slightly more computation

📏 Heuristic Functions

Two heuristics were implemented:

Manhattan Distance

∣x1−x2∣+∣y1−y2∣

• Best for 4-direction movement
• Fast to compute
• Admissible and consistent

Euclidean Distance

sqrt{(x1 — x2)² + (y1 — y2)²}

• Geometric distance
• Slightly slower
• Also admissible

🎮 GUI Visualization

The project includes a fully interactive GUI.

Color Representation

Users can:

• Select algorithm (A* or GBFS)
• Select heuristic
• Enable/Disable dynamic obstacles
• Click to add/remove obstacles
• Reset the grid

⚡ Dynamic Obstacles & Re-Planning

This is where the project becomes truly interesting.

How It Works

• While the agent is moving, obstacles may randomly appear.
• If a new obstacle blocks the current path:

1. The agent detects the blockage.
2. The current position becomes the new start.
3. The algorithm re-runs.
4. The agent continues toward the goal.

This simulates real-time navigation in unpredictable environments.

📊 Performance Metrics

The system tracks:

• Nodes Visited (expanded nodes)
• Path Cost (length of path)
• Execution Time (milliseconds)

This allows comparison between algorithms under different conditions.

🌍 Real-World Applications

This system models problems found in:

• Robotics navigation
• Autonomous vehicles
• Game AI pathfinding
• GPS route planning
• Warehouse automation

🧠 Key Insights

During development, several observations were made:

• Heuristic quality significantly impacts performance.
• A* is more stable in dynamic environments.
• GBFS can be misled by local minima.
• Dynamic re-planning increases computational overhead.

🚀 Future Improvements

Possible enhancements:

• Implement D* Lite for incremental re-planning
• Add diagonal movement
• Add weighted terrain cost
• Add performance graphs
• Compare more algorithms (BFS, UCS, IDA*)

🏁 Conclusion

This project successfully demonstrates:

• Informed search algorithms
• Heuristic-driven decision making
• Real-time obstacle handling
• Performance comparison

Final takeaway:

👉 **A* is more reliable and stable in complex or dynamic environments. 👉 GBFS** is faster in simple, open maps.

Building this dynamic pathfinding agent provided deep insight into how intelligent systems make decisions under uncertainty.