Member Avatar for luvsdabud

Working on program to solve a predefined maze. I'm thinking the strings of spaces and #s should be arranged as strings or lists w/in a list, but not sure how to define spatial relationships so program can "move" through the maze. Just looking to help get started.

  • 3 Contributors
  • 2 Replies
  • 227 Views
  • 2 Years Discussion Span
  • Latest Post Latest Post by hovestar

Dani AI

Generated

Building on 's idea of a stored grid and 's "square" view: treat the maze as a 2D array and model position as (row, column) tuples. Neighbors are just the four offsets (up/down/left/right). Using tuples avoids assigning a unique id to each cell and makes boundary checks simpler.

For an unweighted maze the simplest robust solver is breadth-first search (BFS) — it finds the shortest path in steps. Keep a visited/predecessor map so the path can be reconstructed. Important implementation notes: handle irregular row lengths by checking each row's length, convert rows to mutable lists only when overlaying a path, use collections.deque for the queue, and avoid recursive DFS on large mazes (stack limits).

from collections import deque

def neighbors(r, c, grid):
    for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[nr]):
            yield nr, nc

def find_pos(grid, ch):
    for r, row in enumerate(grid):
        if ch in row:
            return (r, row.index(ch))
    return None

def bfs(grid, start, goal):
    q = deque([start])
    prev = {start: None}
    while q:
        cur = q.popleft()
        if cur == goal:
            break
        for nbr in neighbors(*cur, grid):
            if nbr not in prev and grid[nbr[0]][nbr[1]] != '#':
                prev[nbr] = cur
                q.append(nbr)
    else:
        return None
    path = []
    cur = goal
    while cur:
        path.append(cur)
        cur = prev[cur]
    return list(reversed(path))

# example usage
grid = [
"#########",
"#S #   G#",
"# ### ###",
"#       #",
"#########",
]
start = find_pos(grid, "S")
goal = find_pos(grid, "G")
path = bfs(grid, start, goal)
if path:
    maze = [list(row) for row in grid]
    for r,c in path[1:-1]:
        maze[r][c] = '.'
    print("\n".join("".join(row) for row in maze))

Common pitfalls and tips: pad rows or check per-row bounds if lines differ in length; strip trailing newlines when reading from files; ensure start/goal are open cells; BFS is ideal for shortest-step paths, while A* is better for very large mazes or when using heuristics/costs. In reply to , the snippet above is a compact, copy-pasteable example that demonstrates neighbor calculation, BFS traversal, path reconstruction, and overlaying the path on the input grid.

Recommended Answers

All 2 Replies

Member Avatar for woooee

You would probably have to use a large grid with squares, like a large tic-tac-toe board, with a unique number for each square . Also, if you store what the square is, a wall or open space, then you should be able to come up with a formula/decision table to calculate the squares surrounding any given square and so can tell which way the player can and can not move.

Member Avatar for hovestar

If you have completed this please post the code... otherwise you could read this forum about a similar subject

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.