Ideas for making a maze. 1

[wehttam2007]

I am getting ready to try to make a maze using screen 13. I'm going to first write it down on some grid paper, labeling the lines 200 x 320 for the values of the axes on screen 13. That way it will be easier to plot the lines when im ready to make the maze. Then I will move a pixel around the screen probably using the w,a,s,and d keys, and make the lines a certain color. Then for a collision detection program I will use the color of the lines to tell whether or not I have collided. If anyone has any further ideas on how I could improve this please let me know, it will be very helpful.

Thanks,
Matthew

 

[tsh73]

It sounds as really ?? say, time-consuming approach.
The idea is "laziness is the motor of progress". So why not make Basic did the job for you?

So I can suggest:
1) Make BASIC draw a maze for you (using RND for direction). Run program several times until you get something you like. (probably you'll be correcting your program all along)
2) Probably you will never get "perfect" maze. So you can correct it by hand. I suggest capturing Basic screen (PrintScreen key) and editing it as an image in your favorite image-editing program.
3) Then you can use some ready piece of code to load resulting image. Look around; I'm sure, for example, "all basic code" archive

http://www.allbasiccode.com

have some BMP loaders.

The advantage is you can make as much mazes as you want and load them just by changing filename.

Of course (1) is tricky (and interesting) part...

Hope this helps.

 

[shanley06]

since your using screen 13, you should make a collision array. the way you would do it is like this

