MazeGenerator too slow

Hi there,

I was looking on the Internet for some code to generaze a custom maze (2D for now).

I found some code on the TrueVision3D-site in this topic:
http://www.truevision3d.com/phpBB2/post-41817.html

I downloaded the code and started converting it to Blitz3D (the GenerateMaze-routine, the rest is other stuff like walking around and other things).
My code:
http://users.pandora.be/vge/Blitz/MazeGenerator.bb

I got it working, but it is damn slow (a lot slower than the TV3D version in VB6.0).

A maze in TV3D with the above code (on the TV3D website) generates a maze of 20x20 in about 10 seconds.
The same code (converted to match Blitz-syntax) in Blitz generates a 20x20 maze in about 70-80 seconds (time is recorded and displayed afterwards).

When you launch the code, it asks you for the width and height of the maze.
Just enter "10" for both and see how slow it is in generating the maze structure.

When the maze structure is generated, the maze is shown in 2D onscreen (= fast enough).

Any suggestions on how to speed things up?
Maybe a different approach?

You are slowing everything down by a huge amount by flipping the screen buffers all the time. Do it like this and it's plenty fast!

		percentage = Float(roomcount * 100) / Float(width * height)
		If percentage<>lastperc
			Cls
			Text 0, 0, "Loading " + percentage + "%"
			Flip
			lastperc = percentage
		EndIf

Wow, thanks for the quick reply.

Now it takes about 1.6 seconds to generate a maze of 50x50.

Many thanks.

New version:
http://users.pandora.be/vge/Blitz/MazeGenerator2.bb

1.6 seconds for Blitz vs. 10 seconds for VB.. I like the sound of that..! :)

"PowerPC603" don't forget the showcase area of 'Blitzcoder'. From memory, there are a few bits of code in there.

1.6 seconds to generate a MAZE? That maze code can't be very good, unless it's using some special algorithms to make a particularly interesting maze, or a maze with only one solution.

Should be able to easily generate thousands of mazes a second!

[edit]
Actually the only thing wrong with the code is that you have these lines in your main loop:

percentage# = Float(roomcount * 100) / Float(width * height)
Cls
Text 0, 0, "Loading " + percentage# + "%"
Flip

Remove those completely and a 20x20 maze is generated in 0.003 seconds... That means you can geneerate 333 mazes per second, or one maze 333x the size of a 20x20 maze in one second.

So there's no reason to even have a progress counter. :-)
[/edit]

