Most performance friendly "pathfinding" algorithm for this scenario

Unity Engine
,
21

For some reason I’m getting a StackOverflow. I’m keeping track of all the visited and making sure I don’t revisit those nodes, but nevertheless, I’m still getting the issue.

Here’s the code:

 #region Finding all generators connected to this machine
    public void GetAllConnectedGenerators()
    {
        if (direction == null)
            return;

        HashSet<(int, int)> visited = new HashSet<(int, int)>();

        generators.Clear();

        // GET THE STARTING X AND Y COORDINATE OF THIS MACHINE
        int x = direction.gridLocation.Item1;
        int y = direction.gridLocation.Item2;

        // IF THE OBJECT BELOW THE MACHINE IS NOT A CABLE THEN RETURN, NO NEED TO CHECK ANY OTHERS BECAUSE IT HAS NO CONNECTIONS
        if (!IsCable(x, y))
            return;

        // ADD THIS CABLE TO THE VISITED HASHSET
        visited.Add((x, y));

        // START THE LOOP
        GetSurroundingCables(x, y, visited);

        // NEED TO ALSO CHECK THIS TILE FOR A GENERATOR, I THINK THIS IS IMPOSSIBLE BUT WE DON'T WANT TO RULE IT OUT
        GetConnectedGenerator(x, y);
    }

    public void GetSurroundingCables(int x, int y, HashSet<(int, int)> visited)
    {
        // NORTH
        // CHECK IF THE GAMEOBJECT AT THE LOCATION IS A CABLE
        if (!visited.Contains((x, y + 1)))
        {
            if (IsCable(x, y + 1))
            {
                // GET ANY GENERATORS CONNECTED TO THAT CABLE
                GetConnectedGenerator(x, y + 1);

                // LOOP OVER THE NEXT CABLE
                GetSurroundingCables(x, y + 1, visited);

                // ADD THIS AS A VISITED TILE
                visited.Add((x, y + 1));
            }
        }
        // EAST
        if (!visited.Contains((x + 1, y)))
        {
            if (IsCable(x + 1, y))
            {
                GetConnectedGenerator(x + 1, y);

                GetSurroundingCables(x + 1, y, visited);

                visited.Add((x + 1, y));
            }
        }
        // SOUTH
        if (!visited.Contains((x, y - 1)))
        {
            if (IsCable(x, y - 1))
            {
                GetConnectedGenerator(x, y - 1);

                GetSurroundingCables(x, y - 1, visited);

                visited.Add((x, y - 1));
            }
        }
        // WEST
        if (!visited.Contains((x - 1, y)))
        {
            if (IsCable(x - 1, y))
            {
                GetConnectedGenerator(x - 1, y);

                GetSurroundingCables(x - 1, y, visited);

                visited.Add((x - 1, y));
            }
        }
    }

    public bool IsCable(int x, int y)
    {
        // IF THE ELECTRIC GRID DOES NOT CONTAIN AN OBJECT AT THAT LOCATION, THEN RETURN FALSE
        if (grid.electricGrid[x, y] == null)
            return false;

        // IF THE GAMEOBJECT AT THE LOCATION HAS THE TAG "CABLE" THEN RETURN TRUE
        if (grid.electricGrid[x, y].tag.Equals("Cable"))
            return true;

        return false;
    }

    public void GetConnectedGenerator(int x, int y)
    {
        // IF THE GAMEOBJECT AT THAT LOCATION IS NULL THEN RETURN
        if (grid.grid[x, y] == null)
            return;

        // GET THE CONNECTOR COMPONENT OF THAT GRID LOCATION
        Connector conn = grid.grid[x, y].GetComponent<Connector>();

        // IF CONN IS NOT NULL
        if (conn != null)
        {
            // IF THE GENERATORS DOES NOT CONTAIN THIS GENERATOR
            if (!generators.Contains(conn))
                // ADD THE GENERATOR
                generators.Add(conn);
        }
    }
    #endregion

What could be causing this?

22

Most definitely infinite recursion of your GetSurroundingCables method.

