Creating random path in grid

Question

I need to find a path with required length in the NxN matrix without loops and deadlocks. For example:

1. We Have a grid 7x7 (49 blocks in total) with START (orange) point.
2. We need to build random path length of 25 cells.
   
   etc

My problem is I don't know how to create the path with required length fast and avoid loops and deadlocks.

Answer 1

Edit: I just noticed you don't have a fixed endpoint to steer towards.

In this case, we can solve this with recursive backtracking:

Path FindPathOfLength(int length, Point startPoint) {
    // Track visited state so we don't touch/cross.
    MarkVisited(startPoint, true);

    foreach(cardinal direction in random order) {
        // Check if there's a path of the desired length in this direction.
        path = Extend(length, startPoint, direction);
        if(path == null)
           continue;

        // Finish & return the path.
        path.Add(startPoint);
        return path;
    }

    // Search failed. No such path exists!
    return null;
}

Path Extend(int remainingLength, Point startPoint, Direction currentDirection) {

    // Proceed in the given direction to find our next point.    
    point = startPoint + currentDirection;

    if(point is out of bounds OR point is already visited)
        return null;

    // Avoid touching/crossing path so far.    
    foreach(neighbour in 2x3 rectangle forward, left, and right of point)
        if(neighbour is within bounds AND already visited)
            return null;

    MarkVisited(point, true);

    // Endpoint! Time to bubble back up.    
    if(remainingLength == 0)
        return new Path(point);

    foreach (turnDirection forward, left, or right of currentDirection, in random order ) {
        // Search for a feasible solution to a smaller sub-problem.
        path = Extend(remainingLength - 1, startPoint, turnDirection);
        if(path == null)
             continue;

        // Extend that path to include this point.    
        path.Add(point);
        return path;
    }

    // No such path through this point panned out. Undo our choice to try it.    
    MarkVisited(point, false);
    return null;
}

---

Or, assuming a fixed endpoint (that's feasible to reach in the desired path length. ie. desiredPathLength - ManhattanDistance(start, end) is even), one way we could do this is using a force-directed graph.

We pick n points with floating point coordinates in our grid to start with, with point 0 being our start and point 1 being our end. Place the rest roughly along a line between these two, with small random displacements (this seeds our randomness)

Now we have our initial constraint of a non-self-intersecting line of points with the desired number of intermediate sites, but it might not yet be a "path" since sequential points might not be in adjacent cells.

Then we loop over the points from i = 1 to i = n - 1; in each iteration:

• We apply an attractive force to pull point I toward the closest of four points: point i - 1's position plus or minus one or the x or y. Then the same, relative to point i + 1.

• We apply a repulsion force to nudge point i away from any other points less than 2 grid cells away.

• Also apply a repulsion force to any points that try to stray outside the bounds of the grid.

• If point i lies in a valid grid cell adjacent to the cells of points i - 1 and i + 1, and has no other points in its cell or adjacent cells, then we call it "satisfied"

Once all points are satisfied, we round their positions to grid cells and we have our final path.