Why when creating a grid for example 10x10 and drawing a random path the path is sometimes diagonal sometimes crossover the path and sometimes curved?

Question

using UnityEngine;

public class RandomPathGenerator : MonoBehaviour
{
    public int gridSize = 10;
    public int minPathLength = 5;
    public int maxPathLength = 10;
    public float squareSize = 1f;
    public Color pathColor = Color.red;
    public Color startColor = Color.green;
    public Color endColor = Color.blue;
    public float startEndRadius = 0.4f;

    private Vector2Int[] directions = { Vector2Int.up, Vector2Int.down, Vector2Int.left, Vector2Int.right };

    private Vector2Int startPoint;
    private Vector2Int endPoint;
    private Vector2Int[] path;

    private void OnGUI()
    {
        if (GUI.Button(new Rect(10, 10, 100, 30), "Generate Path"))
        {
            GenerateRandomPath();
        }
    }

    private void GenerateRandomPath()
    {
        ClearGrid();

        startPoint = GetRandomPointOnEdge();
        endPoint = GetRandomPointOnDifferentSide(startPoint);

        int pathLength = Random.Range(minPathLength, maxPathLength);
        path = new Vector2Int[pathLength];
        path[0] = startPoint;
        path[pathLength - 1] = endPoint;

        for (int i = 1; i < pathLength - 1; i++)
        {
            path[i] = GetRandomValidNeighbor(path[i - 1]);
        }
    }

    private Vector2Int GetRandomPointOnEdge()
    {
        int side = Random.Range(0, 4); // 0: Top, 1: Right, 2: Bottom, 3: Left

        int x, y;

        switch (side)
        {
            case 0: // Top edge
                x = Random.Range(0, gridSize);
                y = gridSize - 1;
                break;
            case 1: // Right edge
                x = gridSize - 1;
                y = Random.Range(0, gridSize);
                break;
            case 2: // Bottom edge
                x = Random.Range(0, gridSize);
                y = 0;
                break;
            case 3: // Left edge
                x = 0;
                y = Random.Range(0, gridSize);
                break;
            default:
                x = 0;
                y = 0;
                break;
        }

        return new Vector2Int(x, y);
    }

    private Vector2Int GetRandomPointOnDifferentSide(Vector2Int point)
    {
        int side = Random.Range(0, 3); // 0: Top, 1: Right, 2: Bottom

        int x, y;

        switch (side)
        {
            case 0: // Top edge
                x = Random.Range(0, gridSize);
                y = gridSize - 1;
                break;
            case 1: // Right edge
                x = gridSize - 1;
                y = Random.Range(0, gridSize);
                break;
            case 2: // Bottom edge
                x = Random.Range(0, gridSize);
                y = 0;
                break;
            default:
                x = 0;
                y = 0;
                break;
        }

        if (side % 2 == 0) // Top or Bottom side
        {
            if (point.x == x)
            {
                x = (x + 1) % gridSize;
            }
        }
        else // Right side
        {
            if (point.y == y)
            {
                y = (y + 1) % gridSize;
            }
        }

        return new Vector2Int(x, y);
    }

    private Vector2Int GetRandomValidNeighbor(Vector2Int point)
    {
        Vector2Int neighbor;

        do
        {
            neighbor = point + directions[Random.Range(0, 4)];
        }
        while (!IsValidPoint(neighbor) || IsPointOnPath(neighbor));

        return neighbor;
    }

    private bool IsValidPoint(Vector2Int point)
    {
        return point.x >= 0 && point.x < gridSize && point.y >= 0 && point.y < gridSize;
    }

    private bool IsPointOnPath(Vector2Int point)
    {
        for (int i = 0; i < path.Length; i++)
        {
            if (path[i] == point)
            {
                return true;
            }
        }
        return false;
    }

    private void OnDrawGizmos()
    {
        DrawGrid();
        DrawPath();
        DrawStartAndEndPoints();
    }

    private void DrawGrid()
    {
        Gizmos.color = Color.white;

        for (int x = 0; x < gridSize; x++)
        {
            for (int y = 0; y < gridSize; y++)
            {
                Vector3 squarePos = new Vector3(x * squareSize, y * squareSize, 0f);
                Gizmos.DrawLine(squarePos, squarePos + new Vector3(squareSize, 0f, 0f));
                Gizmos.DrawLine(squarePos, squarePos + new Vector3(0f, squareSize, 0f));
            }
        }

        Gizmos.DrawLine(new Vector3(gridSize * squareSize, 0f, 0f), new Vector3(gridSize * squareSize, gridSize * squareSize, 0f));
        Gizmos.DrawLine(new Vector3(0f, gridSize * squareSize, 0f), new Vector3(gridSize * squareSize, gridSize * squareSize, 0f));
    }

    private void DrawPath()
    {
        if (path == null)
            return;

        Gizmos.color = pathColor;

        for (int i = 0; i < path.Length - 1; i++)
        {
            Vector3 center1 = new Vector3(path[i].x * squareSize + squareSize * 0.5f, path[i].y * squareSize + squareSize * 0.5f, 0f);
            Vector3 center2 = new Vector3(path[i + 1].x * squareSize + squareSize * 0.5f, path[i + 1].y * squareSize + squareSize * 0.5f, 0f);

            Gizmos.DrawLine(center1, center2);
        }
    }

    private void DrawStartAndEndPoints()
    {
        if (startPoint == null || endPoint == null)
            return;

        Vector3 startPointPos = new Vector3(startPoint.x * squareSize + squareSize * 0.5f, startPoint.y * squareSize + squareSize * 0.5f, 0f);
        Vector3 endPointPos = new Vector3(endPoint.x * squareSize + squareSize * 0.5f, endPoint.y * squareSize + squareSize * 0.5f, 0f);

        Gizmos.color = startColor;
        Gizmos.DrawWireSphere(startPointPos, startEndRadius);

        Gizmos.color = endColor;
        Gizmos.DrawWireSphere(endPointPos, startEndRadius);
    }

    private void ClearGrid()
    {
        startPoint = Vector2Int.zero;
        endPoint = Vector2Int.zero;
        path = null;
    }
}

The result when clicking the button:

the red drawn path is diagonal on the left image. in the middle image the path is diagonal and also cross over the path itself and also the start and end points on the same side of the grid. on the right another example.

what I want to make is that the start/end point will never be the same on the same side of the grid. the random path must be up,down,left,right directions not diagonal and never cross over itself.

Answer 1

Well the diagonal and cross over are both due to the very same simple reason:

• You already have set the last position path[pathLength - 1]

• You generate random points path[1] to path[pathLength - 2]

  According to your two rules

  • Next point is a direct neighbor of current
  • Next point is not already contained in path

But what if the last generated random point (path[pathLength - 2]) is not a direct neighbor of the endpoint (path[pathLength - 1])? ;)

=> It connects to the endpoint no matter what resulting in a diagonal and eventually path crossing line

---

So

• first of all you would need to make sure that your endpoint is even reachable at all from your startpoint within and with exactly pathLength - 1 steps
• then you would need to make sure that each random chosen point between those is also always exactly pathLength - 1 - currentIndex steps away from endpoint
• finally you would need to ensure that you only chose a point so that it has at least a next neighbor that also can fulfill that rule in order to not reach a dead end (so basically bubbling recursively down through the neighbors and their respective neighbors etc to check if a field is even valid as point in the path)