2D procedural node map

Hi,
I came up with a problem I am trying to solve, for last couple of days.

I am trying to create procedurally map based on nodes.

Here is my problem


They Are:
1. Overlapping
2. Too close to each other

Here is a code of transforming them:

Code (CSharp):

1.     public static Vector3 RndCircle(float radius)
2.     {
3.         float angle = Random.Range(-Mathf.PI, Mathf.PI);
4.         float x = Mathf.Cos(angle) * radius;
5.         float y = Mathf.Sin(angle) * radius;
6.  
7.         return new Vector3(x, y, 0);
8.     }
9.     void TransformSubNodes(GameObject parent)
10.     {
11.         for(int i = 0; i < parent.transform.childCount; i++)
12.         {
13.             parent.transform.GetChild(i).transform.position = parent.transform.position + RndCircle(5f);
14.         }
15.         ConnectSubNodes(parent);
16.     }

I don't have any idea how to fix it. If someone could point me at some direction, I will be really thankful.

 

You could consider starting with a grid, where each section is only allowed to be occupied by a single node. Every time you add a depth, the next nodes go into adjecent sections that are unoccupied. For more randomness you could add random position offsets to the nodes. Just make sure that if each grid-section is 1x1, your maximum random offset is between 0 and 0.5 (assuming the node starts in the middle of the section) so they dont end up overlapping.

 

In any case, my Script order:
SpawnMasterNode(int SubNodes) <- This Create the first node at (0,0)
SubSubNode(int depth, int ammount) <- This Create a next depth with ammount per depth
SpawnSubNode(GameObject parent, int ammount, int depth) <- spawn a sub node at position (0,0) times ammount (int depth is just for name)
TransformSubNodes(GameObject parent) <- This transform a node 5f away from parent in a random place around parent
ConnectSubNodes(GameObject parent) <- This one draw line between parent and its children
List<GameObject> placed <- this is list of all spawned nodes

Ok, I followed your advice, every node is on 1x1 position



now, the yellow Circle contains two nodes (witch ok, I can destroy or move), but...
the red Circle is what I want to fix to be like a green Circle the lines to not overlap each other.
So that is the problem that I cannot pass, and I have not even close idea how to fix it.

 

The result you have shouldn't happen with the process i described. The step you seem to be missing in your latest process (from what i understand), is creating the grid (2d array). The grid is essential so the program can 'remember' the positions of each node in correlation to eachother. It seems you spawn the subnode in a 'random place'. If you use the 2d array, and the process i described, no place is fully random. Perhaps a step by step guide will clarify my earlier response:

1. Create a 2d or 3d array that can house all the nodes you will need
2. Create a node in the 2d array (first node is concidered master or root node)
   
3. Get all available positions around this node from the 2d array (get node neighbours)
4. Check to see which positions are available, ergo, do NOT yet have an active node in them
   
5. Spawn subnodes within the array in any of the available neighbouring positions
6. Repeat step 2 - 5 as many times as you would like and as long as there are positions available in the 2d array.

This guide just sets up your nodes in a way they will never overlap or cross. The rest seems to be working already (lines between nodes etc...) so you should be fine. You can use the picture in my earlier response for visual support.

Hope it helps.

 

as you said, I have already
1 & 2. "placed" is the array of all nodes (including master) as GameObject witch i can take .transform.position from it
3. i have created a FindLocations function that adds all possible Vector3 arround current node

Code (CSharp):

1.     public List<Vector3> pLocations = new List<Vector3>(); //list of all possible locations
2.  
3.     void FindLocations(GameObject This)
4.     {
5.         pLocations.Clear();
6.         for(int i = 1; i < 91; i++)
7.         {
8.             if(!pLocations.Contains(Loc(This.transform.position, i)))
9.                 pLocations.Add(Loc(This.transform.position, i));
10.         }
11.  
12.     }
13.  
14.     Vector3 Loc(Vector3 center, int multiply)
15.     {
16.         float radius = 5f;
17.         float angle = multiply * 4;
18.         float a = angle / 180 * Mathf.PI;
19.         int x = Mathf.RoundToInt(Mathf.Cos(a) * radius);
20.         int y = Mathf.RoundToInt(Mathf.Sin(a) * radius);
21.  
22.         return new Vector3(x + center.x, y + center.y, 0);
23.     }

