1
\$\begingroup\$

I want to create a random path in a 2d grid given a start point at the bottom row and an end point at the top of the row. I do not want the shortest path, or even the longest. Instead, I want a random path that can go up, down, left and right, but one that does not intersect itself.

I've been researching this question for days and cannot find anything that helps me solve the issue. I've read this questions Simplest way to generate a random path, however, the answer provided does not allow for the path to go backwards.

Some solutions I've thought of

  1. On every row select a random point, then travel to each of these points. This does not allow for moving backwards because I would continue to move up in the rows.
  2. Start the the beginning point, select a random point next, and so on until I reach the goal. This does not work because I can end up trapping myself and reaching a dead end.

How can I achieve this?

Improve this question
\$\endgroup\$
  • 1
    \$\begingroup\$ The reason such algorithms disallow reverse transits when trying to reach a goal position is that most such algorithms are expected to be halting. If you allow reversal, you could end up in a situation where your agent goes up and down over and over forever without every making progress toward the goal. Secondly, are you implying that your path cannot intersect itself? \$\endgroup\$ – Stephan Mar 25 '19 at 21:02
  • \$\begingroup\$ @Stephan, I did forget to mention that the path could not intersect itself, therefore, you could never get stuck in a loop, but a dead end. \$\endgroup\$ – Gary Holiday Mar 25 '19 at 22:07
8
\$\begingroup\$

One common way to solve this type of problem is to still use a shortest path algorithm like A* that takes into account traversal costs. We just lie to it about what's "shortest" ;)

Here we assign our costs for moving into each cell pseudorandomly — effectively making an invisible terrain of hills and valleys, fast roads and slow marshes for the algorithm to navigate. The path will meander to favour the low-cost cells and avoid crossing high-cost barriers, but since these obstacles exist only in the pathfinder, it looks to the player like it turned a corner for no reason.

By using a different seed for each pathfinding query, we can avoid each path settling into the same fast routes, and instead taking completely uncorrelated meanders.

This also lets you finely control the kinds of shapes you get from the paths, by tuning the scale and magnitudes of the pseudorandom cost features — getting big sweeping curves or little fractal zig-zags depending on how you choose to generate this imaginary landscape.

Improve this answer
\$\endgroup\$
  • 1
    \$\begingroup\$ Added bonus is that there is no extra work to take into account actual obstacles. \$\endgroup\$ – Alexis Mar 26 '19 at 8:33
0
\$\begingroup\$

If performance is not an issue, you can just choose a point out of the set of points from which a path to the end exists. Essentially it's like your second option, but after each step you check from which neighbours there's still a path to the end point, and choosing a random point out of the set of valid points.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.