Infinite loop for each procedurally generated level (C# Unity3D)

Question

I'm trying to procedurally generate a constant number of buildings at random positions in my Unity project. However, I get an infinite loop.

This is my code (C#):

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class GenerateMap : MonoBehaviour {

public GameObject plane;

public LayerMask unwalkableMask;
Node[,] Map;
public Vector2 gridWorldSize;

GameObject thisBuilding;

public float nodeRadius;
float nodeDiameter;
int gridSizeX, gridSizeY;

int scale;
public int numBuildings = 5;
public int numPrefabs;
public List<Vector3> positions = new List<Vector3> ();
public List<GameObject> buildingPrefabs = new List<GameObject>();



void Awake(){
    plane = GameObject.CreatePrimitive(PrimitiveType.Plane);
    scale = 15; // scaling the plane gives an 5*scale x 5*scale (x-axis x z-axis) plane, set to 50
    plane.transform.localScale = new Vector3 (scale, 1, scale); //scales only in x and z dimensions
}
// Use this for initialization
void Start () {
    //GameObject building1 = Resources.Load("Buildings/building1") as GameObject;
    //GameObject building2 = (GameObject)Resources.Load ("Buildings/building2");
    //GameObject building3 = (GameObject)Resources.Load ("Buildings/building3");

    nodeDiameter = nodeRadius*2;
    gridSizeX = Mathf.RoundToInt(gridWorldSize.x/nodeDiameter);
    gridSizeY = Mathf.RoundToInt(gridWorldSize.y/nodeDiameter);

    Generate();

}

//int i = 0;

void Generate(){

    for(int i =0; i<numBuildings; i++){
        //while(i < numBuildings){

            CreateGrid();
            List<Node> unwalkables = getUnwalkables();
            thisBuilding =(GameObject)InstantiatePrefab(); i++;
            CreateGrid();
            List<Node> unwalkables2 = getUnwalkables(thisBuilding);


                foreach(Node n in unwalkables){

                    //Debug.Log(n.worldPosition);
                    bool breaking = false;
                    foreach(Node m in unwalkables2){
                    if(n.worldPosition==m.worldPosition){
                    Destroy(thisBuilding);
                    i=i-1;
                    Debug.Log("i after fail " + i);
                    breaking = true;
                    break;

                    }
                    if(breaking)
                    break;
                }

            }
    }
}


Object InstantiatePrefab() {
    int number = Random.Range (0, numPrefabs);
    Vector3 position = new Vector3 (Random.Range (-scale*5, scale*5), 0, Random.Range (-scale*5, scale*5)); //random position in the x,z-plane
    positions.Add (position);
    position.y = buildingPrefabs [number].transform.position.y; //make sure they spawn on top of the plane instead of y=0 w.r.t. their pivot point

    Object building;
    if (number != 2) {
        building = Instantiate (buildingPrefabs [number], position, Quaternion.Euler (-90f, 0f, 0f));
    } else {
        building = Instantiate (buildingPrefabs [number], position, Quaternion.identity);
    }
    return building;
}

void CreateGrid(){

    Map = new Node[gridSizeX, gridSizeY];
    Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x/2 - Vector3.forward * gridWorldSize.y/2;

    for(int x=0; x<gridSizeX; x++){
        for(int y=0; y<gridSizeX; y++){
            Vector3 worldPoint = worldBottomLeft + Vector3.right * (x*nodeDiameter + nodeRadius) + Vector3.forward * (y*nodeDiameter+ nodeRadius);
            bool walkable = !(Physics.CheckSphere(worldPoint, nodeRadius, unwalkableMask));
            Map[x,y] = new Node(walkable, worldPoint, x, y);
        }
    }

}


void OnDrawGizmos()
{
    Gizmos.DrawWireCube(transform.position, new Vector3(gridWorldSize.x, 1, gridWorldSize.y));

    if (Map != null)
    {

        foreach (Node n in Map)
        {
            Gizmos.color = (n.walkable)?Color.white:Color.red;

            Gizmos.DrawCube(n.worldPosition, new Vector3(nodeDiameter-.1f, nodeDiameter*0.5f, nodeDiameter-.1f));
                //Vector3.one * (nodeDiameter-.1f));

        }
    }
}

List<Node> getUnwalkables(){
    List<Node> unwalk = new List<Node>();
    foreach(Node n in Map){
        if(!n.walkable)
        unwalk.Add(n);
    }
    return unwalk;
}

List<Node> getUnwalkables(GameObject obj){
    List<Node> unwalk = new List<Node>();


    int borderWidth = 8; //x-dir
    int borderHeight = 7; //z-dir

    float RightBorder = obj.transform.position.x+nodeRadius+borderWidth*nodeDiameter;
    float LeftBorder = obj.transform.position.x-nodeRadius-borderWidth*nodeDiameter;
    float TopBorder = obj.transform.position.z+nodeRadius+borderHeight*nodeDiameter;
    float DownBorder = obj.transform.position.z-nodeRadius-borderHeight*nodeDiameter;

    //Vector3 worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x/2 - Vector3.forward * gridWorldSize.y/2;

    foreach(Node n in Map){

                if(n.worldPosition.x<RightBorder && n.worldPosition.x>LeftBorder 
                    && n.worldPosition.z>DownBorder && n.worldPosition.z<TopBorder)
                unwalk.Add(n);

    }

    return unwalk;
}

}

It seems to go wrong within this method:

void Generate(){

    for(int i =0; i<numBuildings; i++){
        //while(i < numBuildings){

            CreateGrid();
            List<Node> unwalkables = getUnwalkables();
            thisBuilding =(GameObject)InstantiatePrefab(); i++;
            CreateGrid();
            List<Node> unwalkables2 = getUnwalkables(thisBuilding);


                foreach(Node n in unwalkables){

                    //Debug.Log(n.worldPosition);
                    bool breaking = false;
                    foreach(Node m in unwalkables2){
                    if(n.worldPosition==m.worldPosition){
                    Destroy(thisBuilding);
                    i=i-1;
                    Debug.Log("i after fail " + i);
                    breaking = true;
                    break;

                    }
                    if(breaking)
                    break;
                }

            }
    }
}

If I remove the line: i=i-1; I get no infinite loop, but then I will end up having less buildings than intended. This line causes the for loop to repeat one more iteration, so that It will always generate at least 'numBuildings' amount of buildings.

I've added breaking statements inside the 'foreach' loops so that "i" doesn't keep decreasing if the condition appears to be satisfied multiple times. But this doesn't seem to work, and as soon as numBuildings is about 5 or more it will create an infinite loop. When this happens, I cannot exit anymore except by forcing the task to end.

Does anyone know what I'm doing wrongly, or is there perhaps a better solution to always generate a number of buildings?

I'm ready to answer any questions about the code/scene if necessary.

Answer 1

Well here is the thing: Destroy function does not work instantly. As far as I understand your code (I didn't get into all details), in general it does something like this:

1. Create some building
2. Find all buildings that are 'Unwalkable' and destroy them (which you do by testing free area around buildings)
3. Repeat until you have exactly as much buildings as you need

The endless loop happens because Destroy actually does not destroy anything - it simply marks objects for destruction at the end of frame. The problem is that the whole loop is running in single frame, so actual destruction never happens. This way the number of 'Unwalkables' simply keeps growing with each iteration.

There are number of quick ways to fix this and there is a good way to fix this, the choice is up to you.

The quick ways are:

• Use DestroyImmediate: http://docs.unity3d.com/ScriptReference/Object.DestroyImmediate.html. Just make sure you know what you are doing.

• Turn the loop into a coroutine which runs across several frames, this way Destroy will have time to actually run, and you will see your scene generating in real time.

The good way is to think of an alternative implementation of the algorithm. Instead of placing building and then destroying poorly placed building, try to find a spot for the building that is good to begin with, only then place it. It is best to do it this way because even if you overcome the problem with Destroy function, your algorithm still has a logical problem: what if you simply do not have enough space for all the buildings? You have no clue when to stop with your current implementation. You will just keep generating and destroying building in an infinite loop.