Pathfinding Algorithms Visualizer

Welcome to the Pathfinding Algorithms Visualizer module, a core component of the DAA for Kids project. This interactive tool is designed to illuminate the fascinating world of algorithms that find the shortest or optimal path between two points in a graph or grid. Understanding pathfinding is fundamental to many areas of computer science, from game development and robotics to network routing and logistics.

---

What is Pathfinding?

At its heart, pathfinding is about navigating from a starting point to a destination, often avoiding obstacles and sometimes considering the "cost" of traversing different paths. Our visualizer brings these abstract concepts to life on a grid, allowing you to see exactly how various algorithms explore possible routes and determine the most efficient path.

---

Using the Visualizer

The visualizer provides a dynamic grid environment where you can:

• Define the Environment: Place start and end nodes, draw walls to represent impassable obstacles, and add weights to cells to simulate varying traversal costs.

• Select an Algorithm: Choose from a diverse set of pathfinding algorithms.

• Control Execution: Start, pause, resume, and adjust the speed of the visualization to observe the algorithm's step-by-step process.

• Reset and Generate: Clear the grid or generate random maps to test algorithms under different conditions.

As the algorithm runs, you'll see nodes being visited, the path being constructed (if found), and understand the search pattern unique to each algorithm.

---

Algorithms Explored

This visualizer offers a comprehensive look at a variety of pathfinding algorithms, categorized by their approach and suitability for different types of graphs (weighted vs. unweighted). Each algorithm brings a unique strategy to the problem of finding a path.

Unweighted Graph Algorithms

These algorithms are typically used on graphs where the cost of moving between any two connected nodes is the same (or assumed to be 1). They focus on finding the path with the fewest steps.

• Breadth-First Search (BFS): Explores the graph level by level, guaranteeing the shortest path in terms of the number of edges.

• Depth-First Search (DFS): Explores as far down one branch as possible before backtracking, often used for traversal but not guaranteed to find the shortest path.

Weighted Graph Algorithms

When edges or nodes have different associated costs (weights), these algorithms are necessary to find the path with the minimum total cost.

• Dijkstra’s Algorithm: Finds the shortest paths from a single source node to all other nodes in a graph with non-negative edge weights.

• A* Search Algorithm: An extension of Dijkstra's that uses a heuristic function to guide its search, making it more efficient in many cases, especially for finding a path to a specific destination.

• Greedy Best-First Search: Uses a heuristic to prioritize exploration towards the target, but does not guarantee the shortest path.

• Bellman-Ford Algorithm: Can find the shortest paths from a single source node even in graphs with negative edge weights (though it detects negative cycles).

• Floyd-Warshall Algorithm: Finds the shortest paths between all pairs of nodes in a weighted graph.

Advanced and Specialized Algorithms

This category includes algorithms designed for specific scenarios or offering alternative approaches to pathfinding.

• Bidirectional Search: Runs two searches simultaneously, one from the start and one from the end, meeting in the middle. Can be faster than a single-direction search.

• Jump Point Search: An optimization for grid-based pathfinding that "jumps" over large areas, significantly speeding up search on uniform cost grids.

---

Algorithm Pseudocode

Explore the fundamental logic behind each pathfinding algorithm. Select an algorithm from the dropdown below to view its pseudocode.

Select an Algorithm Breadth-First Search (BFS) Dijkstra’s Algorithm A* Search Algorithm Greedy Best-First Search Bellman-Ford Algorithm Floyd-Warshall Algorithm {/* <-- Check this value */} Bidirectional Search Jump Point Search

Select an algorithm from the dropdown above to see its pseudocode.

BFS(graph, start_node, end_node):
    create a queue Q
    add start_node to Q
    mark start_node as visited
    create a map parent to store parent of each node

    while Q is not empty:
        current_node = Q.dequeue()

        if current_node is end_node:
            return reconstruct_path(parent, start_node, end_node)

        for each neighbor of current_node:
            if neighbor is not visited:
                mark neighbor as visited
                set parent[neighbor] = current_node
                Q.enqueue(neighbor)

    return "No path found"

reconstruct_path(parent, start_node, end_node):
    path = []
    current = end_node
    while current is not null:
        path.add(current)
        current = parent[current]
    reverse path
    return path

