DFS Graph Generation in Python

Question

So I'm trying to get a little more proficient with Python, and decided that making a maze would be a fun thing to know how to do. I found this page that goes over a bit of how to do it.

   create a CellStack (LIFO) to hold a list of cell locations  
   set TotalCells = number of cells in grid  
   choose a cell at random and call it CurrentCell  
   set VisitedCells = 1  

    while VisitedCells < TotalCells 
        find all neighbors of CurrentCell with all walls intact   
        if one or more found 
            choose one at random  
            knock down the wall between it and CurrentCell  
            push CurrentCell location on the CellStack  
            make the new cell CurrentCell  
            add 1 to VisitedCells
        else 
            pop the most recent cell entry off the CellStack  
            make it CurrentCell
        endIf
    endWhile

Now, I've got the following code, although it isn't much past the obvious stuff in the pseudocode.

class Cell:
    top_wall = 0
    bottom_wall = 0
    left_wall = 0
    right_wall = 0
    def knock_down(self,wall):
        if wall is 'top_wall' and self.top_wall is 0:
            self.top_wall = 1
        if wall is 'bottom_wall' and self.bottom_wall is 0:
            self.bottom_wall = 1
        if wall is 'left_wall' and self.left_wall is 0:
            self.left_wall = 1
        if wall is 'right_wall' and self.right_wall is 0:
            self.right_wall = 1
        else
            return 'Error: Wall Already Gone'

maze = [10][10]
CellStack = []          # LIFO stack to hold list of cell locations
TotalCells = 100        # Number of cells in grid
VisitedCells = 0        # Cells that have been visited
CurrentCell = 0         # The current cell

while VisitedCells < TotalCells:

I'm not sure that the class is the best way to do the cells, but I haven't thought of another way to do it yet. However, I've run into a bit of a problem for checking for the neighbors of a cell. The find all neighbors of CurrentCell with all walls intact is throwing me for a bit of a loop.

How can you check whether cells are neighbors?

Mihai Maruseac · Accepted Answer · 2012-07-07 20:06:45Z

1

You can give each cell a position, stored as two integers. Then, two cells are neighbors if those integers are neighbors.

def isCellNeighbor(c1, c2):
   if abs(c1.x - c2.x) == 1: return True
   if abs(c1.y - c2.y) == 1: return True
   return False

The above considers two cells as being neighbors if at least a corner of each one touches the other. You can tweak it to suit your needs.

PS: have a look at the amazing collection of maze algorithms

answered Jul 7, 2012 at 20:06

Mihai Maruseac

21.5k7 gold badges61 silver badges110 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mihai Maruseac Over a year ago

I said that this happens in the answer :)

Collectives™ on Stack Overflow

DFS Graph Generation in Python

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related