---

Hello,

I have written a dll in order to use pathfinding in game (astar algorythm).

I have learned a* algorythm with the very good article of Patrick Lester (at the address http://www.policyalmanac.org/games/aStarTutorial.htm )
Afterthat I have downloaded the exemples and have translated the code and implement the result in my own system. So I would like to thank Patrick Lester for his very good article (and his very good exemple). My system resembles much of P.Lester's exemple.



Features:
== pathfinders objects
== pathmaps
== pathmaps saving/loading from memory and from files
== search path
== basic waytile reader
== evolued path reader : checkpoints
== evolued pathmap operation : inversion
== much faster than v0.9a
== 2 variations of Astar : with or without diagonals
== documentation (french & english)

Current version : v1.0

The version 1.0 is out !

Notice that one file from the doc still need translation...

Commands:
+ Code Snippet

IAA_CREATE PATHFINDER
IAA_DELETE PATHFINDER
IAA_ABOUT
IAA_GET PATHFINDER HEIGHT
IAA_GET PATHFINDER WIDTH
IAA_GET PATHFINDER TILE SIZE
IAA_GET PATHMAP VALUE
IAA_GET PATHFINDER PATHMAP MEM SIZE
IAA_GET TOTAL WAYTILES
IAA_GET WAYTILE X
IAA_GET WAYTILE Y
IAA_GET TOTAL CHECKPOINTS
IAA_GET CHECKPOINT X
IAA_GET CHECKPOINT Y
IAA_GET PATH START X
IAA_GET PATH START Y
IAA_GET PATH STATE
IAA_IS CHECKPOINTS ENABLED
IAA_IS PATH VALID
IAA_LOAD FROM FILE
IAA_SAVE TO FILE
IAA_LOAD FROM MEMORY
IAA_SAVE TO MEMORY
IAA_LOAD ENTIRE FROM MEMORY
IAA_SAVE ENTIRE TO MEMORY
IAA_HORIZONTAL INVERT
IAA_VERTICAL INVERT
IAA_SET PATHMAP VALUE
IAA_SET PATHMAP VALUE RECT
IAA_SEARCH PATH
IAA_SEARCH PATH WITHOUT DIAGONALS
IAA_COMPILE PATH TO CHECKPOINTS

Important Note : the dbpro files and the dll are not free of bugs. You use it at your own risks.The files are provided 'as is', without any warranties of any kind. A complete license is included in the documentation.

Dbpro Version 6.6b or 7.0 recommended, but should work with older and younger versions.


If you have any questions, remarks or bugs , you can contact me at info-tibo@orange.fr. Warning ! You must write the subject of your mail with the mention "[Dbp]" (for antispam) if you send me a mail.

Videos:

Youtube video astar v0.6
Youtube video astar v0.9 (2d application, french subtitles)


Screenshots:







Downloads:
IA::Astar 1.0 French Version
IA::Astar 1.0 English Version


Have fun !

~Darktib

---

Il y a quelques temps, j'ai écrit un tutoriel expliquant comment faire des DLLs avec Code::Blocks : http://www.games-creators.org/wiki/Cr%C3%A9er_des_DLLs_en_C_pour_Dark_Basic_Pro
Il y a une partie qui concerne la conversion des types DBP vers C et vice-versa.
Pour ce qui est des strings, c'est un peu tordu : quand une fonction en renvoie un, il faut détruire d'une certaine manière celui envoyé en paramètre - je n'y ai pas encore jeté un oeil. Par contre, pour envoyer un string comme paramètre, c'est tout con : char*

---

Sauf que ca marche pas... gcc compile bien mais apparement dbp ne comprend pas... (en plus j'ai appris a faire des dlls en lisant ton tuto )
Sur le tuto de TGC ils dise que c'est "LPSTR"...

Enfin...je vais retester. En passant, si tu savais comment rajouter des lignes et des colonnes a des tableaux en C++ ce serait cool.

---

C'est bizarre que ça ne fonctionne pas chez toi. Tu es certain de ne pas avoir fait d'erreur ?
LPSTR signifie "Long Pointer String", c'est parfaitement identique à un char*. C'est juste qu'un bonhomme a trouvé utile de changer les noms des char*...

Jette un oeil à ceci :
+ Code Snippet

8  "SAVE BOARD%S%_Z9saveBoardPc%Filename"

+ Code Snippet

FUNCTION void saveBoard(char *fname){

Ca passe sans problème chez moi.

Si tu as définit ton tableau "type arr[32][24]", tu ne peux pas modifier ses dimensions. Par contre, si c'est un type **arr, tu peux utiliser realloc.

A vue de nez et sans tester...
Allocation :
+ Code Snippet

type **arr;
arr = (type**)malloc(cols*sizeof(type*));
for (unsigned int i=0; i<cols; i++)
	arr[i]=(type*)malloc(rows*sizeof(type));

Réallocation :
+ Code Snippet

unsigned int ncols = cols + 10;
unsigned int nrows = rows - 5;
arr = (type**)realloc(arr, ncols*sizeof(type*));
for (unsigned int i=0; i<ncols; i++)
	arr[i]=(type*)realloc(nrows*sizeof(type));

J'évite d'utiliser new, j'ai rencontré des problèmes avec cette commande. Elle ne fonctionne pas lorsqu'on demande d'allouer beaucoup de mémoire (pour des traitements de données numériques, il m'arrive d'avoir à allouer près d'un giga). Malloc ne m'a jamais laissé tomber

---

oh yea... Totally. How could I forget that??

But if it works really well, I think I'd find this usefull.

---

Nice... can this be adapted for a 3D environment?

( Ce serait genial... et encore felicitations pour le bon travail... ca fait plaisir de voir que les francais sont encore present sur ces forum )

---

@thebulk71 : Yes it can be adapted for a 3d environment (for exemple I have coded this dll for my 3D RTS project...)

@all: I have some bugs, but I think I can put the version I have on the forum.

@Atreides: J'ai modifié les options de GCC et ca fonctionne maintenant parfaitement.Merci pour ton aide (et ton tuto )

The help files are not in the zip (because I haven't the time for write these actually)

---

How's the speed compared with internal DBP systems such as Ian M's A-star example?

---

The speed depend of the pathlength and the computer : for a path which the pathlength is <= 400 waytiles that searchpath function takes 0~2 ms; for paths that pathlength is >400~450 waytiles it takes 2~10(10 is a max) ms.

I don't know how is the speed of DBP internal system so I cannot help you on that point.

Hope this can help you,

~Darktib

PS : Sorry if my english is bad - I'm french

---

Version 0.9 will be out the latest week of november, if I have the time I want.

---

[deleted]

---

Version 0.9a will be out the 2nd December 2007!

Actually I am testing the dll.

Im not sure but I think that there will be only the dll, the *.ini file and 2 or 3 examples.

---

Looks awesome. I may find myself using this at some point.

Your English is good by the way.

---

Thanks Kohaku

If you know where is a post about astar in dbp it would be great to indicate me where is this post (to compare performances)

---

It works with GDK ???
cheers

---

Its a dll, so you can use this plugin with the language you want.
In C/C++ with GDK you can write :
call dll ("astar.dll","SearchPath",parameters) or equivalent.
If you want to know the name of the functions you can use a stringtable reader, such as FileAnalizer.

cheers

---

wow, awesome tutorial, interesting read, ty.

---

You're welcome

---

This is the code that Ian T was talking about:
http://www.thegamecreators.com/?m=codebase_view_code&i=56984d6fa64dd67ceb1e01c8d835c957

Its pretty fast and stable.

---

Thank you!
I will compare IA::Astar and this code now^^
And seasons greetings !

---

Could you be nice , and give us an example for GDK ?
Because my attempts to make it work ,failed misserably.
dbLoadDLL on GDK dont work very well so i used IanM's snippet
+ Code Snippet

// Load the library
HMODULE MyDLL = LoadLibrary("MyDLL.dll");

// This creates a new function pointer type that accepts an
// int argument, and returns an int result.
typedef int (*HelloFnPtr)(int);

// This creates the function pointer itself
HelloFnPtr Hello;

// This fills the function pointer with the address of the function
// within the DLL
Hello = (HelloFnPtr)GetProcAddress(MyDLL,"Hello");

// Finally, we can call the function as if it was a standard
// C function
int x = Hello(1);

// Free the DLL - after this point, it is no longer safe to call
// the Hello function via the function pointer.
FreeLibrary(MyDLL);

But it doesnt work.It crashes when i call SetAstarEngineMap
So any example of this great looking DLL on GDK will be a good news for me.
Cheers

---

I will test your code, and give you the solution if I find.

Have you a short description of the dll commands in gdk ? It could be very useful

Normally, you load the dll, and call the dll functions exported.

So, IA::Astar dll functions are not FunctionYY@@-I-don't-know, it's
z8Functionii, or similar, because its compiled with GCC.

---

Would it be possible for you to adapt this extention to work with predefined nodes in 3d space rather than a full array of nodes? Preset nodes are pretty much the de facto standard for enclosed spaces, but all the interest on the forums seems to be focused towards open maps for things like RTS games. That method really isn't compatible with what I'm doing.

---

I can't adapt it in a list of node, because of performances . For example I have seen last week an astar plugin for Irrlicht with nodes, but when I wanted 128*128 pathmaps I was a 2 fps...in C++...

But I have restarted the developpment of the plugin last week, it will be the version 1.0, and actually it is a total rewrite, more convenient.

If you want to use astar in big spaces you can make several pathmaps which you place 'border to border'. In IA::Astar 0.9a you can use 4 pathmaps with no need to create each pathmap (already created when you call the init function).

---

@Darktib
When you use nodes, you don't create a grid of them You create a node at every corner of every collision object, and links between nodes that can 'see' each other. It is MUCH faster than using a grid for a large area. This is how DarkAI works

---

Well... Perhaps I will try to create a dll using nodes but for the moment I want to finish IAA 1.0 .

How are the DarkAI performances ?

PS : the other advantage of IA::Astar is this dll doesn't need to be executed width dbp, it can be used with all languages supporting dll management (C, C++, VB, etc...)

---

I cannot dowlnoad version 0.6... The page that it links you to keeps forwarding to another random page, like Dallas Hotels, or EBay.

Thanks

EDIT: Do you have the 3D pathfinding example? 2D Does not really help the people who make 3D games

---

The v0.6 have been deleted, because this hosting site delete files after 1 month... If you want I can put the 0.6 on MegaUpload.

All the versions can be adapted for 3d games, If you prefer the code thant the download I can put the 3d example code on the forum.

Actually (at this moment) I code the v1.0 ...This version will have 2d and 3d example. I think the plugin in v1.0 will be 'ready' in about 1-2 months.

cheers,

~Darktib

---

OK, thanks a lot. It would really help to have that 3D example code. You don't have to put up version 0.6, because I thought that it had a 3D example, but I guess it doesn't.

But if it does, feel free to upload it.

---

OK, I will put this example today or tomorrow, just want the time to adapt the function names for IAA 0.9a^^

---

OK, thanks for your help. Any progress on the example?

I hope I am not too persistant!

---

Finish!

It is a total rewrite, that's why it was so slow...

The example is attached to this post, with the zip of IAA 0.9a (maybe it can be useful^^)
The pathmap used can be changed with the 2d example.

Don't forgot comments^^

Cheers,
Darktib

---

Great! Thanks for the 3D example, and releasing a new version of IA Astar!

---

For those who wants IA::Astar news, here is a screenshot. This screenie was taken with more than 1 million polys... and more than 50 000 objects. 10 fps

The average of path research time with a 64*64 pathmap is 0.20 millisecond^^
Screenshot :
+ Code Snippet

[img]http://magehost.free.fr/IMG/osyechose4k0z799n1f1big.png[/img]

---

Darktib, i really love your plugin, its exactly what i was looking for for a long time. the news sound good !!! 0.2 milliseconds is just awesome

I'm waiting for the next version!

cheers

---

Small news : I think the version 1.0 will be out in about 1 or 2 months.

Cheers,
Darktib

---

The french version 1.0 is out

Features and download are in the first post.

Enjoy !

PS: The langage of the version is the langage of the documention and of the examples. For the english users the english version will be out in about 1 or 2 months I think.

---

Is there an estimate to when the English version will be out?

Thanks.

---

The only thing that is not done is to translate the documentation from frenchinto english...

All the function names are in english - but not the prototpye indication. I think translating documentation files will take a long time as it's not interessant neither easy...^^

So I think i can release the dll with english documentation before christmas (^^), but I dont know exactly when.

Cheers,

Darktib

---

Hello all, and Happy new year !

So, I have translated all files except the bigger because of lack of time...

'appologize for releasing it so late, but here is the link :
http://www.mediafire.com/download.php?zj2zuyljhf5
or see first post.


Cheers,

Darktib