hi ive created an a* algorithm for a space themed game, i have created this algorithm well i think, it works perfectly, however im not sure if i have made the algorithm correctly, which may effect the overall performance of the AI. i would show the code but its a bit messy at the moment and im only concerned with one part which i explain below.
the main part i am worried about is how it handles the closed list. to get a new node the algorithm will scan through the closed list and for each node it will scan all neighbours around the new node, if a nodes neighbour is very favourable and is not on the closed list it will be added. this cycle repeats until the goal is found.
now this sounds good, however, if i am finding a path for an npc through a 1000x1000x1000 grid map, each node on the closed list will have 23 neighbours, which means if i had a path which spanned half the map, the algorithm will have to calculate the favourability of 2875000 neighbours to reach the goal. (23500500)/2 – neighbournode amountcycles it took to find goal/half(half because the list increases by 1 every cycle until 500 (might be correct))
the main solution i have came up with is if i were to read the closed list from the end to the beginning instead of beginning to end so that it would start off at the last node found than the first ones found. however it feels hacky as i would rather make the algorithm correctly.
I’d suggest making a small testbed to see if it works, and as expected. Try on a 5x5x5.
I think that A* is effective for this type of problem, and it is possible that you are holding onto more memory than you need to if you have to traverse all 1000x1000x1000 nodes.
There are few good reasons to iterate over a 1000x1000x1000 node graph.
If the voxel graph is static, you are making a space game – most of space is, well, empty space. You probably do not need to represent each voxel as a distinct node in the graph.
Also, are you using a priority queue data structure to sort your frontier by priority? If not, you’ll get a massive performance hit; the tightest big-O for getting the maximum of an unordered list is O(n), whereas popping from and pushing to a well-designed priority queue can give you O(log(n)) performance.
If your game has a static graph, you could conduct a greedy voxel meshing operation to collapse the 1000^3 graph into a graph where each node represents a volume of space that is traversable and each edge represents adjacent volumes. Depending on how sparse the world is, you will likely get a performance benefit. If the graph is static, this step could be pre-processed and loaded from a modulescript.
The above approach introduces a new challenge: given a position, how do we find the node that represents the volume at that position? If we represent our set of traversable regions using a octree data structure, we can locate the volume at a given position in log(n) time.
Together, this should give you something way more performant.
To implement a priority queue could I just add priorities to each position in the closed group depending on when they were chosen, and then read the highest priorities to the the lowest for the next position? (if the position with that priority does not have a closer route or has ended then get the last priority)
Also I really like the idea of using a greedy voxel operation with an octree data structure, Ill definitely check out that method and give it a try.
I dont remember much of it, but I think you can bind custom nodes instead of using a grid, resulting in less iterations. You could set them at the corners of obstacles, like a house, for example. The neighbors would be set by raycasting every other node to see if anything is blocking the paths. After you do this, the nodes are set to be used on the A* function.
I tried this once and it seemed to work, though I ended up using a node grid because my game qas using a grid map.
You need to implement a data structure that provides a Priority Queue implementation.
If you are just adding or removing from a table naively, you need to conduct a linear search to find the closest element every time. This gives you O(n) operations. A binary min heap will likely be the easiest for you to implement.
I have an example of a Lua implementation of such a data structure, but it does not appear to be on my Github. I have finals this week so I’ll update this thread with a link when I have the time to put it on Github.