Dijkstra(graph, start_node, end_node):
    create a priority queue PQ
    create a map distance, initialize all to infinity, distance[start_node] = 0
    create a map parent to store parent of each node

    PQ.add(start_node, 0) # node, priority

    while PQ is not empty:
        current_node = PQ.extract_min()

        if current_node is end_node:
            return reconstruct_path(parent, start_node, end_node)

        for each neighbor of current_node:
            edge_weight = weight(current_node, neighbor)
            new_distance = distance[current_node] + edge_weight

            if new_distance < distance[neighbor]:
                distance[neighbor] = new_distance
                parent[neighbor] = current_node
                if neighbor is in PQ:
                    PQ.decrease_priority(neighbor, new_distance)
                else:
                    PQ.add(neighbor, new_distance)

    return "No path found"

reconstruct_path(parent, start_node, end_node):
    path = []
    current = end_node
    while current is not null:
        path.add(current)
        current = parent[current]
    reverse path
    return path

A_star(graph, start_node, end_node):
    create a priority queue open_set
    create a map came_from to store parent of each node
    create a map g_score, initialize all to infinity, g_score[start_node] = 0
    create a map f_score, initialize all to infinity, f_score[start_node] = heuristic(start_node, end_node)

    open_set.add(start_node, f_score[start_node]) # node, priority

    while open_set is not empty:
        current_node = open_set.extract_min()

        if current_node is end_node:
            return reconstruct_path(came_from, start_node, end_node)

        for each neighbor of current_node:
            tentative_g_score = g_score[current_node] + distance(current_node, neighbor)

            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current_node
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, end_node)
                if neighbor not in open_set:
                    open_set.add(neighbor, f_score[neighbor])

    return "No path found"

heuristic(node_a, node_b):
    // Implement a suitable heuristic function (e.g., Manhattan distance, Euclidean distance)
    return estimated_distance_between(node_a, node_b)

reconstruct_path(came_from, start_node, end_node):
    path = []
    current = end_node
    while current is not null:
        path.add(current)
        current = came_from[current]
    reverse path
    return path

Greedy_Best_First_Search(graph, start_node, end_node):
    create a priority queue PQ
    create a map came_from to store parent of each node
    create a set visited

    PQ.add(start_node, heuristic(start_node, end_node)) # node, priority based on heuristic

    while PQ is not empty:
        current_node = PQ.extract_min()

        if current_node is end_node:
            return reconstruct_path(came_from, start_node, end_node)

        if current_node is in visited:
            continue
        mark current_node as visited

        for each neighbor of current_node:
            if neighbor not in visited:
                came_from[neighbor] = current_node
                PQ.add(neighbor, heuristic(neighbor, end_node))


    return "No path found"

heuristic(node_a, node_b):
    // Implement a suitable heuristic function (e.g., Manhattan distance, Euclidean distance)
    return estimated_distance_between(node_a, node_b)

reconstruct_path(came_from, start_node, end_node):
    path = []
    current = end_node
    while current is not null:
        path.add(current)
        current = came_from[current]
    reverse path
    return path

Bellman_Ford(graph, start_node):
    create a map distance, initialize all to infinity, distance[start_node] = 0
    create a map parent to store parent of each node

    num_vertices = number of vertices in graph

    // Relax edges |V| - 1 times
    repeat num_vertices - 1 times:
        for each edge (u, v) with weight w in graph:
            if distance[u] + w < distance[v]:
                distance[v] = distance[u] + w
                parent[v] = u

    // Check for negative cycles
    for each edge (u, v) with weight w in graph:
        if distance[u] + w < distance[v]:
            return "Graph contains a negative cycle" // Cannot find shortest paths

    return distance, parent // Returns shortest distances from start_node and parent pointers

// Note: To find the path to a specific end_node, you would reconstruct it
// using the parent map after the algorithm completes and confirms no negative cycles.
reconstruct_path(parent, start_node, end_node):
    path = []
    current = end_node
    // Add a check to prevent infinite loops in case of issues or unreachable nodes
    visited_check = set()
    while current is not null and current not in visited_check:
        path.add(current)
        visited_check.add(current)
        current = parent[current]
    // Check if start_node was reached (current is null if not)
    if current is null and start_node not in path:
         return "Path could not be reconstructed" # Or handle as an error
    reverse path
    return path