4 & 5. Spawn Node on position and Remove it from array

Code (CSharp):

1.     void CreateNode()
2.     {
3.         int rnd = Random.Range(0, pLocations.Count);
4.         Vector3 pos = pLocations[rnd];
5.         GameObject go = Instantiate(nodeObj, pos, Quaternion.identity);
6.         pLocations.Remove(pos);
7.         if (go.transform.parent != null)
8.             DrawConnection(go);
9.     }

i was thought about getting an angle between parent and parent.parent of current object then place it with random offset, eg.
float angle = Vector3.Angle(parent, parent.parent)
so this object, transform.position = Random.Range(angle - 5f, angle + 5f);
but, that does not work as suppose to.

so whatever I tried I end up with:

A: Too close or overlapping (so i fixed it with Vector3.Distance)
B: They are crossing the lines (and that is my biggest issue)

 

Here is the enitre code: https://hastebin.com/cazufihuge.cs
using:
attach this script to empty game object
Node List = leave empty
Node Obj = place any GameObject as a node
Mat = material for line renderer
Depth = ...Depth... how deep children will be created
Ammount = Ammount of children per depth
Rest of it, leave empty (seed is for generating the same level all the time, empty seed will randomise it)

 

Its messy, ugly and unoptimized. Also, there is a mistake in there (it might be the random we roll, there is a comment there saying we should 'keep score', but im not sure). Sorry, but i have no more time now to work on this today since i have my own stuff to do. I hope it will help you figure out one way you can achieve what you wish to achieve. Feel free to ask questions offcourse. All you have to do to check it out is add this script to an object in your scene and add an object to the nodeObj field in the inspector then hit play.

Code (CSharp):

