SA-MP Forums

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

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

saw this thread and thought it'd be time for a discussion thread on path finding
http://forum.sa-mp.com/showthread.php?t=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
cessil is offline   Reply With Quote
Old 02/07/2012, 05:41 AM   #2
Lorenc_
High-roller
 
Lorenc_'s Avatar
 
Join Date: Jan 2010
Location: Australia
Posts: 4,122
Reputation: 928
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...
__________________

192.169.82.202:7777 - An awesome CnR server consisting of doozy features! Come, we have players!


Lorenc_ is offline   Reply With Quote
Old 02/07/2012, 09:54 AM   #3
cessil
Beta Tester
 
cessil's Avatar
 
Join Date: Apr 2009
Posts: 2,569
Reputation: 256
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
Y_Less
Beta Tester
 
Y_Less's Avatar
 
Join Date: Jun 2008
Location: 629 - git.io/Y
Posts: 18,314
Reputation: 2579
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
High-roller
 
[HLF]Southclaw's Avatar
 
Join Date: Apr 2009
Location: England
Posts: 4,511
Reputation: 1057
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!
[HLF]Southclaw is offline   Reply With Quote
Old 02/07/2012, 07:52 PM   #6
RyDeR`
High-roller
 
RyDeR`'s Avatar
 
Join Date: Feb 2009
Location: Belgium
Posts: 3,133
Reputation: 645
Default Re: Path Finding

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

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

Quote:
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
High-roller
 
TheArcher's Avatar
 
Join Date: Dec 2009
Location: Home
Posts: 2,509
Reputation: 233
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
High-roller
 
Mauzen's Avatar
 
Join Date: Jun 2007
Location: Western Germany
Posts: 4,329
Reputation: 1084
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 online now   Reply With Quote
Reply

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 09:24 AM.


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