PDA

View Full Version : Path Finding

cessil
02/07/2012, 03:31 AM
saw this thread and thought it'd be time for a discussion thread on path finding

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.
http://i.imgur.com/pQ7M4.jpg

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.
http://i.imgur.com/4qtUm.jpg

Then I do another set of nodes surrounding those.
These, I called Navigation nodes.
http://i.imgur.com/z7Ee6.jpg

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.
http://i.imgur.com/wKy0y.jpg

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_
02/07/2012, 05:41 AM
To use this I assume we need to get all collision nodes of every object :o? Still something extremely useful though it requires so much effort...

cessil
02/07/2012, 09:54 AM
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.

Y_Less
02/07/2012, 10:08 AM
You can probably do better than that for collisions - all objects ALREADY have a rectangle around them called the "bounding box" (they also have a "bounding sphere"). This is a box that the collision of an object is guaranteed to be smaller than, and is easy to check before the more complex collisions need to be done - if you're not in the box then you're not in the object.

I've thought a few times about using this information to determine the approximate size of an object to use that data in streamers (skyscrapers should stream with higher priority than flower pots for example when there are too many objects about) and you could use that here too if someone were to write something to load them. Plus, there are nav-nodes for many objects already so that should be quite simple to develop too if you were to go about this in the right way.

[HLF]Southclaw
02/07/2012, 07:06 PM
I've wondered about this too, I set up a testing ground at a small town in north Tierra Robada (Forgot what it's called) Y_Less may remember my post about checking if a line intersects a polygon, that's what it was for.

I never really got anywhere with it but the general idea was when the player is running/walking/crouching a "noise level" variable is set, then a "zombie" (Deer object) will "hear" the sound depending on "volume" and distance.

He will then proceed to try and figure out a way to get to the player, this was the part I never completed as I kind of fucked up the line intersection check (It was a bit too advanced I think) and the pathfinding. The main thing is, the idea was there! I might give it a go now that you've alerted my of RNPC, I'm very interested in AI and I really want to figure it out and try write some basic systems!

RyDeR`
02/07/2012, 07:52 PM
And here's an implementation of Dijkstra (http://forum.sa-mp.com/showthread.php?t=336000) algorithm if someone's interested.

cessil
03/07/2012, 01:47 AM
And here's an implementation of Dijkstra (http://forum.sa-mp.com/showthread.php?t=336000) 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
07/07/2012, 07:09 PM
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
10/07/2012, 10:57 PM
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.