how to implement A* search algorithm for grid-based pathfinding

Introduction to Grid-Based Pathfinding

Imagine a simple map divided into a checkerboard of squares—we call these squares cells. Each cell is a single, discrete location. You (or an agent) start on one specific cell—the start. You need to reach another specific cell—the goal. Some cells are obstacles; you cannot move into or through them. Your task is to find a sequence of adjacent, non-obstacle cells that connects the start to the goal.

This grid is a practical approximation of the real world. A video game world, a warehouse floor plan, or a city block map can all be represented this way. It simplifies continuous space into a graph where each cell is a node, and movement to neighboring cells (up, down, left, right—and sometimes diagonally) are the edges.

Your immediate intuition is probably correct: you want the shortest route. Not just a route, but the one with the fewest steps. If you're a delivery robot, the shortest path saves battery and time. If you're a game character, it feels smarter and more efficient.

Visually, you can picture spreading out from the start like a drop of ink in water, exploring equally in all directions, level by level. The first time that expanding wave touches the goal, you've found the shortest path—because you explored all shorter possibilities first. This "breadth-first" exploration guarantees optimality, but it can be slow over large grids because it wastes effort exploring everywhere, even in completely wrong directions.

Common Misconception: Any Path Works

A common beginner thought is: "As long as I find a path from start to goal, the job is done." This is a trap. In most real applications, optimality matters. A path that meanders around unnecessarily is inefficient. In a strategy game, a unit taking a long detour looks stupid and wastes in-game time. In robotics, extra movement means extra wear, power drain, and slower response. In logistics, it means higher fuel costs and delayed deliveries.

The difference between "any path" and "the shortest path" is the difference between a solution and a good solution. Our goal with A* is to find that shortest path efficiently—without the brute-force slowness of exploring every single possibility. We do this by being smart about where we explore next, using a hint about the goal's direction. That hint is the heuristic, and it's what makes A* special. But that's the next piece. For now, understand the problem: a grid, blocked cells, and the need for the best (shortest) route.

Core Concepts: Nodes, Edges, and Grids

We've looked at the grid as a picture—a map of squares. But to a computer, and to the A* algorithm, this map is actually a graph. It's a collection of data points connected by rules. To understand A*, we must stop thinking of the grid as just "tiles" and start seeing it as a network of Nodes and Edges.

Nodes and Their Properties

Think of each cell in your grid as a Node. A node isn't just a static location; it's an active data package we create and update during the search. The most important properties we store for each node are:

• Position: Its grid coordinates (e.g., (x, y)). This is its fixed identity.
• g_score: The exact, known cost from the start node to this node. This value changes as we discover cheaper paths to reach it.
• f_score: The total estimated cost (g_score + h_score) for a path through this node to the goal. This is what we use to decide exploration order.

When you visit a node, you're not just marking a square on a map. You're calculating and storing these scores. If you later find a better (cheaper) way to get to the same node, you update its g_score and f_score. The node itself is a dynamic record of our current best understanding of how to reach that position.

class Node:
    def __init__(self, position):
        self.position = position  # (x, y)
        self.g_score = float('inf')  # Start with "unknown/infinite" cost
        self.h_score = 0  # Will be set by heuristic function
        self.f_score = float('inf')
        self.parent = None  # To reconstruct the path later

Edges and Movement Rules

Edges are the connections between nodes. They represent the allowed moves from one cell to an adjacent cell. The set of edges defines your movement rules.

Your edge generation logic determines which neighboring nodes are reachable from a given node. This directly shapes the graph the A* algorithm searches.

def get_neighbors(node, grid, allow_diagonal=False):
    x, y = node.position
    neighbors = []
    # Define moves based on direction set
    moves = [(-1,0), (1,0), (0,-1), (0,1)]  # 4-dir
    if allow_diagonal:
        moves += [(-1,-1), (-1,1), (1,-1), (1,1)]  # Add diagonals
    
    for dx, dy in moves:
        nx, ny = x + dx, y + dy
        # Check if new position is within grid bounds and not an obstacle
        if 0 <= nx < grid.width and 0 <= ny < grid.height and not grid.is_obstacle(nx, ny):
            neighbors.append(Node((nx, ny)))
    return neighbors

