SA-MP Forums A* Pathfinder (3D map) in samp
 User Name Remember Me? Password
 New Account Members List Search Today's Posts Mark Forums Read

 Thread Tools Display Modes
26/12/2018, 01:47 AM   #1
ForT
Gangsta

Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
A* Pathfinder (3D map) in samp

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.
__________________

 Coming soon

Last edited by ForT; 26/12/2018 at 08:30 PM.

 26/12/2018, 05:16 AM #2 MrStead Little Clucker     Join Date: Jul 2014 Location: Russia Posts: 33 Reputation: 4 Re: A* Pathfinder (3D map) in samp I am just now making pathfinder plugin used colandreas and a*. I think it is better to implement another algorithm for CA raycastline. I use multithreading. PathFinder on CA: https://github.com/Fleynaro/PathFinderCA Any help for me could be useful. __________________ SHIP System Bot police and AI in samp
 26/12/2018, 05:19 AM #3 MrStead Little Clucker     Join Date: Jul 2014 Location: Russia Posts: 33 Reputation: 4 Re: A* Pathfinder (3D map) in samp Also, I will often update colandreas in the branch: https://github.com/Fleynaro/MultiColAndreas __________________ SHIP System Bot police and AI in samp
 26/12/2018, 05:26 AM #4 MrStead Little Clucker     Join Date: Jul 2014 Location: Russia Posts: 33 Reputation: 4 Re: A* Pathfinder (3D map) in samp For bigger distance(for example, between LS and LV) it is better to use road pathfinding and just CA pathfinding combined. + in a separate thread and then it would be cool very much! __________________ SHIP System Bot police and AI in samp
 26/12/2018, 05:29 AM #5 MrStead Little Clucker     Join Date: Jul 2014 Location: Russia Posts: 33 Reputation: 4 Re: A* Pathfinder (3D map) in samp But the issue I face working over multithreading is my server to crash sometimes __________________ SHIP System Bot police and AI in samp
26/12/2018, 03:17 PM   #6
ForT
Gangsta

Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
Re: A* Pathfinder (3D map) in samp

Does your Pathfinder work in a 3d world or is it the same as the pamdex plugin that only works 2d?
__________________

 Coming soon

26/12/2018, 04:25 PM   #7
Little Clucker

Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Re: A* Pathfinder (3D map) in samp

Quote:
 Originally Posted by ForT Does your Pathfinder work in a 3d world or is it the same as the pamdex plugin that only works 2d?
works in 3d. Besides road path finding, here is 2d yet

 27/12/2018, 12:41 AM #8 Pottus High-roller     Join Date: Jun 2012 Posts: 4,856 Reputation: 1291 Re: A* Pathfinder (3D map) in samp I would adapt everything to a plugin however doing your rough work in pawn then migrating those ideas to c++ might be faster for development to some degree.
27/12/2018, 06:32 PM   #9
ForT
Gangsta

Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
Re: A* Pathfinder (3D map) in samp

Quote:
 Originally Posted by Pottus I would adapt everything to a plugin however doing your rough work in pawn then migrating those ideas to c++ might be faster for development to some degree.
I uploaded the include in github and for now is the maximum I could do:
https://github.com/fort-samp/3d-pathfinder
__________________

 Coming soon

 28/12/2018, 11:29 AM #10 Baboon Banned   Join Date: Nov 2010 Location: The Netherlands Posts: 920 Reputation: 348 Re: A* Pathfinder (3D map) in samp This deserves more recognition. Excellent job.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post [Plugin] PathFinder by Pamdex pamdex Plugin Development 147 16/01/2019 04:53 PM [Plugin] PathFinder jeanluc162 Plugin Development 19 05/09/2015 07:39 PM MrTransport Scripting Help 6 14/08/2015 05:16 PM AmirSlaYeR Scripting Help 9 06/12/2014 02:44 PM Tomboeg General 16 29/03/2013 06:06 PM

All times are GMT. The time now is 10:10 AM.

 -- (EN) English -- (RU) Русски Contact Us - SA-MP - Archive - Top