Apologies for the somewhat vague title, couldn’t think of the best way to sum up my problem. Have tried searching for some form of info on how best to approach my problem but haven’t found much due to the fact I don’t exactly know the technical term (if there is one) for what I’m trying to do. I don’t need anyone to write out a full script for me, just some kind of insight into how on earth this should be approached.
Basically, I am laying out plans for a game which involves building modular vehicles from large, cubic parts. My research seems to indicate the best way to go about this (correct me if I’m wrong) is by creating prefabs with colliders as children of a single rigidbody’d parent, due to wiggle/wobble that occurs with the alternative - attaching many adjacent rigidbody cubes via joints.
What I’m trying to work out [and I’ve spent the better part of 2 days trying to figure out the best approach] is, if a cube is destroyed, how to a) check if that cube was the last/only remaining connection between two other parts, and b) if “a)” is true, how to “break off” the two now separate parts. To illustrate it kind of crudely:
The first shape shows a single segment of blocks (arranged only across 2 dimensions here for simplicity). In the second shape, one block has been broken off, however, as there remains another block connecting the other parts, nothing happens. In the third shape, the last connecting block has been broken, so the segment separates into two: the root and the newly-formed orphan.
Any kind of input here is welcome (even if it’s just telling me what term to search for in Google!), I normally prefer to try and solve problems on my own but this is completely eluding me and I can’t really move forward until I know exactly what system to use for attaching/detaching parts. Thanks in advance.
Well for one, you’re going to need to keep track of neighbours. Sort of like joints if they weren’t all childed, but no physical component to it.
So whenever you add a new block to the cluster, you record that this block was added and who it neighbours.
Whenever it’s removed, you sever the neighbours. Then if you start at ‘root’ and traverse the link list of neighbours (go from root to the next to the next, etc) you’ll find all neighbours of root. Any blocks NOT found have been orphaned.
Gather up all the orphaned blocks, and start with any given block in it, traverse its neighbour link list to get all blocks in its cluster to generate the orphan. Remove them from the parent, and create a whole new group out of it as the child of another GameObject (I assume) and the neighbour info is already there.
If there are still blocks left over, repeat this cycle, as it means the break created multiple orphans.
Thank you! I knew I had to keep track of each block’s neighbours but I had no clue how to actually use that information. Many thanks for taking the time to explain!
How exactly, in terms of data structures, would you recommend keeping track of everything? You mention a linked list which I’m not particularly familiar with.
public class NodeCollection : ICollection<Transform>
{
#region Fields
private Dictionary<Transform, HashSet<Transform>> _nodes = new Dictionary<Transform, HashSet<Transform>>();
#endregion
#region ICollection Interface
public int Count
{
get
{
return _nodes.Count;
}
}
bool ICollection<Transform>.IsReadOnly
{
get
{
return false;
}
}
public void Add(Transform node)
{
if (_nodes.ContainsKey(node)) return; //already a member
_nodes.Add(node, new HashSet<Transform>());
}
public bool Remove(Transform node)
{
HashSet<Transform> set;
if (_nodes.TryGetValue(node, out set))
{
var e = set.GetEnumerator();
HashSet<Transform> setB;
while (e.MoveNext())
{
if (_nodes.TryGetValue(e.Current, out setB))
{
setB.Remove(node);
}
}
_nodes.Remove(node);
return true;
}
return false;
}
public void Clear()
{
_nodes.Clear();
}
public bool Contains(Transform item)
{
return _nodes.ContainsKey(item);
}
public void CopyTo(Transform[] array, int arrayIndex)
{
_nodes.Keys.CopyTo(array, arrayIndex);
}
public IEnumerator<Transform> GetEnumerator()
{
return _nodes.Keys.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
#endregion
#region Methods
public void LinkAsNeighbours(Transform nodeA, Transform nodeB)
{
HashSet<Transform> setA;
HashSet<Transform> setB;
if(_nodes.TryGetValue(nodeA, out setA) && _nodes.TryGetValue(nodeB, out setB))
{
setA.Add(nodeB);
setB.Add(nodeA);
}
else
{
throw new System.ArgumentException("Nodes must be members of the collection before linking.");
}
}
public void UnlinkAsNeighbours(Transform nodeA, Transform nodeB)
{
HashSet<Transform> setA;
HashSet<Transform> setB;
if (_nodes.TryGetValue(nodeA, out setA) && _nodes.TryGetValue(nodeB, out setB))
{
setA.Remove(nodeB);
setB.Remove(nodeA);
}
else
{
throw new System.ArgumentException("Nodes must be members of the collection when unlinking.");
}
}
public void GetNeighbours(ICollection<Transform> coll, Transform node)
{
HashSet<Transform> set;
if(_nodes.TryGetValue(node, out set))
{
var e = set.GetEnumerator();
while (e.MoveNext())
{
coll.Add(e.Current);
}
}
}
public void WalkNeighbourTree(ICollection<Transform> coll, Transform node)
{
var set = new HashSet<Transform>(); //can be optimized
set.Add(node);
this.RecurseWalkTree(set, node);
var e2 = set.GetEnumerator();
while (e2.MoveNext())
{
coll.Add(e2.Current);
}
}
private void RecurseWalkTree(HashSet<Transform> coll, Transform node)
{
HashSet<Transform> neighbours;
if (_nodes.TryGetValue(node, out neighbours))
{
var e = neighbours.GetEnumerator();
while (e.MoveNext())
{
if (!coll.Contains(e.Current))
{
coll.Add(e.Current);
this.RecurseWalkTree(coll, node);
}
}
}
}
#endregion
}
Note I specifically use a ‘HashSet’ for holding neighbours, because it forces uniqueness (you can only add one of some object to it, no duplicates). Also it is fast to add or remove (it has an O(1) speed for adding/removing/testing contains).
Note though, in the WalkNeighbourTree I create a new HashSet, this can be intense on GC. In general, to deal with the crappy garbage collector in the version of mono we have, I recycle my collections.
Usually what I do is use my ‘TempCollection’ class:
Which I can return recycled Lists and HashSets with…
TempList:
TempHashSet:
So really, if you used those you would rather do:
public void WalkNeighbourTree(ICollection<Transform> coll, Transform node)
{
using(var set = TempCollection.GetSet<Transform>())
{
set.Add(node);
this.RecurseWalkTree(set, node);
var e2 = set.GetEnumerator();
while (e2.MoveNext())
{
coll.Add(e2.Current);
}
}
}
Anyways, with this collection you could keep track of your added nodes, as well as set up links.
Then you can walk the various trees with it to find groups.
Of course… this is all untested (I slapped this together in notepad like right this second), and there are more robust algorithms for searching through the tree (just getting a basic idea out there for now), but this should be able to give you some direction.
Thank you again! Good call on the hashset there, I was wondering how to approach the fact that neighbours could be recorded multiple times. I’ll have a play around and see how it goes. I’m very grateful, many thanks!
I think it would be easier to start checking for blocks to be orphaned at blocks that were connected to the destroyed block. Same result, but different approach.
Actually, the more I thought about it, I realized that it’s not an easier method since there could be redundant connections that would have to be dealt with.
