This project explores multiple AI algorithms to solve the Bloxorz 3D game. My initial challenge with this problem arose during the CS404 - Artificial Intelligence course. After revisiting the problem, I applied various search algorithms to find optimal solutions, including Depth-First Search (DFS) and A* Heuristic Search. Each method offers unique strengths in traversing the maze and finding paths to the goal.
1. Depth-First Search (DFS)
The DFS algorithm explores each potential path deeply before backtracking. In this implementation, nodes in the maze are interconnected to form a structure resembling a linked list, where each node represents a maze tile and links to adjacent nodes. This approach is effective for exploring paths but may not always find the shortest route.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.previous = None
self.up = None
self.down = None
def insert_next(self, n):
self.next = n
def insert_previous(self, n):
self.previous = n
def insert_up(self, n):
self.up = n
def insert_down(self, n):
self.down = nThis Node class represents each tile in the maze. The nodes are connected to adjacent tiles using the insert_next, insert_previous, insert_up, and insert_down methods, creating a grid structure where each tile has connections for path exploration.
2. Maze Class - Setting Up the Maze for DFS
The Maze class sets up the maze layout from an input grid, creating links between adjacent nodes. The setup method iterates through the grid twice, first connecting each row and then linking rows for a complete, interconnected structure.
class Maze:
def __init__(self):
self.heads = []
def setup(self, lines):
for i, line in enumerate(lines):
line = line.strip()
head = Node(line[0])
temp = head
for char in line[1:]:
n = Node(char)
n.insert_previous(temp)
temp.insert_next(n)
temp = n
self.heads.append(head)
for i in range(len(self.heads) - 1):
row1, row2 = self.heads[i], self.heads[i + 1]
while row1 and row2:
row2.insert_up(row1)
row1.insert_down(row2)
row1, row2 = row1.next, row2.nextThe setup method builds the maze by linking nodes row-by-row, creating a fully connected grid for DFS traversal.
3. A* Heuristic Search Algorithm
The A* algorithm combines aspects of DFS and BFS with a heuristic to find the shortest path to the goal. The heuristic function estimates the distance to the goal, enabling the algorithm to prioritize nodes closer to the target. This approach makes A* highly efficient for finding optimal solutions in complex mazes.
import heapq
def heuristic(node, goal):
return abs(node.x - goal.x) + abs(node.y - goal.y)
def a_star_search(maze, start, goal):
open_set = []
heapq.heappush(open_set, (0, start))
came_from = {}
g_score = {start: 0}
f_score = {start: heuristic(start, goal)}
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
return reconstruct_path(came_from, current)
for neighbor in maze.get_neighbors(current):
tentative_g_score = g_score[current] + 1
if tentative_g_score < g_score.get(neighbor, float('inf')):
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
if all(neighbor != n for _, n in open_set):
heapq.heappush(open_set, (f_score[neighbor], neighbor))
return []The a_star_search function implements the A* algorithm. It maintains an open set of nodes to explore and calculates scores using the heuristic to prioritize nodes closer to the goal. This method ensures that the path found is optimal and minimizes the number of steps needed to reach the target.
4. Node Class for A* Implementation
The Node class represents each position in the maze with coordinates (x, y), orientation, and parent node information for A* traversal. Nodes are compared based on their total cost, making the class compatible with the A* algorithm's priority queue.
class Node:
def __init__(self, x, y, orientation, move=None, parent=None):
self.x = x
self.y = y
self.orientation = orientation
self.move = move
self.parent = parent
self.g = 0
self.h = 0
self.f = 0
def __eq__(self, other):
return (self.x == other.x and self.y == other.y and self.orientation == other.orientation)
def __lt__(self, other):
return self.f < other.f
def __hash__(self):
return hash((self.x, self.y, self.orientation))The Node class in A* includes properties for tracking movement and orientation, essential for navigating the 3D game environment. Each node has heuristic values (g, h, and f) used by A* to prioritize nodes in the search.
5. Maze Class - Setting Up the Maze for A*
The Maze class for A* includes methods to validate moves and retrieve neighbors for each node. Valid moves depend on the current orientation, ensuring that the player can only access adjacent tiles that maintain a valid state.
class Maze:
def __init__(self, grid):
self.grid = grid
self.rows = len(grid)
self.cols = len(grid[0])
def is_valid(self, x, y):
return 0 <= x < self.rows and 0 <= y < self.cols and self.grid[x][y] != '#'
def get_neighbors(self, node):
neighbors = []
# Determine neighbors based on node orientation
return neighborsThe Maze class for A* includes is_valid to confirm if a position is traversable and get_neighbors to find adjacent nodes, adapting based on the player’s orientation.
6. Main Function to Run the A* Algorithm
from node import Node
from maze import Maze
from a_star_search import a_star_search
# Sample grid
grid = [
'############',
'#.S..#######',
'#.....######',
'#.......####',
'##......####',
'#####..G####',
'######.#####',
'############'
]
def main():
start, goal = Node(1, 2, 'vertical'), Node(5, 6, 'vertical')
maze = Maze(grid)
path = a_star_search(maze, start, goal)
if path:
print('Path found:', path)
else:
print('No path found')
if __name__ == '__main__':
main()The main function initializes the maze and nodes, executing the A* search to find a solution. If a path is found, it prints the sequence of moves; otherwise, it indicates no valid path exists. This implementation integrates all components of the A* search, from setup to pathfinding.
Comments
Be the first one to comment!