I have a somewhat âsolutionâ to this problem but it is very laggy. Itâs currently programmed to check one cable, then check all adjacent cables, then check all adjacent cables of those cables, etc⊠essentially a flood fill.
There can be multiple generators and multiple machines on any one line of cables, so my question is, whatâs the best way of checking if a machine is hooked up to a generator?
What youâre describing is essentially a Graph, a well known data structure in computer science. Your âflood fillâ algorithm sounds really similar to depth-first-search, and it is a well-known and efficient means of searching a graph. However, there are meaningful optimizations that you may or may not be doing in your search algorithm.
Also, you said the grid is 1000x1000. Thatâs quite large, a million entries. How many of them are actually populated, and are you effectively culling the non-populated and non-connected nodes from your search algorithm?
Sure. Itâs not good - at all. But this is my first time doing something like this.
public void GetGenerators()
{
List<GameObject> alreadyChecked = new List<GameObject>();
Queue<GameObject> toCheck = new Queue<GameObject>();
if (direction == null)
return;
// STARTING X AND Y
int x = direction.gridLocation.Item1;
int y = direction.gridLocation.Item2;
// ENQUEUE THE INITIAL CABLE
toCheck.Enqueue(grid.electricGrid[x, y]);
// CALL THE INITIAL GETCONNECTIONS FOR THE INITIAL CABLE SO THAT THE WHILE WILL ACTUALLY LOOP MORE THAN ONCE
GetConnections(x, y, alreadyChecked, toCheck);
// THE START TIME FOR DETERMINING THE DURATION OF THE WHILE LOOP
float time = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
// LOOP OVER ALL OF THE toCheck QUEUE
while (toCheck.Count > 0)
{
// GET THE NEXT ELEMENT IN THE QUEUE
GameObject obj = toCheck.Dequeue();
// IF THE TAG ON THE OBJECT IS CABLE
if (obj.tag.Equals("Cable"))
{
// GET THE CABLENODE COMPONENT ON THE CABLE
CableNode cableNode = obj.GetComponent<CableNode>();
// IF THE CABLENODE COMPONENT IS NULL, THEN CONTINUE TO THE NEXT ITERATION
if (cableNode == null)
continue;
// LOOP OVER ALL OF THE CONNECTORS (THESE ARE THE GENERATORS) THAT ARE CONNECTED TO cableNode
foreach (Connector connector in cableNode.generators)
{
// IF THE GENERATORS IN THIS CLASS DO NOT CONTAIN THE GENERATOR LISTED IN THE OTHER CABLE, ADD THE GENERATOR HERE
if (!generators.Contains(connector))
{
generators.Add(connector);
}
}
}
}
// THE END TIME FOR DETERMINING THE DURATION OF THE LOOP
float timeNow = DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
// ALWAYS 0, BUT BECAUSE THERE ARE MANY CABLES IT ADDS UP VERY QUICKLY
Debug.Log("Execution of Flood Fill took " + (timeNow - time) + "ms");
}
public void GetConnections(int x, int y, List<GameObject> alreadyChecked, Queue<GameObject> toCheck)
{
// TODO: ADD MIN AND MAX VALUES TO PREVENT INDEXOUTOFBOUNDS
// NORTH
// GET THE OBJECT AT THE LOCATION
GameObject obj = grid.electricGrid[x, y + 1];
// IF THE OBJECT IS NULL
if (obj != null)
{
// IF THE CABLE HAS NOT BEEN CHECKED
if (!alreadyChecked.Contains(obj))
{
// ADD THE CABLE TO THE CHECKED LIST
alreadyChecked.Add(obj);
// ADD THE OBJECT TO THE TOCHECK QUEUE
toCheck.Enqueue(obj);
// GET ALL OF THE CONNECTIONS FOR THIS CABLE
GetConnections(x, y + 1, alreadyChecked, toCheck);
}
}
// EAST
obj = grid.electricGrid[x + 1, y];
if (obj != null)
{
if (!alreadyChecked.Contains(obj))
{
alreadyChecked.Add(obj);
toCheck.Enqueue(obj);
GetConnections(x + 1, y, alreadyChecked, toCheck);
}
}
// SOUTH
obj = grid.electricGrid[x, y - 1];
if (obj != null)
{
if (!alreadyChecked.Contains(obj))
{
alreadyChecked.Add(obj);
toCheck.Enqueue(obj);
GetConnections(x, y - 1, alreadyChecked, toCheck);
}
}
// WEST
obj = grid.electricGrid[x - 1, y];
if (obj != null)
{
if (!alreadyChecked.Contains(obj))
{
alreadyChecked.Add(obj);
toCheck.Enqueue(obj);
GetConnections(x - 1, y, alreadyChecked, toCheck);
}
}
}
EDIT: To add to your update, yes there are 1 million entries and the culling is done by only checking locations where a cable exists which you can see in the code.
Ok one quick optimization I see right off the bat:
Change your already checked list:List<GameObject> alreadyChecked = new List<GameObject>();to a HashSet:HashSet<GameObject> alreadyChecked = new HashSet<GameObject>();
HashSet is much faster at checking âContainsâ than a list is. The list has to pretty much look through every element in the list to check Contains. The HashSet most likely only needs to do a quick calculation and look at a single entry to see if the item is already in the list.
Ok so with the number of objects in your graph that you just shared that performance is way lower than it should be. Definitely some more bad stuff happening here.
Which question do you need to answer by the way?
Is this node hooked up to at least one generator?
How many (and which) generators is this node hooked up to?
Currently your algorithm will search the entire connected graph from your starting node. If you only need to answer the first question you can optimize it to stop searching after it finds a single generator.
I need some way of knowing the total energy stored in each generator connected to the machine, otherwise a machine may not get the power requirement it needs even if it is available.
Another question is - when are you calling this method? Are you calling this every frame for every âslotâ in the map? Every frame for every machine? You really only need to run this algorithm when objects are added/removed from the graph.
Currently, every frame, which I know is very bad. I changed it to every time a new cable is placed, only that cable would update, but I had some trouble with it not updating correctly and not correctly seeing that it was connected to a generator.
Would I be better off having a class that manages all the cables? Currently, each cable has the flood fill script attached to it so obviously, this running every frame on every cable is bound to cause FPS problems.
Maybe I donât actually need a script on the cables at all?
Well⊠OP is actually not interested in pathfinding (despite the title). Depth-or-Breadth-First search is more what theyâre looking for since they need to know all of the generators their thing is connected to and they donât care about the path.
And while their implementation is far from ideal thatâs more or less what their code appears to be doing already. The problem theyâre having as far as I can surmise is that every single populated node in the graph is doing a search every single frame.
I need to find multiple generators from one machine, so I would first need to find ALL generators that exist on the map, with a very slow GameObject.Find call, (or store them in a List), then check individually if that generator is connected to that machine. Arguably, depending on the amount of generators on the map, this will actually be slower.
This is all assuming that I change my current implementation from cable based to machine based.
I canât imagine why the cables would need a script.
I would have a script on each machine and each generator. When anything is placed on the grid, you need to just do the search once and see if the new generator is hooked up to any existing machines or vice versa. Each machine can store references to all the generators its hooked up to and vice/versa and you can update those as new machines are added.
Definitely donât do any of this in Update() directly.
Personally I would have a script on each cable only for identification/data purposes. Store info about it and what not, it may include a list of its âneighboursâ, but not necessarily update that list. But no need for these cables/generator scripts to all be updating the graph.
Then yeah, there would be a âgraphâ component. Its job was to track when a cable/other thing was added to the graph. And update the relationships.
So this way any time you needed to add a new cable or whatever, youâd call your âGraphManagerâ and tell it do so:
GraphManager.AddAndUpdate(Cable cable)
Iâm not sure your specific situation⊠but I recently did a gamejam with a game where your character lays cable. Let me find that code.
There is plenty of optimization potential. If you are familiar with the job system and burst, you can offload this to a worker thread and avoid blocking the main one. If I find time this weekend I will put something together, have not used unity for a long time and this might be a little warm upâŠ
Yes, except of course that thereâs multiple objects rather than just two.
Iâm not familiar with it. Making a worker thread do it is definitely an idea. I will try the previously suggested optimizations first of all and if itâs still causing issues, Iâll make a worker thread.
Feel free to put something together Even if I finish and Iâm fine with the implementation Iâd love to see yours.
Even if I finish and Iâm fine with the implementation Iâd love to see yours.