Intuition: Graph Representation of the Grid

You should now see the grid not as a picture of squares, but as an implicit graph. The nodes are the cells. The edges are the valid moves between them, as defined by your rules. Obstacles simply mean certain nodes exist but have no connecting edges leading into them (or you skip creating them entirely).

This graph view is crucial. A* doesn't "see" a 2D array; it thinks in terms of nodes and paths through the graph. When we talk about "exploring," we mean visiting nodes and examining their edges to discover new nodes. The g_score is the cumulative edge cost along the discovered path from start.

Common Misconception: Nodes are Only Static

A beginner might think: "A node is just a cell on the map. Its position is fixed, so it's static." This is a trap that misses the algorithm's mechanics.

The same cell (position) can have multiple Node instances in our data structures, each with different scores, representing different paths we've considered. When we find a better path to a position, we update the corresponding node's scores. The node's state dynamically reflects our evolving knowledge of the optimal route. Without this mutable state, A* cannot track the cheapest known path or make its intelligent decisions.

Building Intuition: The Shortest-Path Idea

To find the best path, A* needs to play a game of "balance." It looks at two things: how far you've already walked, and how far you think is left to go. If you understand these two numbers, you understand A*.

# When examining a neighbor from the current node:
tentative_g = current.g_score + movement_cost  # e.g., 1 for orthogonal
if tentative_g < neighbor.g_score:
    neighbor.g_score = tentative_g  # Found a better path!
    neighbor.parent = current      # Remember how we got here

Heuristic as Estimated Remaining Cost

If g_score is the past, h_score is the future. It is your best guess of the cost from your current location to the goal.

In a grid where you can only move Up, Down, Left, or Right, the best guess is the Manhattan Distance. Imagine you are a taxi driver in a city with square blocks; you can't drive through buildings. You must count the number of blocks horizontally and vertically to the destination.

def manhattan_distance(node, goal):
    dx = abs(node[0] - goal[0])
    dy = abs(node[1] - goal[1])
    return dx + dy  # Always ≤ true cost on a 4-dir grid

Common Misconception: Heuristic Can Be Arbitrary

A tempting thought is: "I'll just make the heuristic really big so it points strongly to the goal!". This is dangerous.

If h_score is too high, the total estimate f = g + h becomes artificially low for nodes that aren't actually on the best path. A* might explore those "fake" paths first, find a solution, and stop—only to realize later it missed the true shortest route.

Admissibility ensures optimality. By keeping your guess "optimistic" (equal to or less than the real cost), you guarantee that the first time you reach the goal, you have found the best possible way to get there.

Common Misconception: A* Always Finds the Optimal Path

It is a comforting thought: "A* is magic. It always finds the shortest path." But as software engineers, we must be skeptical of absolute promises. A* is not magic; it is a logical machine that follows the F-score (g + h).

The guarantee of optimality is conditional. It only holds true if your heuristic function is admissible. If your heuristic overestimates the cost to the goal, A* can be tricked into finding a longer, suboptimal path and stopping there.

Intuition: Why Admissible Heuristics Guarantee Optimality

Why does this condition matter? The proof is elegant. An admissible heuristic is an optimistic guess. It says, "The cost to the goal is at most this much." It never lies and says "it's closer than it really is."

Because it is optimistic, the f_score of any node on the true shortest path is a lower bound on the total cost of that path.

Therefore, the F-score of the optimal path (≤ C*) is always lower than the F-score of any suboptimal path (> C*). A* expands nodes in increasing order of F-score. It must expand the optimal path nodes before it can possibly expand the suboptimal ones. When it finally reaches the goal via the optimal path, it stops. Optimality is guaranteed.

Pitfall: Assuming Perfect Heuristics

Another trap is thinking your heuristic must be perfect (exact) for A* to work well. It doesn't.

