Introduction to Pathfinding

Pathfinding is the process of finding the shortest or most efficient route between two points. In computer science, it's commonly used in game development, robotics, and mapping applications. We'll explore pathfinding in a grid-based environment, which is a common scenario in games and simulations.

Foundations of Pathfinding

  1. Grid-Based Environment : Your environment is divided into a grid, where each cell in the grid is a potential step in a path.

  2. Nodes and Neighbors : Each cell in the grid is a node. Pathfinding involves moving from one node to its neighboring nodes until the target is reached.

  3. Algorithm Choice : Many algorithms exist for pathfinding, like A*, Dijkstra’s, and Breadth-First Search (BFS). We’ll start with a simple approach, often referred to as flood fill, which is similar to BFS.

In our example, we will use an Environment class and a Tile class . The environment (a grid) will be responsible for the pathfinding calculation, and the tile will offer methods to help find neighbors and store temporary data that will be needed in the calculation.

Accessing Neighbors in a Grid

  1. Neighbor Definition : In a 2D grid, a node typically has up to 8 neighbors (up, down, left, right, and diagonals). For simplicity, we might start with 4 neighbors (excluding diagonals).

  2. Getting Neighbors : For a node at (x, y), its neighbors are (x-1, y), (x+1, y), (x, y-1), (x, y+1).

Let's look at the neighbor access functions inside the Tile class: 

def get_neighbors(self):
    # Initialize an empty list to store neighboring cells
    neighbors = []

    # Check if the left neighbor exists (making sure the cell is not on the left edge)
    if self.x > 0: 
        # Append the left neighbor to the neighbors list
        neighbors.append(self.all_cells[self.x - 1][self.y])

    # Check if the right neighbor exists (making sure the cell is not on the right edge)
    if self.x < self.cols - 1: 
        # Append the right neighbor to the neighbors list
        neighbors.append(self.all_cells[self.x + 1][self.y])

    # Check if the upper neighbor exists (making sure the cell is not on the top edge)
    if self.y > 0: 
        # Append the upper neighbor to the neighbors list
        neighbors.append(self.all_cells[self.x][self.y - 1])

    # Check if the lower neighbor exists (making sure the cell is not on the bottom edge)
    if self.y < self.rows - 1: 
        # Append the lower neighbor to the neighbors list
        neighbors.append(self.all_cells[self.x][self.y + 1])

    # Return the list of neighboring cells
    return neighbors

The function is part of a class that represents a cell in a grid. It finds and returns the adjacent cells of the current cell.

Flood Fill for Pathfinding

  1. Basic Concept : Start from the initial node and “flood” out to neighboring nodes, then to their neighbors, and so on, until the target is reached.

  2. Implementation : Use a queue to manage nodes to visit. Initially, enqueue the starting node. Then, repeatedly dequeue a node, enqueue its unvisited neighbors, and mark them as visited.

Let's look at the Flood Fill calculation within the Environment class: 

def flood_fill(self):
    # Check if the flood fill process is still running
    if self.running:        
        # Check if there are still cells to be processed
        if len(self.stack) > 0:
            # Remove the first cell from the stack and work on it
            current_cell = self.stack.pop(0)
            # Mark the current cell as visited
            current_cell.visited = True
            
            # Check if the current cell is the goal or end node
            if current_cell == self.end_node:
                println("Goal Reached!")
                # Stop the flood fill process
                self.running = False
                # Mark that the path has been found
                self.path_found = True
                # Reconstruct the path from the current (end) cell
                self.reconstruct_path(current_cell)
        
            # Iterate through all neighboring cells of the current cell
            for neighbor in current_cell.get_neighbors():
                # Check if the neighbor has not been visited and is not an obstacle
                if not neighbor.visited and not neighbor.isObstable:
                    # Mark the neighbor as visited
                    neighbor.visited = True
                    # Add the neighbor to the stack for further processing
                    self.stack.append(neighbor)
                    # Set the current cell as the parent of the neighbor for path reconstruction
                    neighbor.parent = current_cell

Reconstructing the Optimal Path

  1. Tracking Paths : As you visit each node, store where you came from. This way, you can trace back from the target to the start.

  2. Reconstruction : Once the target is found, follow the stored paths backward to the start, which gives you the optimal path.

Let's look how the environment finally manages to reconstruct the path: 

def reconstruct_path(self, current_cell):
    # Notify the start of path reconstruction
    println("Reconstruction Started")
    
    # Loop back from the current cell (typically the end node) to the start node
    while current_cell.parent is not None:
        # Add the current cell to the path list
        self.path.append(current_cell)
        # Move to the parent of the current cell
        current_cell = current_cell.parent
        # Notify that one loop iteration is completed
        println("Loop")
    
    # Add the start node to the path list
    self.path.append(self.start_node)
    # Notify the end of path reconstruction
    println("Reconstruction Ended")

The function is used to trace and construct the path found by the pathfinding algorithm. It works backward from the end node to the start node.