26.12.2018, 01:47
(
Last edited by ForT; 26/12/2018 at 08:30 PM.
)
In recent days I have developed a pathfinder totally in pawn and until then it is functional. My initial idea was to develop it and make it work even though it was too slow to use and then try to adapt it to a plugin.
How does it work?
The A * algorithm in question is not the biggest problem, in fact it calculates up to 3000 nodes without crashing the server (which is done in pawn is fast). The problem is in the 'spiral' algorithm I'm using to generate the nodes before looking for a path, below is the image of how it basically works:
The spiral begins between the start and end nodes, spreading through both, to each node it creates, I use the CA_RayCastMultiLine function from top to bottom to catch all the collisions and in each collision create a new node in the place, as in the image :
All of these nodes are interconnected with each other if there is no collision between them. Thus, the path between a and b will be found even if it is under a bridge (example).
The problem is how I am connecting the nodes: For each created node I'm looping in the opposite direction of the spiral until I make a complete loop, and for each node the loop passed I'm checking if there is no collision between the nodes, checking if the difference Z is not greater than 1.8.
The discussion here is that based on this method, can you think of any better logic or way to create these nodes and connect them using CA_RayCastMultiLine? Another question is how much better performance will be if I do this same method in C ++ and adapt to a plugin, because currently to calculate a path between 50 meters with 3.0 distance between the nodes takes about 1-2 + seconds.
#EDIT 1
I found a better solution, in fact I do not need to connect them before looking for the path. The algorithm A * itself will seek the neighbors only from the necessary nodes. With this, I can now find a path between 50 meters in just 40 ms.
How does it work?
The A * algorithm in question is not the biggest problem, in fact it calculates up to 3000 nodes without crashing the server (which is done in pawn is fast). The problem is in the 'spiral' algorithm I'm using to generate the nodes before looking for a path, below is the image of how it basically works:
The spiral begins between the start and end nodes, spreading through both, to each node it creates, I use the CA_RayCastMultiLine function from top to bottom to catch all the collisions and in each collision create a new node in the place, as in the image :
All of these nodes are interconnected with each other if there is no collision between them. Thus, the path between a and b will be found even if it is under a bridge (example).
The problem is how I am connecting the nodes: For each created node I'm looping in the opposite direction of the spiral until I make a complete loop, and for each node the loop passed I'm checking if there is no collision between the nodes, checking if the difference Z is not greater than 1.8.
The discussion here is that based on this method, can you think of any better logic or way to create these nodes and connect them using CA_RayCastMultiLine? Another question is how much better performance will be if I do this same method in C ++ and adapt to a plugin, because currently to calculate a path between 50 meters with 3.0 distance between the nodes takes about 1-2 + seconds.
#EDIT 1
I found a better solution, in fact I do not need to connect them before looking for the path. The algorithm A * itself will seek the neighbors only from the necessary nodes. With this, I can now find a path between 50 meters in just 40 ms.