Shortest Path Algorithm

Hi,
I am not sure if this has been discussed before but I implemented the Dijkstra's algorithm trying to solve the Single-pair shortest-path problem in a 3D graph. I think that many people are looking for this because many issues in Game programming are related to this. So here we go:
First the link for the Blitz3D code:

http://www.moraldigames.com/Temp/Spa.zip

The interface is quite simple:
First you must create a graph using the following command:
mygraph = Graph_Create(0)
0 is the graph id (you can create many graphs using different id's)

Then you have to build the graph by adding vertices:
v1.Vertex = Graph_CreateVertex(mygraph, x1, y1, z1)
v2.Vertex = Graph_CreateVertex(mygraph, x2, y2, z2)
...

In order to create connections between vertices use:
Vertex_Connection(v1, v2)
...

After the construction of the graph simply call:
Graph_FindShortestPath(mygraph, src, dest)
where src and dest are existing vertices within mygraph
Each graph has the bestsearch vertex and after the previous call you can trace the shortest path following the predecessor member of the bestsearch vertex

The most interesting is that you can define your own 'cost' between two vertices by modifying the Vertex_GetCost() function in the way you like. Currently in the program the 'cost' between two vertices is their distance

If you are confused check the source.
If you build a graph and you find that the program does not calculate the shortest path please let me now in order to debug it.

Enjoy!

Hey, none has commented this! :(
I thought it was very useful for most on Blitz3D threads.

Hi Moraldi, this is really good work and comes quite handy. Highly appreciated, Thank You !

I found one! Thanks lo-tekk :)

I'll second lo-tekk's thoughts. I haven't DL'd it yet but taking the burden of converting the ol' A* routine is great news. Thanks for the great contribution!

Thanks Dustin but the time you needed to post is much more than the downloading time... :)

Agreed. But I'm at work and they've done a fine job of rendering the USBs useless. And lately I've been 12+ hours/day so the machine at home hasn't gotten much use lately. But I'll grab it soon enough.

Oh, I see USB's they are not suffers only in Greece..

I downloaded it - but I am playing Crysis.

puki playing Crysis, my brother playing Crysis, all my friends playing Crysis. I am the only playing with Blitz3D...? :)

at moment i do play Unreal Tournament 3..

Good job! :)

Why not place this in the code archives?

Thanks Ian, yea you have right I will put this in code archives...

I will comment, EXCELLENT!
I'm always interested in good pathfinding solutions and this seems to be a good one!

Even on very large layouts this baby rolls right along.
Thanks for sharing this algo.

Thanks Swampdonkey!
Did you build a large graph? can you post it?.

Nice, i did this a few years back, don't think i ever released the source or editor.

It's was good learning session. Dijkstra's algorithm is cool and simple to code.

It wasn't for me a learning session but decided to release because this wonderful community many times help me too in the past.

Hey Moraldi,

Yah I built a rather extensive scene with it and it worked with no problems. Im intergrating it into my world editor. No screens to show at this time, but later ;)

Thanks again.

Thanks for the info. It helps me a lot because I indent to integrate to my Mesh Factory library

I have created a demo about shorthest path on blitzmax
using dijkstra algorithm.

It's a beta version. The Algorithm use Dijkstra. Note A* is an update of Dijktra using an heuristic( usually, distance between start position and target position )

http://www.box.net/shared/kv47bffppz

I sure would like to se what you have PatMaba, but I dont have the b3d.dll, what library is that from?

Glad to see an increasing interest on shortest path methods. I believe these algorithms can give game-play depth in Blitz3D games.

Well done. I didn't have debug on, so it went fullscreen and thus I had no pointer. I was confused for a bit, but after changing the graphics mode all was well.

Graphics3D 800, 600, 32, 2

I would guess a common use for this might include:

Creatures chasing a character around a complex environment (which could be a single room or an entire complex, as in "Intruder alert: all units to Sector 12")

Economic managment in trading games (space routes, for example)

Other applications? (games or not)

Civ-type or strategy games in general.
You can set a cost for each node taking into account its resources.
This way a computer controlled player can decide to go to the node with maximum cost finding his way with this algorithm