Generating random Path in 2D Grid in C# (Tower Defense)

Question

im trying to create a 2D TowerDefense Game and i´m stuck with creating a random Path between a random start- and endpoint. These two points are located at the top edge and bottom edge respectively. Currently my code is looking for the direction on the x axis where the end point is. If the path is level with the end point, a straight path is generated to that point. But I want more variety. The path shouldn't just go left or right and then down. For example, I want something like curves, but the path must not collide.

I hope someone can help me with my Code.

Code:

public class MapGenerator : MonoBehaviour

{ public GameObject mapTile;

[SerializeField] private int mapWidth;      //set in the unity environment
[SerializeField] private int mapHeight;     //set in the unity environment

public static List<GameObject> mapTiles = new List<GameObject>();
public static List<GameObject> pathTiles = new List<GameObject>();

public static GameObject startTile;
public static GameObject endTile;

private bool reachedX = false;
private bool reachedY = false;

private GameObject currentTile;
private int currentIndex;
private int nextIndex;

public Color startTileColor;
public Color endTileColor;
public Color mapColor;
public Color pathColor;

private void Start()
{
    generateMap();
}

//selecting all Tiles at the top Edge
private List<GameObject> getTopEdgeTiles()
{
    List<GameObject> edgeTiles = new List<GameObject>();

    for (int i = mapWidth * (mapHeight - 1); i < mapWidth * mapHeight; i++)
    {
        edgeTiles.Add(mapTiles[i]);
    }

    return edgeTiles;
}

//selecting all Tiles at the bottom Edge
private List<GameObject> getBottomEdgeTiles()
{
    List<GameObject> edgeTiles = new List<GameObject>();

    for (int i = 0; i < mapWidth; i++)
    {
        edgeTiles.Add(mapTiles[i]);
    }

    return edgeTiles;
}

//void for moving down
private void moveDown()
{
    pathTiles.Add(currentTile);                     //adding currentTile to PathTile
    currentIndex = mapTiles.IndexOf(currentTile);   //getting current Index of Tile in mapTiles
    nextIndex = currentIndex - mapWidth;            //setting next Index
    currentTile = mapTiles[nextIndex];              //setting next currentTile
}

//void for moving left
private void moveLeft()
{
    pathTiles.Add(currentTile);
    currentIndex = mapTiles.IndexOf(currentTile);
    nextIndex = currentIndex - 1;
    currentTile = mapTiles[nextIndex];
}

//void for moving right
private void moveRight()
{
    pathTiles.Add(currentTile);
    currentIndex = mapTiles.IndexOf(currentTile);
    nextIndex = currentIndex + 1;
    currentTile = mapTiles[nextIndex];
}


private void generateMap()
{
    //setup 2D Map
    for (int y = 0; y < mapHeight; y++)
    {
        for (int x = 0; x < mapWidth; x++)
        {
            GameObject newTile = Instantiate(mapTile);

            mapTiles.Add(newTile);

            newTile.transform.position = new Vector2(x, y);
        }
    }

    List<GameObject> topEdgeTiles = getTopEdgeTiles();
    List<GameObject> bottomEdgeTiles = getBottomEdgeTiles();

    int rand1 = Random.Range(0, mapWidth);
    int rand2 = Random.Range(0, mapWidth);

    startTile = topEdgeTiles[rand1];        //random starting point
    endTile = bottomEdgeTiles[rand2];       //random end point

    currentTile = startTile;

    moveDown();


    //starting the path algorithm
    bool moving = true;

    while (moving)
     {

         if (!reachedX)
         {
             if (currentTile.transform.position.x > endTile.transform.position.x)
             {
                 moveLeft();
             }
             else if (currentTile.transform.position.x < endTile.transform.position.x)
             {
                 moveRight();
             }
             else
             {
                 reachedX = true;
             }
         }
         else if(!reachedY) {
             if (currentTile.transform.position.y > endTile.transform.position.y)
             {
                 moveDown();
             }
             else
             {
                 reachedY = true;
             }
         }
         else if (reachedX && reachedY)
         {
             moving = false;
         }
     }

    pathTiles.Add(endTile);

    //setting colors for each tile
    foreach (GameObject obj in mapTiles)
    {
        obj.GetComponent<SpriteRenderer>().color = mapColor;
    }

    foreach (GameObject obj in pathTiles)
    {
        obj.GetComponent<SpriteRenderer>().color = pathColor;
    }

    startTile.GetComponent<SpriteRenderer>().color = startTileColor;
    endTile.GetComponent<SpriteRenderer>().color = endTileColor;

}

}

This generate something like: current path generation

An I want something like that: my imagination

Thank you and Best Regards!

Answer 1

I actually tried a bunch of different ways of producing random paths. They all worked, but in all cases the vast majority of the paths that were generated were not pleasing -- not enough wiggles or not using most of the available area.

This is a way that I think would work well, but it would be a fair bit of code:

1. Generate about 4 or 5 random points. Make sure you have at least one in each quadrant.
2. Calculate the Voronoi diagram of those points, along with the entrance and exit.
3. Try to find a Hamiltonian path through the diagram from the entrance to the exit. If you can't find one, then just take the longest simple path that you found.
4. In each Voronoi cell, connect the path entry point to the exit point with a smooth curve.

The Hamiltonian path, along with the requirement to have a point in each quadrant, ensures that the path uses the available space well. The number of random points determines how tight the curves are.