1

Hi guys.

I am trying to implement Kruskal’s algorithm for maze generation right now. I create a grid of cubes (nodes) which each have a script that contains an array of their adjacent nodes. My problem is that I am trying to store the edges that connect the nodes in a list, to be used in the algorithm later, however the edges are being stored twice (I’m guessing it is because the edges are being stored in forwards and backwards order (i.e. 1 -[edge]- 2, when it hits 1, it creates an edge to 2, when it hits 2, it creates an edge to 1). The edges it stores are implemented as a ScriptableObject, and just stored in a list.

	void Weights()
	{
		Vertices verts;
		
		for(int i = 0; i < gridSize.x; ++i)
		{
			for(int j = 0; j < gridSize.y; ++j)
			{
				Transform node;
				node = grid[i, j];
				
				Edge edge = ScriptableObject.CreateInstance("Edge") as Edge;
				
				verts = node.GetComponent<Vertices>();
				
				// Adjacent nodes are stored as shown below
				
				///////////[0]////////////
				////////[3][x][1]/////////
				///////////[2]////////////
				
				////// Up = Position j, Down = Negative j
				////// Right = Positive i, Left = Negative i
				if(i - 1 >= 0 && i + 1 < gridSize.x)
				{
					verts.adjNode[3] = grid[i - 1, j];
					verts.SetAdjWeight(3);
					
					edge.SetConnectingNodes(node, verts.adjNode[1]);
					edges.Add (edge);
					
					verts.connectedNodes[3] = grid[i - 1, j];
					
					verts.adjNode[1] = grid[i + 1, j];
					verts.SetAdjWeight(1);
					
					edge.SetConnectingNodes(node, verts.adjNode[3]);
					edges.Add (edge);
					
					verts.connectedNodes[1] = grid[i + 1, j];
				}
				else if(i - 1 < 0)
				{
					verts.adjNode[3] = null;
					verts.SetAdjWeight(3);
					
					verts.connectedNodes[3] = null;
					
					verts.adjNode[1] = grid[i + 1, j];
					verts.SetAdjWeight(1);
					
					edge.SetConnectingNodes(node, verts.adjNode[1]);
					edges.Add (edge);
					
					verts.connectedNodes[1] = grid[i + 1, j];
				}
				else if(i + 1 >= gridSize.x)
				{
					verts.adjNode[3] = grid[i - 1, j];
					verts.SetAdjWeight(3);
					
					edge.SetConnectingNodes(node, verts.adjNode[3]);
					edges.Add (edge);
					
					verts.connectedNodes[3] = grid[i - 1, j];
					
					verts.adjNode[1] = null;
					verts.SetAdjWeight(1);
					
					verts.connectedNodes[1] = null;
				}
				
				if(j - 1 >= 0 && j + 1 < gridSize.y)
				{
					verts.adjNode[2] = grid[i, j - 1];
					verts.SetAdjWeight(2);
					
					edge.SetConnectingNodes(node, verts.adjNode[2]);
					edges.Add (edge);
					
					verts.connectedNodes[2] = grid[i, j - 1];
					
					verts.adjNode[0] = grid[i, j + 1];
					verts.SetAdjWeight(0);
					
					edge.SetConnectingNodes(node, verts.adjNode[0]);
					edges.Add (edge);
					
					verts.connectedNodes[0] = grid[i, j + 1];
				}
				else if(j - 1 < 0)
				{
					verts.adjNode[2] = null;
					verts.SetAdjWeight(2);
					
					verts.connectedNodes[2] = null;
					
					verts.adjNode[0] = grid[i, j + 1];
					verts.SetAdjWeight(0);
					
					edge.SetConnectingNodes(node, verts.adjNode[0]);
					edges.Add (edge);
					
					verts.connectedNodes[0] = grid[i, j + 1];
				}
				else if(j + 1 >= gridSize.y)
				{
					verts.adjNode[2] = grid[i, j - 1];
					verts.SetAdjWeight(2);
					
					edge.SetConnectingNodes(node, verts.adjNode[2]);
					edges.Add (edge);
					
					verts.connectedNodes[2] = grid[i, j - 1];
					
					verts.adjNode[0] = null;
					verts.SetAdjWeight(0);
					
					verts.connectedNodes[0] = null;
				}
			}
		}
		
		edges.OrderBy(o=>o.edgeWeight);
	}

Above is the code which I am using to get the weights of each node and store the edges.

An example of my problem is this:

x - x - x
|   |   |
x - x - x
|   |   |
x - x - x

In the above 3x3 grid, there are 12 edges, represented by -'s and |'s. However, when I run my program with a 3x3 grid, my list of edges contains 24 Edge scripts.

Any help in solving this would be greatly appreciated.

Thanks,
Chris

2

Since you are scanning the entire grid, do not add the edges behind your current block in the direction of travel of each loop. Basically, remove edges.Add from the i-1 and j-1 cases.

Out of curiosity, why a ScriptableObject and not just an instance of a System.Serializable?

3

If you have random weights, the MST-Algorithm turns into something that just connects random edges. You don’t need the weights for the algorithm, just shuffle your edges.

Kruskal’s Algorithm actually isn’t really Kruskal’s Algorithm anymore if you use random weights or just ignore weights when picking nodes.

And if you don’t have weights, you actually don’t need Edge objects as those are basically just there, so you can add properties like weight to a connection between two nodes. If you don’t need that, just use your grid which defines the edges implicitly and if you need a list of edges, just use something like this and have x/y just be the indices into your grid:

public class Edge { int fromX,fromY; int toX,toY; }

And ScriptableObject has too much overhead for a simple Edge as you don’t use its features at all.

If you show more code, I’m sure we can strip it down even further.

cheers