You’re not adding the neighbor to the visited list until after you fully visit that neighbor… and in the process of fully visiting that neighbor you’re visiting all of its neighbors… ad infinitum.

You’re doing way too much stuff in the GetSurroundingCables method. Usually when people write a graph search, that method would literally just return a list of the neighbors. Then you just add all those neighbors to the queue of nodes to inspect. It’s straightforward to write it without recursion too, using just a Queue or Stack.

Pseudocode:

Queue<GameObject> toInspect = new Queue...
HashSet<GameObject> alreadyInspected = new HashSet...
toinspect.Enqueue(startingNode);

// Keep looking at nodes until we run out.
while (toInspect.Count > 0) {
  var current = toInspect.Dequeue();
  // don't inspect anything twice
  if (alreadyInspected.Contains(current)) {
    continue;
  }

  alreadyInspected.Add(current);

  // HERE IS WHERE YOU WOULD CHECK CURRENT NODE FOR GENERATORS

  // Add all of the current node's neighbors to the inspection list.
  var neighborsList = GetNeighborsOfNode(current);
  foreach (var neighbor in neighborsList) {
    toInspect.Enqueue(neighbor);
  }
}
23

Minutes after I posted it I realised the issue, it’s exactly what you said, I don’t add them to the visited list until after, causing an infinite loop.

I should also probably mention that the new algorithm works worlds better, and it’s only called once an update is made to the cables, I’m now on 2000 FPS. Thanks everyone for all of your help.

24

So, I’m back.

Sorry I had some work to take care of.

So I looked through my existing code and unfortunately it won’t help… BUT maybe this will help, I tossed it together just now.

So basically my idea is this:

  1. Only update the graph as you add entries
  2. Each “thing” in the graph (generator, cable, etc) has a “GraphTile” component on it. It’s only used to store some graph information to speed up look up. Like the index in the graph.
  3. One of the identifying information is a “ClusterId”, this is just an index that relates it to other tiles. Basically any tile that has the same ClusterId belongs to the same “cluster” (is interconnected) as any other tile with that id. As tiles are added, we determine if it joined an existing cluster, conjoined multiple existing clusters, or is a loan tile that is a member of its own new cluster.

With that information you can tell if a machine is connected to a generator if any generator exists with the same clusterid as the generator.

The GraphTile for data:

using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using UnityEngine;

public class GraphTile : MonoBehaviour
{

    //shouldn't necessarily be edited in inspector, but will be there for information purposes. Consider making readonly via a custom editor?
    public int ClusterId; //what cluster is it a member of in the graph?
    public int GraphIndex = -1; //the index in the graph for quick lookup

    public int Type; //in my case I'm just using this to know which of the 3 types of nodes I drop it is, will be a value of 0,1,2... you can do whatever you want here. Like an enum of "generator, cable, machine, etc"

}

And the Graph:

