Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

AppGameKit Showcase / A* Pathfinding

Author
Message
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 10th Jun 2018 15:04 Edited at: 10th Jun 2018 15:09
Hey guys,

this is an early implementation of A* pathfinding, using a binary heap structure for managing the open list.
I used this guide by Patrick Lester: https://www.gamedev.net/articles/programming/artificial-intelligence/a-pathfinding-for-beginners-r2003/

It's pretty fast and works well on any grid size
The pathfinding process is slowed down in the video by way of illustration...




Cheers
PSY


PSY LABS Games
Coders don't die, they just gosub without return
Golelorn
1
Years of Service
User Offline
Joined: 20th Nov 2016
Location:
Posted: 12th Jun 2018 23:41
Thanks, Psy! I am sure I will find this handy. My own A* is far too slow, and I was struggling with heap optimization.
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 13th Jun 2018 03:09
Does it do 8-way searches? Or just 4?
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 13th Jun 2018 06:49
It does 8-way searches by default.
In case you want/need 4-way searches only, you just need to pass a parameter when calling the pathfinding function


PSY LABS Games
Coders don't die, they just gosub without return
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 13th Jun 2018 21:05
You make me wanna tackle my own pathfinding again. I understand the concept pretty well, but managing it in code has always been a headache for me. Are you managing the open list with a binary heap as the article suggested?
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 14th Jun 2018 06:43
Yeah, I'm using the binary heap system, as it is extremely fast, and very easy to implement.
There's some good info on it out there, a good tutorial is mentioned in the article.

I pretty much ported Patrick Lester's code from Blitz to AGK.
I made some small improvements ( i.e. fixed the size of most arrays, put the parent nodes and the walkability of tiles into a type instead of using seperate arrays, restructured some bits of code, made the code more readable, sped up some cost calculations etc. )
The binary heap part was perfect, so I didn't tweak anything there.


PSY LABS Games
Coders don't die, they just gosub without return
Phaelax
DBPro Master
15
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 15th Jun 2018 16:26
We should do some speed tests between yours and the one I ported.
Tiled TMX Importer V.2
XML Parser V.2
Base64 Encoder/Decoder
Purple Token - Free online hi-score database
Legend of Zelda

"I like offending people, because I think people who get offended should be offended." - Linus Torvalds
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 17th Jun 2018 17:10
Absolutely.
We just need to fix a grid size and the random seed


PSY LABS Games
Coders don't die, they just gosub without return
george++
11
Years of Service
User Offline
Joined: 13th May 2007
Location: Hellas
Posted: 17th Jun 2018 22:00
Hi PSY,
Do you have a download link of your astar lib?
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 17th Jun 2018 23:51
Hey george++,

Not yet. Basically, it's finished, but I want to make some minor changes to the code ( mostly variable declarations to prevent it from interfering with game code, and some clean up stuff ).
And I'll do some speed tests on different grid sizes to check if everything's okay.

Would've done all that already if I hadn't been on vacation



PSY LABS Games
Coders don't die, they just gosub without return
george++
11
Years of Service
User Offline
Joined: 13th May 2007
Location: Hellas
Posted: 18th Jun 2018 20:22
Why not use a type to encapsulate all variables of the lib?
PSY
Valued Member
1
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 19th Jun 2018 18:27
Most variables are encapsuled in types or declared local in functions.
The lib currently uses some display and debugging stuff which won't be compiled in the final code, so I need to do some clean-up first.
Also, the lib uses some DIM declarations which I need to rename.


PSY LABS Games
Coders don't die, they just gosub without return

Login to post a reply

Server time is: 2018-06-24 07:58:31
Your offset time is: 2018-06-24 07:58:31