Uhhhh... 2D Maze Generator Help!

Questions & Answers
1

So for my map i will have platforms spawn with paths on them. these are made from a 3by3 grid like so…

O O O
O O O
O O O

a straight path would look like…

/ O /
/ O /
/ O /

And so on…
Every “Path” is a 3d prefab.

The dimensions of these paths are 10by10 unity meters (or whatever there called :P)
Im using java script and i decided to use arrays to handle the “grid” of my paths.
So now to my problem,
i started coding and got this far,
#pragma strict

var grid : int[,];
var spawner : Transform;

function Start(){

And then i was like uhhhhhhh… what do i do now?
Im still a noob at coding, could someone please point me in the right direction?
thanks!

4

OK so here comes some thought-process. Not the most optimal, but anyway. Vonni’s answer is good for a start, generate a bunch of stuff randomly and place them too, so they have proper Unity positions, and create the START and END explicitly.

Write a simple function that takes two (neighboring) platforms as arguments, and returns true if the second is reachable from the first, and false if they’re not traversable. This is the same as adjacency in graphs.

bool IsReachable(int from, int to)

where int is the coordinate in the array. There’s probably a better way to reference them tho, for example Vector2’s maybe.
So when you generate the platforms, store them in a 2D array for referencing, because it’s easier to iterate through the neighbors this way.

IsReachable() should be able to find out with the help of the coordinates AND the GameObjects (platforms) they reference, if to is reachable from from. This is probably most easily done if you always cast a ray from the center of your from platform to the direction (left/right/top/bottom) of your to platform, and the length of the ray should be exactly 10, because of the way the platforms are set up. If two platforms are traversable, the platformLength ray cast between their centers should never collide with anything. In the opposing case, they are not traversable. See this so you know what I mean:

[6519-maze1.png|6519]

Of course they must already be placed next to each other if you use this method. Another way to do this phase with the same principle is you create a script component for the prefabs which stores a 3x3 array of bools, and you can check with a simple algorithm if these bools are “traversible” :slight_smile: Yeah this is probably a lot more efficient than casting rays for real, but also means a bit more clever code.

So the next step would be to use an algorithm similar to a graph traversing algorithm, for example breadth-first of depth-first traversal. Now I hope you know something about graphs, but if not, it’s not that bad:

Graph (mathematics)

Graph (abstract data type)

Depth-first search

What you try to do is starting from START, try to get to END with some form of traversal. The best should be for you here is depth-first search, and you can also see maze generation as an application of depth-first search in the link I provided! You might be better off reading stuff there, than with my “solution” :slight_smile:
There’s even some fairly short code there that generates a maze, but that may be a different setup from yours, nevertheless you should read stuff because this problem is not so simple.

Anyway, if you can’t reach the END of the maze, you can randomly (OR not randomly but cleverly) change some of the platforms, and try again. And basically repeat this until you can actually reach END, then you’re done, and you can enable the prefabs. I know I know, this algorithm is not guaranteed to end, so you may need some heuristic… I’d count how many times have I traversed a platform during the algorithm, and if it’s say higher than 5, I will not change it anymore.

Comments are welcome, since I just made this up.

2

Please refer to it as ‘UnityScript’, because it is not exactly Javascript.
I just got done with doing something akin to this here:

Well, if you want a 3x3 grid, I assume you would require a 2D array, with the first set of arrays being the number of rows, and the second set being the number of columns.

Do you just want a straight line? To me, it looks like ‘0’ and ‘/’ can be replaced with ‘true’ and ‘false’.

Also, could you give some more detail or context? I can’t quite tell what you mean by ‘handle’.

Do you want to set them in the inspector?
Do you want to spawn them randomly?

3

This is just a draft, but should be enough to get you started:

var mazePlatforms : Transform[]; // Your platform Prefabs
function Start(){
	for(var y : int = 0; y < rowLength; y++){
		for(var x : int = 0; x < columbLength; x++){
			Instantiate(mazePlatforms[Random.Range(0,mazePlatforms.Length],Vector3(x*10,y*10,0),Quaternion.identity); 
		}
	}
}

You would probably want a START and an END. And this random spawning of platforms would most likely create an impassible maze. So you would need some more code here :stuck_out_tongue:

Best of luck!