A* Pathfinder (3D map) in samp

A* Pathfinder (3D map) in samp - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: Other (https://sampforum.blast.hk/forumdisplay.php?fid=7)
+--- Forum: Everything and Nothing (https://sampforum.blast.hk/forumdisplay.php?fid=23)
+--- Thread: A* Pathfinder (3D map) in samp (/showthread.php?tid=662209)

Pages: 1 2

A* Pathfinder (3D map) in samp - ForT - 26.12.2018

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.

Re: A* Pathfinder (3D map) in samp - MrStead - 26.12.2018

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.

Re: A* Pathfinder (3D map) in samp - MrStead - 26.12.2018

Also, I will often update colandreas in the branch: https://github.com/Fleynaro/MultiColAndreas

Re: A* Pathfinder (3D map) in samp - MrStead - 26.12.2018

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!

Re: A* Pathfinder (3D map) in samp - MrStead - 26.12.2018

But the issue I face working over multithreading is my server to crash sometimes

Re: A* Pathfinder (3D map) in samp - ForT - 26.12.2018

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

Re: A* Pathfinder (3D map) in samp - MrStead - 26.12.2018

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

Re: A* Pathfinder (3D map) in samp - Pottus - 27.12.2018

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.

Re: A* Pathfinder (3D map) in samp - ForT - 27.12.2018

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/dimmyi/3d-pathfinder

Re: A* Pathfinder (3D map) in samp - Baboon - 28.12.2018

This deserves more recognition. Excellent job.

Re: A* Pathfinder (3D map) in samp - Pottus - 29.12.2018

Quote:

Originally Posted by ForT

I uploaded the include in github and for now is the maximum I could do:
https://github.com/fort-samp/3d-pathfinder

It would probably be a lot faster writing this into the plugin, it isn't even that overly complex so it probably wouldn't take long to do. That would remove a significant bottle neck, after that next step is to make it threaded and return the results in a callback and continue to refine the pathfinding algorithm.

Re: A* Pathfinder (3D map) in samp - Crayder - 29.12.2018

We could perhaps just add a similar feature to ColAndreas. With that we could simply create a 0.75x2.0x[length between nodes] prism between the nodes and collision test that object to be absolutely sure a player body can fit, if that doesn't affect performance too much. If it does affect performance a lot then ray's will have to suffice.

The hardest part after that is getting the nodes... Which I wrote a whole thread [here] about a while back. We'd have to the nodes for the whole 3D world (or even custom maps) with 63 degree slope limits, small objects, and many other factors in mind.

Re: A* Pathfinder (3D map) in samp - MrStead - 30.12.2018

My plugin will come to the realease soon.
https://github.com/Fleynaro/PathFinderCA

[SPOILER]

[/SPOILER]

Re: A* Pathfinder (3D map) in samp - MrStead - 30.12.2018

Also I created PathFinder in pawn long ago: https://pastebin.com/ere8c6EX

Re: A* Pathfinder (3D map) in samp - ForT - 30.12.2018

Quote:

Originally Posted by MrStead

My plugin will come to the realease soon.
https://github.com/Fleynaro/PathFinderCA

[SPOILER]

[/SPOILER]

For the picture it seems that works the same way as the GPS plugin, but inside homes, away from the roads also works?

Re: A* Pathfinder (3D map) in samp - MrStead - 30.12.2018

Quote:

Originally Posted by ForT

For the picture it seems that works the same way as the GPS plugin, but inside homes, away from the roads also works?

yes, it does! it's a mixture of road finding and physic finding

Re: A* Pathfinder (3D map) in samp - Kar - 30.12.2018

Quote:

Originally Posted by MrStead

yes, it does! it's a mixture of road finding and physic finding

Can u create a thread for the plugin?

What are the advantages of using this over the GPS plugin?

Re: A* Pathfinder (3D map) in samp - kristo - 31.12.2018

Quote:

Originally Posted by Kar

What are the advantages of using this over the GPS plugin?

If pulled off well, this plugin could be way better than mine. Mine uses node data dumped out of the game while this uses a large amount of raycasts to generate paths from scratch. I'm not sure about the performance and reliability of this approach, but it is much more versatile, making it possible to generate paths in any environment, not just the road network. I'm not a fan of the current API though, it has the same issues as RouteConnector's does.

Re: A* Pathfinder (3D map) in samp - Pottus - 01.01.2019

You guys are really taking things to the next level here for SA-MP real visionaries! I would really like to have a tour of your test server MrStead show me what you got.

Re: A* Pathfinder (3D map) in samp - Kar - 01.01.2019

Quote:

Originally Posted by Pottus

You guys are really taking things to the next level here for SA-MP real visionaries! I would really like to have a tour of your test server MrStead show me what you got.

It's about damn time