Super!! Now add a imagebuffer to draw the maze on, save the image buffer as a bmp file, load the bmp file as a terrain, texture it, scale it, light it and then you have a fast dungeon for a game----(if you add in characters, monsters, treasures etc.... Nice Work!
Please note that you will have to use your own images for the textures. The code shows my bmp,png,jpg directories and file names!

Dim horizwalls(0, 0)
Dim vertwalls(0, 0)
Dim walkable(0, 0)

Graphics 1024,768,0,2
SetBuffer BackBuffer()
Global mazebuf=CreateImage(512,512) 

MazeWidth% = Input("How wide do you want the maze to be? ")
MazeHeight% = Input("How high do you want the maze to be? ")
Cls

StartTime% = MilliSecs()
GenerateMaze(MazeWidth%, MazeHeight%)
StopTime% = MilliSecs()

DrawMaze(MazeWidth%, MazeHeight%, StopTime% - StartTime%)
;--------------------------------------------------------------
Cls

Graphics3D 1024,768,16
SetBuffer BackBuffer()
light=CreateLight()
PositionEntity light,100,100,100

camera=CreateCamera()
PositionEntity camera,100,4,120
CameraRange camera,.1,800 

mazio=LoadTerrain("bmp/mazo1.bmp")
maziotex=LoadTexture("jpg/woodpanel.jpg")
ScaleTexture maziotex,4,4
TerrainDetail mazio,3000,True 

EntityTexture mazio,maziotex
ScaleTexture maziotex,4,4
ScaleEntity mazio,1,6,1
sky = CreateSphere(36)
	FlipMesh sky
	ScaleEntity sky,512,300,512
	PositionEntity sky,256,0,256
	sky_tex=LoadTexture("png/cloud256.png")
	ScaleTexture sky_tex,1,1
	EntityTexture sky,sky_tex
    EntityOrder sky,1

While Not KeyDown(1)
If KeyDown( 205 )=True Then TurnEntity camera,0,-1,0 
If KeyDown( 203 )=True Then TurnEntity camera,0,1,0 
If KeyDown( 208 )=True Then MoveEntity camera,0,0,-.5
If KeyDown( 200 )=True Then MoveEntity camera,0,0,.5

UpdateWorld
RenderWorld
Flip

Wend

;0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-0-

Function GenerateMaze(width%, height%)
	; This function generates the entire maze

	; Redim arrays to hold all required data
    Dim walkable(width%, height%)
	Dim horizwalls(width%, height%)
	Dim vertwalls(width%, height%)

	; Declare some local variables
    Local wentleft = False
    Local wentright = False
    Local wentup = False
    Local wenddown = False
    Local roomcount = False

	; Randomize Rnd-function
	SeedRnd MilliSecs()

	; Fill entire arrays with "True"
    For x = 1 To width%
        For y = 1 To height%
            horizwalls(x, y) = True
            vertwalls(x, y) = True
        Next
    Next

	; Start generating the maze at a random point in the grid (between 1 and 20 in both directions)
    xx = Int(Rnd(1, width%))
    yy = Int(Rnd(1, height%))

	; Set current tile as "walkable"
    walkable(xx, yy) = True

	; Set some other vars
    wentleft = False
    wentright = False
    wentup = False
    wentdown = False

	; Count rooms (number of tiles already created)
    roomcount = 1

    Repeat
		; Choose any direction to go next
        Direction = Int(Rnd(1, 4))

        If wentup And wentdown And wentright And wentleft Then
			Repeat
                xx = Int(Rnd(1, width))
                yy = Int(Rnd(1, height))
            Until walkable(xx, yy) = True
        End If

		; Store current xx and yy positions
        oxx = xx
        oyy = yy

        Select Direction
            Case 1 ; up
                yy = yy - 1

                If yy < 1 Then yy = 1

                If walkable(xx, yy) = False Then
                    roomcount = roomcount + 1
                    walkable(xx, yy) = True
                    horizwalls(xx, yy) = False
                    wentup = True
                Else
                    yy = oyy
                End If

            Case 2 ; left
                xx = xx - 1

                If xx < 1 Then xx = 1

                If walkable(xx, yy) = False Then
                    roomcount = roomcount + 1
                    walkable(xx, yy) = True
                    vertwalls(xx, yy) = False
                    wentleft = True
                Else
                    xx = oxx
                End If

            Case 3 ; down
                yy = yy + 1

                If yy > height Then yy = height

                If walkable(xx, yy) = False Then
                    roomcount = roomcount + 1
                    walkable(xx, yy) = True
                    horizwalls(oxx, oyy) = False
                    wentdown = True
                Else
                    yy = oyy
                End If

            Case 4 ; right
                xx = xx + 1

                If xx > width Then xx = width

                If walkable(xx, yy) = False Then
                    roomcount = roomcount + 1
                    walkable(xx, yy) = True
                    vertwalls(oxx, oyy) = False
                    wentright = True
                Else
                    xx = oxx
                End If
        End Select
		
	Until roomcount = width * height
End Function


Function DrawMaze(width%, height%, TimeNeeded%)
	Cls
    SetBuffer ImageBuffer(mazebuf) 

	Color 255, 255, 255
	

	Line 50, 50, 50, 50 + (height% * 10)
	Line 50, 50, 50 + (width% * 10), 50

	For y = 1 To height%
		For x = 1 To width%
			If horizwalls(x, y) Then
				Line (x * 10) + 40, (y * 10) + 50, (x * 10) + 50, (y * 10) + 50
			EndIf
		Next
	Next

	For y = 1 To height%
		For x = 1 To width%
			If vertwalls(x, y) Then
				Line (x * 10) + 50, (y * 10) + 40, (x * 10) + 50, (y * 10) + 50
			EndIf
		Next
	Next

	Flip
	SaveBuffer(ImageBuffer(mazebuf),"bmp/mazo1.bmp") 
;  press any key to exit this function	 
WaitKey()

End Function

@ sswift:

The generator creates a maze with only 1 solution and you can get anywhere in the maze.

The 2 versions I posted didn't generate the entrance and exit yet, but this has been fixed now.

The progress is now also reduced per 10% (not per 1% as before), so the progress is still shown, and works 10x faster.

The code also rescales the window to display the maze.

But when the maze is bigger than my desktop resolution, the window doesn't get much bigger, so there will be a certain limit to the size of the maze.

Now also pressing F8 when the maze is generated will save the maze to disk.

http://users.pandora.be/vge/Blitz/MazeGenerator3.bb

You could always scroll the maze (i.e. centre the viewport on the player (or average it for multiple players).

Currently there is no player.

This code was meant to generate a maze with one solution and it must be able to save the maze to disk, so the user can print the maze on a piece of paper and solve it manually.

Later on, I plan to generate that same maze in 3D, where the player can walk around in, like the TrueVision3D version (for the link, see top post).

I don't know yet if I can make this work, because then I would have to manually build the entire 3D mesh from scratch, and I don't know if I can do it (never did anything like this before).
You can use the "LoadTerrain" command for this (generating a 3D-object), but I've seen it produces something ugly (the walls don't go straight up like it should).
Also the terrain depends on the bitmap, which was generated by the 2D-drawing routine.
In order to create thicker walls and wider pathways, the bitmap-size should be significantly bigger and consumes too much memory.

Also the bitmap must be square and the size must be a power of 2.
If you created a maze, for which the 2D bitmap is slightly bigger than 256x256, then you have to generate a bitmap of 512x512, which creates a terrain where almost 3/4 of the total size is totally flat.

This new (4th version) draws the maze onto a separate imagebuffer, which can be any size.
http://users.pandora.be/vge/Blitz/MazeGenerator4.bb

The mazes are now generated in a square, so you only have to enter 1 parameter.

I created a maze with size 500x500 today with this new version and it took only about 76 seconds.
The bitmap has a size of 2540x2540.

Umm, the latest version doesn't have a entrance and exit, like you were suggesting.
Perhaps if the image generated had thicker lines, the LoadTerrain method of making a 3D terrain would work..ie. vertical walls.
Cheers!

@ gpete:
Sorry, my fault. The link in my latest post was linked to the first version, but that has been corrected now (see latest post).