Sign In

Access your saved progress

or

Intermediate 25 min

Mini Project: Build Your Own Pathfinding Toy

Let’s build a small pathfinding application. You can run it in a browser or as a console app.

Project Overview

Goal: Create a pathfinding tool where users can:

  • Define grid size
  • Place obstacles
  • Choose algorithm (Dijkstra or A*)
  • Run the algorithm
  • See the path and statistics

Basic Implementation

Here’s a complete HTML/JavaScript version you can run in a browser:

<!DOCTYPE html>
<html>
<head>
    <title>Pathfinding Toy</title>
    <style>
        body { font-family: Arial, sans-serif; padding: 20px; }
        .controls { margin-bottom: 20px; }
        .grid { display: inline-grid; gap: 2px; background: #e2e8f0; padding: 10px; }
        .cell { width: 30px; height: 30px; border: 1px solid #cbd5e1; cursor: pointer; }
        .cell.empty { background: white; }
        .cell.wall { background: #1e293b; }
        .cell.start { background: #10b981; }
        .cell.goal { background: #ef4444; }
        .cell.visited { background: #94a3b8; }
        .cell.path { background: #fbbf24; }
        .stats { margin-top: 20px; padding: 10px; background: #f8fafc; border-radius: 5px; }
    </style>
</head>
<body>
    <h1>Pathfinding Toy</h1>
    <div class="controls">
        <label>Grid Size: <input type="number" id="grid-size" value="15" min="5" max="30" /></label>
        <label>Algorithm: 
            <select id="algorithm">
                <option value="dijkstra">Dijkstra</option>
                <option value="astar">A*</option>
            </select>
        </label>
        <button id="run-btn">Run Algorithm</button>
        <button id="clear-btn">Clear</button>
    </div>
    <div id="grid-container"></div>
    <div class="stats" id="stats"></div>

    <script>
        // Implementation code here (from previous page)
        // ... (include dijkstra and astar functions)
    </script>
</body>
</html>

Extension Ideas

Once you have the basic version working, try these extensions:

1. Diagonal Movement

Add 8-direction movement with diagonal costs:

directions = [
    (-1, 0), (1, 0), (0, -1), (0, 1),  # 4-direction
    (-1, -1), (-1, 1), (1, -1), (1, 1)  # Diagonals
]

# Diagonal moves cost √2 ≈ 1.41
cost = 1.41 if abs(dr) + abs(dc) == 2 else 1.0

Challenge: Make sure A* heuristic accounts for diagonal movement (use Euclidean distance).

2. Variable Terrain Costs

Add different terrain types with different costs:

terrain_costs = {
    0: 1,    # Grass
    2: 5,    # Mud
    3: 0.5,  # Road
    4: 10,   # Water
}

Challenge: Update the grid to support multiple terrain types, and modify the algorithm to use variable costs.

3. Multiple Heuristics

Let users choose between different heuristics:

  • Manhattan distance (4-direction)
  • Euclidean distance (8-direction)
  • Chebyshev distance (max of row/col differences)
  • Zero (Dijkstra mode)

Challenge: Implement all heuristics and add a selector in the UI.

4. Save and Share Grids

Allow users to save grid configurations and share them:

// Save grid as JSON
function saveGrid() {
    const config = {
        grid: grid,
        start: start,
        goal: goal,
        size: gridSize
    };
    localStorage.setItem('savedGrid', JSON.stringify(config));
}

// Load grid
function loadGrid() {
    const saved = localStorage.getItem('savedGrid');
    if (saved) {
        const config = JSON.parse(saved);
        // Restore grid
    }
}

Challenge: Add import/export functionality and URL sharing.

5. Animated Visualization

Show the algorithm running step by step with animation:

async function visualizeStep(step) {
    // Update grid visualization
    renderGrid();
    // Wait before next step
    await new Promise(resolve => setTimeout(resolve, 100));
}

Challenge: Add play/pause controls and speed adjustment.

6. Performance Comparison

Show side-by-side comparison of algorithms:

  • Nodes expanded
  • Time taken
  • Path length
  • Memory usage

Challenge: Run both algorithms on the same grid and display comparison metrics.

Challenge Panel

Here are some specific challenges to try:

Challenge 1: Diagonal Movement with Optimality

Goal: Add diagonal movement to A* while maintaining optimality.

Hint: Use Euclidean distance as the heuristic, and make sure diagonal moves cost √2.

Difficulty: Intermediate

Show Hint

Euclidean distance is admissible for 8-direction movement. Make sure your cost calculation matches: diagonal = √2, straight = 1.

Challenge 2: Weighted A*

Goal: Implement weighted A* (wA*) that trades optimality for speed.

Hint: Multiply the heuristic by a weight factor (e.g., 1.5). This makes A* explore fewer nodes but may find suboptimal paths.

Difficulty: Advanced

Show Hint

Instead of f(n) = g(n) + h(n), use f(n) = g(n) + w × h(n) where w > 1. This biases the search more toward the goal.

Goal: Implement Jump Point Search, an optimization of A* for uniform-cost grids.

Hint: Skip nodes that don’t change the direction of the optimal path. This reduces the number of nodes explored.

Difficulty: Advanced

Show Hint

JPS “jumps” over nodes in straight lines and diagonals when there are no obstacles. It’s much faster than A* on uniform grids.

Testing Your Implementation

Test with these scenarios:

Simple case:

  • 10×10 grid
  • No obstacles
  • Start: (9, 0), Goal: (0, 9)
  • Expected: Straight diagonal path

Maze:

  • 20×20 grid
  • Many obstacles creating a maze
  • Both algorithms should find the same path length

No path:

  • Start and goal separated by walls
  • Should handle gracefully (return null, show message)

Performance test:

  • Large grid (50×50)
  • Compare nodes expanded between Dijkstra and A*

Key Takeaways

Before finishing:

  1. Start simple - Get basic version working first
  2. Add features incrementally - One extension at a time
  3. Test thoroughly - Try edge cases and different scenarios
  4. Visualize - Seeing the algorithm run helps understanding
  5. Experiment - Try different heuristics, costs, and optimizations

Final Knowledge Check

What’s Next?

Congratulations! You’ve completed the tutorial. In the completion page, we’ll summarize what you’ve learned and suggest next steps for further learning.

Progress 100%
Page 7 of 7
← Previous → Next