MazeGenerator too slow
Blitz3D Forums/Blitz3D Beginners Area/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! |
| ||
| @ 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 |
| ||
| 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. 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). |
   |