Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Depth-first-search maze generation algorithm with blocks instead of walls

I am trying to implement the depth first search algorithm into my game. I have been studying this web page: http://www.mazeworks.com/mazegen/mazetut/index.htm , only to find that I wouldn't be able to use it with blocks instead of Walls. What I mean by blocks is a square that covers the whole cell, instead of just the edges. I thought that it would be easier to do it this way, but now I am not so sure. Has anyone done this? If so, how? (psuedocode is fine). Or, should I just go with the walls method, if it is easier?

like image 357
Xedfire Avatar asked May 21 '11 16:05

Xedfire


People also ask

How we can generate a maze .give an algorithm?

Another way of generating a maze is by applying a randomized Depth First Search (DFS) to the grid. The algorithm starts at a given cell and marks it as visited. It selects a random neighboring cell that hasn't been visited yet and makes that one the current cell, marks it as visited, and so on.

What is depth first search maze?

Depth-first search is an algorithm that can be used to generate a maze. The idea is really simple and easy to implement using recursive method or stack. Basically, you start from a random point and keep digging paths in one of 4 directions(up, right, down, left) until you can't go any further.

What is a perfect maze?

A perfect maze is a maze where any two cells can be joined by a unique path. In the literature, there exist eleven maze generation algorithms as compiled by Buck in 2015 in his book “Mazes for Programmers”. Each algorithm creates mazes differently. Our aim is to analyze how perfect mazes are generated.


1 Answers

depending on what you actually wish to achieve i've two solutions for you. they are both basically the algorithm presented on the website you've referenced.

1.) there are blocks at predefined positions in your maze

  • you run the algorithm on a 2*k+1 grid
  • assume the numbering of your cells starts top left with (0,0). mark all cells with 2 odd coordinates ( (2*p+1, 2*q+1); p,q < k ) as blocks.
  • you run the modified algorithm from your source on the remaining cells ('even cells'). the modifications are:
    • start with an even cell picked at random
    • a 'neighbour cell' is the second but next cell in any grid direction; i.e. you 'jump' over a brick.
    • instead of knocking down the wall between cells, you turn the block into an accesible cell. however, this cell will not be considered by the selection and backtracking

2.) instead of walls separating cells you want blocks.

before starting the algorithm mark any number of cells as blocks. proceed as outlined in your source but never consider any of the block cells. you will have to take special precautions if you want want to guarantee complete accessibility in your maze. a simple scheme would be to never mark a cell as a block that has more than 1 blocks as neighbours.

hope these ideas suit your needs,

best regards, carsten

like image 199
collapsar Avatar answered Oct 14 '22 10:10

collapsar