1. using System.Collections.Generic;
2. using UnityEngine;
3.  
4. public class Map : MonoBehaviour
5. {
6.     [SerializeField] private GameObject nodeObj;
7.     [SerializeField] private int gridSizeX = 64;
8.     [SerializeField] private int gridSizeY = 64;
9.     private Node[,] nodeGrid;
10.     private List<Node> finishedNodes;
11.     private class Node
12.     {
13.         public int x { get; set; }
14.         public int y { get; set; }    
15.         public bool hasParent { get; set; }
16.         public Vector2Int parentPosition { get; set; }
17.     }
18.  
19.  
20.     // Execution pipeline:
21.     private void Start()
22.     {
23.         finishedNodes = new List<Node>();
24.  
25.         InitGrid();
26.  
27.         // ======================================================================================================================
28.         // THE FOLLOWING CODE IN THIS METHOD (Start()) YOU CAN CUSTOMIZE TO MANIPULATE THE RESULT, SO YOU CAN GET WHAT YOU WANT
29.         // THIS IS A SIMPLE EXAMPLE TO SHOW YOU WHAT IT CAN DO:
30.         // ======================================================================================================================
31.  
32.         // Master node:
33.         Node masterNode = GetAndAddNodeToGrid((int)(gridSizeX * 0.5f), (int)(gridSizeY * 0.5f));
34.  
35.         // The following code splits, and can be modified to
36.         List<Node> split0 = GetAndAddNodeSplit(masterNode, 2);
37.  
38.         // Fractal typed explicitly, you could create a function that can do this indefinetly:
39.         foreach (Node n0 in split0)
40.         {
41.             List<Node> splits0 = GetAndAddNodeSplit(n0, 2);
42.  
43.             foreach (Node n1 in splits0)
44.             {
45.                 List<Node> splits1 = GetAndAddNodeSplit(n1, 2);
46.  
47.                 foreach (Node n2 in splits1)
48.                 {
49.                     List<Node> splits2 = GetAndAddNodeSplit(n2, 2);
50.                 }
51.             }
52.         }
53.  
54.         // Always call this last, as this takes all data and actually creates the gameobjects in the scene:
55.         PrintNodeObjects();
56.     }
57.  
58.  
59.     // Custom methods:
60.     private void InitGrid()
61.     {
62.         // Init grid with null values:
63.         nodeGrid = new Node[gridSizeX, gridSizeY];
64.     }
65.  
66.     private List<Vector2Int> GetViablePerpendicularNeighbourPositions(Node _node)
67.     {
68.         List<Vector2Int> viableNeighbourPositions = new List<Vector2Int>();
69.  
70.         if (_node.x - 1 >= 0) // Bound check
71.             if (nodeGrid[_node.x - 1, _node.y] == null) // Check for position availability
72.                 viableNeighbourPositions.Add(new Vector2Int(_node.x - 1, _node.y)); // Add to list
73.  
74.         if (_node.x + 1 < gridSizeX - 1)
75.             if (nodeGrid[_node.x + 1, _node.y] == null)
76.                 viableNeighbourPositions.Add(new Vector2Int(_node.x + 1, _node.y));
77.  
78.         if (_node.y - 1 >= 0)
79.             if (nodeGrid[_node.x, _node.y - 1] == null)
80.                 viableNeighbourPositions.Add(new Vector2Int(_node.x, _node.y - 1));
81.  
82.         if (_node.y + 1 < gridSizeY - 1)
83.             if (nodeGrid[_node.x, _node.y + 1] == null)
84.                 viableNeighbourPositions.Add(new Vector2Int(_node.x, _node.y + 1));
85.  
86.         return viableNeighbourPositions;
87.     }
88.  
89.     private Node GetAndAddNodeToGrid(int _x, int _y, Vector2Int parentPosition = default)
90.     {
91.         Node newNode = new Node() { x = _x, y = _y };
92.         nodeGrid[_x, _y] = newNode;
93.  
94.         // If there is a parentNode, save its position in the current node:
95.         if (parentPosition != default)
96.         {
97.             nodeGrid[_x, _y].hasParent = true;
98.             nodeGrid[_x, _y].parentPosition = new Vector2Int(parentPosition.x, parentPosition.y);
99.         }
100.        
101.         finishedNodes.Add(newNode);
102.  
103.         return newNode;
104.     }
105.  
106.     private List<Node> GetAndAddNodeSplit(Node node, int splitCount)
107.     {
108.         List<Vector2Int> nodeNeighbours = GetViablePerpendicularNeighbourPositions(node);
109.         List<Node> nodeSplits = new List<Node>();
110.  
111.         for (int i = 0; i < splitCount; i++)
112.         {        
113.        
114.             // Atm completely random, perhaps good idea to keep score so we dont roll the same random twice:
115.             int rand = Random.Range(0, nodeNeighbours.Count);
116.  
117.             Node newNode = GetAndAddNodeToGrid(nodeNeighbours[rand].x, nodeNeighbours[rand].y, new Vector2Int(node.x, node.y));
118.  
119.             nodeSplits.Add(newNode);
120.         }
121.  
122.         return nodeSplits;
123.     }
124.  
125.     private void PrintNodeObjects()
126.     {
127.         foreach (Node n in finishedNodes)
128.         {
129.             GameObject node = Instantiate(nodeObj);
130.             node.transform.position = new Vector2(n.x, n.y);
131.  
132.             if (n.hasParent)
133.             {
134.                 LineRenderer lr = node.AddComponent<LineRenderer>();
135.                 lr.startWidth = 0.1f;
136.                 lr.endWidth = 0.1f;
137.                 lr.SetPosition(0, new Vector3(n.x, n.y));
138.                 lr.SetPosition(1, new Vector3(n.parentPosition.x, n.parentPosition.y));
139.             }
140.         }
141.     }
142. }

 

I managed to make it work, it's slow, so I am highly NOT recommended this for mobile games:
https://mega.nz/#!zsdFlK7R!2Ek_HrenkVOsvzHP__mrY2eUOf03SEdV2lcuCdwXMX8

NodeObj = use this as node GameObject
LineMaterial = material that will be used for LineRenderer
Depth = How many "children" are going to be from first node

It's not used: "Ammount"
Ammount = How many nodes are going to be created for each depth
if you want to use it edit line 56
instead of:

Code (CSharp):

1. for(int i = 0; i < id * 4 * d; i++){

use:

Code (CSharp):

1. for(int i = 0; i < Ammount; i++){

I hope i helped you.