Just released: HTML5/Javascript Maze Generator

[Charlo]

I don't know if you could call it a "game", but I just released a maze generator written in Javascript.  It's on my site at http://charlo.gamemakersgarage.com/games/mazegen.php.

Despite the prevalence of maze generators using the same algorithm that I used, I didn't look at anybody else's code while writing this, so it's probably way bulkier than it needs to be.  It took me about a week on-and-off to get a version that did anything other than 1.) fail to do anything when hitting the "generate" button or 2.) get stuck in an infinite loop and crash the browser.  It will still crash your browser if you try to generate past 26000 cells or so.

The interface should be straightforward enough, just enter your parameters and hit the generate button to create a maze.  "Solve" will mark the solution path in red.  Left and right clicks will move the start and end points around.  I did add one game-like feature; you can use the arrow keys to move a dot around the maze. 

Check it out and tell me what you think!

[Gan]

Wow that's impressive! I really like your site Charlo. Plus that maze generator is made of epic sauce. I'm sure the solve feature uses a flood path algorithm but what'd you use to generate the maze?

[Circuit]

That's awesome.  I have no idea how to code any of that.   

[GMG Kurt]

Amazing! I don't even know what PHP stands for 

[Charlo]

Wow that's impressive! I really like your site Charlo. Plus that maze generator is made of epic sauce. I'm sure the solve feature uses a flood path algorithm but what'd you use to generate the maze?

Thanks!  The algorithm is depth-first search.  Read about it on wikipedia: http://en.wikipedia.org/wiki/Maze_generation_algorithm

That's awesome.  I have no idea how to code any of that.   

Yeah, it is pretty awesome.  If I hadn't smartened up on Wikipedia beforehand, I doubt I would have been able to code it either.  But now it seems fairly straightforward.

Amazing! I don't even know what PHP stands for 

It stands for PHP: Hypertext Preprocessor, but it's just the language my site was coded in; the maze generator is Javascript.

[GMG Kurt]

I read the wikipedia on it. so cool

[Gan]

Yeah it's cool. Code is hidden from the user, it's so flexible, data can be saved and did I mention it's so cool?

[Charlo]

UPDATE!  You can now generate "curvy" or "straight" mazes, along with the normal maze type.  Curvy mazes aren't literally curvy, they just have very twisty passageways.  Mazes not based on a rectangular grid are not in the cards at this point. 

[Connors]

Oh i didn't notice you can click and move the starting point. And it still finds the shortest path!

[Gan]

There's a way to generation huge maps without JS timeout. Add a count variable and a maxcount variable. Make the maxcount equal something like 100000. Now up the count variable inside your recursive loops. When count is equal to maxcount stop the recursive loop but save the loop's position. If the recursive loop is unfinished, call a timer on the same method. The timer can be 0.1 sec. That'll allow the method to continuously run until it finishes the looping. Then when the recursion has finished, call the finish code.

An alternative way would be to get the time at the beginning of the method and get the time in the loop and compare the two. If the time is greater than 2 sec, exit the loop and restart the method after 0.1 sec.

P.S These methods mimic a background thread. The timeout for 0.1 sec allows the gui to update and stay responsive.

[Charlo]

I sorta took Gan's advice and made the generation and solving loops non-recursive.  Now I'm basically doing this for the generation:
[code javascript]
while (theMaze.generatedCellCount < theMaze.cellCount - 1) {
    doGeneration();
}[/code]
And
[code javascript]
while (currentCell.isEnd !== true) {
    doSolve();
}[/code]
for solving the maze.  The variables to keep track of the state of each loop (generatedCellCount and currentCell) are declared in a broader scope to make this possible.

Now you can go to 1000x1000 and it only takes a minute to generate!  However, Chrome (which seems to have a faster JS engine than Firefox) choked on 2000x2000 and didn't display anything.  I don't know what happens in any other browsers.

[Gan]

When I make a maze around 250x250 cells, the web page's scroll bars get quite longer but the maze doesn't display. My guess is that it hides under the background of the site.

I'm on Safari.

[Charlo]

When I make a maze around 250x250 cells, the web page's scroll bars get quite longer but the maze doesn't display. My guess is that it hides under the background of the site.

I'm on Safari.

Try clearing your cache.  Safari might be saving an old version of the page.  Firefox, Chrome, and my old version of Safari don't have a problem with extending way past the boundaries of the page.

[Gan]

Cleared my cache. At size of 250, it doesn't display.
It worked perfectly for Chrome though.

[Charlo]

Cleared my cache. At size of 250, it doesn't display.
It worked perfectly for Chrome though.

Weird.  I just upgraded Safari to version 5.0.6, tested it again, and didn't have any problems.

The drawing of the maze to the canvas takes up the most processing power by far, so Safari could be running into some kind of memory limit after it generates the maze.  I saw similar behavior (scroll bars expanding but nothing drawn) in Chrome when I tried a 2000x2000 maze, and have no idea what causes it.  It shouldn't be disappearing behind anything because there's nothing there for it to disappear behind, just a background color.