An admissible heuristic only needs to be a lower bound. The Manhattan distance is rarely the exact remaining cost (unless you are on a straight line), but it is perfectly valid. Its "inaccuracy" simply means A* might explore a few extra nodes, but it will still find the optimal path.

Focus on admissibility first. Ensure your heuristic never overestimates. Once that safety guarantee is in place, you can worry about making the heuristic more accurate (closer to the true cost) to speed up the search. But never sacrifice admissibility for speed, or you lose the guarantee of the shortest path.

Designing a Heuristic Function

We've established that the heuristic is A*'s crystal ball—a way to guess the remaining distance to the goal. But a crystal ball that lies is useless. In fact, a lying crystal ball can be dangerous.

Designing a heuristic is not about guessing randomly; it is about mathematically estimating the best-case scenario. It asks: "If there were absolutely no obstacles, what is the absolute minimum cost to get from here to there?"

Choosing Manhattan Distance

def manhattan_heuristic(node_pos, goal_pos):
    dx = abs(node_pos[0] - goal_pos[0])
    dy = abs(node_pos[1] - goal_pos[1])
    return dx + dy  # Admissible for 4-dir movement

Euclidean Distance for Diagonal Movement

import math

def euclidean_heuristic(node_pos, goal_pos):
    dx = node_pos[0] - goal_pos[0]
    dy = node_pos[1] - goal_pos[1]
    return math.sqrt(dx*dx + dy*dy)  # Admissible for 8-dir with diagonal cost √2

def chebyshev_heuristic(node_pos, goal_pos):
    dx = abs(node_pos[0] - goal_pos[0])
    dy = abs(node_pos[1] - goal_pos[1])
    return max(dx, dy)  # Admissible for 8-dir with diagonal cost 1

Intuition: Heuristic Should Never Overestimate

Common Pitfall: Using a Non-Admissible Heuristic

Integrating A* into Game AI Pathfinding

We've learned how A* works on a static map. But in a real game, the world is alive. Enemies move, doors open and close, and the player might suddenly block a corridor. Your perfect path from 2 seconds ago might be blocked right now.

This brings us to the practical side of Game AI: Dynamic Environments and Real-Time Performance. We need to adapt our static algorithms to a world that changes while we are thinking.

Intuition: Real-Time Performance Needs

Games run at 60 frames per second (FPS). You have roughly 16 milliseconds to do everything: render graphics, play sounds, update physics, and calculate AI. If your pathfinding takes 100ms, your game will stutter.

def a_star_limited(start, goal, max_nodes):
    open_set = {start}
    nodes_explored = 0
    
    while open_set:
        if nodes_explored > max_nodes:
            # STOP EARLY! Return best path found so far
            return reconstruct_best_path() 
            
        current = get_lowest_f_score(open_set)
        # ... standard A* logic ...
        nodes_explored += 1
            

Common Misconception: A* is Too Slow for Games

Beginners often hear "A* is optimal but slow" and assume it's unusable for real-time games. This is false. A* is the backbone of thousands of commercial games. The trick is applying the right optimizations.

Final advice: Start with a clean, correct A*. Profile your game. If it's too slow, identify the bottleneck (too many units? huge map?). Then apply the specific optimization that solves that problem. Never optimize blindly.

Full A* Algorithm Implementation Walkthrough

We have the theory, the intuition, and the math. Now, let's put it all together into code. Writing A* from scratch can feel like assembling a complex machine, but if we break it down into these five distinct phases, it becomes a manageable loop.

Step 1: Initialize Start Node

The algorithm begins with a single piece of data: where you are. We create a node object for the start position.

• g_score = 0: The cost to get from start to start is zero.
• f_score = h(start): We calculate the heuristic (Manhattan distance) to the goal. This is our "guess" for the total cost.

We place this start node into our Open Set (often a Priority Queue or Min-Heap). This is the only node we know about right now.

start_node = Node(start_position)
start_node.g_score = 0
start_node.f_score = heuristic(start_position, goal_position)
heapq.heappush(open_heap, (start_node.f_score, start_node))

