# Most performance friendly "pathfinding" algorithm for this scenario

Hi there,

I have a 2D array that is 1000 by 1000.

I am able to place GameObjects into that array and they will represent their real-world location.

The GameObjects in question are Cables, which attach to one another like the following:

These cables transfer electricity to other locations.

Generators can be attached anywhere within a 4 radius circle around the cable and it will connect. Like so:

The solar panels will produce the energy, the cables will transfer that energy along to a machine that will use said energy.
Like so:

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?

Would you mind sharing your code?

Sure. Itâs not good - at all. But this is my first time doing something like this.

``````    public void GetGenerators()
{
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

// 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))
{
}
}
}
}

// 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
{
// ADD THE CABLE TO THE CHECKED LIST
// 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)
{
{
toCheck.Enqueue(obj);
GetConnections(x + 1, y, alreadyChecked, toCheck);
}
}

// SOUTH
obj = grid.electricGrid[x, y - 1];

if (obj != null)
{
{
toCheck.Enqueue(obj);
GetConnections(x, y - 1, alreadyChecked, toCheck);
}
}

// WEST
obj = grid.electricGrid[x - 1, y];

if (obj != null)
{
{
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.

Definitely an improvement, Iâd say I can get 5x more cables than previously.

I thought Iâd state the numbers here,

I was getting 5 FPS with 25 cables, and now at ~100 cables Iâm getting 20.

But still with a map so large, I should really be aiming for as low FPS drop as possible.

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.

So unfortunately its the second question.

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?

Why not just use the existing algorithms out there.

Like Dijkstra or A*.

The algorithms are well defined and exist on the internet:

Here are my own personal implementations:
A* - spacepuppy-unity-framework-3.0/SPPathfinding/Graphs/AStarPathResolver.cs at master Â· lordofduct/spacepuppy-unity-framework-3.0 Â· GitHub
(note this one I implemented with both a single call, and a âsteppingâ version. The âsteppingâ version can be called repeatedly over a series of frames in a coroutine to spread the work over time when threading isnât available to you)

Keep in mind I use a BinaryHeap for fast sorting of my open list:

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.

Oh, if theyâre just trying to search there graph for neighbours.

Yeah, build your graph, and only update it any time a new one is added.

1 Like

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.

1 Like

Okay, I will give this a try.

Thank you to everyone for your help. I will update later on how this went for me.

1 Like

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:

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.

So this is the general mechanic of the game. There are ânetwork switch nodesâ (the cubes) and you can connect them with cable.

As cable is laid, I have to update the graph to know who is connected to what.

Is this anything like what youâre doing?

1 Like

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.

Thereâs multiple objects in mine as wellâŠ I just only had 2 in that demo scene.

Iâll be back shortly and Iâll show you my code.