[cessil]

saw this thread and thought it'd be time for a discussion thread on path finding
https://sampforum.blast.hk/showthread.php?tid=355849

I've been doing a bit of path finding in 2D space and you could apply the same techniques in a 3D space.

Here's a basic path finding problem, the player wants to get to the destination, however there's an object in the way.


This is the first step of what I've been doing, each corner of the object has a node, each node connects with another node to create a shape around the edge.
These, I call collision nodes.


Then I do another set of nodes surrounding those.
These, I called Navigation nodes.


Now from the starting position we want to create a new node that will connect to any node that it can.
So here I run a test on every Navigation node, I'll break it down to steps.

1. Create a new node at the player's position, we'll call it newNode
2. Create a new line from newNode (player's position) to a Navigation node, let's call it newLine
3. Now loop through all the collision lines and check if they intersect newLine
4. If a collision line intersects with newLine then you don't want to connect newNode to the navigation node, on the other hand, if no collision lines intersect with newNode and the navigation node then you want to add that connection
5. Repeat for every navigation node

In this picture you can see newNode connecting to the navigation nodes, the light blue are new connections, the green lines are invalid because they intersect with collision node connections


6. Do the same thing with newNode with the destination point
7. use a path finding algorithm to go from player's position to player's destination. (probably best to use AStar)

And there's the final solution for the problem.


I've seen some people using Dijkstra's which is alright but serves a different purpose to AStar, if you know where point A and point B are then you should use AStar, if B is unknown then you should use Dijkstra's

[Lorenc_]

To use this I assume we need to get all collision nodes of every object ? Still something extremely useful though it requires so much effort...

[cessil]

Well in a contained environment, like a map with a few objects it could be done a lot easier, or just having basics and using a rectangle around each object.

[RyDeR`]

And here's an implementation of Dijkstra algorithm if someone's interested.

[cessil]

Quote:

Originally Posted by RyDeR` And here's an implementation of Dijkstra algorithm if someone's interested.

To convert that to AStar all you need is a couple more variables.
In Dijkstra's you calculate the smallest cost to get to each node until you hit the target node, in AStar you calculate the cost of each node from the starting node, the distance between that node and the final node, then you add them together and choose the one with the lowest score to move on until you get the final node.

[TheArcher]

Hmm, nice trying if you can end it. I did a quick research and i've seen few algorithms about pathfinding. I wondered if its possibile to find the the nearst point from air (maybe it's just a straight line), and what about landing on the ground, it should find also the nearst point between the objects. :/

Edit: Also the old CNPC plugin had a pretty good pathfinding which was good enough for bots.

[Mauzen]

Im currently trying to develop decent path finding for RNPC. The algorithm isnt a big deal as soon as you got the nodes, creating the nodes is the real problem for me. Im planning to let NPCs move anywhere using the MapAndreas data to detect obstacles (the whole map might be transformed into a 6000x6000 bit blocked/not blocked map for speed first, 4mb more or less dont make a big difference compared to the 70mb for the full mapandreas data i guess)

Finding the corners for the nodes for obstacles is really tricky. Creating a node for every 1x1m block might be a way, but probably takes ages. I read about on-the-fly generation of nodes somewhere. Create the nodes by "moving" towards the target point until you hit an obstacle, this might at least speed it up a bit and reduce ram usage. Gonna test it later.