Return to Answer

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 already visited)
        return null;

    // Avoid touching/crossing path so far.    
    if(point + currentDirection is in range 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;
}

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;
}

One way we could do this is using a force-directed graph.

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 already visited)
        return null;

    // Avoid touching/crossing path so far.    
    if(point + currentDirection is in range 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.

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. The rest can be chosen randomly.

This gives us our initial constraint of an exact length of our sequence, but it might not yet be a "path" since sequential points might not be in adjacent cells / the path might cross itself.

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

• We apply a spring force to pull point i toward a distance of 1 unit away from points i - 1 and i + 1.

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

• If point i lies in a 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.

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.