SA-MP Forums

Go Back   SA-MP Forums > SA-MP Scripting and Plugins > Filterscripts > Includes

Reply
 
Thread Tools Display Modes
Old 20/04/2012, 06:44 PM   #1
RyDeR`
High-roller
 
RyDeR`'s Avatar
 
Join Date: Feb 2009
Location: Belgium
Posts: 3,133
Reputation: 645
Default Dijkstra.inc - Dijkstra pathfinding algorithm

Introduction

This is a basic implementation of the dijkstra algorithm, including a basic example of a GPS system working on nodes, using this include.

Function(s)

We have only one basic function:
pawn Code:
stock Dijkstra(const aeNodes[][], iStart, iEnd, aiPath[], const iSize = sizeof(aeNodes))

Here's how the node array should look like:
pawn Code:
enum e_Nodes {
    Float: e_fNX,
    Float: e_fNY,
    Float: e_fNZ,
    e_iLink1,
    e_iLink2,
    e_iLink3,
    e_iLink4
};
If the link is invalid you have to use -1. See usage in the example filterscript.

Example

In the link below, there's a basic GPS system using this pathfinding include. The nodes included are complete LV nodes and were made by me a while ago. I will do the whole San Andreas world once I have some free time and when I feel like it. I don't recommend using the default San Andreas nodes from NODESX.DAT with this include as there are too much to calculate in a reasonable time.


GPS.pwn

Download

Dijkstra.inc
__________________

Sup?

Last edited by RyDeR`; 17/05/2012 at 08:38 AM.
RyDeR` is offline   Reply With Quote
Old 20/04/2012, 07:11 PM   #2
Danny
High-roller
 
Danny's Avatar
 
Join Date: Jul 2010
Location: In a galaxy far far away, near the Netherlands
Posts: 1,761
Reputation: 1519
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

So, this is basically a sort of system including positions for checkpoints and the system calculates where's the closest position is? Am I right with this? Cause I'm afraid I don't really understand the working and usages of this system.
__________________
I hate reputation-askers, so DON'T ASK, JUST EARN!

come into my life, it's a man made paradise

http://www.buzzfeed.com/norbertobric...omp-stomp-clap
Danny is offline   Reply With Quote
Old 20/04/2012, 07:15 PM   #3
Fj0rtizFredde
High-roller
 
Fj0rtizFredde's Avatar
 
Join Date: Jun 2008
Location: Sweden
Posts: 1,076
Reputation: 119
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Nice done, Ryder. I will be using this in my future project.
__________________
Slowly coming back to Sa-Mp..

Latest crap I've made:
[Include]CleverBot - Never Be Alone Again!
Fj0rtizFredde is offline   Reply With Quote
Old 20/04/2012, 07:31 PM   #4
Macluawn
Gangsta
 
Macluawn's Avatar
 
Join Date: Aug 2010
Posts: 606
Reputation: 71
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Quote:
Originally Posted by -Danny- View Post
So, this is basically a sort of system including positions for checkpoints and the system calculates where's the closest position is? Am I right with this? Cause I'm afraid I don't really understand the working and usages of this system.
dijkstra's algorithm find the shortest path between any 2 points.
Macluawn is offline   Reply With Quote
Old 20/04/2012, 08:21 PM   #5
wups
High-roller
 
wups's Avatar
 
Join Date: Apr 2010
Location: Lithuania
Posts: 1,368
Reputation: 133
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Well, there is this plugin released, you know?
wups is offline   Reply With Quote
Old 20/04/2012, 08:33 PM   #6
TheArcher
High-roller
 
TheArcher's Avatar
 
Join Date: Dec 2009
Location: Home
Posts: 2,509
Reputation: 233
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Just Amazing! Keep your work up.
__________________
TheArcher is offline   Reply With Quote
Old 20/04/2012, 09:11 PM   #7
RyDeR`
High-roller
 
RyDeR`'s Avatar
 
Join Date: Feb 2009
Location: Belgium
Posts: 3,133
Reputation: 645
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Thanks!

Quote:
Originally Posted by wups View Post
Well, there is this plugin released, you know?
It is not the same. The GPS thing is just an example using this include. You can create tons of other stuff using this include.
__________________

Sup?
RyDeR` is offline   Reply With Quote
Old 20/04/2012, 10:03 PM   #8
[NVC]Eduardo
Huge Clucker
 
[NVC]Eduardo's Avatar
 
Join Date: Jan 2012
Posts: 226
Reputation: 1
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Nice
__________________
Ľ Brasil - Virtual World RPG« v1.0
IP: 37.59.160.245:7777
+ Forum: vwbrasil.forumeiros.com
[NVC]Eduardo is offline   Reply With Quote
Old 20/04/2012, 10:27 PM   #9
Nanory
Big Clucker
 
Nanory's Avatar
 
Join Date: Feb 2009
Posts: 116
Reputation: 12
Default AW: Dijkstra.inc - Dijkstra pathfinding algorithm

I love Dijkstra and it's really useful.
As you said with this algorithm you can do a lot of things. We learned it at school (graph theory) and it's not only for GPS Systems.

Furthermore the plugin from Gamer_Z doesn't work on every server (on the other hand Gamer_Z work is also good)
__________________

Life of German
German Reallife since 2008
Nanory is offline   Reply With Quote
Old 20/04/2012, 11:59 PM   #10
Y_Less
Beta Tester
 
Y_Less's Avatar
 
Join Date: Jun 2008
Location: 629 - git.io/Y
Posts: 18,299
Reputation: 2572
Default Re: Dijkstra.inc - Dijkstra pathfinding algorithm

Actually, most GPSes don't use this simply because to calculate any route would take FAR too long. I believe they do multiple levels - find the shortest path between near you and your destination on major roads, then get you to and from those major roads using a subset of the smaller roads between where you are and the nearest point on the major road.
Y_Less 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
[Plugin] [REL] GPS Plugin - Gamer_Z's Advanced Pathfinding. Gamer_Z Plugin Development 427 08/09/2014 01:42 PM
An algorithm for vehicle streamers Double-O-Seven Scripting Help 1 10/10/2011 08:17 PM
[Include] M4S7reamer v1 (object streamer that uses a zoning algorithm) M4S7ERMIND Includes 17 22/07/2011 08:03 PM
NPC Artificial Intelligence - Shortest path algorithm Harry_Gaill Screenshots and Videos 76 14/05/2011 06:13 PM
Bullets Algorithm ? MJ! Help Archive 0 18/08/2010 07:38 PM


All times are GMT. The time now is 11:41 AM.


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