# Randomly generate directed graph on a grid

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: http://i.stack.imgur.com/9uaM6.png

Here are some good examples of randomly generated (or hand tweaked) graphs: i.stack.imgur.com/uUGeL.png (can't post another link, sorry)

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.

-
You could generate a completely random set of rocks, then check if corresponding graph has a solution, and if not, then throw it away and start over. With an 8x4 grid this cannot take that long. I am sure that there are cleaner solutions. –  Job Jan 18 '12 at 4:18
This was my first approach but I need to do it on a slightly larger scale and brute forcing it seemed to take awhile and was trying to find a better approach. –  Talon876 Jan 18 '12 at 6:49

• 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.

• 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.

-

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.

-
I knew I would regret selling back that book last year, I think one of my friends has it somewhere though. Any particular algorithm in there that I should look for? Or just look over all of the one's with graphs and see if I can find one that looks useful? Oh and there's one optimal solution (I suppose there could be a tie for that though) and infinite other solutions since you could just go back and forth between two nodes any number of times and then solve it. –  Talon876 Jan 19 '12 at 9:20

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.

-
@Talon876 This is a type of randomized algorithm I was talking about. –  c0da Jan 19 '12 at 9:56