Randomly generate directed graph on a grid
- by Talon876
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.
