- Home /
Want to Improve the procedural generation of walls in my game so they cannot cut off a portion of the map? How can I best do this?
,I'm making a game similar to Tank Trouble which has a procedurally generated map. The map is essentially a square of random size from a to b with procedurally generated walls. The procedural generation uses two loops (one for vertical and one for horizontal) to generate walls and they have a 1/4 chance at each possible position.
However, I want to add optimizations so the players can't spawn in a box and such. I made a script that tests if a wall completes a square on the map and will not spawn it if so.
This is still not perfect and I know another feature I want to add is detection for walls connecting two of the borders. If any number of walls in any certain path were to connect two borders together, that would cause a portion of the map to be cut off and if one of the players spawns there they would be stuck. Does anyone have any ideas on how this could be done?
The walls have box colliders and are all children of one game object for simplicity (don't know if that affects anything)
Answer by toddisarockstar · Apr 18, 2020 at 03:28 AM
you should defiantly mark your walls in a 2d grid.
even a simply 2d array of bool would give you much more flexability. then there are plenty of algos you can use to do great stuff. it doesn't have anything to do with colliders or the physics engine... it's just math.
the simpliest way to solve you dilemia is a simple flood fill algo. just like what a paint program uses when you click the paint bucket. this will find all the available squares to a position in your level.
in your case a flood fill algo will tell you how many level boundary are accessible to a given point. and can even tell you if two specific points are accessible to each other.
so first of all, i would make a two array that matches the size of your level. hopefully your object positions are all positive whole numbers. then as you spawn your walls, you mark the corresponding 2d index in the 2d grid of variables.
now you can run the algo.......... the algo requires its own separate grid to ensure that squares are not checked twice. and it also need a list of squares to check.
so you start with adding the first position to the list. then you run the algo till the list is empty.
the algo starts with the first index on the list. then adds everything around it that is not a wall to the list, removes the first position on the list, then marks it as "used" on it's grid so it cant be added to the list again.
this results in paging through every coordinate in your level that can be accessed by a point.
here is a working example of the math what i'm talking about. it makes a grid, marks random spots, it build some walls accordingly, then plots accessible squares from a given point. so you can see the also im talking about. using UnityEngine; using System.Collections; using System.Collections.Generic;
public class deleteme : MonoBehaviour {
//this is grid for marking wall
public bool[,] grid;
public bool[] limits = new bool[4];
//these are movent coordinates for algo
Vector2[] cross = new Vector2[]{
new Vector2(0,1),
new Vector2(1,0),
new Vector2(-1,0),
new Vector2(0,-1)};
void Start () {
int x, y;
grid = new bool[10, 10];
// mark some random walls
x = 10; while (x>0){x--;
y = 10; while (y>0){y--;
if(Random.Range(0,100)<40){grid[x,y]=true;}
}}
// build walls according to grid
x = 10;while(x>0){x--;
y = 10;while(y>0){y--;
GameObject g = GameObject.CreatePrimitive(PrimitiveType.Cube);
g.transform.position = new Vector3(x,0,y);
if(grid[x,y]){g.transform.position = new Vector3(x,1,y);}}}
floodfill (1,1);
x = limits.Length;
y = 0;
while(x>0){x--;
if(limits[x]){y++;}
}
string s = "sucks";
if(y>2){s = "is good";}
print ("player can see " + y + " boundrys so i think this level " + s);
}
void floodfill (int x, int y){
GameObject g = GameObject.CreatePrimitive (PrimitiveType.Cylinder);
g.transform.localScale = new Vector3 (.2f, 10, .2f);
g.transform.position = new Vector3 (x, 1, y);
limits = new bool[4];
if (grid [x, y]) {
print ("you tryed to started me on a wall");
}else{
List<Vector2> next = new List<Vector2> ();
bool[,] check = new bool[10, 10];
next.Add(new Vector2(x,y));
while (next.Count>0) {
x = (int)next[0].x; y = (int)next[0].y;
int i = cross.Length;
while(i>0){i--;
bool outofbounds = false;
Vector3 v = new Vector3(x+cross[i].x,y+cross[i].y);
if(v.x<0){outofbounds = true; limits[0]=true;}
if(v.x>10-1){outofbounds= true; limits[1]=true;;}
if(v.y<0){outofbounds = true; limits[2]=true;}
if(v.y>10-1){outofbounds = true; limits[3]=true;}
if(!outofbounds){
if(check[(int)v.x,(int)v.y] == false){
check[(int)v.x,(int)v.y] = true;
// chere here if looking for specific spot
if(grid[(int)v.x,(int)v.y]==false){
g = GameObject.CreatePrimitive(PrimitiveType.Sphere);
g.transform.position = new Vector3(v.x,1,v.y);
next.Add(v);}
}}}
next.RemoveAt(0);
}}}
}
Thanks so much for your in depth answer. I have never heard of any flood fill algorithms but will definitely look into the subject. Also using the 2D bool array is a good suggestion. I thought about doing that before but it would be a bit more complicated because the walls are either positioned at x + 0.5 or y + 0.5 depending it they are vertical or horizontal but I will definitely try to go that route.
Your answer
![](https://koobas.hobune.stream/wayback/20220612231627im_/https://answers.unity.com/themes/thub/images/avi.jpg)