Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The most straightforward way to create such a level is to find a way to solve it. This way, you can basically generate any random starting configuration and determine if it is a valid level by trying to have it solved. This will generate the most diverse levels.</p> <p>And even if you find a way to generate the levels some other way, you'll still want to apply this solving algorithm to prove that the generated level is any good ;)</p> <h3>Brute-force enumerating</h3> <p>If the board has a size of NxN cells, and there are also N colours available, brute-force enumerating all possible configurations (regardless of wether they form actual paths between start and end nodes) would take:</p> <ul> <li>N^2 cells total</li> <li>2N cells already occupied with start and end nodes</li> <li>N^2 - 2N cells for which the color has yet to be determined</li> <li>N colours available.</li> <li>N^(N^2 - 2N) possible combinations.</li> </ul> <p>So,</p> <ul> <li>For N=5, this means 5^15 = 30517578125 combinations.</li> <li>For N=6, this means 6^24 = 4738381338321616896 combinations.</li> </ul> <p>In other words, the number of possible combinations is pretty high to start with, but also grows ridiculously fast once you start making the board larger. </p> <h3>Constraining the number of cells per color</h3> <p>Obviously, we should try to reduce the number of configurations as much as possible. One way of doing that is to consider the minimum distance ("dMin") between each color's start and end cell - we know that there should at least be this much cells with that color. Calculating the minimum distance can be done with a simple flood fill or Dijkstra's algorithm. (N.B. Note that this entire next section only discusses the <em>number</em> of cells, but does not say anything about their <em>locations</em>)</p> <p>In your example, this means (not counting the start and end cells)</p> <pre><code>dMin(orange) = 1 dMin(red) = 1 dMin(green) = 5 dMin(yellow) = 3 dMin(blue) = 5 </code></pre> <p>This means that, of the 15 cells for which the color has yet to be determined, there have to be at least 1 orange, 1 red, 5 green, 3 yellow and 5 blue cells, also making a total of 15 cells. For this particular example this means that connecting each color's start and end cell by (one of) the shortest paths fills the entire board - i.e. after filling the board with the shortest paths no uncoloured cells remain. (This should be considered "luck", not every starting configuration of the board will cause this to happen).</p> <p>Usually, after this step, we have a number of cells that can be freely coloured, let's call this number U. For N=5, </p> <pre><code>U = 15 - (dMin(orange) + dMin(red) + dMin(green) + dMin(yellow) + dMin(blue)) </code></pre> <p>Because these cells can take any colour, we can also determine the maximum number of cells that can have a particular colour:</p> <pre><code>dMax(orange) = dMin(orange) + U dMax(red) = dMin(red) + U dMax(green) = dMin(green) + U dMax(yellow) = dMin(yellow) + U dMax(blue) = dMin(blue) + U </code></pre> <p>(In this particular example, U=0, so the minimum number of cells per colour is also the maximum).</p> <h3>Path-finding using the distance constraints</h3> <p>If we were to brute force enumerate all possible combinations using these color constraints, we would have a lot less combinations to worry about. More specifically, in this particular example we would have:</p> <pre><code> 15! / (1! * 1! * 5! * 3! * 5!) = 1307674368000 / 86400 = 15135120 combinations left, about a factor 2000 less. </code></pre> <p>However, this still doesn't give us the actual paths. so a better idea would be to a backtracking search, where we process each colour in turn and attempt to find all paths that:</p> <ul> <li>doesn't cross an already coloured cell</li> <li>Is not shorter than dMin(colour) and not longer than dMax(colour).</li> </ul> <p>The second criteria will reduce the number of paths reported per colour, which causes the total number of paths to be tried to be greatly reduced (due to the combinatorial effect).</p> <p>In pseudo-code:</p> <pre><code>function SolveLevel(initialBoard of size NxN) { foreach(colour on initialBoard) { Find startCell(colour) and endCell(colour) minDistance(colour) = Length(ShortestPath(initialBoard, startCell(colour), endCell(colour))) } //Determine the number of uncoloured cells remaining after all shortest paths have been applied. U = N^(N^2 - 2N) - (Sum of all minDistances) firstColour = GetFirstColour(initialBoard) ExplorePathsForColour( initialBoard, firstColour, startCell(firstColour), endCell(firstColour), minDistance(firstColour), U) } } function ExplorePathsForColour(board, colour, startCell, endCell, minDistance, nrOfUncolouredCells) { maxDistance = minDistance + nrOfUncolouredCells paths = FindAllPaths(board, colour, startCell, endCell, minDistance, maxDistance) foreach(path in paths) { //Render all cells in 'path' on a copy of the board boardCopy = Copy(board) boardCopy = ApplyPath(boardCopy, path) uRemaining = nrOfUncolouredCells - (Length(path) - minDistance) //Recursively explore all paths for the next colour. nextColour = NextColour(board, colour) if(nextColour exists) { ExplorePathsForColour( boardCopy, nextColour, startCell(nextColour), endCell(nextColour), minDistance(nextColour), uRemaining) } else { //No more colours remaining to draw if(uRemaining == 0) { //No more uncoloured cells remaining Report boardCopy as a result } } } } </code></pre> <h3>FindAllPaths</h3> <p>This only leaves FindAllPaths(board, colour, startCell, endCell, minDistance, maxDistance) to be implemented. The tricky thing here is that we're not searching for the shortest paths, but for <em>any</em> paths that fall in the range determined by minDistance and maxDistance. Hence, we can't just use Dijkstra's or A*, because they will only record the shortest path to each cell, not any possible detours. </p> <p>One way of finding these paths would be to use a multi-dimensional array for the board, where each cell is capable of storing multiple waypoints, and a waypoint is defined as the pair (previous waypoint, distance to origin). The previous waypoint is needed to be able to reconstruct the entire path once we've reached the destination, and the distance to origin prevents us from exceeding the maxDistance.</p> <p>Finding all paths can then be done by using a flood-fill like exploration from the startCell outwards, where for a given cell, each uncoloured or same-as-the-current-color-coloured neigbour is recursively explored (except the ones that form our current path to the origin) until we reach either the endCell or exceed the maxDistance.</p> <p>An improvement on this strategy is that we don't explore from the startCell outwards to the endCell, but that we explore from both the startCell and endCell outwards in parallel, using Floor(maxDistance / 2) and Ceil(maxDistance / 2) as the respective maximum distances. For large values of maxDistance, this should reduce the number of explored cells from 2 * maxDistance^2 to maxDistance^2.</p>
    singulars
    1. This table or related slice is empty.
    1. POWhat to use for flow free-like game random level creation?
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USAstrotrain
    1. USAstrotrain
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload