koobas.hobune.stream
Pathfinding through pairs of connections
Okay this is a bit of a complicated problem. I have a List called pipeData. The list contains sets of two ints, call these ints points. The two points form a connection, e.g. (1,3) (4,2) (2,3) (4,3). Now, what I need is to find a way to check if, say, point 4 is connected to point 1. The function then needs to search through the (4,3), then (1,3) and return true. If no connection is found then return false. The number of connections will be somewhere between 10-40, but is theoretically uncapped because the user creates these points in an editor. The number of connections between the points is also uncapped, and the function will run on button press, not on update.
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.IO;
public class EditorChassis : MonoBehaviour {
List<int[]> pipeData = new List<int[]>();
void Start() {
//Create a random connection list to test against
string debug = "Connections created:";
for(int i = 0;i<20;i++) {
int pointA = Random.Range(0,20);
int pointB = Random.Range(0,20);
temp_pipeData.Add = new int[] {pointA,pointB}
debug += " ("+pointA+","+pointB+")";
}
print(debug);
print(Connected(0,20));
}
bool Connected(int start,int end) {
//return true if connected, false if not
}
}
If you want to do some research on your own (you should), you should have a look at graph and possibly Graph theory. Your problem is called the shortest path problem. There are several algorithms that solve this efficiently, look up Dijkstra's Algorithm or A*.
When implementing your algorithm of choice, remember that the vertices might be in different graphs, and thus a solution might not be found.
He is going with nodes and tree (at least it looks like) DFS/BFS are more appropriate since he is not looking for the shortest path but just if they are related.
@fafase True, but the easiest way of discovering this is by finding the shortest path. The algorithm you described below your answer is actually Dijkstra's Algorithm in an undirected&unweighted graph. (Yes, it's just a BFS.)
This is exactly what I was looking for, I'll throw it on here for future reference. Thank you for your help
using UnityEngine;
using System.Collections;
using System.Collections.Generic;
using System.IO;
public class EditorChassis : MonoBehaviour {
List<int[]> pipeData = new List<int[]>();
List<int> visited = new List<int>();
void Start() {
//Create a random connection list to test against
string debug = "Connections created:";
for(int i = 0;i<20;i++) {
int pointA = Random.Range(0,20);
int pointB = Random.Range(0,20);
temp_pipeData.Add = new int[] {pointA,pointB}
debug += " ("+pointA+","+pointB+")";
}
print(debug);
print(Connected(0,20));
}
bool Connected(int start,int end) {
visited.Clear();
return Connection(start,end);
}
bool Connection(int pointA,int pointB){
if (pointA == pointB) return true;
for(int i = 0;i<pipeData.Count;i++) {
if (!visited.Contains(i)) {
if (pipeData[i][0] == pointA) {
visited.Add(i);
if (Connection(pipeData[i][1],pointB) == true) return true;
}
else if (pipeData[i][1] == pointA) {
visited.Add(i);
if (Connection(pipeData[i][0],pointB) == true) return true;
}
}
}
return false;
}
}
One drawback of your implementation is the limited size it affords. See You are using recursive function, which means your Connection method calls Connection method within it and this may happens many times. This works for relative small size tree, try this on a Google server system and you will soon be facing a stack overflow exception. That is because each method call is piling new variable on the stack but the previous ones remains until we reach the bottom of the tree.
You may want to consider queuing and while loop ins$$anonymous$$d of for loop and call to Connection method over and over again.
I've never used queuing before and I don't know how to use it, could you give me an example of what you mean?
This is for queue : http://en.wikipedia.org/wiki/FIFO and its buddy the stack :http://en.wikipedia.org/wiki/LIFO_(computing)
You could create a Node class or stucture where you store the info you want.
public class Node{
private Vector2 position;
public Vector2 Position{get{return position;}}
public List<Node> connections = new List<Node>();
public Node(Vector2 position){
this.position = position;
}
// You don't need the method, it is just to show which it is
public bool Contains(Node node){
return connection.Contains(node);
}
}
Note that the members should maybe be private.
The user is allowed to add and remove these connections freely, and there is no hierarchy of the nodes. The project is large and moving from List to Node() is not possible. Or maybe I misunderstood your answer? If so, please continue
I don't think I explained myself correctly. I specified points as (1,5) (5,2) (4,3) etc. These are NOT Vector2's, they are pairs - bridges. By (1,5) it means that this pair connects point 1 and 5 together, creating a bridge between the two. To test between two points you'll need first a pair that contains the starting point, then, using the second point in the pair, find another entry, to expand the 'connection' Eg. "'are 1 and 3 connected?' (1,5)-(5,7)-(2,7)-(2,3) therefore 'true'". Again, the pair is not a Vector2 and does not contain x and y values, it's a bridge between points.
Ok, so what you need is a tree of nodes and use DFS or BFS algorithm.
You can remove the position from the node but you should keep the list and add a parent node and a already visited bool.
Let's consider you have a tree that looks like this:
1
$$anonymous$$__
| |
5 6
$$anonymous$$__
| |
8 7
$$anonymous$$__
| |
4 3
Then you take the starting node 1, and you enqueue in a queue the list of node connected to it (5,6). In the same time, you mark those with the starting node as parent. Then dequeue (you get 5), has it been visited, nope, mark as visited, is it the end node, nope, enqueue all linked nodes with 5 as parent(6,8,7). Dequeue, you get 6, has it been visited. nope, mark as visited, is it the end node, nope, nothing to enqueue. Dequeue, you have 8 same again, marked as visited, not the end, add to the queue with 8 as parent(nothing to queue). Take 7, not the end (shorting), 4 and 3 are added. Now we are going to get to 3 and it is the end, happens to be it was the last one. So we just need to go up the parents and store them in a list: 3 has 7, 7 has 5, 5 has 1
3->7->5->1 revert that list and make it an array and that is it.
So I spoke to a $$anonymous$$cher of $$anonymous$$e, and he explained exactly what you just said. I'll post the solution in a new answer.