using System.Collections;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class GraphExample : MonoBehaviour
{

    const int GRAPH_SIZE = 101; //graph is 101x101 centered around 0,0... so allowed indices are -50,50
    const int GRAPH_HALF_SIZE = GRAPH_SIZE / 2;

    public GameObject CubePrefab1;
    public GameObject CubePrefab2;
    public GameObject CubePrefab3;

    private Graph _graph = new Graph();

    private void Update()
    {
        if(Input.GetMouseButtonDown(0))
        {
            var ray = Camera.main.ScreenPointToRay(Input.mousePosition);
            var coll = this.GetComponent<Collider>();
            RaycastHit hit;
            if (coll.Raycast(ray, out hit, float.PositiveInfinity))
            {
                var pos = hit.point;
                pos.x = Mathf.Round(pos.x);
                pos.z = Mathf.Round(pos.z);

                var tile = _graph.GetNode((int)pos.x, (int)pos.z);
                if(tile == null)
                {
                    tile = Instantiate(CubePrefab1, pos, Quaternion.identity).AddComponent<GraphTile>();
                    tile.Type = 0;
                    _graph.SetNode((int)pos.x, (int)pos.z, tile);
                }
                else
                {
                    var itype = (tile.Type + 1) % 3;
                    Destroy(tile.gameObject);
                    switch(itype)
                    {
                        case 0:
                            tile = Instantiate(CubePrefab1, pos, Quaternion.identity).AddComponent<GraphTile>();
                            break;
                        case 1:
                            tile = Instantiate(CubePrefab2, pos, Quaternion.identity).AddComponent<GraphTile>();
                            break;
                        case 2:
                            tile = Instantiate(CubePrefab3, pos, Quaternion.identity).AddComponent<GraphTile>();
                            break;
                    }
                    tile.Type = itype;
                    _graph.SetNode((int)pos.x, (int)pos.z, tile);
                }

            }
        }
    }



    public class Graph : IEnumerable<GraphTile>
    {

        #region Fields

        private int _clusterIdCounter = 0;
        private GraphTile[] _grapharray = new GraphTile[GRAPH_SIZE * GRAPH_SIZE];
        private HashSet<GraphTile> _knownTiles = new HashSet<GraphTile>();

        #endregion

        #region Methods

        public GraphTile GetNode(int x, int y)
        {
            x += GRAPH_HALF_SIZE;
            y += GRAPH_HALF_SIZE;
            if (x < 0 || x >= GRAPH_SIZE || y < 0 || y >= GRAPH_SIZE) return null;

            int i = x + y * GRAPH_SIZE;
            return _grapharray[i];
        }

        public void SetNode(int x, int y, GraphTile tile)
        {
            x += GRAPH_SIZE / 2;
            y += GRAPH_SIZE / 2;
            int i = x + y * GRAPH_SIZE;

            this.SetNode(i, tile);
        }

        private void SetNode(int index, GraphTile tile)
        {
            if (index < 0 || index >= _grapharray.Length) return;

            if (tile == null)
            {
                //removed a node
                if (!object.ReferenceEquals(_grapharray[index], null))
                {
                    //slot is being marked empty, disconnect any clusters that would be

                    //TODO - perform the work of splitting/disconnecting clusters
                    _knownTiles.Remove(_grapharray[index]);
                    _grapharray[index] = null;
                }
                else
                {
                    //slot was already empty, do nothing
                    _grapharray[index] = null;
                    return;
                }
            }
            else
            {
                //added a node

                if (tile.GraphIndex >= 0 && tile.GraphIndex < _grapharray.Length && !object.ReferenceEquals(_grapharray[tile.GraphIndex], null))
                {
                    //a node exists in the slot already... lets first check if it's the same node
                    if (_grapharray[index] == tile && tile.GraphIndex == index)
                    {
                        //we set the tile to the place it already is... no need to do anything, back out now
                        return;
                    }
                    else if(_grapharray[tile.GraphIndex] == tile && index != tile.GraphIndex)
                    {
                        //we moved it, set its old spot empty
                        this.SetNode(tile.GraphIndex, null);
                    }
                    else
                    {
                        //the tile has its GraphIndex set to something arbitrary... that's a faulty state.
                        //No need to do anything  to the tile there, this new tile will just be updated to its appropriate data
                    }
                }

                if(!object.ReferenceEquals(_grapharray[index], null))
                {
                    //we placed the new tile in a spot that is already taken. Remove that tile from the known list and use its clusterid since we already know what its connected to
                    tile.ClusterId = _grapharray[index].ClusterId;
                    _knownTiles.Remove(_grapharray[index]);
                    _grapharray[index] = tile;
                    _knownTiles.Add(tile);
                }
                else
                {
                    //it's placed in an empty spot... resolve cluster connections
                    tile.ClusterId = 0;
                    tile.GraphIndex = index;
                    foreach (var neigh in GetNeighbours(index))
                    {
                        if (tile.ClusterId == 0)
                        {
                            //made a connection to a new cluster, add this new tile to that cluster
                            tile.ClusterId = neigh.ClusterId;
                        }
                        else
                        {
                            //we joined more than 1 cluster, add this new cluster to our existing cluster
                            int ci = neigh.ClusterId;
                            foreach (var t in _knownTiles)
                            {
                                if (t != null && t.ClusterId == ci) t.ClusterId = tile.ClusterId;
                            }
                        }
                    }

                    if (tile.ClusterId == 0)
                    {
                        //found no neighbours, create new cluster id
                        _clusterIdCounter++;
                        //in theory after adding 2^32 tiles you could create a cluster id that still exists if and only if that cluster never had its id adjusted by a connection...
                        //if this is a feared situation, here is where you should check existing cluster ids and increment again until a unique one is found.
                        //the odds of this happening are ridiculous, so I won't do it. There's also the consideration of the 0 meaning empty, but eh, this is again for demonstration purposes only

                        tile.ClusterId = _clusterIdCounter;
                    }
                    _grapharray[index] = tile;
                    _knownTiles.Add(tile);
                }
            }
        }

        public IEnumerable<GraphTile> GetNeighbours(GraphTile tile)
        {
            if (tile == null || tile.GraphIndex < 0 || tile.GraphIndex >= _grapharray.Length || _grapharray[tile.GraphIndex] != tile) return Enumerable.Empty<GraphTile>();

            return GetNeighbours(tile.GraphIndex);
        }

        private IEnumerable<GraphTile> GetNeighbours(int index)
        {
            if (index < 0 || index >= _grapharray.Length) yield break;

            int x, y;
            IndexToCoordinate(index, out x, out y);

            var node = GetNode(x, y + 1);
            if (node != null) yield return node;

            node = GetNode(x + 1, y);
            if (node != null) yield return node;

            node = GetNode(x, y - 1);
            if (node != null) yield return node;

            node = GetNode(x - 1, y);
            if (node != null) yield return node;
        }


        private void IndexToCoordinate(int index, out int x, out int y)
        {
            if(index < 0 || index >= _grapharray.Length)
            {
                x = int.MinValue;
                y = int.MinValue;
                return;
            }

            x = (index % GRAPH_SIZE) - GRAPH_HALF_SIZE;
            y = (index / GRAPH_SIZE) - GRAPH_HALF_SIZE;
        }

        public IEnumerator<GraphTile> GetEnumerator()
        {
            return _knownTiles.GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return _knownTiles.GetEnumerator();
        }

        #endregion

    }

}

