PureBasic Forums - English

Posted: **Tue Jun 07, 2011 12:13 pm**

I've got a maze generator, and although it creates a maze, I'm after the rendering to be a bit different: I want the "walls" to be as wide as the path, not a thin line. I know I have all the data, but the only method I can think of is to reprocess all the maze data into another (larger) maze grid that I can then use. I would prefer to have the renderer deal with it.

Ideas anyone?

Code: Select all

; 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  


Macro Stack_Push(Stack, Value)
  LastElement(Stack)
  AddElement(Stack)
  Stack = Value
EndMacro

Macro Stack_Pop(Stack, Variable)
  LastElement(Stack)
  Variable = Stack
  DeleteElement(Stack)
EndMacro


#Scale = 25
#Width = 10
#Height = 10

Structure strMazeCell
  BackTrack.a
  Solution.a
  Border.a
  Walls.a
EndStructure

Global Dim Maze.strMazeCell(0, 0)

Procedure DrawMaze()
    
  FlipBuffers() 
  ClearScreen(RGB(0, 0, 0))

  StartDrawing(ScreenOutput())
  For y = 0 To #Height
    For x = 0 To #Width
      If maze(x, y)\Walls <> 0 And maze(x, y)\Walls <> %1111
        ; NESW
        If (Maze(x, y)\Walls & %1000) = %1000
         LineXY(x * #Scale, y * #Scale, (x * #Scale) + #Scale, y * #Scale)
        EndIf
        If (Maze(x, y)\Walls & %0100) = %0100
         LineXY(x * #Scale, y * #Scale, x * #Scale, (y * #Scale) + #Scale)
        EndIf
        If (Maze(x, y)\Walls & %0010) = %0010
         LineXY(x * #Scale, (y * #Scale) + #Scale, (x * #Scale) + #Scale, (y * #Scale) + #Scale)
        EndIf
        If (Maze(x, y)\Walls & %0001) = %0001
         LineXY((x * #Scale) + #Scale, y * #Scale, (x * #Scale) + #Scale, (y * #Scale) + #Scale)
        EndIf
        
      EndIf
    Next
  Next
  StopDrawing()
  
EndProcedure


Procedure GenerateMaze(width.i, height.i)
  NewList PointStack.Point()
  
  Protected TotalCells.i = (width + 1) * (height + 1)
  Protected VisitedCells.i = 1
  Protected x.i, y.i
  
  Dim Maze.strMazeCell(width, height)
  For x = 0 To width
    For y = 0 To height
      With Maze(x, y)
        \BackTrack = 0
        \Walls = %1111 ; NESW all set
        \Solution = 0
        
        \Border = 0 ; NESW
        If x = 0
          \Border | %0100
        EndIf
        If y = 0
          \Border | %1000
        EndIf
        If x = Width
          \Border | %0001
        EndIf
        If y = Height
          \Border | %0010
        EndIf
      EndWith
      
    Next
  Next
  
  x = Random(width) : y = Random(height)
  
  Protected p.Point
  p\x = 0
  p\y = 0
  Stack_Push(PointStack(), p)
  
  NewList PossibleDirections.a()

  While VisitedCells < TotalCells
    If (Maze(x, y)\Border & %1000) = 0 And Maze(x, y - 1)\Walls = %1111
      AddElement(PossibleDirections())
      PossibleDirections() = %1000
    EndIf
    If (Maze(x, y)\Border & %0100) = 0 And Maze(x - 1, y)\Walls = %1111
      AddElement(PossibleDirections())
      PossibleDirections() = %0100
    EndIf
    If (Maze(x, y)\Border & %0010) = 0 And Maze(x, y + 1)\Walls = %1111
      AddElement(PossibleDirections())
      PossibleDirections() = %0010
    EndIf
    If (Maze(x, y)\Border & %0001) = 0 And Maze(x + 1, y)\Walls = %1111
      AddElement(PossibleDirections())
      PossibleDirections() = %0001
    EndIf
    
    If ListSize(PossibleDirections()) > 0
      SelectElement(PossibleDirections(), Random(ListSize(PossibleDirections()) - 1))
      
      Select PossibleDirections()
        Case %1000
          Maze(x, y)\Walls & %0111
          Maze(x, y - 1)\Walls & %1101
          y - 1
        Case %0100
          Maze(x, y)\Walls & %1011
          Maze(x - 1, y)\Walls & %1110
          x - 1
        Case %0010
          Maze(x, y)\Walls & %1101
          Maze(x, y + 1)\Walls & %0111
          y + 1
        Case %0001
          Maze(x, y)\Walls & %1110
          Maze(x + 1, y)\Walls & %1011
          x + 1
      EndSelect
      
      p\x = x
      p\y = y
      Stack_Push(PointStack(), p)
      
      VisitedCells + 1
    Else
      Stack_Pop(PointStack(), p)
      x = p\x
      y = p\y
    EndIf

    ClearList(PossibleDirections())
    
    DrawMaze()
  Wend
  
EndProcedure

InitSprite()

OpenWindow(0, 0, 0, (#Scale * (#Width + 1) + 1), (#Scale * (#Height + 1) + 1) , "aMAZEing...", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(0), 0, 0, WindowWidth(0), WindowHeight(0), #False, #False, #False)

GenerateMaze(#width, #height)

Repeat
  Repeat
    Event = WindowEvent()
    
    Select Event 
      Case #PB_Event_CloseWindow
        End 
    EndSelect
  Until Event = 0


  DrawMaze()
  
  Delay(1)
ForEver

Posted: **Tue Jun 07, 2011 1:23 pm**

I don't have the answer, but what you posted isn't a maze. It's just a single long twisted path.

Posted: **Tue Jun 07, 2011 1:42 pm**

That's due to it's size (11x11), that's why it's easy for you...

Bump up the size and you have a maze, I'll be doing a minimum of 64x64 but I need to get the basics working first.

Posted: **Tue Jun 07, 2011 1:59 pm**

Even at 64x64 it's still just a long path, with only a few cells that go off from the main path. It's very easily solved just by following it with the mouse. I suggest you find a different algorithm for your maze, as this one seems to be flawed in a big way.

Edit: Here, just to show how flawed it is... I made a 64x64 maze, then did a flood-fill with a paint program to "follow" the path. As you can see, it leads to a dead-end really quick... an unsolvable maze!

Posted: **Tue Jun 07, 2011 2:09 pm**

I've just editted it to be more random - the problem was my random bit selector wasn't very random...

Posted: **Tue Jun 07, 2011 4:49 pm**

@Foz:

Here's a simple way to do what you want:

1. Add a new constant

Code: Select all

#Thick = #Scale/2 ; Wall thickness

2. Replace the four LineXY() statements with these four Box() statements

Code: Select all

Box(x * #Scale - #Thick, y * #Scale - #Thick, #Scale + #Thick, #Thick)
Box(x * #Scale - #Thick, y * #Scale - #Thick, #Thick, #Scale + #Thick)
Box(x * #Scale - #Thick, (y * #Scale) - #Thick + #Scale, #Scale + #Thick, #Thick)
Box((x * #Scale) + #Scale - #Thick, y * #Scale - #Thick, #Thick, #Scale + #Thick)

Please also add the EnableExplicit statement at the start of your code, in order to detect spelling mistakes.

Posted: **Tue Jun 07, 2011 5:00 pm**

Actually worked it out - and yes there was a problem with the original code, getting my up down left rights all mixed up, this was why when I first tried to draw the path in blocks, it didn't work.

Now it works:

EnableExplicit added on request

Code: Select all

; 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  

EnableExplicit

Macro Stack_Push(Stack, Value)
  LastElement(Stack)
  AddElement(Stack)
  Stack = Value
EndMacro

Macro Stack_Pop(Stack, Variable)
  LastElement(Stack)
  Variable = Stack
  DeleteElement(Stack)
EndMacro


#Scale = 10
#Width = 10
#Height = 10

Structure strMazeCell
  BackTrack.a
  Solution.a
  Border.a
  Walls.a
EndStructure

Global Dim Maze.strMazeCell(0, 0)

Procedure DrawMaze()
  Protected x.i, y.i, i.i, j.i
  
  FlipBuffers() 
  ClearScreen(RGB(0,0,0))

  StartDrawing(ScreenOutput())
  For y = 0 To #Height
    For x = 0 To #Width
      ; ; NESW
      ; If (Maze(x, y)\Walls & %1000) = %1000
      ;  LineXY(x * #Scale, y * #Scale, (x * #Scale) + #Scale, y * #Scale)
      ; EndIf
      ; If (Maze(x, y)\Walls & %0100) = %0100
      ;  LineXY(x * #Scale, y * #Scale, x * #Scale, (y * #Scale) + #Scale)
      ; EndIf
      ; If (Maze(x, y)\Walls & %0010) = %0010
      ;  LineXY(x * #Scale, (y * #Scale) + #Scale, (x * #Scale) + #Scale, (y * #Scale) + #Scale)
      ; EndIf
      ; If (Maze(x, y)\Walls & %0001) = %0001
      ;  LineXY((x * #Scale) + #Scale, y * #Scale, (x * #Scale) + #Scale, (y * #Scale) + #Scale)
      ; EndIf

      ; NESW
      i = (x * 2) +1
      j = (y * 2) +1
      If Maze(x, y)\Walls <> %1111
        Box(i * #Scale, j * #Scale, #Scale, #Scale)
      EndIf
      
      If (Maze(x, y)\Walls & %1000) = 0 ; North
        Box(i * #Scale, (j-1) * #Scale, #Scale, #Scale)
      EndIf
      If (Maze(x, y)\Walls & %0100) = 0 ; East
        Box((i+1) * #Scale, j * #Scale, #Scale, #Scale)
      EndIf
      ; If (Maze(x, y)\Walls & %0010) = 0 ; South
      ;   Box(i * #Scale, (j+1) * #Scale, #Scale, #Scale)
      ; EndIf
      ; If (Maze(x, y)\Walls & %0001) = 0 ; West
      ;   Box((i-1) * #Scale, j * #Scale, #Scale, #Scale)
      ; EndIf
    Next
  Next
  StopDrawing()
  
EndProcedure


Procedure GenerateMaze(width.i, height.i)
  NewList PointStack.Point()
  
  Protected TotalCells.i = (width + 1) * (height + 1)
  Protected VisitedCells.i = 1
  Protected x.i, y.i
  
  Dim Maze.strMazeCell(width, height)
  For x = 0 To width
    For y = 0 To height
      With Maze(x, y)
        \BackTrack = 0
        \Walls = %1111 ; NESW all set
        \Solution = 0
        
        \Border = 0 ; NESW
        If y = 0      ; North
          \Border | %1000
        EndIf
        If x = Width  ; East
          \Border | %0100
        EndIf
        If y = Height ; South
          \Border | %0010
        EndIf
        If x = 0      ; West
          \Border | %0001
        EndIf
      EndWith
      
    Next
  Next
  
  x = Random(width) : y = Random(height)
  
  Protected p.Point
  p\x = 0
  p\y = 0
  Stack_Push(PointStack(), p)
  
  NewList PossibleDirections.a()

  While VisitedCells < TotalCells
    If (Maze(x, y)\Border & %1000) = 0 And Maze(x, y - 1)\Walls = %1111 ; North
      AddElement(PossibleDirections())
      PossibleDirections() = %1000
    EndIf
    If (Maze(x, y)\Border & %0100) = 0 And Maze(x + 1, y)\Walls = %1111 ; East
      AddElement(PossibleDirections())
      PossibleDirections() = %0100
    EndIf
    If (Maze(x, y)\Border & %0010) = 0 And Maze(x, y + 1)\Walls = %1111 ; South
      AddElement(PossibleDirections())
      PossibleDirections() = %0010
    EndIf
    If (Maze(x, y)\Border & %0001) = 0 And Maze(x - 1, y)\Walls = %1111 ; West
      AddElement(PossibleDirections())
      PossibleDirections() = %0001
    EndIf
    
    If ListSize(PossibleDirections()) > 0
      SelectElement(PossibleDirections(), Random(ListSize(PossibleDirections()) - 1))
      
      Select PossibleDirections()
        Case %1000  ; North
          Maze(x, y)\Walls & %0111
          Maze(x, y - 1)\Walls & %1101
          y - 1
        Case %0100  ; East
          Maze(x, y)\Walls & %1011
          Maze(x + 1, y)\Walls & %1110
          x + 1
        Case %0010  ; South
          Maze(x, y)\Walls & %1101
          Maze(x, y + 1)\Walls & %0111
          y + 1
        Case %0001  ; West
          Maze(x, y)\Walls & %1110
          Maze(x - 1, y)\Walls & %1011
          x - 1
      EndSelect
      
      p\x = x
      p\y = y
      Stack_Push(PointStack(), p)
      
      VisitedCells + 1
    Else
      Stack_Pop(PointStack(), p)
      x = p\x
      y = p\y
    EndIf

    ClearList(PossibleDirections())
    
    ;DrawMaze()
  Wend
  
EndProcedure

InitSprite()

OpenWindow(0, 0, 0, (#Scale * (#Width + 1)*2) + #Scale, (#Scale * (#Height + 1)*2)  + #Scale, "aMAZEing...", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(0), 0, 0, WindowWidth(0), WindowHeight(0), #False, #False, #False)

GenerateMaze(#width, #height)

Define e.i

Repeat
  Repeat
    e = WindowEvent()
    
    Select e 
      Case #PB_Event_CloseWindow
        End 
    EndSelect
  Until e = 0

  DrawMaze()
  
  Delay(1)
ForEver

PureBasic Forums - English

Mazes

Mazes

Re: Mazes

Re: Mazes

Re: Mazes

Re: Mazes

Re: Mazes

Re: Mazes