4
\$\begingroup\$

I need an algorithm to split a grid into randomly generated paths where:

  • A path is a list of cells connected at most to two adjacent cells.
  • Paths have a minimum and maximum length.
  • All cells in the grid belong to a path.
  • Grid might have gaps.

The algorithm must be random, with no artificial bias. With this I mean:

  • There should be no bias for path positions/trajectories (e.g. wrong if a path always starts at (0, 0), paths always starting adjacent to other path path ends, etc.)
  • There should be no bias for path lengths. E.g. algorithm must not favor a short length if a longer path would fit.
  • Natural bias due to grid state (even intermediate states) is fine (unavoidable?).

Input is width, height, number of gaps.

Example of finished grid:

1--1  0  4--4
|     |  |
1--1  0  4--4
   |  |     |
2  1  0  4--4
|     |
2  0--0  3--3
|           |
2--2  3--3--3

Example of grid with gaps:

0--0--0  2--2
      |     |
.  1  0  .  2
   |  |     |
1--1  0  2--2
|
1  .  3  3--3
|     |     |
1--1  3--3--3
\$\endgroup\$
  • \$\begingroup\$ Does it matter if a path sometimes forms a closed loop? Or should it always be a curve bracketed by two dead ends? \$\endgroup\$ – DMGregory Oct 5 '17 at 11:35
  • \$\begingroup\$ Your rules contradict. If paths have minimum and maximum lengths, the whole grid needs to be used, and there should be no bias towards path length, there are a good number of configurable cases where not all those conditions can be met (such as small grids with high minimum path lengths, in which case longer paths will always be favored) \$\endgroup\$ – Weckar E. Oct 5 '17 at 11:55
  • \$\begingroup\$ Out of curiosity, though, what is the input exactly? What parts of these are user-configurable? Are the empty spaces pre-set? \$\endgroup\$ – Weckar E. Oct 5 '17 at 11:57
  • \$\begingroup\$ @DMGregory it actually doesn't matter. You can undo a loop by removing a connection. \$\endgroup\$ – kaoD Oct 5 '17 at 12:07
  • \$\begingroup\$ @WeckarE grid size and gaps are the inputs. \$\endgroup\$ – kaoD Oct 5 '17 at 12:08
2
\$\begingroup\$

I would suggest you look into tunnelling algorithms, which are used to generate random mazes.

The very basic algorithm is similar to a recursive back-tracker algorithm:

currentCell = startCell

do {
    tempcell=currentCell
    for each direction (up/down/left/right) do {

        if tempCell+direction is valid(inside maze, not already tunnelled) {
            currentCell = tempCell+direction
            currentCell.previous = tempCell
            end loop
        }
    }
    if(tempCell== currentCell) {// no new path selected. backtrack
        currentCell = currentCell.previous
    }
} while (currentCell != startCell)

You can modify this algorithm to have some custom additional constraints, such as making sure that there is not another tunnelled cell within X cells, which would create gaps.

This is a very rough way to do it. There is a ton of online material about it, which I suggest you read.

\$\endgroup\$
  • \$\begingroup\$ I don't see how this solves the problem. Can you elaborate please? \$\endgroup\$ – kaoD Oct 6 '17 at 14:59
  • \$\begingroup\$ It's not a full solution. It's a basic tunnelling algorithm that you can use, with some modification, to solve your problem. It's a starting point for procedural maze generation. \$\endgroup\$ – Ian Young Oct 6 '17 at 15:10
2
\$\begingroup\$

This question may be a better fit for the comp sci SE or the math SE as it leans on some non-trivial theoretical CS / combinatorics. If you need truly unbiased behavior, you'll probably need to ask over there. That being said, I suspect that may not be what you want though. for instance, as stated, your problem description would allow things like a 4x5 area divided into 20 paths of size 1, or a 4x5 area with 19 gap tiles.

