Randomly generate directed graph on a grid

Question

I am trying to randomly generate a directed graph for the purpose of making a puzzle game similar to the ice sliding puzzles from Pokemon.
This is essentially what I want to be able to randomly generate: http://bulbanews.bulbagarden.net/wiki/Crunching_the_numbers:_Graph_theory.

I need to be able to limit the size of the graph in an x and y dimension. In the example given in the link, it would be restricted to an 8x4 grid.
The problem I am running into is not randomly generating the graph, but randomly generating a graph, which I can properly map out in a 2d space, since I need something (like a rock) on the opposite side of a node, to make it visually make sense when you stop sliding. The problem with this is that sometimes the rock ends up in the path between two other nodes or possibly on another node itself, which causes the entire graph to become broken.

After discussing the problem with a few people I know, we came to a couple of conclusions that may lead to a solution.

• Including the obstacles in the grid as part of the graph when constructing it.
• Start out with a fully filled grid and just draw a random path and delete out blocks that will make that path work.

The problem then becomes figuring out which ones to delete to avoid introducing an additional, shorter path. We were also thinking a dynamic programming algorithm may be beneficial, though none of us are too skilled with creating dynamic programming algorithms from nothing. Any ideas or references about what this problem is officially called (if it's an official graph problem) would be most helpful.

Here are some examples of what I have accomplished so far by just randomly placing blocks and generating the navigation graph from the chosen start/finish. The idea (as described in the previous link) is you start at the green S and want to get to the green F. You do this by moving up/down/left/right and you continue moving in the direction chosen until you hit a wall. In these pictures, grey is a wall, white is the floor, and the purple line is the minimum length from start to finish, and the black lines and grey dots represented possible paths.

Here are some bad examples of randomly generated graphs:

Here are some good examples of randomly generated (or hand tweaked) graphs:

I've also seemed to notice the more challenging ones when actually playing this as a puzzle are ones which have lots of high degree nodes along the minimum path.

Answer 1

• it's ice, you will move unless you hit a rock.
• the only way to change direction is to hit a rock.
• if you hit a rock you have to change directions.
• cycles are good, for obvious reasons.
• there can be multiple starts, and multiple ends.

more advanced properties:

• the cells without adjacent rocks are not reachable (some can be traversed)
• walls are rocks too, if you remove them, you can decide to wrap around.
• you can use sub-grids as patterns ("tiling" 3x3, 3x4, 5x5, ...etc)
• you can overlay a puzzle MxN tile on top of non-traversable MxN area and add a rock to redirect in/out of it.
• rotation or symmetry of a tile can be interesting
• you can expand a tile by inserting icy rows / columns

example:

S=start, E=end, o=rock, .=ice

3 . 2 o        3 . . 2 o         . . . . . o o
4 . . E   ~=   4 . . . E   ~=    . . . . . 2 E
o . . .        o . . . .         . . . . . . .
S . 1 o        S . . 1 o         S . . . . 1 o

example of combining tiles:

3 . . 2 o       o 2 . . 3      3 . . 2 o 7 . . 6
4 . . . E   +   E . . . 4  =   4 . . . . . . . 5
o . . . .       . . . . o      o . . . . . . . o
S . . 1 o       o 1 . . S      S . . 1 o 8 . . E

you might like the game Tsuro, it uses tiles to generate a random board.

Answer 2

Maybe reverse engineering could help you if you are up for that.

If there is one and only one solution to each problem, you can probably generate a graph based on the unique answer. This won't require you to do dynamic programming or even skip brute force and opt for a methodical generation.

You can go about it by:

1. Keeping a MxN graph ready
2. creating one/multiple solution(s)
3. making a question around it if it is a singular solution problem
4. if there are multiple solutions to the problem, then you can repeat the above procedure in a way so that the current iteration does not inhibit another solution.

Though you will need to device a way according to the problem complexity and problem size that will generate this question for you. Don't just go for brute-force. Try some randomized algorithm instead. This could help you.

Answer 3

How about another approach? Start with an empty maze and add blocks like this:

1. Randomly starting block and ending block.
2. Make 1-3 "sliding" steps in random (but not returning) direction and with random length (*). Place a block after each step (to stop the slide).
3. Find a shortest path to the exit. If there are too few segments (low level difficulty), take a random segment of the path and split it with a block. Otherwise, place a block as in step 1 and exit.
4. Repeat 1 with caution (*): when you choose the length of a sliding step, make it so that the block you put will not close the previous path.

Finishing touch: find the shortest route with the algorithm you provided. Take note of all cells that are used and start filling up the rest randomly, every time making sure the shortest route does not get shorter.

There is a caveat in step two, when you can't put the last block so that it does not cross the used paths, but I see two solutions to this: move the ending block earlier or undo a few steps and try once again.

And another thought for the random length of the sliding steps - you might want to choose it so that a block placed earlier is reused, as long as the paths don't overlap.