C++ How to generate a random Path

Question

I'm trying to write a function that can generate a random path for a given 2D array of points (x, y).

Now the path has a few requirements I'd like it to meet in order for it to be valid. The path cannot:

• ...be a straight line from point A to B.
• ...go back on itself but can go backwards (demonstrated below).
• ...run parallel/along itself.

I also want to make sure the path starts from the left and ends on the right to hopefully keep it simple.

So I'm looking for something that would do:

.........     | .........     | ########.
.........     | .........     | .......#.
##....### end | ....####.     | ...#####.
.######..     | #####..#.     | ...#.....
.........     | .......## end | ...###### end

But I don't know where to start and there's vary little information available that does something similar to this.

I could go the A* rout but that seems overkill and from what I know about A* (vary little) I'd need to create "fake" obstacles. Anyway before I go on a rant, can anyone help me?

Any suggestions is greatly appreciated! Thank you.

Answer 1

You can just try things one square at a time until you find a solution:

• do
  • create an array e.g. bool points[Num_Rows][Num_Columns] = { false };, tracking where you've been
  • initialise std::pair<int,int> cursor { rand() % Num_Rows, 0 };, tracking where you are repeat
    • work out which directions your cursor can move in without leaving the board or breaking your rules
    • if there are none, you're bust: go back to "do" above
    • pick one, recording that you've moved there by setting the related points[] element
      • if you're cursor's in the right-hand column, you're done, break from the loop

Answer 2

The following description and code snippet should give you enough information to solve the problem without providing an exact solution. Note: the following does not satisfy all of your criteria (e.g., preventing a straight line solution) but any missing pieces should be easy to fill in.

---

1. Create the grid
2. Generate random starting cell
3. Generate random ending cell that is different than the starting cell
4. Walk from the starting cell to the ending cell
   1. Mark each position as being 'visited'
   2. Determine the valid moves from this position
      1. At least 1 valid move: add this position position to the 'solution path' and update this position to be one of the valid moves
      2. No valid moves: update this position to be the position most recently added to the solution path (i.e., backup) and remove the position most recently added to the solution path
         • Note if the 'solution path' is empty restart again at step 4
5. Reset the grid back to its original state
6. Traverse the solution path and mark each cell as 'visited'
7. Print grid

---

// Step 1
Grid grid(10, 10);

// Step 2
Cell start = grid.generateRandomCell();

// Step 3
Cell end = start;
while (end == start)
{
    end = grid.generateRandomCell();
}

std::vector<Cell> solutionPath;

// Step 4
Cell pos = start;
while (pos != end)
{
    // Step 4.1
    grid.setValue(pos, '#');

    // Step 4.2
    std::vector<Cell> possibleMoves = getPossibleMoves(grid, pos);
    if (!possibleMoves.empty())
    {
        // Step 4.2.1
        solutionPath.push_back(pos);
        pos = possibleMoves[rand() % possibleMoves.size()];
    }
    else
    {
        // Step 4.2.2
        if (!solutionPath.empty())
        {
            pos = solutionPath.back();
            solutionPath.erase(--solutionPath.end());
        }
        else
        {
            pos = start;
            grid.reset();
        }
    }
}

// Step 5
grid.reset();

// Step 6
for (size_t i = 1; i < solutionPath.size(); ++i)
{
    grid.setValue(solutionPath[i], 'A' + ((i - 1) % 26));
}
grid.setValue(start, '@');
grid.setValue(end, '!');

// Step 7
std::cout << grid << "\n";