[Include] Dijkstra.inc - Dijkstra pathfinding algorithm

[Include] Dijkstra.inc - Dijkstra pathfinding algorithm - Printable Version

+- SA-MP Forums Archive (https://sampforum.blast.hk)
+-- Forum: SA-MP Scripting and Plugins (https://sampforum.blast.hk/forumdisplay.php?fid=8)
+--- Forum: Filterscripts (https://sampforum.blast.hk/forumdisplay.php?fid=17)
+---- Forum: Includes (https://sampforum.blast.hk/forumdisplay.php?fid=83)
+---- Thread: [Include] Dijkstra.inc - Dijkstra pathfinding algorithm (/showthread.php?tid=336000)

Dijkstra.inc - Dijkstra pathfinding algorithm - RyDeR` - 20.04.2012

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 Код:

stock Dijkstra(const aeNodes[][], iStart, iEnd, aiPath[], const iSize = sizeof(aeNodes))

Here's how the node array should look like:

pawn Код:

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.

[ame]http://www.youtube.com/watch?v=rENx33otwE4[/ame]

GPS.pwn

Download

Dijkstra.inc

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - Danny - 20.04.2012

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.

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - Fj0rtizFredde - 20.04.2012

Nice done, Ryder.

I will be using this in my future project.

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - Macluawn - 20.04.2012

Quote:

Originally Posted by -Danny-

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.

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - wups - 20.04.2012

Well, there is this plugin released, you know?

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - TheArcher - 20.04.2012

Just Amazing! Keep your work up.

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - RyDeR` - 20.04.2012

Thanks!

Quote:

Originally Posted by wups

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.

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - [NVC]Eduardo - 20.04.2012

Nice

AW: Dijkstra.inc - Dijkstra pathfinding algorithm - Nanory - 20.04.2012

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)

Re: Dijkstra.inc - Dijkstra pathfinding algorithm - Lorenc_ - 21.04.2012

Quote:

Originally Posted by wups

Well, there is this plugin released, you know?

Well, there is not a linux version for that plugin...

Thanks RyDeR`, going to upgrade my gps system

the paste id is invalid btw.

EDIT: nvm, lacks on nodes