cbAStar - The way to intelligent pathfinding

Announce your Work In Process and finalized projects here.
Post Reply
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

cbAStar - The way to intelligent pathfinding

Post 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 cbAStar 1.0.0 as a ZIP from GitHub
cbAStar GitHub project page
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.

EDIT:

2020-09-21: The old download link was broken for many years. Now the library is available in GitHub (links above). And it's been ten years since I last edited this post. Let's see if I'll edit it again in 2030. :)

Last edited by Jare on Mon Sep 21, 2020 7:39 pm, edited 4 times in total.
Valtzu
Active Member
Posts: 115
Joined: Sun Aug 26, 2007 2:40 pm
Location: Sauvo
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post by Valtzu »

Example media missing in the package. Nice work though, seems to work. :)
User avatar
Jonez
Devoted Member
Posts: 575
Joined: Mon Aug 27, 2007 8:37 pm

Re: cbAStar - The way to intelligent pathfinding

Post 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.
-Vuoden 2008 aloittelijan ystävä -palkinnon voittaja-
Image <- protestipelikilpailun voittaja.
Space War
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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]
User avatar
Jonez
Devoted Member
Posts: 575
Joined: Mon Aug 27, 2007 8:37 pm

Re: cbAStar - The way to intelligent pathfinding

Post 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.
Attachments
bug.PNG
bug.PNG (32.06 KiB) Viewed 39283 times
-Vuoden 2008 aloittelijan ystävä -palkinnon voittaja-
Image <- protestipelikilpailun voittaja.
Space War
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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.
MaGetzUb
Guru
Posts: 1715
Joined: Sun Sep 09, 2007 12:35 pm
Location: Alavus

Re: cbAStar - The way to intelligent pathfinding

Post by MaGetzUb »

Wow, this lookslike very, good A* libary. One guestion, why you didn't put this also finnish side too? :shock:
Solar Eclipse
Meneillä olevat Projektit:
We're in a simulation, and God is trying to debug us.
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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).
Guest

Re: cbAStar - The way to intelligent pathfinding

Post 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.
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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! :)
User avatar
buke44
Active Member
Posts: 169
Joined: Sat May 23, 2009 8:10 pm
Location: Tampere

Re: cbAStar - The way to intelligent pathfinding

Post 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.
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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?
User avatar
buke44
Active Member
Posts: 169
Joined: Sat May 23, 2009 8:10 pm
Location: Tampere

Re: cbAStar - The way to intelligent pathfinding

Post 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.
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post 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.
skorpioni-cb
Advanced Member
Posts: 364
Joined: Wed Dec 03, 2008 3:48 pm
Location: Turku

Re: cbAStar - The way to intelligent pathfinding

Post 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:
En tiedä, mitä tiedän, mutta tiedän ettei se ole mitään kaunista.

I know not what I know, but I do know that it's not beautiful.
kaale0
Newcomer
Posts: 2
Joined: Thu Mar 07, 2013 5:21 pm

Re: cbAStar - The way to intelligent pathfinding

Post by kaale0 »

This will be very useful to me too.
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post by Jare »

Still nice to hear that people use it. :)
User avatar
Jare
Devoted Member
Posts: 877
Joined: Mon Aug 27, 2007 10:18 pm
Location: Pori
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post by Jare »

Hello everyone! :)

I just came to read this topic again for nostalgy. And I noticed that the cbAStar's download link had been broken for many years because I had hosted it in my former website kpelit.net, which I had shut down a long time ago. I have created a new download link now (see above and below).

Now I decided to bring this library to version control and host it in GitHub. It's still the very same code from 2009 without any changes, and I do not have any plans for developing the library. But if you have any problems with the library, you can always create an issue in GitHub (or ask in this topic and I might create an issue about it in GitHub). Or development ideas or whatever.

I do not promise to do any work on the library, but I might consider if it's something relatively simple and does not take much time. But as CB is not used much anymore, I guess there is not much need for further development of this library.

Download cbAStar 1.0.0 as a ZIP from GitHub
cbAStar GitHub project page
User avatar
valscion
Moderator
Moderator
Posts: 1599
Joined: Thu Dec 06, 2007 7:46 pm
Location: Espoo
Contact:

Re: cbAStar - The way to intelligent pathfinding

Post by valscion »

Nice! Thanks for resurrecting broken download links :)
cbEnchanted, uudelleenkirjoitettu runtime. Uusin versio: 0.4.1 — Nyt myös sorsat GitHubissa!
NetMatch - se kunnon nettimättö-deathmatch! Avoimella lähdekoodilla varustettu
vesalaakso.com
Post Reply