public class Node
{
public string id;
public List<Node> connections;
}
Each node is composed of an identifier and a list.
The list includes references to the other nodes to which it is connected.
Characteristics of the list:
There will never be a node included in your own list.
There will never be repeated nodes.
There will never be more than 4 nodes.
PROBLEM
With a list of nodes of X size,
create an algorithm that converts the list into a two-dimensional matrix
respecting the connections between the nodes.
In case it is not possible, return null.
using System.Collections.Generic;
using UnityEngine;
public class Test : MonoBehaviour
{
public class Node
{
public string id;
public List<Node> connections;
public Node(string id)
{
this.id = id;
connections = new List<Node>();
}
}
public List<Node> list;
public void Start()
{
list = CreateNodes();
Node[,] matrix = ListToMatrix(list);
Print(matrix);
}
public Node[,] ListToMatrix(List<Node> lst)
{
Node[,] array = null;
#region Example
//array = new Node[3, 4]
//{
// { null, null, lst[3], lst[6] },
// { null, lst[2], lst[0], null },
// { lst[4], lst[1], lst[5], null }
//};
#endregion Example
// <- HELP
return array;
}
public List<Node> CreateNodes()
{
List<Node> nodes = new List<Node>();
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");
Node d = new Node("D");
Node e = new Node("E");
Node f = new Node("F");
Node g = new Node("G");
a.connections.Add(c);
a.connections.Add(d);
a.connections.Add(f);
b.connections.Add(c);
b.connections.Add(e);
c.connections.Add(a);
c.connections.Add(b);
d.connections.Add(a);
d.connections.Add(g);
e.connections.Add(b);
f.connections.Add(a);
g.connections.Add(d);
nodes.Add(a);
nodes.Add(b);
nodes.Add(c);
nodes.Add(d);
nodes.Add(e);
nodes.Add(f);
nodes.Add(g);
return nodes;
}
public void Print(Node[,] matrix)
{
if (matrix == null)
return;
string result = "";
for (int x = 0; x < matrix.GetLength(0); x++)
{
for (int y = 0; y < matrix.GetLength(1); y++)
{
Node node = matrix[x, y];
result += string.Format("{0} ", node != null ? node.id : "X");
}
result.Remove(result.Length - 1);
result += '\n';
}
Debug.Log(result);
}
}
What do you need this for? Seems to me like you’d rather want a tree representation.
May be a case of XY-Problem.
Until i looked at your code, i was pretty sure you wanted to throw out the node type, in which case you’d lose information since the matrix has no way of representing the connections nodes once had. However, since you intend to keep the nodes all of this just seems even more redundant to me.
You did not mention whether the array has to be minimal in size. If not, just go with a tree representation, get the maximum depth and width of the tree and just shove it into a jagged arrays’ center.
(Edit: )You wrote ‘in case it is not possible, return null’. In case… what is not possible? What’s the criteria for failure? You did not name any criteria that may fail. Based on the given information, there is no case i can think about that would result in null being returned. This probably comes down to a missing size restriction or something.
I am making a random dungeon generator. Unfortunately I have encountered this problem and my brain cannot process it.
I know that the problem may seem unrelated to Unity or a dungeon generation system but the real code is much more complex than this and I wanted to simplify it a lot so that people could focus specifically on what is important.
I’m going to try to give you a context about what I’m trying to solve:
The nodes represent rooms.
The matrix is the complete map.
I have to place the rooms correctly so that I don’t find inconsistencies like doors opening into the void or walls.
Then I just instantiate the rooms according to their position in the matrix.
The only information I have is a list of all the rooms and their connections.
I know that B - F are not connected because B does not appear in the connections of F and F does not appear in the connections of B.
The array is composed only of the type Node as the original list.
Indeed, the minimum size that lists can acquire is 0.
An impossible scenario would be, for example, that A is connected to G (in the image above).
Hm, interesting approach. Short of brute-forcing this, I’m not sure there’s an elegant algorithm.
Usually the way binding of isaac style generators work is they walk along adding rooms, and when they want to lock a room, they always put the key in a preceding room.
If at any point they find they have wrapped around themselves (and cannot go further) they abandon and retry, and for a sufficiently small dungeon eventually you’ll succeed.
I studied different ways to be able to produce the game map but I wanted the rooms to be designed by hand.
The random part focuses on the distribution of the rooms.
The original list is obtained from a node editor I created for this game.
If I get a good result, I plan to publish my system as a plugin in the assetstore.
I’m sure it would be helpful to many people.
I’d just try random-brute-forcing it and I bet for a small amount of rooms it won’t take long to succeed.
Otherwise you’re gonna have to come up with some space partitioning scheme or some other way of finding out if there simply isn’t any way to make it fit.
If all that matters is the distribution of rooms on a map preserving the connections between rooms, the Wave Function Collapse Algorithm could be an idea. I highly recommend the article The Wavefunction Collapse Algorithm explained by Robert Heaton.
Basically, in that algorithm, you define rules on how rooms have to be positioned to each other and the algorithm then tries to find a valid setup. The complete algorithm goes a lot further than what you need, but a simplified version of it could be a solution to your problem.
If the developer using your tool finishes a layout, you would save the rooms and which other rooms they are connected to. Then, you would put this list into your algorithm which tries to distribute the rooms by placing one after another respecting the neighboring restrictions and trying to find the next room that it should place by looking at the connections. If the algorithm fails to place the rooms in this matter, repeat for a fixed amount of times. I used this myself in the past and it is a nice, albeit slightly dull way to force a layout.
Thank you very much, this looks like exactly what I was looking for.
I knew it should have been invented already but I didn’t know the name of the algorithm and I couldn’t find useful information for what I wanted to do on the Internet.
I don’t know how long I can take to implement it, if I don’t get it I will try the brute force as I was told before.
In the meantime I am open to new ideas and opinions that may arise.
As I said, if look at some implementations for it like the one by Maxim Gumin, you might be overwhelmed at first, the complete algorithm is quite a challenge for understanding, prgoramming and using it. However, a simplified version, such as Robert Heaton explains it in the linked article further down, is feasible within a reasonable amount of time and gets the job done in your case.
Yeah, this is a common problem, I believe. Happens to me all the time.