Page 1 of 1

cbAStar - The way to intelligent pathfinding

Posted: Tue Aug 04, 2009 1:59 am
by Jare
So you guys who do not speak Finnish may have thought that almost anything related to CoolBasic is written in Finnish and that only a small portion of that stuff is in English too. Well, you guys are absolutely right. But I decided to do some little thing about that: I decided to develop my newest CB library so that everything in it is written in English! The code itself, all comments, all documentation, all in English.

Well, to the point then. cbAStar is a function library that allows you to implement an easy-to-use and powerful pathfinding system into your CB projects. The actual library consists of one .cb source code file which does all the tricks so there is no need for DLL's or any other external libraries.

As the library's name stands, cbAStar uses the A* algorithm (A Star) as its base functionality. Towards it have been made a bunch of functions to advance the library's abilities and to make it more easier to be implemented. Shortly said, the A* algorithm finds a path by comparing a starting node's (node = cell = square = tile = what ever you want to call it) adjacent nodes to each other and estimating which of them would give the best way to an ending node. The estimation is done by calculating movement cost to an intended node and a very cautious evaluation of lenght of the path that is still left from the node. The algorithm will select a node that has a lowest estimation. This loop is continued until a path is finally found or until all possible nodes are scanned and a path cannot be found.

cbAStar is designed to suit games that uses different kind of engines. You can use CoolBasic's inbuild tilemaps in your game and cbAStar initializes just amazingly with your game. Or you can have whatever engine for your game's maps and you are still able to logically implement the library into your game. cbAStar does not move any objects - it just gives the programmer instructions on how to move them. So therefore the library is not tied in objects. You can use objects in your game or you can do everything with images.

The whole packet contains the following items:
- cbAStar library source code
- Wide documentation
- Example game to test the system in action with a tilemap (+ three media files related to it. The same files can be found in CoolBasic's Media folder).
- Example program to test all of the system's features in a grid based view.
- Logo to be used in your games if you wish.

Things that could have been done better in the library (and probably will be developed):
- Documentation: My English is not excellent. So you are free to send me PM everytime your inbuild English parser throws an syntax error or you see non-standard expressions while interpreting the documentation. 8-)
- Documentation: Maybe a HTML format would be better than TXT, but that would take too much time. Maybe I'll make a HTML documentation later.
- If a path is followed accurately, an object (or a character) can have at most eight different moving directions (which isn't much). Well, maybe this can be twisted some how.

The current version of the library is 1.0, so it is ready to be used at full volume. There may be coming a 2.0 version some time. Atleast if I get enough new developing ideas and time for it.

The license is attached to the documentation so I'm not gonna paste it here. But the main point of the license is that the library is free and modifiable when used in non-commercial products. But refer to the actual license to see that more closely.

And what for did I originally decided to start making this library? I'm developing a long game project named Madot 4 and I was not satisfied with its current pathfinder. So I decided to spend many, many hours on developing a much more powerful pathfinder. And I'm pleased with the results.

Download a RAR archive
EDIT:

2010-01-27: I've been playing with my webhost domain for the past couple of months. During that time I've maged to take cbAStar offline and broke the link above. Now it's back online with an updated link. If the link dies again, you can always contact me by e-mail: jare(insert the character here)kpelit.net so I will know to fix the link again.


Re: cbAStar - The way to intelligent pathfinding

Posted: Tue Aug 04, 2009 5:57 pm
by Valtzu
Example media missing in the package. Nice work though, seems to work. :)

Re: cbAStar - The way to intelligent pathfinding

Posted: Tue Aug 04, 2009 6:31 pm
by Jonez
Try using the original media in coolbasic media folder. They should work perfectly.

The NODE_WIDTH and NODE_HEIGHT constans in "Ultimate Example Program" seem to be pretty useless, since you use integers anyway. I'd like to test the speed, but lazy as I am, now I'd have to change the code itself :).

Regarding the cbAStar.cb, great job. This is yet another part in coolbasic programming we were missing.

Re: cbAStar - The way to intelligent pathfinding

Posted: Tue Aug 04, 2009 6:49 pm
by Jare
Valtzu wrote:Example media missing in the package. Nice work though, seems to work. :)
Whoops! :oops:

I just forgot to put the folder it in the archive. Added now.
Jonez wrote:Try using the original media in coolbasic media folder. They should work perfectly.

The NODE_WIDTH and NODE_HEIGHT constans in "Ultimate Example Program" seem to be pretty useless, since you use integers anyway. I'd like to test the speed, but lazy as I am, now I'd have to change the code itself :).

Regarding the cbAStar.cb, great job. This is yet another part in coolbasic programming we were missing.
Yea, i added the constants later and forgot to update the code. My bad. But now it's fixed.

Thanks for the feedback for both of you! :)
EDIT:

Here is the speed testing code (a simple one):

Code: Select all

Include "cbAStar.cb"

map = LoadMap("Example Media\cdm2.til","Example Media\tileset.bmp")

cbAStarInitializeUsingTilemap()

Repeat
	cycles = Input("How many cycles? ")
	DrawScreen 
	Until KeyHit(cbKeyReturn) And cycles > 0
CloseInput

Dim total_time
For i = 1 To cycles
	tmr	= Timer()
	Repeat
		start_x	= Rand(cbAStarMapWidth-1)
		start_y	= Rand(cbAStarMapHeight-1)
		end_x	= Rand(cbAStarMapWidth-1)
		end_y	= Rand(cbAStarMapHeight-1)
	Until GetAStarObstacle(start_x,start_y)=False And GetAStarObstacle(end_x,end_y)=False
	CalculatePath(start_x,start_y, end_x,end_y)
	total_time = total_time + (Timer()-tmr)
