Friday, April 14, 2017

Monkey-X - Maze - Recursive Division with Rooms - code example


#rem
Recursive Division with Rooms - Maze

From the book - Mazes for programmers -

#end


Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class recursivedivisionrmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        recursivedivisionrmaze
    End Method
    '
    ' This method creates the maze
    '
     ' We set every cell connection to true. Then
     ' we recursively split the grid in half by adding 
     ' walls back in. Every wall we add has one passage.
     '
     ' We add walls with a few lines in the divide 
     ' function. It basically skips recursion at random
     ' at a smaller then <size.
     '
    Method recursivedivisionrmaze()
        ' Set all wall connections to true
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y].north = True
            map[x][y].east = True
            map[x][y].south = True
            map[x][y].west = True
        Next
        Next
        ' Here we recursivly create the maze
        divide(0,0,width,height)
        ' Here we add walls to the outer edge of the 
        ' map.
        For Local y=0 Until height
            map[0][y].west = False
            map[width-1][y].east = False
        Next
        For Local x=0 Until width
            map[x][0].north = False
            map[x][height-1].south = False
        Next
    End Method
    ' Here we divide the grid vertically and
    ' horizontally. We exit it if the cell size
    ' is <=1
    Method divide(x:Int,y:Int,w:Int,h:Int)
        If h <= 1 Or w <= 1 Then Return
        ' Here we add the rooms        
        Local roomw:Int=Rnd(3,8)
        Local roomh:Int=Rnd(3,8)
        If w<roomw And h<roomh And Int(Rnd(6)) = 0 Then Return
        ' Here we select to either do a horizontal 
        ' or vertical wall.
        If h>w
            divide_horizontally(x,y,w,h)
        Else
            divide_vertically(x,y,w,h)
        End If
    End Method
    ' Here we create a horizontal line in the map
    Method divide_horizontally(x:Int,y:Int,w:Int,h:Int)
        ' Get the y location where we create the wall
        Local divide_south_of:Int = Rnd(h-1)
        ' Here we set the location of the door
        Local passage_at:Int = Rnd(w)
        ' Loop through the width of the map
        For Local x1=0 Until w
            ' If not on the open door area
            If passage_at <> x1 Then
                ' if not out of bounds
                If x+x1 < width And y+divide_south_of < height
                ' Get the cell location
                Local x2:Int = x+x1
                Local y2:Int = y+divide_south_of
                ' Unlink the walls
                map[x2][y2].south = False
                If y2+1<height 
                map[x2][y2+1].north = False
                End If
                End If
            End If
        Next
        ' Recurse - Make a new wall horizontally
        ' and vertically in the area we just did.
        divide(x,y,w,divide_south_of+1)
        divide(x,y+divide_south_of+1,w,h-divide_south_of-1)
    End Method    
    ' Here we create a vertical wall
    Method divide_vertically(x:Int,y:Int,w:Int,h:Int)
        ' get the location where we create the walls
        Local divide_east_of:Int = Rnd(w-1)
        ' One location where we create an open door(passage)
        Local passage_at:Int = Rnd(h)
        ' Loop from top to bottom of the map
        For Local y1=0 Until h
            ' If not on a passage
            If passage_at <> y1 Then
            ' If not out of bounds
            If y+y1<height And x+divide_east_of < width
                ' Get the current cell to carve into
                Local x2:Int = x+divide_east_of
                Local y2:Int = y+y1
                ' Disconnect(carve) the wall
                map[x2][y2].east = False
                If x2+1<width
                map[x2+1][y2].west = False
                End If
            End If
            End If
        Next
        ' Divide in this area again
        divide(x,y,divide_east_of+1,h)
        divide(x+divide_east_of+1,y,w-divide_east_of-1,h)
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:recursivedivisionrmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New recursivedivisionrmaze(20,20,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            Seed = Millisecs
            maze = New recursivedivisionrmaze(20,20,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Recursive Division mazes with rooms.",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Recursive Division Algorithm - code example


#rem
Recursive Division Algorithm - Maze

From the book - Mazes for programmers -

#end


Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class recursivedivisionmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        recursivedivisionmaze
    End Method
    '
    ' This method creates the maze
    '
     ' We set every cell connection to true. Then
     ' we recursively split the grid in half by adding 
     ' walls back in. Every wall we add has one passage.
     '
    Method recursivedivisionmaze()
        ' Set all wall connections to true
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y].north = True
            map[x][y].east = True
            map[x][y].south = True
            map[x][y].west = True
        Next
        Next
        ' Here we recursivly create the maze
        divide(0,0,width,height)
        ' Here we add walls to the outer edge of the 
        ' map.
        For Local y=0 Until height
            map[0][y].west = False
            map[width-1][y].east = False
        Next
        For Local x=0 Until width
            map[x][0].north = False
            map[x][height-1].south = False
        Next
    End Method
    ' Here we divide the grid vertically and
    ' horizontally. We exit it if the cell size
    ' is <=1
    Method divide(x:Int,y:Int,w:Int,h:Int)
        If h <= 1 Or w <= 1 Then Return
        If h>w
            divide_horizontally(x,y,w,h)
        Else
            divide_vertically(x,y,w,h)
        End If
    End Method
    ' Here we create a horizontal line in the map
    Method divide_horizontally(x:Int,y:Int,w:Int,h:Int)
        ' Get the y location where we create the wall
        Local divide_south_of:Int = Rnd(h-1)
        ' Here we set the location of the door
        Local passage_at:Int = Rnd(w)
        ' Loop through the width of the map
        For Local x1=0 Until w
            ' If not on the open door area
            If passage_at <> x1 Then
                ' if not out of bounds
                If x+x1 < width And y+divide_south_of < height
                ' Get the cell location
                Local x2:Int = x+x1
                Local y2:Int = y+divide_south_of
                ' Unlink the walls
                map[x2][y2].south = False
                If y2+1<height 
                map[x2][y2+1].north = False
                End If
                End If
            End If
        Next
        ' Recurse - Make a new wall horizontally
        ' and vertically in the area we just did.
        divide(x,y,w,divide_south_of+1)
        divide(x,y+divide_south_of+1,w,h-divide_south_of-1)
    End Method    
    ' Here we create a vertical wall
    Method divide_vertically(x:Int,y:Int,w:Int,h:Int)
        ' get the location where we create the walls
        Local divide_east_of:Int = Rnd(w-1)
        ' One location where we create an open door(passage)
        Local passage_at:Int = Rnd(h)
        ' Loop from top to bottom of the map
        For Local y1=0 Until h
            ' If not on a passage
            If passage_at <> y1 Then
            ' If not out of bounds
            If y+y1<height And x+divide_east_of < width
                ' Get the current cell to carve into
                Local x2:Int = x+divide_east_of
                Local y2:Int = y+y1
                ' Disconnect(carve) the wall
                map[x2][y2].east = False
                If x2+1<width
                map[x2+1][y2].west = False
                End If
            End If
            End If
        Next
        ' Divide in this area again
        divide(x,y,divide_east_of+1,h)
        divide(x+divide_east_of+1,y,w-divide_east_of-1,h)
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:recursivedivisionmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New recursivedivisionmaze(20,20,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            Seed = Millisecs
            maze = New recursivedivisionmaze(20,20,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Recursive Division Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Thursday, April 13, 2017

Monkey-X - Maze - Growing Tree Algorithm - code example


#rem
Growing Tree Algorithm - Maze

From the book - Mazes for programmers -

#end


Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class growingtreemaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        growingtreemaze
    End Method
    '
    ' This method creates the maze
    '
     ' The growing tree algorithm is like the prim's
     ' algorithm. It has a list with cells and either
     ' picks one out randomly or the last one. This
     ' cell location is used to carve to a neighbor.
     ' If the list is empty then the maze is done.
     '
     '
     '
    Method growingtreemaze()
        'This variable is used to select more or less
        'variation. Lower is longer paths
        Local variation:=Rnd(1,5)
        ' This is the list with neighbor cells
        Local availneighbors:Stack<cell> = New Stack<cell>
        ' pick a random cell position
        Local x:Int=Rnd(0,width)
        Local y:Int=Rnd(0,height)
        ' push to the neighbor list
        availneighbors.Push(New cell(x,y))
        ' mark visited
        map[x][y].visited = True
        ' loop until the list is emtpy
        While availneighbors.IsEmpty = False
            ' variable that holds the position we are
            ' on in the stack(deletion)
            Local p:Int
            ' Chose between random and last
            If Int(Rnd(variation)) = 0 'last
                p = availneighbors.Length-1
                x = availneighbors.Get(p).x
                y = availneighbors.Get(p).y
            Else'random
                'get random position from list
                p = Rnd(availneighbors.Length)
                x = availneighbors.Get(p).x
                y = availneighbors.Get(p).y
            End If
            ' make list for positions around the current cell
            Local dirs:Stack<Int> = New Stack<Int>
            ' put cells on the dirs list if unvisited and 
            ' on the map.
            If y-1 >= 0 And map[x][y-1].visited = False Then dirs.Push(0)
            If x+1 < width And map[x+1][y].visited = False Then dirs.Push(1)
            If y+1 < height And map[x][y+1].visited = False Then dirs.Push(2)
            If x-1 >= 0 And map[x-1][y].visited = False Then dirs.Push(3)
            ' if there are directions we can go into
            If dirs.Length > 0
                ' from all positions around the current cell
                ' select one direction.
                Local s:Int=dirs.Get(Rnd(0,dirs.Length))
                ' carve into direction and set x,y with new value
                Select s
                    Case 0'north
                    map[x][y].north = True
                    y-=1                    
                    map[x][y].south = True                    
                    Case 1'east
                    map[x][y].east = True
                    x+=1
                    map[x][y].west = True
                    Case 2'south
                    map[x][y].south = True
                    y+=1
                    map[x][y].north = True
                    Case 3'west
                    map[x][y].west = True
                    x-=1
                    map[x][y].east = True
                End Select
                ' mark new position as visited
                map[x][y].visited = True
                ' push new position to the availneighbors 
                ' list
                availneighbors.Push(New cell(x,y))                    
            Else ' if no neighbors then remove from 
                 ' availneighbors list
                availneighbors.Remove(p)
            End If
        Wend
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:growingtreemaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New growingtreemaze(20,20,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            Seed = Millisecs
            maze = New growingtreemaze(20,20,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Growing Tree Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - True Prim's Algorithm - code example


#rem
True Prim's Algorithm - Maze

From the book - Mazes for programmers -

#end

Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class trueprimsmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        trueprimsmaze
    End Method
    '
    ' This method creates the maze
    '
    ' You have a list for neighbors. You put
    ' a start position in the list from the map.
    ' On the map each cell has a random value.
    ' We pick a cell from the neighbor list with the lowest
    ' value. We then create a list with the directions around 
    ' the current position if they are unvisited.
    ' We select to carve into this new direction. The one
    ' With the lowest value. Put the new position on the neighbor
    ' list.
    ' If there was no direction to go around the current cell
    ' then remove this position from the neighbor list.
    ' When the list is empty then the maze is done.
    ' 
    Method trueprimsmaze()
        ' This is the list with neighbor cells
        Local availneighbors:Stack<cell> = New Stack<cell>
        ' Put a random value on each of the cells in the map.
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y].value = Rnd(0,100)
        Next
        Next
        ' These hold the start position
        Local x:Int,y:Int
        ' Find start position. The position on the map
        ' with the lowest value
        Local lowest:Int=100
        For Local y1=0 Until height
        For Local x1=0 Until width
            If map[x1][y1].value < lowest Then
                x = x1
                y = y1
                lowest = map[x1][y1].value
            End If
        Next
        Next
        ' push to the neighbor list
        availneighbors.Push(New cell(x,y))
        availneighbors.Top.value = map[x][y].value
        ' mark visited
        map[x][y].visited = True
        ' loop until the list is emtpy
        While availneighbors.IsEmpty = False
            ' get the position on the map with the lowest
            ' value.
            Local lowest:Int=100
            ' We need to remember the item position on the list
            ' we select. So we can delete it later on.
            Local itemtodelete:Int
            For Local i = 0 Until availneighbors.Length
                If availneighbors.Get(i).value < lowest
                    lowest = availneighbors.Get(i).value
                    x = availneighbors.Get(i).x
                    y = availneighbors.Get(i).y
                    itemtodelete = i
                End If
            Next

            ' make list for positions around the current cell
            Local dirs:Stack<Int> = New Stack<Int>
            ' put cells on the dirs list if unvisited and 
            ' on the map.
            If y-1 >= 0 And map[x][y-1].visited = False Then dirs.Push(0)
            If x+1 < width And map[x+1][y].visited = False Then dirs.Push(1)
            If y+1 < height And map[x][y+1].visited = False Then dirs.Push(2)
            If x-1 >= 0 And map[x-1][y].visited = False Then dirs.Push(3)
            ' if there are directions we can go into
            If dirs.Length > 0
                ' from all positions around the current cell
                ' select the direction with the lowest value
                Local s:Int=-1
                Local lowest:Int=500
                For Local i = 0 Until dirs.Length
                    If dirs.Get(i) = 0
                    If map[x][y-1].value < lowest Then
                        lowest = map[x][y-1].value
                        s = 0
                    End If
                    End If
                    If dirs.Get(i) = 1
                    If map[x+1][y].value < lowest Then
                        lowest = map[x+1][y].value
                        s = 1
                    End If
                    End If
                    If dirs.Get(i) = 2
                    If map[x][y+1].value < lowest Then
                        lowest = map[x][y+1].value
                        s = 2
                    End If
                    End If
                    If dirs.Get(i) = 3
                    If map[x-1][y].value < lowest Then
                        lowest = map[x-1][y].value
                        s = 3
                    End If
                    End If
                Next
                ' carve into direction and set x,y with new value
                Select s
                    Case 0'north
                    map[x][y].north = True
                    y-=1                    
                    map[x][y].south = True                    
                    Case 1'east
                    map[x][y].east = True
                    x+=1
                    map[x][y].west = True
                    Case 2'south
                    map[x][y].south = True
                    y+=1
                    map[x][y].north = True
                    Case 3'west
                    map[x][y].west = True
                    x-=1
                    map[x][y].east = True
                End Select
                ' mark new position as visited
                map[x][y].visited = True
                ' push new position to the availneighbors 
                ' list
                availneighbors.Push(New cell(x,y))
                ' Set the value of the item
                availneighbors.Top.value = map[x][y].value                    
            Else ' if no neighbors then remove active item from 
                 ' availneighbors list
                availneighbors.Remove(itemtodelete)
            End If
        Wend
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:trueprimsmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New trueprimsmaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New trueprimsmaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "True Prim's Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Simplified Prim's Algorithm - code example

#rem
Simplified Prim's Algorithm - Maze

From the book - Mazes for programmers -

#end


Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class simplifiedprimsmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        simplifiedprimsmaze
    End Method
    '
    ' This method creates the maze
    '
    ' What the algorithm does is: It starts with 
    ' a list with a start location on it. We take
    ' a random location from the list and see if there
    ' are neighbors cells that have not been visited.
    ' We select one of those neighbors and carve towards
    ' it. We add that new cell to the list. 
    ' If there are no neighbors then we remove that cell
    ' from the list.
    ' The maze is finished if the list is empty.
    ' 
    ' The method is somewhat like a flood(seed) fill.
    ' 
    Method simplifiedprimsmaze()
        ' This is the list with neighbor cells
        Local availneighbors:Stack<cell> = New Stack<cell>
        ' pick a random cell position
        Local x:Int=Rnd(0,width)
        Local y:Int=Rnd(0,height)
        ' push to the neighbor list
        availneighbors.Push(New cell(x,y))
        ' mark visited
        map[x][y].visited = True
        ' loop until the list is emtpy
        While availneighbors.IsEmpty = False
            'get random position from list
            Local p:Int=Rnd(availneighbors.Length)
            x = availneighbors.Get(p).x
            y = availneighbors.Get(p).y
            ' make list for positions around the current cell
            Local dirs:Stack<Int> = New Stack<Int>
            ' put cells on the dirs list if unvisited and 
            ' on the map.
            If y-1 >= 0 And map[x][y-1].visited = False Then dirs.Push(0)
            If x+1 < width And map[x+1][y].visited = False Then dirs.Push(1)
            If y+1 < height And map[x][y+1].visited = False Then dirs.Push(2)
            If x-1 >= 0 And map[x-1][y].visited = False Then dirs.Push(3)
            ' if there are directions we can go into
            If dirs.Length > 0
                ' from all positions around the current cell
                ' select one direction.
                Local s:Int=dirs.Get(Rnd(0,dirs.Length))
                ' carve into direction and set x,y with new value
                Select s
                    Case 0'north
                    map[x][y].north = True
                    y-=1                    
                    map[x][y].south = True                    
                    Case 1'east
                    map[x][y].east = True
                    x+=1
                    map[x][y].west = True
                    Case 2'south
                    map[x][y].south = True
                    y+=1
                    map[x][y].north = True
                    Case 3'west
                    map[x][y].west = True
                    x-=1
                    map[x][y].east = True
                End Select
                ' mark new position as visited
                map[x][y].visited = True
                ' push new position to the availneighbors 
                ' list
                availneighbors.Push(New cell(x,y))                    
            Else ' if no neighbors then remove from 
                 ' availneighbors list
                availneighbors.Remove(p)
            End If
        Wend
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:simplifiedprimsmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New simplifiedprimsmaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New simplifiedprimsmaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Simplified Prim's Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Randomized Kruskals Algorithm - code example


#rem
Randomized Kruskal's Algorithm - Maze

From the book - Mazes for programmers -

#end

Import mojo


Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Field value:Int
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class randomizedkruskalsmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        randomizedkruskalsmaze
    End Method
    '
    ' This method creates the maze
    '
    ' Randomized kruskal works by creating a stack list
    ' with connections between each cell. Either a east or
    ' a south. On the map each cell has a unique value.
    ' we randomly pick a connection from the list and connect it
    ' if the map values are different. We then turn both the
    ' different map values and turn them into one value.
    ' We then delete this connection from the list. The maze 
    ' is done if the list is empty.
    '
    Method randomizedkruskalsmaze()
        ' create a stack list with cell class
        Local connection:Stack<cell> = New Stack<cell>
        ' variable with value to assign to each cell
        Local val:Int=0
        ' loop though the map
        For Local y=0 Until height
        For Local x=0 Until width
            ' add east link to connection stack
            If x<width-1
                connection.Push(New cell(x,y))
                connection.Top.east = True
            End If
            ' add south link to connection stack
            If y<height-1
                connection.Push(New cell(x,y))
                connection.Top.south = True            
            End If
            ' give the map its unique value
            map[x][y].value = val
            ' increase the value
            val+=1
        Next
        Next
        ' loop until the connection stack is empty
        While connection.IsEmpty = False
            ' get a random link from the stack
            Local r:Int = Rnd(connection.Length)
            ' get its x and y and value
            Local x:Int = connection.Get(r).x
            Local y:Int = connection.Get(r).y
            Local v:Int = map[x][y].value
            ' s we use to see if it is east or south
            Local s:Int
            If connection.Get(r).east = True Then s = 0
            If connection.Get(r).south = True Then s = 1
            ' remove the link from the stack list
            connection.Remove(r)
            ' here we carve a connection if the cell
            ' we are on and the east or south has a different
            ' value. Then we give them one and the same value.
            Select s
                Case 0 'east
                If map[x][y].value <> map[x+1][y].value
                    map[x][y].east = True
                    map[x+1][y].west = True
                    merge(v,map[x+1][y].value)
                End If
                Case 1'south
                If map[x][y].value <> map[x][y+1].value
                    map[x][y].south = True
                    map[x][y+1].north = True
                    merge(v,map[x][y+1].value)
                End If
            End Select
        Wend
    End Method
    ' This method takes all of one value on the map and turns it into 
    ' another.
    Method merge(a:Int,b:Int)
        For Local y=0 Until height
        For Local x=0 Until width
            If map[x][y].value = b Then map[x][y].value = a
        Next
        Next
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:randomizedkruskalsmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New randomizedkruskalsmaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New randomizedkruskalsmaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Randomized Kruskal's Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Recursive Backtracker - code example


#rem
Recursive Backtracker Algorithm - Maze

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class recursivebacktrackermaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        recursivebacktrackermaze
    End Method
    '
    ' This method creates the maze
    '
    '
    '
    Method recursivebacktrackermaze()
        ' This is a list that contains a x and y value
        Local path:Stack<cell> = New Stack<cell>
        ' These variables we use to store the current cell we 
        ' are on.
        Local x:Int=0,y:Int=0
        ' push the first position to the top of the list
        path.Push(New cell(x,y))
        ' mark the position as visited
        map[x][y].visited = True
        ' loop until we have nothing left on the stack
        While path.IsEmpty = False
            ' get position from the top of the stack list
            x = path.Top.x
            y = path.Top.y
            'get unvisited neighbours
            Local dir:Stack<Int> = New Stack<Int>
            If y-1 >= 0 And map[x][y-1].visited = False Then dir.Push(0)
            If x+1 < width And map[x+1][y].visited = False Then dir.Push(1)
            If y+1 < height And map[x][y+1].visited = False Then dir.Push(2)
            If x-1 >= 0 And map[x-1][y].visited = False Then dir.Push(3)
            ' If we have unvisited neighbours
            If dir.Length > 0
                ' get a random direction
                Local s:Int = dir.Get(Rnd(dir.Length))
                ' carve to new position and add to top of stack
                ' and mark visited for the selected direction.
                Select s
                    Case 0'north
                    map[x][y].north = True
                    map[x][y-1].south = True
                    path.Push(New cell(x,y-1))
                    map[x][y-1].visited = True
                    Case 1'east
                    map[x][y].east = True
                    map[x+1][y].west = True
                    path.Push(New cell(x+1,y))
                    map[x+1][y].visited =True
                    Case 2'south
                    map[x][y].south = True
                    map[x][y+1].north = True
                    path.Push(New cell(x,y+1))
                    map[x][y+1].visited = True
                    Case 3'west
                    map[x][y].west = True
                    map[x-1][y].east = True
                    path.Push(New cell(x-1,y))
                    map[x-1][y].visited = True
                End Select
            Else  
                'If no neighboors then backtrack 
                '(remove top item from stack)
                path.Pop
            End If
        Wend

    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:recursivebacktrackermaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New recursivebacktrackermaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New recursivebacktrackermaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Recursive Backtracker Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Hunt and Kill Algorithm - code example


#rem
Hunt and Kill Algorithm - Maze

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class huntandkillmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        makehuntandkillmaze
    End Method
    '
    ' This method creates the maze
    '
    ' We start left top of the map and step into a random direction
    ' were we have not been before and carve a path there.
    ' When we can not find a unvisited cell around our last position
    ' we enter the kill mode and find a new unvisited spot on the map
    ' and carve a path to one of the visited cells around it. Then we
    ' return to hunt mode. If no more spots are found in kill mode
    ' then the maze is finished.
    '
    '
    Method makehuntandkillmaze()
        Local x:Int=0,y:Int=0
        Local state:String="hunt"
        map[x][y].visited = True
        Repeat
            If state="hunt"
                'read around x,y for unvisited cells
                Local dir:Stack<Int> = New Stack<Int>
                If y-1 >= 0 And map[x][y-1].visited = False Then dir.Push(0)
                If x+1 < width And map[x+1][y].visited = False Then dir.Push(1)
                If y+1 < height And map[x][y+1].visited = False Then dir.Push(2)
                If x-1 >= 0 And map[x-1][y].visited = False Then dir.Push(3)
                'If we have a place to go then carve a path
                If dir.Length > 0
                    Local s:Int=dir.Get(Rnd(dir.Length))
                    If s = 0 'north
                        map[x][y].north = True
                        map[x][y-1].south = True
                        y-=1
                    End If
                    If s = 1 'east
                        map[x][y].east = True
                        map[x+1][y].west = True
                        x+=1
                    End If
                    If s = 2 'south
                        map[x][y].south = True
                        map[x][y+1].north = True
                        y+=1
                    End If
                    If s = 3 'west
                        map[x][y].west = True
                        map[x-1][y].east = True
                        x-=1
                    End If
                    map[x][y].visited = True
                    Else 'no place to go so go into kill mode
                    state = "kill"
                End If
            End If
            If state = "kill"
                ' if we are done flag
                Local newspot:Bool=False
                'loop through the entire map
                For Local y1=0 Until height
                For Local x1=0 Until width
                    'if we find a unvisited cell
                    If map[x1][y1].visited = False
                        'set to current position
                        x = x1
                        y = y1
                        'exit flag
                        newspot = True
                        'back to hunt mode next
                        state = "hunt"
                        ' create a list with visited cells around the new spot
                        Local dir:Stack<Int> = New Stack<Int>
                        If y-1 >= 0 And map[x][y-1].visited = True Then dir.Push(0)
                        If x+1 < width And map[x+1][y].visited = True Then dir.Push(1)
                        If y+1 < height And map[x][y+1].visited = True Then dir.Push(2)
                        If x-1 >= 0 And map[x-1][y].visited = True Then dir.Push(3)
                        ' pick a direction from the list
                        Local s:Int=dir.Get(Rnd(dir.Length))
                        'carve a path to the selected cell
                        Select s
                            Case 0'north
                            map[x][y].north = True
                            map[x][y-1].south = True
                            Case 1'east
                            map[x][y].east = True
                            map[x+1][y].west = True
                            Case 2'south
                            map[x][y].south = True
                            map[x][y+1].north = True
                            Case 3'west
                            map[x][y].west = True
                            map[x-1][y].east = True                            
                        End Select
                        'mark the new cell visited
                        map[x][y].visited = True
                        'exit the for for loop
                        Exit
                    End If
                Next
                Next
                ' If we have no new spot then we are done
                If newspot = False Then Return
            End If
        Forever
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:huntandkillmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New huntandkillmaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New huntandkillmaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Hunt and Kill Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Friday, April 7, 2017

Monkey-X - Maze - Wilsons Algorithm - code example


#rem
Wilson's Algorithm - Maze

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field x:Int,y:Int
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool=False
    Method New(x:Int,y:Int)
        Self.x = x
        Self.y = y
    End Method
End Class

Class wilsonmaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        makewilsonmaze
    End Method
    '
    ' This method creates the maze
    '
    ' The Wilson method of making a maze works by
    ' using the random walk method to create
    ' paths on unvisited parts on the map. It starts
    ' at a random position and moves around. If 
    ' its path overlaps then start over again. This until the
    ' path reaches a visited cell. Then carve the
    ' path out.
    '
    '
    Method makewilsonmaze()
        ' tool for adding/subtracting directions
        Local mx:Int[] = [0,1,0,-1]
        Local my:Int[] = [-1,0,1,0]
        ' one cell must be visited on the map
        Local x:Int=Rnd(0,width)
        Local y:Int=Rnd(0,height)
        map[x][y].visited = True
        ' temp cell location
        Local nx:Int,ny:Int
        ' starting state
        Local state:String="makepath"
        ' here we select the starting cell 
        ' an unvisited cell.
        Local exitloop:Bool=False
        While exitloop = False
            ' create random pos
            x = Rnd(0,width)
            y = Rnd(0,height)
            ' if unvisited then exit loop and set temp
            ' position variables
            If map[x][y].visited = False
                exitloop = True
                nx = x
                ny = y
            End If
        Wend
        ' create stack list
        Local path:Stack<cell> = New Stack<cell>
        ' push first cell on the stack list
        path.Push(New cell(x,y))
        ' if leftover = false then map is done
        Local leftover:Bool=True
        While leftover=True
            ' here we make the path
            If state="makepath"
                ' select a diagonal direction
                Local dir:Int
                dir=Rnd(0,4)
                ' if inside of the map
                If nx+mx[dir]>=0 And ny+my[dir]>=0 And nx+mx[dir]<width And ny+my[dir]<height
                    ' set new position
                    nx+=mx[dir]
                    ny+=my[dir]
                    Local go:Bool=True
                    For Local i=0 Until path.Length
                        ' if we already have that position then start over
                        If path.Get(i).x = nx And path.Get(i).y = ny
                            path = New Stack<cell>
                            nx = x
                            ny = y
                            path.Push(New cell(x,y))        
                            go = False    
                            Exit                
                        End If
                    Next
                    ' add new position to list and see
                    ' if we have reached a visited cell.
                    If go=True
                        path.Push(New cell(nx,ny))
                        If map[nx][ny].visited = True
                            ' if we reached a visited cell then
                            ' carve out the path
                            state = "carvepath"
                        End If
                    End If
                End If
            End If
            '
            ' Here we carve the path we created
            If state="carvepath"
                ' for getting the direction between the
                ' data on the stack list
                Local dir:Int
                ' get the first cell from the stack
                ' list and mark it visited
                Local x1:Int,y1:Int
                x1 = path.Get(0).x
                y1 = path.Get(0).y
                map[x1][y1].visited = True
                ' loop through the stack starting with the
                ' second cell on the stack list
                For Local i=1 Until path.Length
                    ' copy the cell from the stack
                    ' list into vars and mark visited on map
                    Local x2:Int=path.Get(i).x
                    Local y2:Int=path.Get(i).y
                    map[x2][y2].visited = True
                    ' find the direction between previous
                    ' and current cell from stack
                    If x2=x1 And y2<y1 Then dir=0
                    If x2>x1 And y2=y1 Then dir=1
                    If x2=x1 And y2>y1 Then dir=2
                    If x2<x1 And y2=y1 Then dir=3
                    ' carve out the path
                    Select dir
                        Case 0'up
                        map[x1][y1].north = True
                        map[x2][y2].south = True
                        Case 1'right
                        map[x1][y1].east = True
                        map[x2][y2].west = True
                        Case 2'down
                        map[x1][y1].south = True
                        map[x2][y2].north = True
                        Case 3'left
                        map[x1][y1].west = True
                        map[x2][y2].east = True
                    End Select
                    ' the last cell from the stack list
                    ' becomes the first cell
                    x1 = x2
                    y1 = y2
                Next
                'we no longer need the path list
                'so erase it
                path = New Stack<cell>
                ' here we check if there are unvisited cells
                ' left
                leftover = False
                For Local i=0 Until height
                For Local ii=0 Until width
                    If map[ii][i].visited = False Then 
                        leftover = True
                        Exit
                    End If
                Next
                Next
                ' if there are unvisited cells left
                ' then find a new cell to work with
                Local exitloop:Bool=False
                While exitloop = False And leftover = True
                    Local x3:Int=Rnd(0,width)
                    Local y3:Int=Rnd(0,height)
                    If map[x3][y3].visited = False
                        x = x3
                        y = y3
                        nx = x3
                        ny = y3
                        exitloop = True
                    End If
                Wend
                ' put the new cell on the path
                path.Push(New cell(x,y))
                ' back to making the path
                state = "makepath"
            End If

        Wend
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:wilsonmaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New wilsonmaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New wilsonmaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Wilson Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Thursday, April 6, 2017

Monkey-X - Maze - Aldous-Broder - code example


#rem
Aldous-Broder Maze

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
    Field visited:Bool
End Class

Class aldousbrodermaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        makealdrousbrodermaze
    End Method
    '
    ' This method creates the maze
    ' This is like the drunken walk algorithm.
    ' You start a a random position And go in a
    ' random diagonal direction. If the New cell
    ' is unvisited Then carve a path And mark
    ' visited. If not visited Then keep moving around
    ' (no carving) until a unvisited cell is encountered.
    '
    Method makealdrousbrodermaze()
        Local remaining:Int=width*height-1
        Local mx:Int[] = [0,1,0,-1]
        Local my:Int[] = [-1,0,1,0]
        Local x:Int=Rnd(0,width)
        Local y:Int=Rnd(0,height)
        Local nx:Int,ny:Int
        map[x][y].visited = True
        While remaining>0        
            ' random direction 0up 1right 2down 3left
            Local dir:Int=Rnd(0,4)
            ' create new position
            nx = x+mx[dir]
            ny = y+my[dir]
            ' if in bounds
            If nx>=0 And ny>=0 And nx<width And ny<height
            ' if unvisited
            If map[nx][ny].visited = False
                ' mark visited
                map[nx][ny].visited = True
                ' exit loop counter -1
                remaining-=1
                ' carve into direction
                Select dir
                    Case 0'up
                    map[x][y].north = True
                    map[nx][ny].south = True
                    Case 1'right
                    map[x][y].east = True
                    map[nx][ny].west = True
                    Case 2'down
                    map[x][y].south = True
                    map[nx][ny].north = True
                    Case 3'left
                    map[x][y].west = True
                    map[nx][ny].east = True
                End Select
            End If
            ' set new position as current position
            x=nx
            y=ny
            End If
        Wend
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:aldousbrodermaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New aldousbrodermaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New aldousbrodermaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Aldous Broder Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Sidewinder Algorithm - code example


#rem
Sidewinder algorithm Mazes

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
End Class

Class bintreemaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        makesidewindermaze
    End Method
    '
    ' This method creates the maze
    '
    ' Starts left top and moves to bottom right.
    ' Every series of cells horizontally it picks a corridor towards
    ' the bottom.
    ' The series of cells horizontally connect also.
    '
    ' aaabbcccc
    '  |  |  |
    '
    Method makesidewindermaze()
        For Local y = 0 Until height
        Local runstart:Int = 0
        For Local x = 0 Until width
            If y>0 And (x+1 = width Or Rnd(3)  <1)
                Local cell:Int=runstart+Rnd(x - runstart + 1)
                map[cell][y].north = True
                map[cell][y-1].south = True
                runstart = x+1
            Elseif x+1 < width
                map[x][y].east = True
                map[x+1][y].west = True
            End If
        Next
        Next
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:bintreemaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New bintreemaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New bintreemaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Sidewinder Algorithm Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function

Monkey-X - Maze - Binary Tree - code example


#rem
Binary Tree Mazes

From the book - Mazes for programmers -

#end

Import mojo

Class cell
    Field north:Bool,east:Bool
    Field south:Bool,west:Bool
End Class

Class bintreemaze
    Field width:Int,height:Int
    Field tilewidth:Float,tileheight:Float
    Field map:cell[][]
    Method New(mazewidth:Int,mazeheight:Int,sw:Int,sh:Int)
        Self.width = mazewidth
        Self.height = mazeheight
        map = New cell[width][]
        For Local i=0 Until width
            map[i] = New cell[height]
        Next
        For Local y=0 Until height
        For Local x=0 Until width
            map[x][y] = New cell
        Next
        Next
        tilewidth = Float(sw)/Float(mazewidth)
        tileheight = Float(sh)/Float(mazeheight)
        makebintreemaze
    End Method
    '
    ' This method creates the maze
    '
    ' We go from left top to bottom right step by step.
    ' Here we remove then either the north wall or the west wall.
    '
    '
    Method makebintreemaze()
        ' north(0) west(1)
        For Local y=0 Until height
        For Local x=0 Until width
            ' create a stack
            Local dir:Stack<Int> = New Stack<Int>
            ' if on position where we can remove north and west wall
            ' add option to stack
            If y>0 Then dir.Push(0)
            If x>0 Then dir.Push(1)
            If dir.Length>0
                ' Get random north or west
                Local s:Int=dir.Get(Rnd(dir.Length))
                ' remove the north wall and south wall on neigbour cell
                If s=0 Then 
                    map[x][y].north=True
                    map[x][y-1].south=True
                End If
                ' remove the west wall and east wall on neigbour cell
                If s=1 Then
                    map[x][y].west=True
                    map[x-1][y].east=True
                End If
            End If
        Next
        Next
    End Method
    '
    ' Draw the maze
    '
    Method draw()
        For Local y=0 Until height
        For Local x=0 Until width
            Local x1:Int=x*tilewidth
            Local y1:Int=y*tileheight
            SetColor 255,255,255
            If map[x][y].north = False
                DrawLine x1,y1,x1+tilewidth,y1
            End If
            If map[x][y].east = False
                DrawLine x1+tilewidth,y1,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].south = False
                DrawLine x1,y1+tileheight,x1+tilewidth,y1+tileheight
            End If
            If map[x][y].west = False
                DrawLine x1,y1,x1,y1+tileheight
            End If
        Next
        Next
    End Method
End Class

Global maze:bintreemaze

Class MyGame Extends App
    Method OnCreate()
        SetUpdateRate(1)
        maze = New bintreemaze(10,10,500,400)
    End Method
    Method OnUpdate()        
        If MouseHit(MOUSE_LEFT)
            maze = New bintreemaze(10,10,500,400)
        End If
    End Method
    Method OnRender()
        Cls 0,0,0 
        SetColor 255,255,255
        maze.draw
        DrawText "Binary Tree Maze",0,480-40
        DrawText "Press Mouse or Touch to create new maze",0,480-20
    End Method
End Class


Function Main()
    New MyGame()
End Function