[Include] Dijkstra.inc - Dijkstra pathfinding algorithm

[RyDeR`]

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:

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

Here's how the node array should look like:

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

[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.

[Fj0rtizFredde]

Nice done, Ryder. I will be using this in my future project.

[Macluawn]

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.

[wups]

Well, there is this plugin released, you know?

[TheArcher]

Just Amazing! Keep your work up.

[RyDeR`]

Thanks!

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.

[[NVC]Eduardo]

Nice

[Nanory]

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)

[Y_Less]

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.