Maze Generator

So, fun little story: One of my custom titles is that I'm a coder.
"But Twage, you've never shown us anything that you've coded!"
Yes, you're right, I haven't. Yet.


Well, I have that title because I am about to start college in a week or so as a Computer Science major, which means I will doing coding for a living. I have made many small programs for my high school courses in programming, but none of them have really been all that noteworthy. However, I have one that I thought might be worth sharing.

You see, I've been working on a program in NetBeans (written in Java) that will print out a maze that is randomly generated on the spot, and is one of three sizes - you pick. It will always have at least on solution if not more than one, and most will be pretty simple to solve.

I'm not sure exactly how to take it from NetBeans and give it to you guys to play with in an environment where it could run on its own though, and it isn't anywhere near being finished. When it is finished though, I'll need a bit of help getting it out of NetBeans. I know GitHub exists, I just don't know much about it...

In the spoiler below, I explain how the behemoth of a program works:

Spoiler

(Hopefully I did the spoiler thing right...)
This is the Maze Building Program by Twage (And hopefully a few friends).
This program creates a randomly generated maze of
varying size by piecing together a variety of pre-created Blocks,
each of which are stored inside the program.
Each Block is a perfect 8x8 unit square, with walls inside.
As all squares do, Blocks have 4 sides.
Depending on where the entry/exit gaps on each side fall,
each side is labelled with a certain "type" of side. For example,
having gaps in the 2nd and 7th positions along the side
may be classified as "Side Type B". In my code, there are 5 types of sides,
including a solid wall for Blocks along the exterior of the maze.

Blocks are created such that they fit together like puzzle pieces
with matching side types in order to make one large, fluent maze.
There are (or will eventually be) 576* different blocks, one for each
possible combination of side types.

*This number excludes any Blocks that would have 2+ walls
on opposite sides of the Block, which would be impossimble
unless the maze was only 1 Block wide, which my program does not allow.

The actual creation of the maze is, as you may expect, very complicated.
It is broken into multiple parts:

1. The creation of individual building Blocks in the Block matrix named Grid.

2. The selection of what type of sides the blocks will have,
- The top and left sides are copied from the pre-existing adjacent Blocks,
and the right and bottom sides are randomly generated.
- The code will determin if a Block is on the edge/corner of the maze,
and overwrite the side types with an x,
meaning that side is an exterior wall.

3. Based upon the 4 side types the Block has been given,
the Block's constructor then calls on the ChooseType method
located in the Block Class, which hosts a large library of data for
the different interiors of Blocks with all kinds of sides.

The method finds the correct type of Block through
a large number of switch cases that go through every possible
combination of side types.
The Block's interior wall data is then retrieved.

4. Each line of walls in the maze is 8 units long and could be described by
8 booleans, which is compressed into a pair of hexadecimal digits
The data for the interior of the Block is stored as a
series of hexadecimal digits, written in pairs.

As there are a total of 18 lines of walls in the maze
(9 horizontal and 9 vertical), this means there are 18 pairs
of hexadecimal digits to describe all of the walls in each Block.

5. Once all Blocks have been generated
and the set of hexadecimal digits for each Block have been stored,
the Print method in the Maze Class (this one)
is called to write out and display the whole thing
in the MyDrawingArea window.

There are many sub-steps to this process:
- The method goes back through the Grid matrix
in the same fashion its constructor did:
From left to right, descending one row at a time.
- It reads each Block's hexadecimal code
and converts it into an array of booleans to be used in the Line method,
which iterates through the array of booleans and
either does or does not draw a line
based on the boolean it is currently looking at.
- The method determines whether or not it is drawing
horizontally or vertically based on which overall half of
the hexadecimal pairs it is looking at.
(The method switches from horizontal to vertical halfway through
because that is how the data is intended to be coded at first.)
- Repeat hyphens 1-3 until maze is fully formed.

6. Now that the maze has fully generated, been printed out,
and the code has finished running, the maze should be ready to play!

"Twage, why are you wasting my time making this thread?!"
Calm down, there's a point to this wall of text. I'm not just trying to show off.

I need your help.

For any of you who actually took the time to read the wall of text that is the program's explanation, I need help creating all of those 576 Blocks. I can acredit those who contribute in the finalization of the code. All you need to do is submit the hexadecimal reduction of a maze Block, and then tell me what side types you made it with. I will show you how to do all of that if you PM me, but I don't feel like going into detail on how to do it here if no one replies.

So, hopefully a few of you will offer a helpful hand in the creation of this program. I know this community is one of the best out there in terms of friendliness, and I hope some of you will step up.

Thanks so much for taking the time to read all of this,
- Twage.

 

Two people did a maze generator in survival

 

Sorry, I should have clarified that this is not Minecraft based.

 

ah.

 

I'm also a programmer, and in my opinion this is a needlessly complicated way to go about creating a maze. There are so many simpler ways. Also, even with your system you plan to use, having a separate maze block for every possible thing is also inefficient, you could much easier have the program create the different types for you.

 

Agreed with modern. The hardest part would be having the maze actually generate a maze not a path with useless closed off junk next to it

________________________________

Also your final comment is confusing me a bit. Are you asking for submissions for mazes that work?

________________________________

Oh I see what you are trying to do. I think you approach will be tedious as each block must be manually generated. Stitching those pregenerated blocks together is not very impressive, and you could probably find a better and more efficient way to do it.

 

I am a relatively new coder, and I only started learning a couple years ago - cut me some slack here. I had another idea as to how to go about doing this, I just could not for the life of me figure out how to make it happen. I knew I could make it so the path would randomly generate it self by snaking through and empty space, turning at random points after random amounts of distances, and at random intervals there would be branching dead ends, but I couldn't figure out how to keep the maze from generating in such a way to where the solution wouldn't generate itself into a coil, trapping itself as a dead end and never reaching the finish point.

In addition, I'm not sure how I would keep track of where to put walls or not as it generates - those would be some pretty massive matrices of Booleans that would constantly be changing as they generate...

 

I apologize if I came across as a little mean, I just wanted to help. :/

So basically if you already are able to create a branching snaking path, a simple way to guarantee it doesn't coil is have it return an error and restart if it can't spread out to the end anymore. alternatively, leave it coiled and put the end there instead.
Also, saving massive matrices of Booleans is generally a bad idea, but in this case it wouldn't be too bad. Just start off with your dozens of arrays for columns and rows, all with enough booleans in there and all set to false. Then as your generation system snakes out, it can easily find the right row and right term in the array to change to true.
I feel like there's a better way to store them while taking advantage of Java's OOP style, but I'm not willing to spend more than 5 minutes thinking about it atm. :P Sorry!

________________________________

Also curious, how would you do it?
It'd be quite difficult to get a functional and aesthetically pleasing maze to be generated reliably.

 

My favorite way of designing mazes kind of off brand, but works pretty well.

How it works is that maze blocks, or "cells" are placed in a cooling fashion, like a randomized version of snake. If the front of the snake hits a cell that has already been placed or the area constraints, it puts a wall there instead. You would be surprised how well this works, and it always generates a complete maze.

Of course this is a oversimplification, but this type of maze creating is one you can find all over the Internet, as it is fairly popular and relatively simple.

 

Hmm, so like it snakes around randomly and whenever it encounters repeats of paths it puts a wall?