I have been trying to create path finding algorithm based on node connection.
Basically, a node can have any number of neighbors and they are linked using List.
Now, I have tried to make it thread safe and multi agent ready, so I realized that I will need to do :
separate actual node connection info with nav path finding data. I am using basic A* path finding so all the data storage for flagging isVisitedNode, etc had to be separated from the node connection data sets.
Initialize the data for path finding when calculation is called.
Now, putting the performance aside, the pure initialization of navigation data alone is a bit costly, because it basically needs to go through all the nodes in the scene and then recreate the nav data set so the A* can walk through it. I am wondering if anyone had experience of dealing with such case? Is this unavoidable process? Is there any trick or cleaver way to optimize and use as little memory as possible?
If there are 100s of agents in the scene they all be doing this initialization of creating path nodes then it can quickly add up.
Also I found tracking of navigation nodes synced with the actual node connection difficult, because of the neighbors so I have assigned the id to each nodes in the scene and then assgin the same id that is corresponding to the connection nodes when I recreate navigation nodes and its neighbors. And I use dictionary to look up the navigation nodes using that id. This works, but creating dictionary of pair (id , nav node) for a* to walk through costs a lots of memory per path calculation request.
If anyone have good experience / insight into path finding system, can you tip me off please?
What do you mean by initialise the data for pathfinding? There shouldn’t be any extra data to initialise.
Sure you will create some data during the path finding process. But initialisation should just be a case of setting up a collection for your closed and open nodes, nothing more.
Yeah your whole process sounds a bit wonky. What kind of graph are you building?
We use a grid for our pathfinding that we build by just starting at one end of the map and shooting raycasts straight down onto the terrain in 1 unit increments. From there getting the neighbors of a given node is as simple as looking up, down, left, right, and diagonal in the grid index.
class Node
{
// the indices of this node's position in the grid
int X;
int Y;
// the graph this node belongs to
Node[,] graph;
List<Node> GetNeighbors()
{
// obviously sanity check X and Y first, but omitted here
neighbors.Add(graph[X - 1, Y]);
neighbors.Add(graph[X+1, Y]);
neighbors.Add(graph[X, Y-1]);
// etc etc
}
}
Yeah I am talking about setting up those collections for the path finding purpose. If you have many nodes, then creating collection of opened nodes ( which is well, all the nodes in the scene ) this is almost the same cost as having duplicate of the nodes themselves as far as the cost of the memory goes.
And because there can be any number of neighbor nodes ( the system is not a grid ) I can’t use a simple look up left right up down to get the connected nodes.
I don’t have experience with A* or really anything to do with games so this is purely a theoretical suggestion ..
The easiest and safest way to handle multithreading is with immutable structures. In other words, create classes which, once constructed, can never change. In this way, the threads can all have simultaneous read access and don’t have to worry about interfering with one another.
I think this will help solve your “initialization cost” problem as well.
I don’t think you need to redo all this work for each agent.
If there are certain parts of the structure which must be mutable because of the implementation of A*, this is a great opportunity for the flyweight design pattern. Consider your path finding data class, are there pieces which can be immutable and shared amongst all agents? Separate that component into it’s own class, then simply reference the immutable component from the original class. In this way, you only need to generate the immutable portions once and can share it with all the agents. This will possibly save some initialization time and memory and will be easier to reason with in a multi threaded environment.
Yeap, That is pretty much what I have implemented so far. I have say node connection data which is shared and there is collection data for nav calculation purpose. I was just wondering if there is any way to reduce those nav calculation data storage, because they are being initialized per agent and they are map size dependent.
I still don’t get why you have anything map size dependent on a per agent basis.
Your map data should look something like this. This gets initialised once in the game for every Node.
public class Node (){
public List<Node> GetNeighbours() {...}
}
Then at pathfinding time you create something like this. (Might perform better as a struct, bench mark it).
public class NodeInfo (){
public Node thisNode;
public Node lastNode;
public float hCost;
public float gCost;
public float fCost;
}
NodeInfo must be initialised per Node visited, per path, per agent. But the whole point of A* is it’s allows you to visit the minimum number of nodes needed to find the shortest path.
Edit: This is basically the same as what @eisenpony said. The Node class represents (mostly) immutable map data. The NodeInfo class represents the mutable data that needs to occur per thread.
Humm… There are immutable map data already which is where I get the info for neighbours and so on.
But the way I am initializing the path finding data is that I create NodeInfo like data that has information such as isVisited and I reset them per node and use those collection to walk through the path. Perhaps I am doing something that isn’t memory friendly in the first place.
Here is snip set of the path finding code :
private IEnumerator FindPath(List<SlotBase> slotBaseToInitialize, SlotBase slotStart, SlotBase slotEnd)
{
resultNode = null;
InitNavData(slotBaseToInitialize);
NavNode startNode;
if (!nodes.TryGetValue(slotStart.GetID(), out startNode))
yield break;
NavNode endNode;
if (!nodes.TryGetValue(slotEnd.GetID(), out endNode))
yield break;
startNode.cost = 0;
startNode.isVisited = false;
startNode.parentNode = null;
NavNode nextNode;
int cnt = 0;
while (unVisitedList.Count > 0)
{
// find min distance node
nextNode = SlotWithLeastCost();
if (nextNode == null)
{
Debug.Log("Failed to calculate path : " + cnt);
yield break;
}
cnt++;
nextNode.isVisited = true;
unVisitedList.Remove(nextNode.slot.GetID());
//Debug.Log("nextNode nodeTo : " + nextNode.gameObject.name);
if (nextNode == endNode)
{
// Debug.Log("Shortest path found");
break;
}
// now nextNode is neighbour node with smallest distance
for (int i = 0; i < nextNode.slot.GetNeighborsCount(); i++)
{
ushort nID = nextNode.slot.GetNeighbors()[i].GetID();
NavNode nNode;
if (nodes.TryGetValue(nID, out nNode))
{
if (!nNode.isVisited)
{
float costToNeighbor = nextNode.cost + Vector2.SqrMagnitude(nextNode.slot.GetPosition() - nNode.slot.GetPosition());
if (nNode.cost > costToNeighbor)
{
nNode.cost = costToNeighbor;
nNode.parentNode = nextNode;
}
}
}
}
}
resultNode = endNode;
yield break;
}
unVisitedList stores ID of every nodes in the scene. I generate that collection in the initialization code. ID of the nodes are required because the graph is not necessary a grid and I found that there isn’t very nice way to quickly link between nodeInfo and its Neighbors.
What I am saying is, yes, I can find neighbor nodes from the current node, but it isn’t easy to find nodeinfo associated with those neighbor nodes, because the nodeInfo has link to the nodes, but not the otherway around. ( since the nodeinfo is being generated per agent per path finding , they can’t be linked to the node itself. ) If it was a simple grid system, then I can probably get the nodeinfo using the position of the grid. But I can’t do that. So I generate Dictionary collection with <ID, nodeinfo> and ID is the same ID used for the nodes. What I have found was that it is a bit costly to initialize the Dictionary in the first place because it is map size dependent ( number of nodes ) and even if I cache it and reuse them to reduce GC, I still have to go through the set of nodes to see if anything has added or removed etc. This initialization code is around 1/3 - 1/2 of cost of pathfinding.
That’s not A*. That might be where our wires are getting crossed.
In A*, your unvisited list contains the start Node. Then each iteration you remove the lowest cost Node from unvisited, and add all of its neighbours to unvisited.
So you only ever need to initialise the data for the nodes you visit. And you only initialise them when you visit them.
In the ‘average’ case you’ll only visit a small fraction of nodes.
Note that in practice because you don’t care about the order of the nodes in unvisited, a hashset often has better performance.
I also use a dictionary for this purpose with A*. But it only ever contains the nodes that are relevant.
So first check if the dictionary contains the key, and if not, create a NodeInfo and add it.
I see… I think my path finding algorithm may be slightly different. Perhaps it isn’t A* but something a bit close to it. I am not sure what it is based on. I will try your way so the unvisited list gets added as it go along. Interesting.
Using coroutines isn’t really multithreading…so what you’re doing is “thread safe” in your scope, because two coroutines will never try to set a field at the same time and cause deadlock. You’re not threading, you’re doing synchronous processing. The difference is that you won’t receive any of the benefits of threading.
One performance tip is that you’re killing yourself iterating over multiple lists. If the order of the elements don’t matter, you can save yourself a lot of CPU cycles by switching to a data structure that doesn’t care about order, like a HashSet as suggested, and enumerating over it instead of iterating. Just be sure to skip the garbage allocating foreach and use an enumerator manually.
I would suggest moving to A*. A* would be far more performant then what you have set up, by virtue of the fact that it explores far fewer nodes on the graph. Choosing the correct algorithm beats optimizing the wrong algorithm every day of the week.
What you’ve built is essentially Dijkstra’s algorithm. Dijkstra’s algorithm is a breadth first search for the shortest path. Which means it examines nodes in all directions until it finds a path. A* on the other hand is a directed search. Meaning it examines the nodes in the direction of the destination first. If an admissible heuristic exists, A* will always do better.
Note that even with Dijkstra’s there is no need to initialize the entire collection of nodes. You should only be initializing nodes and adding them to the unvisited list when they turn up as a neighbor of a node you are examining. This will dramatically improve performance in all but the worst case scenario (ie no path exists).
A* typically involves two collections
The closed set requires add and contains operations, meaning something like a HashSet is ideal.
The open set requires add, remove, contains and min operations. The remove operations suggest a HashSet. A sorted collection of some sort might also work. If performance was critical, I would probably benchmark several types of collections.
Either way fixing the algorithm will likely boost performance more then choosing the right collection.
I have implemented A* and now generating the open and closed collections on the fly. This indeed removes the initial data generation to minimal and scales up per visited nodes. I guess the memory cost for generating the visited nodes are unavoidable.
Anyway, I did take a look at the heap storage and hashset, they seems to be very cool indeed. While I was thinking about the collection types, I was wondering what would be the good way to associate the path finding data nodeinfo and their corresponding shared , unchanged node ? The biggest problem is when I call upon original data to get the neighbours, I can get them in form of list of neighbour nodes, but then there is no way for me to link that back to the nav path data nodeinfo that I generate on the fly. Which is why I am using dictionary to keep them in track by ID number.
Even if you use the grid I don’t see how this can be done if you are separating nodeinfo data from node data. There must be some way to link those together so that getting neighbour nodeinfo is possible. I can’t think of better way than using Dictionary at the moment. Using grid doesn’t help, because using coordinates means nothing if you can’t get the nodeinfo back on that specific coordinates. NodeInfo has to be stored in some kind of another grid set of something.
@Dameon I am using threading at the moment. I know the code I have pasted does look like a normal corroutine, but I am calling it using the threaded co routine. It is running on the background thread. Because there could be more than one agent searching the path at any time running on the background thread, I had to separate the nav path finding data from the nodes data.
Do you mean “typically your open set is a priority queue”? In A* openset is the one you use to get the least cost node, and the closed one is there to just check if it exist or not.
Yeap, I also checked that out, and after changing the algorithm to A* all my collections are now Dictionary. I had to check both openset and closedset to see if the nodeinfo has already been created or not, and create new one on the fly if both of them didn’t have it.
Yeah, that is exactly what I am doing. I was just wondering if there is any other trick out there. It’s also pity and I will probably have to experiment a bit, but creating heap and stuffs like that using Dictionary may be too much of pain, or it may be too slow.
I think I have reached the point where I can move on to the other things for now and come back when things needs to be optimised again.
I will try your way so the unvisited list gets added as it go along. Interesting.