SA-MP Forums

Go Back   SA-MP Forums > SA-MP Scripting and Plugins > Scripting Help > Discussion

Thread Tools Display Modes
Old 02/07/2012, 03:31 AM   #1
cessil's Avatar
Join Date: Apr 2009
Posts: 2,742
Reputation: 283
Default Path Finding

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.

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
cessil is offline   Reply With Quote
Old 02/07/2012, 05:41 AM   #2
Lorenc_'s Avatar
Join Date: Jan 2010
Location: Australia
Posts: 4,224
Reputation: 1006
Default Re: Path Finding

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...
Lorenc_ is offline   Reply With Quote
Old 02/07/2012, 09:54 AM   #3
cessil's Avatar
Join Date: Apr 2009
Posts: 2,742
Reputation: 283
Default Re: Path Finding

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.
cessil is offline   Reply With Quote
Old 02/07/2012, 10:08 AM   #4
Spam Machine
Y_Less's Avatar
Join Date: Jun 2008
Location: 629 -
Posts: 14,542
Reputation: 2780
Default Re: Path Finding

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.
Y_Less is offline   Reply With Quote
Old 02/07/2012, 07:06 PM   #5
[HLF]Southclaw's Avatar
Join Date: Apr 2009
Location: England
Posts: 4,462
Reputation: 1122
Default Re: Path Finding

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!

Motion graphic gifs made on request
[HLF]Southclaw is offline   Reply With Quote
Old 02/07/2012, 07:52 PM   #6
RyDeR`'s Avatar
Join Date: Feb 2009
Location: Belgium
Posts: 3,097
Reputation: 657
Default Re: Path Finding

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

RyDeR` is offline   Reply With Quote
Old 03/07/2012, 01:47 AM   #7
cessil's Avatar
Join Date: Apr 2009
Posts: 2,742
Reputation: 283
Default Re: Path Finding

Originally Posted by RyDeR` View Post
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.
cessil is offline   Reply With Quote
Old 07/07/2012, 07:09 PM   #8
TheArcher's Avatar
Join Date: Dec 2009
Location: Home
Posts: 2,464
Reputation: 241
Default Re: Path Finding

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.
TheArcher is offline   Reply With Quote
Old 10/07/2012, 10:57 PM   #9
Mauzen's Avatar
Join Date: Jun 2007
Location: Western Germany
Posts: 4,786
Reputation: 1313
Default Re: Path Finding

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.
Mauzen is offline   Reply With Quote

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
Object Path Jeroen52 Scripting Help 4 30/05/2012 07:21 PM
Problem with pawno path Jay. Help Archive 8 18/06/2010 08:33 PM
[HELP] File Path Haegon Help Archive 11 07/07/2009 08:02 AM

All times are GMT. The time now is 03:38 AM.

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