{/* <-- Check this ID */} ```python Floyd_Warshall(graph): num_vertices = number of vertices in graph create a matrix dist of size num_vertices x num_vertices create a matrix next_node of size num_vertices x num_vertices // To reconstruct paths // Initialize dist matrix for i from 0 to num_vertices - 1: for j from 0 to num_vertices - 1: if i == j: dist[i][j] = 0 elif edge exists from i to j: dist[i][j] = weight(i, j) next_node[i][j] = j else: dist[i][j] = infinity next_node[i][j] = null // Apply the algorithm for k from 0 to num_vertices - 1: // Intermediate vertices for i from 0 to num_vertices - 1: // Start vertices for j from 0 to num_vertices - 1: // End vertices if dist[i][k] is not infinity and dist[k][j] is not infinity: if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] next_node[i][j] = next_node[i][k] // dist matrix now contains shortest paths between all pairs // next_node matrix can be used to reconstruct paths return dist, next_node reconstruct_path_floyd_warshall(start_node, end_node, next_node): if next_node[start_node][end_node] is null: return "No path exists" // Or handle as error path = [start_node] current = start_node while current is not end_node: current = next_node[current][end_node] path.add(current) return path ```

Bidirectional_Search(graph, start_node, end_node):
    create queue_forward and queue_backward
    create visited_forward and visited_backward sets
    create parent_forward and parent_backward maps

    queue_forward.enqueue(start_node)
    visited_forward.add(start_node)
    parent_forward[start_node] = null

    queue_backward.enqueue(end_node)
    visited_backward.add(end_node)
    parent_backward[end_node] = null

    while queue_forward is not empty and queue_backward is not empty:
        // Search from start
        current_f = queue_forward.dequeue()
        if current_f in visited_backward:
            return reconstruct_bidirectional_path(parent_forward, parent_backward, current_f)

        for each neighbor of current_f:
            if neighbor not in visited_forward:
                visited_forward.add(neighbor)
                parent_forward[neighbor] = current_f
                queue_forward.enqueue(neighbor)

        // Search from end
        current_b = queue_backward.dequeue()
        if current_b in visited_forward:
            return reconstruct_bidirectional_path(parent_forward, parent_backward, current_b)

        for each neighbor of current_b:
            if neighbor not in visited_backward:
                visited_backward.add(neighbor)
                parent_backward[neighbor] = current_b
                queue_backward.enqueue(neighbor)

    return "No path found" // Queues are empty and no intersection found

reconstruct_bidirectional_path(parent_forward, parent_backward, meeting_node):
    path = []
    // Path from start to meeting_node
    current = meeting_node
    while current is not null:
        path.add(current)
        current = parent_forward[current]
    reverse path

    // Path from meeting_node to end_node
    current = parent_backward[meeting_node] // Start from the node *before* the meeting node in backward search
    while current is not null:
        path.add(current)
        current = parent_backward[current]

    return path

// Note: Jump Point Search is complex and typically implemented on a grid.
// This pseudocode provides a high-level overview of the core idea.

JPS(grid, start_node, end_node):
    create open_set (priority queue)
    create came_from map
    create g_score map, initialize all to infinity, g_score[start_node] = 0
    create f_score map, initialize all to infinity, f_score[start_node] = heuristic(start_node, end_node)

    open_set.add(start_node, f_score[start_node])

    while open_set is not empty:
        current_node = open_set.extract_min()

        if current_node is end_node:
            return reconstruct_path(came_from, start_node, end_node)

        // Find "jump points" from the current node
        neighbors = find_jump_points(current_node, came_from[current_node], grid)

        for each neighbor (jump_point):
            tentative_g_score = g_score[current_node] + distance(current_node, jump_point)

            if tentative_g_score < g_score[jump_point]:
                came_from[jump_point] = current_node
                g_score[jump_point] = tentative_g_score
                f_score[jump_point] = g_score[jump_point] + heuristic(jump_point, end_node)
                if jump_point not in open_set:
                    open_set.add(jump_point, f_score[jump_point])

    return "No path found"

find_jump_points(current_node, parent_node, grid):
    // This is the core complex part of JPS.
    // It involves pruning redundant neighbors and recursively searching for forced neighbors
    // and jump points in cardinal and diagonal directions.
    // Returns a list of significant "jump points" reachable from current_node.
    pass // Placeholder for complex logic

heuristic(node_a, node_b):
    // Implement a suitable heuristic function (e.g., Manhattan distance, Euclidean distance)
    return estimated_distance_between(node_a, node_b)

reconstruct_path(came_from, start_node, end_node):
    path = []
    current = end_node
    while current is not null:
        path.add(current)
        current = came_from[current]
    reverse path
    return path