Mastering 3D Maze Pathfinding: BFS, UCS, and A* for CSCI 561 Homework 1

Introduction to 3D Maze Pathfinding in CSCI 561

In this tutorial, we explore the core concepts behind CSCI 561 Homework 1, where you must guide an agent through a 3D grid maze using search algorithms. The maze consists of points with up to 18 possible actions, including diagonal moves. Your goal is to find the optimal shortest path from an entrance to an exit using Breadth-First Search (BFS), Uniform-Cost Search (UCS), and A* Search. Understanding these algorithms is crucial for artificial intelligence and robotics applications, such as autonomous drone navigation or video game AI pathfinding.

Understanding the 3D Maze Configuration

The maze is a 3D grid where each point (x,y,z) has a list of available actions (e.g., X+, Y-, X+Y+). The 18 actions correspond to movements along axes or diagonals. For example, action code 7 (X+Y+) moves diagonally in the XY plane. The input file specifies each point's actions. Your agent can only move using actions listed at the current point. If an action leads to a wall or out of bounds, the move fails.

This setup mirrors real-world pathfinding challenges, like a delivery drone navigating a city with no-fly zones, or a character in a game like Minecraft moving through a cave system. By mastering this assignment, you build skills applicable to modern AI and robotics.

Algorithm 1: Breadth-First Search (BFS)

BFS explores all nodes at the present depth level before moving deeper. In this problem, each move costs 1 unit, regardless of direction. BFS guarantees the shortest path in terms of number of moves. Implement BFS using a queue. Start from the entrance, mark it visited, and enqueue its neighbors. Continue until you find the exit.

For the given example with entrance (60,103,97) and exit (64,103,97), BFS will find the path (60,103,97) -> (61,103,97) -> ... -> (64,103,97) because all moves are along X+.

from collections import deque

def bfs(entrance, exit, actions_dict):
    queue = deque([(entrance, [entrance])])
    visited = set([entrance])
    while queue:
        current, path = queue.popleft()
        if current == exit:
            return path
        for action in actions_dict.get(current, []):
            neighbor = apply_action(current, action)
            if neighbor and neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

Algorithm 2: Uniform-Cost Search (UCS)

UCS expands the node with the lowest path cost. Since each move costs 1, UCS behaves like BFS here, but it generalizes to weighted graphs. Use a priority queue (min-heap) keyed by cumulative cost. This algorithm is optimal for non-negative costs. In this assignment, all moves have equal cost, so UCS and BFS yield the same path length, but UCS is more flexible for future extensions.

import heapq

def ucs(entrance, exit, actions_dict):
    heap = [(0, entrance, [entrance])]
    visited = set()
    while heap:
        cost, current, path = heapq.heappop(heap)
        if current in visited:
            continue
        visited.add(current)
        if current == exit:
            return path
        for action in actions_dict.get(current, []):
            neighbor = apply_action(current, action)
            if neighbor and neighbor not in visited:
                heapq.heappush(heap, (cost+1, neighbor, path+[neighbor]))
    return None

Algorithm 3: A* Search

A* combines UCS with a heuristic to estimate remaining cost. For a 3D grid, use Manhattan distance (or Euclidean) as heuristic. A* is often faster than BFS/UCS because it directs search toward the goal. The heuristic must be admissible (never overestimate). For this maze, Manhattan distance works: |x1-x2| + |y1-y2| + |z1-z2|. Since diagonal moves exist, Manhattan may not be strictly admissible for all paths, but it's acceptable if you consider that diagonal moves cover more distance. Alternatively, use Euclidean distance for better admissibility.

def heuristic(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1]) + abs(a[2]-b[2])

def astar(entrance, exit, actions_dict):
    heap = [(0, entrance, [entrance])]
    g_cost = {entrance: 0}
    while heap:
        f, current, path = heapq.heappop(heap)
        if current == exit:
            return path
        for action in actions_dict.get(current, []):
            neighbor = apply_action(current, action)
            if not neighbor:
                continue
            new_g = g_cost[current] + 1
            if neighbor not in g_cost or new_g < g_cost[neighbor]:
                g_cost[neighbor] = new_g
                f = new_g + heuristic(neighbor, exit)
                heapq.heappush(heap, (f, neighbor, path+[neighbor]))
    return None

Handling Input and Output

Your program must read input.txt and write output.txt. The input format: first line contains entrance and exit coordinates. Then each line: (x y z), action1, action2, .... Actions are comma-separated. Parse carefully. Output the path as a sequence of points: (x1,y1,z1), (x2,y2,z2), .... Ensure no trailing comma.

Sample input:

(0,0,0) (100,103,97)
(0,0,0), X+, Y+
(1,0,0), X-, X+
...

Sample output:

(0,0,0), (1,0,0), ...

Optimization Tips for Large Mazes

• Use dictionaries for fast action lookup.
• Precompute neighbor coordinates for each action to avoid repeated calculations.
• For A*, use a good heuristic. Consider diagonal distance (Chebyshev) if diagonal moves are allowed.
• To speed up UCS/A*, use a closed set (visited) to avoid re-expanding nodes.

Real-World Trends: Pathfinding in AI and Gaming

Pathfinding algorithms are everywhere. Self-driving cars like Tesla use variants of A* for route planning. In video games like Fortnite or Call of Duty, AI enemies use BFS/A* to navigate maps. Even apps like Google Maps rely on A* for shortest routes. By mastering these algorithms, you're building skills for cutting-edge tech careers.

Common Mistakes to Avoid

• Forgetting to mark nodes as visited can cause infinite loops.
• Incorrect action parsing — ensure you handle spaces and commas.
• Not handling out-of-bounds moves — your program should skip illegal actions.
• Using non-admissible heuristic in A* may yield suboptimal paths.

Testing Your Solution

Test with provided sample inputs. Use Vocareum's terminal to run your code. Check output format exactly: no extra spaces, correct parentheses. For the easy test cases, BFS should work fine. For complex cases, A* will be faster. Ensure your code compiles and runs without command-line arguments.

Conclusion

By implementing BFS, UCS, and A* for this 3D maze, you gain hands-on experience with search algorithms fundamental to AI. This homework prepares you for more advanced topics like robotics path planning and game AI. Practice with different maze configurations to solidify your understanding.