For my first project I’m trying to create a game in the ‘Basebuilding’ genre.
Low on animation, low on modeling.
The game consists of 2 fases.
‘Build Fase’
‘Fight Fase’
In the ‘FightFase’ the player will have to move units through the structure made in the ‘BuildFase’.
The player connects prefabs containing nodes.
Each prefab setion comes with a series of nodes. The most complex section will have a ‘center node’ and one node on each side.
The average section will have walls, floor, ceiling , so maybe 4 nodes on average.
Each time a section is placed, positions of all the nodes in it are stored in a List.
This is what such a structure could end up to be:
And the List of Vector3’s belonging to it:
Now I’ve looked up some pathfinding tutorials.
Most of them discribe looking for adjacent nodes, getting to the desired location in as less ‘steps’ as posible, creating a path backtracking through the steps.
I did some testing.
When I loopt through the indexnubers of a list of around 2400!!! nodes.(That is around 600 average sections) Comparing if the indexnuber contains the Vector3 I’m looking for during that itteration of the loop. ( it takes just under a second just to find 1 Vector in that list.
Going through all itterations finding the optimal path in all directions will take a very long time!
Am I going at this the wrong way, are there better solutions for implementing pathfinding in this situation?
Whenever you have nodes [with weights], Dijkstra’s algorithm is a good solution. Its Wikipedia entry is a good overview, as it has a lot of flashy images, but try to find other sources if you want to actually use it, since the description is very abstract.
The good old A* (Wikipedia) might also be helpful, that is the algorithm that we used in problems like yours.
Both algorithms are proven to be good solutions when trying to find a path through a network of nodes.
Another vote for Dijkstra. It’s quite clever, works in 3D, performs reasonalbly well, and is easy to adapt to most cases. If you also have your own nodes already set up, this algorithm requires very little additional memory overhead, and the algorithm can run in a coroutine, which is really nice if you don’t need the path right away (I let my actors idle while the path processing is running in the background).
I used Dijkstra for a small app that would plot the shortest course between two solar systems back when Elite Dangerous came out and I got access to a partial DB of some 120’000 star Systems. Given a ship’s single jump range the code then built the graph. With an average of 5 stars in range of each star (i.e. 5 Connections per vertex), plotting a 17 jump route took less than a second, but somewhere around 25 jumps run times increased noticeably, so you’ll need to manage the complexity of your graph (your example Looks very manageable).
Dutch name, I’m going for the Dutch guy. I had a similar approach in mind.
I just had a really interesting thought !
When the structure is filled with walls on the outside, and is sectioned off with walls on the inside (small rooms, corridors etc) this thing will aproximately have a 40-60 ratio between ‘Centernodes’ and ‘Edgenodes’.
A ‘Centernode’ will never be next to a ‘Edgenode’ and visaversa. Red dots and white dots will Always alternate. So making two Lists/Arrays, alternating searching for the next node, things could be done in aproximately half the time!
If you find yourself in a position where you have to loop through the entire list looking for 1 specific coordinate, there is probably some way you could optimize your data structures to reduce the amount of work you need to do. Maybe each node caches a list of adjacent nodes, or maybe you store your coordinates in some sort of tree or hash table so that you can find a specific coordinate more quickly.
But even if you have to search the entire list, spending 1 second to iterate over 2400 items sounds pretty slow. I bet you are doing something wrong in that loop (or something wrong in your speed test).
If your map is just a set of equal-size cubes arranged in a grid, then I would forget Dijkstra’s algorithm and A* and just use breadth-first search. It’s very simple, and in this case it’s probably faster.
Breadth First Search is basically just Dijkstra with a constant edge cost, thusly removing the step from the algorithm that tallies the cost. And well, since your nodes are all equidistant, their edge costs are constant, so you can ignore the edge cost.
Note A* is just Dijkstra with a heuristic applied to the cost.
So basically all 3 algorithms are just iteratively more complex versions of the former. Each adding more information to better suit certain requirements (by adding a heuristic to Dijkstra you try the closer path first reducing the amount of iterations, the added complexity tries to make it more performant… where as Dijkstra adds to BFS an edge cost, which can be used to describe a non-uniform graph, adding performance cost to better describe a non-uniform space).
I had a similar approach in mind.