screen 13
'set up the array
dim collision%(32000)
'set up x and y variables
x%=1
y%=1
'bload a previously saved map onto the collision array
''make sure that the level you load only uses color 0
'''for places you can walk and color 15 for places
''''you can't walk
def seg=varseg(collision%(0))
bload "level.map",varptr(collision%(0))
def seg
'next is the do-loop part of the game
''i will use inp(96) to handle the keyboard
'''since it has better results than inkey$
do
'if user presses up and if the pixel ahead of you is 
''color 0 then move up 1
if (inp(96)=72) and (pixelcol x%,y%-1=0) then y%=y%-1
if (inp(96)=80) and (pixelcol x%,y%+1=0) then y%=y%+1
if (inp(96)=75) and (pixelcol x%,x%-1=0) then x%=x%-1
if (inp(96)=77) and (pixelcol x%,x%+1=0) then x%=x%+1
pset (x%,y%),4
loop until (inp(96)-1)

'create sub pixelcol
function pixelcol(x%,y%)
def seg=varseg(collison%(0))
pixelcol=peek(320*y%+x%)
def seg
end function

 

[wehttam2007]

Thanks a lot guys... I'll try and see what I can do!

Matthew

 

[quebasic2]

Check around on qbasic sites, seems I remeber seeing a maze program that randomly drew complex mazes that were always solveable.

 

[Pappy1942]

Hi,
Try this url

http://www.easystreet.com/~jkirwan/misc004.html

The programming is in C but the explaination is easy to follow and program in BASIC.

Pappy
You learn something new everyday.

 

[tsh73]

Oh, Pappy1942!
The thing you pointed to is _avesome_!
BTW the programs actually in Basic, but it is the _idea_ that actually wonderful!

 

[logiclrd]

A conceptually easier way to make a maze is to maintain a list in addition to the maze being made: a list of all squares that are not currently in the maze but which are ADJACENT to the maze.

Think of it this way: the maze is originally empty and you have a grid full of squares that are not "in the maze". Then, you repeatedly pick a square to add to the maze. After you add a square to the maze, you need to check for new squares that are now adjacent to the maze but which weren't before.

The easiest way to represent this is to use an array to represent the maze structure, one entry per square in the grid. Each entry is either an invalid value (e.g. -1) to indicate that it is not "in the maze" yet, or it is the index of the square to which that block was connected when it was added. This 'index' of the square must be calculated in some way such that no two squares in the maze have the same index, and you can easily determine which square is being referred to given the index. Typically, this can be done by numbering from left to right across each row, and then top-down. The index of square (column,row) would then be [tt]row*width + column[/tt], and the coordinate of a square can then be extracted using integer division and modulus (the [tt]\[/tt] and [tt]MOD[/tt] operators in QB): [tt]row = index \ width[/tt], and [tt]column = index MOD width[/tt].

In addition to these indices, a special value (e.g. -2) can be used to refer to the entrance to the maze. In this way, the maze becomes, in essence, a tree structure, with each point referring back towards the root of the tree. Here is an example:
[tt]
0 1 2 3 4 5 6 7 8 9

+ ^ +----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
0 | -2 <-0 <-1 | | | | | | | |
| | | | | | | | |
+ ^ +----+ ^ +----+----+----+----+----+----+----+
| | | | | | | | | | | |
10 | 0 <-10| 2 | | | | | | | |
| | | | | | | | | |
+----+ ^ +----+----+----+----+----+----+----+----+
| | | | | | | | | | |
20 | | 11 <-21| | | | | | | |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+
| | | | | | | | | | |
30 | | | | | | | | | | |
| | | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+
. . . . . . . . . . .
. . . . . . . . . . .
[/tt]
The above shows a partially-generated maze on a 10x10 grid (not all of the grid is shown, obviously). You can see the references back stored by squares that have already been added -- connected -- to the maze. The list mentioned earlier, which contains the candidates for the next square to be added to the maze, contains the following squares:
[ul]
[li]#3 (adjacent to #2, which is &quot;in the maze&quot
[li]#13 (adjacent to #12)
[li]#20 (adjacent to #10, and to #21)
[li]#23 (adjacent to #22)
[li]#32 (adjacent to #22)
[li]#33 (adjacent to #23)
[/ul]
The algorithm then picks a random entry from this list as the next square to add to the maze. Say, for instance, that it picks square #13, connecting it back to #12. The maze will now look like this:

[tt]
0 1 2 3 4 5 6 7 8 9

+ ^ +----+----+----+----+----+----+----+----+----+
| | | | | | | | | |
0 | -2 <-0 <-1 | | | | | | | |
| | | | | | | | |
+ ^ +----+ ^ +----+----+----+----+----+----+----+
| | | | | | | | | | |
10 | 0 <-10| 2 <-12| | | | | | |
| | | | | | | | |
+----+ ^ +----+----+----+----+----+----+----+----+
| | | | | | | | | | |
20 | | 11 <-21| | | | | | | |
| | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+
| | | | | | | | | | |
30 | | | | | | | | | | |
| | | | | | | | | | |
+----+----+----+----+----+----+----+----+----+----+
. . . . . . . . . . .
. . . . . . . . . . .
[/tt]
Obviously #13 is no longer in the list of squares adjacent to the maze, because it is now actually in the maze itself. Its neighbours must be checked to see if any of them are now new candidates:
[ul]
[li]#12 is already &quot;in the maze&quot;
[li]#3 and #23 are already in the adjacency list
[li]#14 is not in the adjacency list or in the maze, so it is added to the list
[/ul]
There are two issues that remain to be worked out. Firstly, to tell if squares are already in the adjacency list or not, you need to either scan through the adjacency list (which is relatively slow, though of course on the order of time it takes to generate a maze it isn't THAT significant), or another special value can be used to mark that a square is already in the maze. Here are the special values now in use:
[ul]
[li]-1: Means a square is not in the maze and also not in the adjacency list.
[li]-2: Means the square refers back to the entrance -- &quot;outside&quot; the maze
[li]-3: Means the square is in the adjacency list.
[/ul]
Secondly, there is the case where an entry in the adjacency list could be connected in more than one way. This is obviously very easy to check: you look for adjacent squares that are &quot;in the maze&quot;, and pick one of them at random. It may seem that you could simply store the connection point in the adjacency list and have an entry for each way to connect a square, but to do that, you would then have to scan the adjacency list for duplicates every time you added a square. Instead of scanning, you could check if the square had already been added and ignore it if it had, but the result is still the same: added overhead.

After taking all of the above into account, we have the following. For the example maze above, after adding square #13, the raw values in the array are as follows:
[tt]
-2, 0, 1, -3, -1, -1, -1, -1, -1, -1
0, 10, 2, 12, -3, -1, -1, -1, -1, -1
-3, 11, 21, -3, -1, -1, -1, -1, -1, -1
-1, -3, -3, -1, -1, -1, -1, -1, -1, -1
[/tt]
(followed by 6 more lines of -1 values)

You can see how -3 values &quot;wrap around&quot; the outside of the maze that has been generated so far. Using an asterisk (*) to denote squares in the adjacency list, the maze now looks like this:
[tt]
+ +-+-+-+-+-+-+-+-+-+
| |*| | | | | | |
+ +-+ +-+-+-+-+-+-+-+
| | |*| | | | | |
+-+ +-+-+-+-+-+-+-+-+
|*| |*| | | | | | |
+-+-+-+-+-+-+-+-+-+-+
| |*|*| | | | | | | |
+-+-+-+-+-+-+-+-+-+-+
: : : : : : : : : : :
. . . . . . . . . . .
[/tt]

While this explanation is long-winded, you can see how this approach is very generic and does not require any fixing up/finding new places to start building a maze. For those inclined in graph theory, you can see that this approach can be used generically to build a maze in any undirected graph topology.