P_O's hellish mazes.

[Pixel_Outlaw]

I have been working on a 2d maze generator if anyone is interested. I suppose we could have a sort of competitive maze solving. How fast can you solve this monster? Start in the upper left and make your way to the lower right. Once I get the code really clean and fast I'll probably release the application. (Lots of tweaking to be done and perhaps a GUI too.)



I personally hate mazes but I like to generate them.

[Ruldra]

How fast can you solve this monster?

People would get insane before finding a solution

[Lordstar]

ooh dude you can totaly sell these to restaurants to put on the back of kids menus.

[shoe-sama]

lol these mazes are easy

just time consuming

gives you something to do though lol

[undamned]

That's awesome.
-ud

[Shatterhand]

I 1cc it in 22 minutes and 36 seconds.

Edit: But I used save-states.

[MX7]

I don't think that i'd bother trying to 'solve' it, but it sure is beautiful

[Udderdude]

I can't even look at it without going cross-eyed.

[Super Laydock]

*hands over utmost respect*

Awesomeness!

I'll never solve it since I hate any maze I can't solve within 10 minutes or so, but the freaks are going to go berserk over this stuff.

[nem]

Not to steal your thunder, but I was interested in generating mazes at one time, and ran across this. The way it solves it is a lot of fun to watch.

Anyway, nice work!

[Ed Oscuro]

The way it solves it is a lot of fun to watch.

If by "fun" you mean "painful," yes.

It quickly boxed out the 1/5 of the maze it must go into (all the way up to the right wall of the maze), but then it started searching in a counter-clockwise movement - the 4/5 of the maze it did not need do go to. It ended up searching about half the maze, mostly unnecessarily, lolz

It'd be cool if there was a way to solve it yourself...

[shoe-sama]

too inefficient

[SpooN]

Uhm to solve a maze fast is a pretty simple thing to do for an computer, however this system simulates how to solve a maze if you can't view it from the top and if you don't take the algorithm behind the maze into account I guess it's even the most efficient one (mmh, I wonder the math behind it might be pretty complex).

EDIT: Well I agree it could avoide obvious deadends, but that's all I see.

[Ed Oscuro]

Oh, if it's not meant to realize where it is in relation to the edges, that would make sense. It found its way across the maze pretty darn quick, though. It seemed like it was always looking for the longest run first.

[SpooN]

I think the concept is more that you don't know where the exit is. If you know that the maze is rectangular one could possibly find a better algorithm but I'm not too sure of it.
And it seems to me it uses the old "put your right hand on the wall and walk along" (which means go left if you move backwards in this case) algorithm, with which you can solve any 2d maze with entrance and exit on the outside.
This has gotten me interested, I'd really like to know how developed this field is in math and which field it even is ^^ (graph theory would be my guess but who knows?!)

[Ed Oscuro]

I think the concept is more that you don't know where the exit is.

That'd make more sense if the exit location got switched up

[Pixel_Outlaw]

The algorithm I use is pretty easy.

1 make an array of cells
2 pick one cell that has not been visited
3 from that unvisited cell begin carving into the neighboring cells marking them visited as they are visited.
4 continue carving until you reach a dead end of visited cells
5 find an unvisited cell that has a visited neighbor
6 knock down that wall between the visited and unvisited cell
7 start back to 3

I have been running quite a few maze applications. And the right or left hand method will not guarantee the fastest solving time. If I add some loops that algorithm becomes useless too.

[shoe-sama]

fill tool in paint whenever there's a split

surely there's a way to emulate that

[SpooN]

Ed Oscuro this isn't really something one can discuss because, uhm the machine just uses an algorithm and it does neither know where it nor anything else, I was thinking about the underlying theoretical problem, in which the general approach would imply perfect memory, but it really is nothing worth 3 posts of us

Pixel_Outlaw, of course the algorithm wont solve every maze the fastest, but over the set of every maze (of a given dimension) it might be the fastest in average. And I'm not sure how a "loop" would look in a 2d maze, since you have your hand attached to the wall connected to the entrance (if you just meant very unlucky constellations then don't mind).

shoe-sama don't know if I understand you right but if I do then your algorithm works the same way the hand algorithm does. It doesn't matter if you choose right, left or random as long as you eliminate every possibility.

[Ed Oscuro]

Ed Oscuro this isn't really something one can discuss because, uhm the machine just uses an algorithm and it does neither know where it nor anything else, I was thinking about the underlying theoretical problem

It looks like you're discussing it to me :D Clearly this is "thinking outside the box" (literally!), but it would make for an interesting update to the algorithm.

Maze algorithms are already fast enough, especially on modern computers; that sort of upgrade would be a very cool addition.

Shoe: Fill tool would only leave those paths that aren't possible to enter since they're boxed off, unless you only set it to fill in for a certain length. For P_Hat's maze, every path is apparently reachable and so the whole maze turns (insert fill tool color here).

For a laugh, I opened up the Paintl in Vista and it took a good second figuring out what to do. Unfortunately it only drew the change onscreen when it was finished. Started my fan running too!

[UnscathedFlyingObject]

Blow it up 3X the size and I'll give it some thought.

[landshark]

Use the photoshop solving method.

http://taint.org/2007/06/19/121541a.html