SA-MP Forums

Go Back   SA-MP Forums > Other > Everything and Nothing

Reply
 
Thread Tools Display Modes
Old 26/12/2018, 01:47 AM   #1
ForT
Gangsta
 
ForT's Avatar
 
Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
Default 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.
ForT is offline   Reply With Quote
Old 26/12/2018, 05:16 AM   #2
MrStead
Little Clucker
 
MrStead's Avatar
 
Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Default 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.
MrStead is offline   Reply With Quote
Old 26/12/2018, 05:19 AM   #3
MrStead
Little Clucker
 
MrStead's Avatar
 
Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Default Re: A* Pathfinder (3D map) in samp

Also, I will often update colandreas in the branch: https://github.com/Fleynaro/MultiColAndreas
MrStead is offline   Reply With Quote
Old 26/12/2018, 05:26 AM   #4
MrStead
Little Clucker
 
MrStead's Avatar
 
Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Default 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!
MrStead is offline   Reply With Quote
Old 26/12/2018, 05:29 AM   #5
MrStead
Little Clucker
 
MrStead's Avatar
 
Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Default Re: A* Pathfinder (3D map) in samp

But the issue I face working over multithreading is my server to crash sometimes
MrStead is offline   Reply With Quote
Old 26/12/2018, 03:17 PM   #6
ForT
Gangsta
 
ForT's Avatar
 
Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
Default 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

ForT is offline   Reply With Quote
Old 26/12/2018, 04:25 PM   #7
MrStead
Little Clucker
 
MrStead's Avatar
 
Join Date: Jul 2014
Location: Russia
Posts: 33
Reputation: 4
Default Re: A* Pathfinder (3D map) in samp

Quote:
Originally Posted by ForT View Post
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
MrStead is offline   Reply With Quote
Old 27/12/2018, 12:41 AM   #8
Pottus
High-roller
 
Pottus's Avatar
 
Join Date: Jun 2012
Posts: 4,856
Reputation: 1291
Default 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.
Pottus is online now   Reply With Quote
Old 27/12/2018, 06:32 PM   #9
ForT
Gangsta
 
ForT's Avatar
 
Join Date: Sep 2012
Location: Florianópolis - SC Country: Brazil
Posts: 674
Reputation: 257
Default Re: A* Pathfinder (3D map) in samp

Quote:
Originally Posted by Pottus View Post
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

ForT is offline   Reply With Quote
Old 28/12/2018, 11:29 AM   #10
Baboon
Banned
 
Join Date: Nov 2010
Location: The Netherlands
Posts: 920
Reputation: 348
Default Re: A* Pathfinder (3D map) in samp

This deserves more recognition. Excellent job.
Baboon is offline   Reply With Quote
Reply

Thread Tools
Display Modes

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


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
How To Instail Samp Cpanel Into Website To Make Samp Server Panel MrTransport Scripting Help 6 14/08/2015 05:16 PM
[HELP] How To Create Turf And /attack System For RP , Im Going To Wiki.Samp And forum Samp ? || +Rep || AmirSlaYeR Scripting Help 9 06/12/2014 02:44 PM
SAMP Add a 'A new version of samp is available' text at the start of samp client. Tomboeg General 16 29/03/2013 06:06 PM


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


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.