Pathfinding

[ziggi]

After ColAndreas integration (#7), need to add raycast pathfinding. Also need to add A* pathfinding for MapAndreas and ColAndreas.

#define FCNPC_MOVE_MODE_AUTO          (-1)
#define FCNPC_MOVE_MODE_NONE          (0)
#define FCNPC_MOVE_MODE_MAPANDREAS    (1)
#define FCNPC_MOVE_MODE_COLANDREAS    (2)

#define FCNPC_MOVE_PATHFINDING_AUTO    (-1)
#define FCNPC_MOVE_PATHFINDING_NONE    (0)
#define FCNPC_MOVE_PATHFINDING_Z       (1)
#define FCNPC_MOVE_PATHFINDING_RAYCAST (2)

native FCNPC_GoTo(npcid, Float:x, Float:y, Float:z, type = FCNPC_MOVE_TYPE_AUTO, Float:speed = FCNPC_MOVE_SPEED_AUTO, mode = FCNPC_MOVE_MODE_AUTO, pathfinding = FCNPC_MOVE_PATHFINDING_AUTO, Float:radius = 0.0, bool:setangle = true, Float:dist_offset = 0.0, stopdelay = 250);

[WoutProvost]

See my reply on this issue. I think we should let the user decide wether to use MapAndreas and path finding. I don't think it's a good idea to integrate a pathfinding method, without letting the user decide if the method should be used. If the user wants to sacrifice RAM or performance, then let him toggle on MapAndreas and/or pathfinding. If the user doesn't want to do that (because not all NPC use cases require the use of MapAndreas and/or pathfinding), then let him toggle off MapAndreas and/or pathfinding.

[ziggi]

@WoutProvost, I agree with it, thank you. Issue updated.

[Crayder]

@ziggi When and how do you plan on integrating ColAndreas? Mainly how.

[ziggi]

@Crayder I will try to merge all the source code. When I will be have good mood for this.

[Crayder]

Well, the main two functions you'll want to use are CA_RayCastLine and CA_RayCastLineAngle.

Would the way you're planning to do this work alongside the ColAndreas plugin being loaded? And would both plugins be accessing the same data that is loaded? If we would need to change the CA plugin up a bit to do so feel free to count me in.

[WoutProvost]

Since ColAndreas uses quite some resources, I really think it's best to load the plugin just once (if it is even possible of course). Maybe you can add something like CA_GetAddress(); @Crayder? I've mentioned this already in this post.

[Crayder]

Obviously we only want to load the models and map once.

And ColAndreas isn't like MapAndreas, an address isn't simple as it sounds. Both plugins would need the bullet physics library (which just means adding it to FCNPC, it's already the root of CA) and a way to share the data between them. How it will be shared is still a cloud to me.

[karimcambridge]

Please consider path finding with nodes.

[ziggi]

@karimcambridge, I doesn't want to work with nodes, because they are awful. You can use GPS plugin for this.

[karimcambridge]

Damn @ziggi.. the GPS plugin is crashy as fuck.

It would be a good learning experience though.

[BitFros7y]

Well i hate nodes, specially the ones from SA and i dont see why they are in these plugin at all (not after that FCNPC_AddPointToPath function implementation). Also if GPS plugin is crashing it doesnt mean FCNPC has to be stuffed with alternative. There is a way to communicate between them and its more than enough from my perspective...

[rt-2]

I actually use a pathfinder plugin on top of this already and it works good, I hope I can keep it if I choose to in the next version.

[dimmyi]

I recently had an idea of how to do pathfinding on the 3d map by creating and connecting nodes at runtime. You only need the CA_RayCastMultiLine function of the colandreas that is already inserted in the plugin. For more details see the post I created in the samp forum: https://forum.sa-mp.com/showthread.php?t=662209

[ziggi]

I know about A*, but it's should be implemented with threads. And I have no time for now.

[dimmyi]

Is it really necessary to calculate about 2k - 3k of nodes? Because even in pawn the execution time is irrelevant, in c ++ it should be much faster, or am I mistaken?

[ziggi]

Just try to calculate path from LS to LV with your script. SA-MP server works in one thread, so, any execution in main thread blocks processing of other plugins or scripts.

[Fleynaro]

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

[ziggi]

As you can see, I define two path finding algorithms:

#define FCNPC_MOVE_PATHFINDING_Z       (1)
#define FCNPC_MOVE_PATHFINDING_RAYCAST (2)

FCNPC_MOVE_PATHFINDING_Z - it's default A* algorithm with can be used with MapAndreas or ColAndreas. FCNPC_MOVE_PATHFINDING_RAYCAST - it's raycast path finding, where I'm planning implement something like human vision into NPC.

[WoutProvost]

Gathered some documentation:

• Pamdex's PathFinder plugin: thread and repo, uses a separate thread for path calculation
• Ryder's Dijkstra include: thread
• ForT's Pathfinder include: thread and repo
• Fleynaro's PathFinder include: pastebin
• Fleynaro's PathFinder plugin: repo
• Crayder's Pathfinding theory: thread
• Cessil's Pathfinding theory: thread

Important NavMesh settings for the NavMeshAgent/NPC:

• agent radius: about 0.7
• agent height: about 1.8
• max slope: 63.5 degrees
• step height: ????
• drop height: ????
• jump distance: ????

[Crayder]

I was looking into generating a navigational mesh for the map at one point. The most simplified way I found but never actually did was importing the map into Unity, using it's navigational mesh generator, then extracting the data needed to produce that mesh. From there we would need a plugin that could interpret this data and navigate it.

It would be best if we could efficiently generate this mesh during runtime though, like each time an object is placed test which planes could be walked on and generate part of the mesh for each slope that is walkable. You'd also want this to be able to connect the meshes for different objects so you can go under bridges and such.

It's a complicated mess.

Here's a lib:

• Recast Navigation: repo

And this repo if your interested in the Unity generated method, it already imports the map and all:

• SanAndreasUnity: repo

[WoutProvost]

The navmesh is definitely the most complicated part of this feature.

For the other part, the multithreading, I've been doing some research and experiments.

[WoutProvost]

This amazing repo imports the map in Unity. Unity is able to bake a navmesh.

Unity code available here.