The solution presented here does not provided that level of unbiased behavior. Here's the overview of a solution:

  • Select your gap tiles.
  • Build a spanning tree of the remaining area(s). Since the gaps are random & it's possible that they might partition the initial area into two disjoint regions.
  • For each spanning tree, examine every intersection & modify the connectivity such that it connects at most two adjacent cells.
  • Finally, examine each resulting path & consider splitting it as needed. As an extreme example, it's possible that your initial spanning tree has no branches (that is, it's a long serpentine path that fills the whole area); if that's undesirable, use some max length & subdivide the paths such that no region exceeds your threshold. Ensuring a minimum path length is not entirely possible with this approach; I suspect adding such a constraint results in a much harder problem that scales very poorly.

Here's an example, where * indicates a cell & . indicates a gap. Randomly pick some gaps:

*  *  *  *  *

*  .  *  .  *

*  *  *  *  *

*  *  *  .  *

Next, build a spanning tree. The only two ways to produce unbiased spanning trees (& by extension, unbiased mazes) are Wilson's algorithm or the Aldous-Broder algorithm (or a cross-over version that starts with one & switches to the other in an attempt to speed it up). If you don't need truly unbiased techniques, Kruskal's algorithm is pretty good & much faster. Jamis Buck's Mazes for Programmers is a great resource that covers the biases of numerous maze algorithms.


To address the minimum length constraint raised via comments: Favoring longer paths is a bias. In that case you, you should try either the recursive backtracker (RB) algorithm or the hunt-and-kill (H&K) algorithm for building your spanning trees. Truly unbiased algorithms have ~30% dead ends & ~22% dead ends. In contrast, the RB & H&K algorithms are have ~10% dead ends & intersections. That should correlate to longer paths. On average RB gives tends to have a longest path that's approximately double that of the longest path from H&K, thus RB biases 1 long path & many shorter paths whereas H&K biases towards more average length paths. Try both, run some tests & see if one work better. If you like both, use both & pick between them at run time, either randomly or based on the output. Also, the biases & %'s reported are for grids without gaps - I anticipate similar results with gaps, but the results may vary.


To continue, here's a possible spanning tree with the intersections labelled for later use:

*--*  *--*--*
|           |
*  .  *  .  *
|     |     |
*--A--B--*--C
   |  |     |
*--*  *  .  *

Next break the intersections. There are a couple of different ways to do this, each with some tradeoffs. Probably the least biased way is to first select the count (1-3 for a 3-way intersection, 2-4 for a 4-way) & then select the directions. Obviously breaking N connections on an N-way intersection will orphan the connecting node to a path of size 1. Alternatively, you could lower the max, thus ensuring that the connecting node attaches to at least one other node. This can still orphan other nodes, but that can sometimes be fixed as a post processing step if desired.

Starting with A, there are connections going Left Right & Down. Randomly select how many to break (1 or 2) & then randomly select that many. Let's say we break L & D, the result is now:

*--*  *--*--*
|           |
*  .  *  .  *
|     |     |
*  *--B--*--C
      |     |
*--*  *  .  *

At B, I'll break U & D. At C I'll break L, resulting in:

*--*  W--*--*
|           |
*  .  Y  .  *
|           |
*  *--*--*  *
            |
*--X  Z  .  *

Note that Y & Z are orphaned. In this case, it's possible to join them to W & X respectively, but in general you cannot guarantee you'll have such options. You could attempt to find a different spanning tree, but that may not help as it's possible that some nodes may start as orphans:

*  .  *  *  *

.  .  *  .  *

*  *  *  *  *                

Ultimately, it depends on what you're making. For most games, any reasonably balanced (even if subtly biased) solution is probably going to be good enough. If not, request migration to the comp sci SE or the math SE.

\$\endgroup\$
  • \$\begingroup\$ Unfortunately the minimum length constraint is very important. The grid paths will form words, and having any short words in the game board would make it unfun. I have been trying to brute force splitting the intersections and discarding those who produce paths below minimum length, but it does indeed scale very poorly. \$\endgroup\$ – kaoD Oct 6 '17 at 14:58
  • 1
    \$\begingroup\$ You should probably edit your problem statement then as that's a significant constraint. \$\endgroup\$ – Pikalek Oct 6 '17 at 20:08
  • 1
    \$\begingroup\$ I've updated my answer to include options that bias the spanning tree in an attempt to avoid overly short paths. \$\endgroup\$ – Pikalek Oct 7 '17 at 15:15

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.