Maze - CyclePoppingRandomTreeAlgorithm

Topics: algorithm, graph
May 26, 2010 at 1:02 AM
Edited May 26, 2010 at 1:28 AM

Hi there,

I am trying to create a maze based on a bidirectional - graph. I have a grid of vertices and each vertex is connected with its neighbour.

Example a 2x2 grid has 4 vertices and 8 edges

I am using the CyclePoppingRandomTreeAlgorithm to generate random mazes based on a root node. The route to the root node can be traced from every vertex by traversing its successors.

This works perfectly for the root node (0,0) and any random node from which we start to traceback to the root node. But if i select any other root node i.e (1,1) this node is somehow not connected to the graph any more. And the traceback will loop for ever.

Maybe you can help me by implementing an random kruskal algorithm to generate randon mazes.

Cheers and thanks in advance.

Code-Based on this tutorial: http://blog.dotnetwiki.org/archive/2004/05/07/190.aspx

 

        private List<Edge<string>> _pathToFinal;

        private BidirectionalGraph<string, Edge<string>> _graph;
        private IDictionary<string, Edge<string>> _successor;



(...)


_graph = new BidirectionalGraph<string, Edge<string>>(false);
            _grid = new String[_row, _column];

            // add vertecies


            for (int i = 0; i < _row; i++)
            {
                for (int j = 0; j < _column; j++)
                {
                    _grid[i, j] = String.Format("{0},{1}", i, j);
                    _graph.AddVertex(_grid[i, j]);

                }
            }

            // add edges bidirectional
            for (int i = 0; i < _row - 1; i++)
            {
                for (int j = 0; j < _column - 1; j++)
                {                   
                    _graph.AddEdge(new Edge<string>(_grid[i, j], _grid[i, j + 1]));
                    _graph.AddEdge(new Edge<string>(_grid[i, j + 1], _grid[i, j]));
                    _graph.AddEdge(new Edge<string>(_grid[i, j], _grid[i + 1, j]));
                    _graph.AddEdge(new Edge<string>(_grid[i + 1, j], _grid[i, j]));
                    _graph.AddEdge(new Edge<string>(_grid[_row - 1, j], _grid[_row - 1, j + 1]));
                    _graph.AddEdge(new Edge<string>(_grid[_row - 1, j + 1], _grid[_row - 1, j]));
                    _graph.AddEdge(new Edge<string>(_grid[i, _column - 1], _grid[i + 1, _column - 1]));
                    _graph.AddEdge(new Edge<string>(_grid[i + 1, _column - 1], _grid[i, _column - 1]));
                }
            }

(...)
CyclePoppingRandomTreeAlgorithm<string, Edge<string>> cprta = new CyclePoppingRandomTreeAlgorithm<string, Edge<string>>(_graph);
// (0,0) works perfectly. any other root node will fail @ while loop
cprta.RandomTreeWithRoot(_grid[_endPoint.X, _endPoint.Y]);
_successor = cprta.Successors;
var startEdge = _successor[_grid[_startPoint.X, _startPoint.Y]];
var endEdge = _successor[_grid[_endPoint.X, _endPoint.Y]];
_pathToFinal = new List<Edge<string>>();

while
(startEdge != endEdge)
{ Edge<string> e = startEdge;
// if any other root node than (0,0) was selected it will loop 4ever or break with an memory exeeded exception
_pathToFinal.Add(e);
startEdge = _successor[e.Target];
}