Note, in my example here I have some mouse logic that adds some prefabs to the scene. I do this to make sure my code actually worked.

Also, my graph is centered around 0,0 and is 101 wide/long. Some logic in the ‘Graph’ class relies on this (GRAPH_SIZE, GRAPH_HALF_SIZE, and the subtraction related to it which is for offsetting around 0,0,0). You of course would want to adapt said behaviour to your own needs instead… or better generalize it however you need. I was just slapping this together quick for demonstration purposes.

Also note the TODO, I didn’t implement the cluster breaking logic. Figured get this out there and we could tackle that if we determined it necessary.

Lastly that clusterid technically has a limit in that it relies on int. You’ll see I have notes about it in the code… my idea is that if you’ve added that many nodes, you’ve also created more instances than Unity’s own InstanceId can support. I honestly don’t know what unity does when it runs out/loops… but if you want to deal with that looping, that comment in my code is where you want to deal with it.

2 Likes
25

I like this approach very much. It means that the connection “math” is already done by the time you place the cable, which is a really nice way of doing this.

For the moment, I will conduct further testing with my current implementation and if I find that it is still causing issues, this is definitely the way forward.

Thanks a lot :slight_smile:

26

could you please explain a bit more the logic you need. I.e. do you need a shortest path between generator(s) and machine(s). Are machines consuming energy? if so, how? i.e. the shortest path machine consumes the power from the connected generator and a second machine further away in the grid would not be powered?

or do you only need to understand, what kind of independent circuits exist and if such an independent grid has at least 1 generator in the circuit that enables all connected machines? (in this case, what kind of sense does your drawing with the 3 generators make)

27

This is solved now, but for future reference and anyone else who might be having a similar problem.

The logic is not the shortest path, it’s just simply “get every generator attached to this machine”. The machines do consume energy, and they will consume it equally split between all the generators (with power in them) that the machine is attached to.

  • By attached I mean there is a cable running from the generator to the machine, and this can be as many generators as you’d like.
1 Like