Random Maze Generator

A random maze generating system for WC3. A function takes parameters for positioning and size of the maze and creates it. Also offers random generation of entrance/exit points and has the option of setting a minimum for how far apart they must be.

Due to the thread limit, this system currently supports:
Mazes with or without generated exit/entrance work up to 80 x 80.
(Beware when generating large mazes, from about 60 x 60 upwards. Your WC3 will freeze for a period of time, it was up to between 30 seconds and 1 minute for me on an 80 x 80 maze.)

Edit: Updated with new stats and the new version.

Cool, tho the "dead ends" are not especially realistic(atleast not in the pic)

Very interesting and well made system, it has my approval.

If possible, it would be great if you could make it work on bigger areas too (maybe use short waits?), but it is still very great.

I am afraid your code is a little opaque to me, so if I am way off the mark I apologize. I think it uses a random exploration algorithm to build the maze. There is another method for generating mazes with better branching. This is something I wrote recently for someone on wc3jass:
https://webfiles.berkeley.edu/p_d/maze.w3x

I have not implemented exit/entrances, and my terrain is not half as beautiful as yours, but maybe it solves the dead end realism problem.

By random exploration, do you mean starts at a point and explores until it reaches a dead end then back tracks and repeats? If so, then no.

Looking at your map, it looks like I used exactly the same method as you did. Create all the walls, then pick two random, adjacent blocks and remove the wall between them (if they are not already joined, or in the same 'set' in your case, it would appear).

Yup. Cool.

I played around twiddling with triggersleeps and got around 25-35s for an 80x80 map so my code is no better. Maybe timers could do a better job- perhaps run the script every .0005s, see how it goes.

It may also be possible to improve the asymptotics towards the end. When you have m a few single or double cells in a nxn maze that need to be freed, the probabilistic algorithm will take around mn^2 (/4 ?) tries. If you explicitly constructed a list of the walls that are options for being broken, you should spend around n^2 total to build a list of sets, and then m^2 or less time to randomly select walls from this much shorter list. This will only be faster if the sets are mostly small (except the big one!) and you can floodfill them in constant time, not n^2, when you break a wall.

I had had the idea of creating a list of all possible walls to break at the beginning of the algorithm and then choosing unique random ones from the list. The number of possible wall breaks in a maze is equal to (w x h) - w + (w x h) - h = 2wh - w - h. This further simplifies to 2 x w^2 - 2w in a square maze. This would make a large amount of the processing come upfront (up to 12640 iterations in an 80 x 80 maze) but would make the subsequent random selection a lot shorter. Overall, it would probably be more efficient than the current system, as there would be no redundancy in wall checks (where a wall that has already been destroyed is randomly selected for possible destruction and all the checks that go with it).

Toyed around with my version a bit more and the 80x80 mazes. First off found that arrays are much faster than game cache. Making that switch for the set structure dropped me from 30s to 20s- that's with about 300,000 read/writes. Next I tried running the code from a timer. I figured that the game was insufficiently frozen. Anyway, with a 100us elapse, it brought the time down to 4.7s! When you can afford to run code with global vars, it's (apparently) an easy way to do process intensive things in JASS-trigger sleep action is way too player friendly. So, try giving a timer loop a shot.

That includes the time to kill all those damn trees, but not create.

You could probably get the same result with multithreading and triggersleepaction, but to say the least that scares me.

Global vars should be no big deal multiinstancing wise if you put a mutex on it.

I'm sure atleast part of the long delay is for the destruction of the old walls (they have the dust cloud animation when they die), the creation of the new walls (loading new destructables) and then killing some of those ones. I have checked, and when you can't see any part of the maze you are creating, WC3 does freeze for less time.

Great system but one little problem. Units like the footman can waltz right through where two walls meet in a straight line.

Example, If you have a wall that looks like:

|
|

The Footman can waltz right through the "end" of the wall inbetween the two peices.

That would only occur with certain values (apparently my default ones ^^). It just means the pathing map doesn't fully cover the area as it should. I'll check it out later when I get back from a class.

Ahh it occurred to me how to do this really fast. The disjoint set stuff lets you tell whether or not to break a wall in amortized O(1) time. The really stupid thing I was doing was randomly visiting the walls, which takes.. I don't know.. a long time when you have only a couple breakable walls in a maze of thousands. But since you never need to visit the same wall twice, you can just make a list of all the walls, randomize the order, then go through them one by one. This you can do in O(N) by randomly picking an element from 1 to n to swap with the nth, then 1 to n - 2 with n-1th, etc. So the whole thing takes just O(N cells). If you use a separate array for vertical and horizontal walls you can still generate the same enormous mazes very quickly.

How come the maze only has 2 openings if u press 'esc' over and over?

It generates a brand new maze each time.

Does this maze offer options to add monsters and A certain ammount of levels to get to? Or an option ot have increasingly difficult monsters as you progress and treasure chests? Because I dont understand how it would be possible to trigger in stuff if your not familiar with jass.