Next i

Print "Whole execution time: "+Float(total_time)/1000+"s"
Print "Average time per cycle: "+Float(total_time/cycles)/1000+"s"
WaitKey
It uses the same map as the other example game. It calculates random paths on the map and outputs spent time. cbAStar seems to be quite heavy in my tests: average time was about 150ms per path (my processor operates @2.33GHz). But the randomizer affetcs this making it often calculate very long paths.[/edit]

Re: cbAStar - The way to intelligent pathfinding

Posted: Wed Aug 05, 2009 1:35 pm
by Jonez
It seems that the calculation process isn't perfect. Notice how the program offers the route under the wall, even though it's actually one node longer than the alternative.

Re: cbAStar - The way to intelligent pathfinding

Posted: Wed Aug 05, 2009 1:56 pm
by Jare
Jonez wrote:It seems that the calculation process isn't perfect. Notice how the program offers the route under the wall, even though it's actually one node longer than the alternative.
You've got me there. But it's not a bug! It's a feature :) . The algorithm does not even go through all possibble paths. Decision (about which node should be taken next) are made by estimating lenght of the path that is still left from the next node. And it's quite a problem to properly estimate the path. :)

So it fails here, but usually it gives the shortest path.

Re: cbAStar - The way to intelligent pathfinding

Posted: Fri Aug 07, 2009 10:32 pm
by MaGetzUb
Wow, this lookslike very, good A* libary. One guestion, why you didn't put this also finnish side too? :shock:

Re: cbAStar - The way to intelligent pathfinding

Posted: Sat Aug 08, 2009 12:27 am
by Jare
MaGetzUb wrote:Wow, this lookslike very, good A* libary.
Thanks! :)
MaGetzUb wrote:One guestion, why you didn't put this also finnish side too? :shock:
Because I am kind of lazy. Making the English documentation took a lot of time. If I put this to the Finnish side too, I have to make another documentation. But I've planned to sometime make a smaller documentation in Finnish and then put the library into CBKK. (For those who does not know what it is, it's a website for CoolBasic functions and example codes, but the whole site and it's contents is only in Finnish. The address is http://cbkk.systec.fi).

Re: cbAStar - The way to intelligent pathfinding

Posted: Wed Oct 07, 2009 11:29 am
by Guest
You could Just use Google translate or some other to convert it all. When I read the Finish side I have a window open to Google translate and cut and past to get a mostly readable translation. Work quit well.

Re: cbAStar - The way to intelligent pathfinding

Posted: Wed Oct 07, 2009 12:49 pm
by Jare
Vieras wrote:You could Just use Google translate or some other to convert it all. When I read the Finish side I have a window open to Google translate and cut and past to get a mostly readable translation. Work quit well.
Cool. I need to consider that option. I'm not sure how well Google can translate from English to Finnish but for sure it's worth trying. Thanks for the idea! :)

Re: cbAStar - The way to intelligent pathfinding

Posted: Thu Sep 09, 2010 8:29 am
by buke44
It makes Memory Acces Violation-error if I try to follow long path using function FollowPath (). The error comes when there is Drawscreen in program.

Re: cbAStar - The way to intelligent pathfinding

Posted: Thu Sep 09, 2010 9:16 am
by Jare
buke44 wrote:It makes Memory Acces Violation-error if I try to follow long path using function FollowPath (). The error comes when there is Drawscreen in program.
Can you post a simple example code that demonstrates the error, please?

Re: cbAStar - The way to intelligent pathfinding

Posted: Sat Sep 11, 2010 4:04 pm
by buke44
I solved my problem. I changed line 120 of cbAStar
old

Code: Select all

ReDim CbAStarMap(CbAStarMapWidth-1,CbAStarMapHeight-1,CbAStarMapDepth)
new

Code: Select all

ReDim CbAStarMap(CbAStarMapWidth,CbAStarMapHeight,CbAStarMapDepth)
I think that happen because my map system uses 0,0 as map too, and cbAStar excepts that map starts at 1,1.

Re: cbAStar - The way to intelligent pathfinding

Posted: Sat Sep 11, 2010 7:22 pm
by Jare
buke44 wrote:I solved my problem. I changed line 120 of cbAStar
old

Code: Select all

ReDim CbAStarMap(CbAStarMapWidth-1,CbAStarMapHeight-1,CbAStarMapDepth)
new

Code: Select all

ReDim CbAStarMap(CbAStarMapWidth,CbAStarMapHeight,CbAStarMapDepth)
I think that happen because my map system uses 0,0 as map too, and cbAStar excepts that map starts at 1,1.
Currently I don't remember how I programmed the dimensions but according to the change you made I would assume that CBAstar considers the map starting from 0,0, not from 1,1. If it really do consider the map dimensions starting from 1,1 and ending at CbAStarMapWidth,CbAStarMapHeight in some part of the program, then I'm not surprised it crashes.

I need to check the code when I have time.

Re: cbAStar - The way to intelligent pathfinding

Posted: Thu May 10, 2012 4:29 pm
by skorpioni-cb
Thanks bro, for this library, I really appreciate you for that.
Sorry, for pop-up this thread, but if someone needs 'find the path-way library' then they can find it, without searching it so much :roll:

Re: cbAStar - The way to intelligent pathfinding

Posted: Mon Mar 11, 2013 10:04 am
by kaale0
This will be very useful to me too.

Re: cbAStar - The way to intelligent pathfinding

Posted: Mon Mar 11, 2013 8:37 pm
by Jare
Still nice to hear that people use it. :)