koobas.hobune.stream
Uhhhh... 2D Maze Generator Help!
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!
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:
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" :) 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:
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" :) 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.
Thanks for your well thought out post. $$anonymous$$y most Gracious thanks, $$anonymous$$ileSplit P.S. Like the SC2 avatar!
Please refer to it as 'UnityScript', because it is not exactly Javascript. I just got done with doing something akin to this here:
http://answers.unity3d.com/questions/374735/grid-creation-from-center.html
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?
Ok, thanks for the reply I made different prefabs IN UNITY that were a plane and cubes for walls. To make a straight path made a plane and divided it up into 9 parts (3 by 3) then put a cube (/) and did not put a cube (O). What i meant by handle was that i hope that when the code is done it will spawn a grid of these pre defined "planes and cubes" and each plane and cubes will be assigned an array. the first is [0,0] one up it will be [0,1] one to the right would be [1,0]. Now im new to unity script and is used to a different language that uses arrays also and i assumed they were similer, thats what i ment by "handle"
So you could just make a boolean array ( var myBoolArray : boolean[,]; ) that is 3x3, and have a cure be spawned in the positions that are true, and have one not spawn in the positions that are false.
Read more here:
http://docs.unity3d.com/Documentation/ScriptReference/Object.Instantiate.html
http://forum.unity3d.com/threads/34015-Newbie-guide-to-Unity-Javascript-(long)
I don't think his question is how to implement one platform, but to generate a random maze where the platforms are placed dinamically and in a way that they can be traversed.
In which case I wouldn't care about the construction of one platform in code, just create all the possible prefabs for platforms. I sort of have a solution in my had, I can try to solve it a little later.
z_murc is 100% right! Sorry if i couldn't explain it as well. I searched the web and couldn't find anything! Could someone help me out? thanks!!!
Ok, i got a basic part of my code, // var path : Transform[,]; var pathType : Transform; var zSpawnCord : int; var xSpawnCord : int;
//Spawn Path function Update(){ if(xSpawnCord<101){ Instantiate(pathType,Vector3(xSpawnCord,0,zSpawnCord), Quaternion.identity);
//Check on adding x
if(zSpawnCord==100){
//Add 1 to X
xSpawnCord = (xSpawnCord + 10);
zSpawnCord = 0;
}
else{
zSpawnCord = (zSpawnCord + 10);
}
}
} This only makes one type of platform but its a start!!! Sry for the code bug :( O$$anonymous$$, so my question is, how can i "number" each one of the "Tiles"? $$anonymous$$aybe with arrays?
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 :P
Best of luck!