Step 2: The Main Loop (Pop)

Now the engine runs. We enter a while loop that continues as long as the open_heap is not empty.

In every iteration, we pop the node with the lowest f_score. This is the most "promising" node—the one that looks closest to the goal based on our math.

Crucial Check: If the node we popped is the Goal, we stop immediately. We found the optimal path!

while open_heap:
    current = heapq.heappop(open_heap)[1]  # Get lowest f_score
    
    # If we reached the goal, we are done
    if current.position == goal_position:
        return reconstruct_path(current)
    
    # Mark as visited so we don't process it again
    closed_set.add(current.position)

Step 3: Neighbor Expansion

If we haven't reached the goal, we look around. We generate all valid neighbors (Up, Down, Left, Right) for the current node.

We ignore neighbors that are:

• Obstacles (walls).
• Already in the Closed Set (we already found the best path to them).

neighbors = get_neighbors(current, grid)
for neighbor in neighbors:
    if neighbor.position in closed_set:
        continue
    # ... calculate costs ...

Step 4: Update Scores (The Heart of A*)

This is the most critical step. For every valid neighbor, we calculate a tentative g_score:

We compare this tentative_g with the neighbor's current known g_score.

Is this new path better? (i.e., is tentative_g < neighbor.g_score?)

• Yes: Update the neighbor's scores, set its parent to current, and push it onto the Open Heap.
• No: Do nothing. The old path to this neighbor was better.

tentative_g = current.g_score + 1  # Assuming cost 1

if tentative_g < neighbor.g_score:
    neighbor.g_score = tentative_g
    neighbor.f_score = tentative_g + heuristic(neighbor, goal)
    neighbor.parent = current
    heapq.heappush(open_heap, (neighbor.f_score, neighbor))

Step 5: Reconstruct Path

Once the loop finishes (because we popped the Goal), we have a "breadcrumb trail" of parent pointers.

We start at the Goal node and follow the parent link backwards until we hit the Start node. We then reverse this list to get the path from Start to Goal.

def reconstruct_path(node):
    path = []
    while node is not None:
        path.append(node.position)
        node = node.parent
    return path[::-1]  # Reverse list

Common Pitfall: The "G-Score" Bug

What This Tutorial Covers

Goals and Expected Outcomes

By the end of this tutorial, you will have built a complete, correct A* search algorithm from scratch. You will understand how to represent a grid as a graph, choose an admissible heuristic for your movement rules, and implement the open/closed sets with a priority queue.

More importantly, you'll know why each piece matters—how g_score and h_score combine to guide the search efficiently, and how to avoid common pitfalls that break optimality. You'll also learn practical optimizations like heuristic caching and early exit strategies, and how to adapt A* for real-time game environments with dynamic obstacles. This isn't just theory; you'll have working code you can drop into a game, simulation, or robotics project.

Common Misconception: Pathfinding is Only for Games

It's easy to think pathfinding lives only in video games, but that's just the most visible example. In logistics, companies use pathfinding algorithms to optimize delivery routes across cities. In robotics, it's used for motion planning—figuring out how a robotic arm should move without colliding.

Network routing protocols (like OSPF) use variants of shortest‑path algorithms to direct data packets efficiently. Even in biology, researchers model how molecules move through crowded cellular environments using similar search techniques. The core problem—finding an optimal sequence of steps through a constrained space—appears any time an autonomous agent must traverse a physical or abstract graph. A* is a specific solution to that universal problem, and mastering it opens doors far beyond entertainment.

Frequently Asked Questions & Troubleshooting

Even with the best theory, implementation details can trip you up. As Professor Pixel, I've seen thousands of students struggle with the same few pitfalls. Below is a curated guide to the most common questions, complete with interactive tools to help you diagnose issues instantly.

Final Advice: If you are stuck, start with a tiny 3x3 grid. Manually trace the algorithm on paper. If the computer disagrees with your paper, you have found your bug. Happy coding!