Stack Overflow
Stack Overflow

Questions tagged [maze]

A maze is a tour puzzle in the form of a complex branching passage.

A maze is a tour puzzle in the form of a complex branching passage through which the solver must find a route. The pathways and walls in a maze are fixed, and puzzles in which the walls and paths can change during the game are categorised as tour puzzles. The Cretan labyrinth is the oldest known maze.

Technically the maze is distinguished from the labyrinth, which has a single through-route with twists and turns but without branches, and is not designed to be as difficult to navigate. In everyday speech, both maze and labyrinth denote a complex and confusing series of pathways.

1093 questions
288
votes
10 answers

Representing and solving a maze given an image

What is the best way to represent and solve a maze given an image? Given an JPEG image (as seen above), what's the best way to read it in, parse it into some data structure and solve the maze? My first instinct is to read the image in pixel by…
Whymarrh
  • 13,139
  • 14
  • 57
  • 108
78
votes
9 answers

What's a good algorithm to generate a maze?

Say you want a simple maze on an N by M grid, with one path through, and a good number of dead ends, but that looks "right" (i.e. like someone made it by hand without too many little tiny dead ends and all that). Is there a known way to do this?
Greg
  • 1,304
  • 1
  • 12
  • 8
76
votes
14 answers

Programming theory: Solve a maze

What are the possible ways to solve a maze? Ive got two ideas, but I think they are not very elegant. Base situation: We have a matrix, and the elements in this matrix are ordered in a way that it represents a maze, with one way in, and one out. My…
therufa
  • 2,050
  • 2
  • 25
  • 39
50
votes
8 answers

Generating a tower defense maze (longest maze with limited walls) - near-optimal heuristic?

In a tower defense game, you have an NxM grid with a start, a finish, and a number of walls. Enemies take the shortest path from start to finish without passing through any walls (they aren't usually constrained to the grid, but for simplicity's…
BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
36
votes
8 answers

Algorithm for maze/labyrinth generation with no dead ends?

I'm looking for a maze generation algorithm that can generate a labyrinth with a single continuous path and no dead ends but only a start and end. Like this: Image from http://www.astrolog.org/labyrnth/maze/unicursl.gif Where do I find or go about…
Fejuto
  • 599
  • 1
  • 5
  • 10
30
votes
10 answers

Solve all 4x4 mazes simultaneously with least moves

I came across this quite interesting problem, where we have a 4x4 maze and a robot in it trying to get to the goal. The thing is, you have to find a sequence of predefined commands that will always result in the robot reaching the goal. Let's say we…
Olavi Mustanoja
  • 2,045
  • 2
  • 23
  • 34
19
votes
8 answers

Implementing a randomly generated maze using Prim's Algorithm

I am trying to implement a randomly generated maze using Prim's algorithm. I want my maze to look like this: however the mazes that I am generating from my program look like this: I'm currently stuck on correctly implementing the steps highlighted…
donth77
  • 605
  • 1
  • 12
  • 23
16
votes
2 answers

List.append() changing all elements to the appended item

I seem to have a problem with my maze generating program made in Python. I'm trying to randomly create a path that branches out at select points, with the points getting stored as it goes along. When the maze gets to a dead end, it will sort back…
Matt Habel
  • 1,493
  • 2
  • 14
  • 35
16
votes
6 answers

Count the number of "holes" in a bitmap

Consider a MxN bitmap where the cells are 0 or 1. '1' means filled and '0' means empty. Find the number of 'holes' in the bitmap, where a hole is a contiguous region of empty cells. For example, this has two holes: 11111 10101 10101 11111 …
florin
  • 13,986
  • 6
  • 46
  • 47
15
votes
1 answer

Data Structure to Represent a Maze

I'm writing a game of Dynamic maze in which after each time the structure of maze will change (Some doors will be closed and some doors will open. Something like Triwazard in HP4). Can anyone suggest me which data structure will be best suited to…
Mahesh Gupta
  • 2,688
  • 9
  • 30
  • 46
15
votes
3 answers

JavaScript Maze Solver Algorithm

HTML
Height:
Aleksandr Sinkevič
  • 317
  • 1
  • 4
  • 15
12
votes
3 answers

How to create a random pacman maze

Hello I have been working on an algorithm to generate a random pacman maze. I have seen a couple of articles but could not break down the logic. I am using the maze algorithm depth first search and then I mirror the maze to make each maze…
Mystery Person
  • 181
  • 1
  • 7
11
votes
2 answers

Breadth-first search on an 8x8 grid in Java

What I'm trying to do is count how many moves it takes to get to the goal using the shortest path. It must be done using a breadth first search. I put the 8x8 grid into a 2d array which is filled with one of four chars, E for empty (can move into…
Ethan
  • 155
  • 1
  • 1
  • 8
9
votes
1 answer

Creating a 'hard' maze using Prim's Algorithm

I am using Prim's Algorithm to create a maze. I have successfully done so, but I am now trying to make it 'harder' by changing the way that it selects potential cells to be added to the maze. In my mind, 'hard' lies between two extremes: Extreme #1…
Juicetin
  • 220
  • 1
  • 10
9
votes
1 answer

How to randomly create a fair maze for a multiplayer game?

[Updated my questions at the end] I am creating a 2d multiplayer RTS game which happens inside a maze. I have used Growing Tree algorithm to randomly generate the maze. I thought that the maze would be fair for each team as long as each team's…
Mahdad Baghani
  • 779
  • 12
  • 25
1
2 3
…
72 73