For those who don’t know, A* is simply a better form of Dijkstra, which in turn is a algorithm that finds the best route from point A to point B. I’ve already implemented Dijkstra once, but today I wanted to try A*.
Mind noticing I’ve yet to add parallel scripting to this, since I’m interested in making A HORDE OF FLIES that chases people, using this algorithm to go around corners and such (very terrifying) and maybe even some boid stuff to make them move like an organized cloud.
This is really cool! Does it merely raycast to check if it can continue in a certain direction?
Yes. The algorithm raycasts to find its possible neighbors (green) for every step it takes (red).
Hi, I believe this could be optimized by doing an initial flood fill so that raycasts are not needed (later). However, a downside is that any real-time changes to the map might cause issues.
The problem with such a mechanic is that, I believe, small holes/tunnels/compartments might become inaccessible, forcing me to reduce the space between the nodes and end up making the whole thing more dense. Either that or I’ll have to set up a bunch of checkpoints all throughout the map.
With the way I’m doing it, the node table just fills itself up as needed. Also, do players count as real-time changes? The enemies will fly towards them.
Either way, I will already optimize it by:
Thx for the feedback btw
I believe you can solve the holes/tunnels issue by using octrees. This would enable you to have dynamic densities throughout the whole map.
Oh, I’ve never tried that. I’ll try to learn octrees and then, if successful, add them in. Thanks a lot for the suggestion, I wouldn’t have found that myself.