2
\$\begingroup\$

I'm trying to generate a random path on a 2D grid given that:

  • The width and height of the grid are given
  • The length of the path to generate is given
  • The path can't move "back"
  • The path starts from a random point at height 0 and ends at a random point at max height
  • A path segment cannot "touch" with a path segment that is at its height - 1 that is not the latest generated segment of the previous height

This is what two paths generated from the parameters {Width:11, Length:17, PathLength:30} would look like:

generated path example 1 generated path example 2

and this is an example of a path that should not be generated:

Bad example

The result of the algorithm should be a list of value pairs such as this: (8,6) in any order, which indicates the segments of the path. I've been trying to solve this problem for a while, but I have problems understanding how to make this have a given length. If the given length was not a requirement I could just generate it with a nested for cycle and some rules. Please help!

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Just wanted to say, nice work clearly defining your problem and solution criteria. We get a lot of procedural generation questions that are quite vague, but this one is extremely specific, especially the inclusion of both image examples and counter-examples that we can use to evaluate proposed solutions. \$\endgroup\$
    – DMGregory ♦
    Commented Nov 27, 2020 at 13:37
  • 1
    \$\begingroup\$ Thank you. I have also found an elegant solution to this problem, I will post it as soon as I'm confident about the implementation. \$\endgroup\$
    – Oro Portaluri
    Commented Nov 27, 2020 at 19:18
  • \$\begingroup\$ I believe a truly elegant solution could involve taxicab geometry :) I will think on it for fun! en.m.wikipedia.org/wiki/Taxicab_geometry \$\endgroup\$
    – Jon
    Commented Nov 29, 2020 at 8:08
  • \$\begingroup\$ I suggest that explaining what 'The path can't move "back"' would improve the question. Such as 'back' == 'up'. \$\endgroup\$
    – Vorac
    Commented Dec 1, 2020 at 7:44
  • \$\begingroup\$ Did your elegant solution ever pan out? It would be worth giving this old question an accepted answer if you found something that worked for you. \$\endgroup\$
    – DMGregory ♦
    Commented Aug 25, 2021 at 11:41

1 Answer 1

Reset to default
1
\$\begingroup\$

Some pseudo algorithm that can at least give a start.

  1. Since start and endpoint can be random, generate them at the start to make sure we can generate a valid path.
  2. Find out how many side steps the path can take: PathLength - Length - abs((start.x - end.x)). This gives you the shortest path to the goal. If this value is bigger than your pathlength, your end.x needs to be closer to start.x. If this value cannot be divided by 2 - since it is the length of shortest path, for every sidestep we need to go one in the other direction - you need to move goal.x to either +1 or -1.
  3. From 2 you got now the value of how many detour steps you can take. You have now a few options on how you want to generate the path. My approach would be to make a collection of predefined segments you pick from. You can sort them by their amount of sidesteps and just chain them together.
  4. If you have used up all sidesteps but are still missing a pathlength, prolong the connection between segments.

Some elements with sidestep count 3:

0001 0001 1111 0111
0111 0011 1000 1100
1100 0110
     1100
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .