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
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 10th Jun 2018 15:04 Edited at: 9th Oct 2018 10:06
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...



EDIT: DOWNLOAD NOW AVAILABLE


Cheers
PSY


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

Attachments

Login to view attachments
Golelorn
2
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
2
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
2
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
2
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
2
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
2
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
GarBenjamin
2
Years of Service
User Offline
Joined: 30th Nov 2016
Location: USA
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 12th Sep 2018 18:21 Edited at: 12th Sep 2018 18:22
Wow,

it's been a long time

I've had some other non-coding stuff going on, but I'll be done with everything within the next 2 weeks.
First thing on my to-do list after that will be finishing this lib


PSY LABS Games
Coders don't die, they just gosub without return
PHeMoX
User Offline
Joined: 9th Jan 2018
Location:
Posted: 1st Oct 2018 22:38
Very interesting stuff! Be sure to test performance on mobile too if you can. I'd love to know.

I'm working on my own system as well and must say it is tricky stuff to get right.
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 9th Oct 2018 10:15 Edited at: 9th Oct 2018 10:16
Hey guys,

I just uploaded the A* pathfinding system. See first post for download link.

Notes:
I heavily commented the complete code. The code -as it is now- visualizes the pathfinding process.
It's easy to remove the visual stuff and use the library for pathfinding purposes only.
The only thing that has to be done is to set up an array which holds the actual path that has been found. See the ShowPathFinding funtion in main.agc to get an idea how to do that.

COLS and ROWS represent the x and y dimension of the node grid.
node[x,y].blocked defines if the node is walkable or not.

Feel free to use the library for your projects.
Feedback welcome


Have a good one,
PSY


PSY LABS Games
Coders don't die, they just gosub without return
PHeMoX
User Offline
Joined: 9th Jan 2018
Location:
Posted: 1st Nov 2018 22:45
My first impressions of this are very good. Haven't had time to go through all code yet, but it did remind me how I should really pay more attention to writing more clean code hahah. This project is very clean. Well done.
Also, works fine, although I for a second missed I have to press Return to make it continue it's search. Seems excellent code to learn from, so much appreciated! Thanks
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 2nd Nov 2018 20:52
Thank you PheMoX !

Glad you find it useful. If you have any questions, just shoot


PSY


PSY LABS Games
Coders don't die, they just gosub without return
PHeMoX
User Offline
Joined: 9th Jan 2018
Location:
Posted: 6th Nov 2018 22:55
Yeah, I do have a question, when you have two walls where a diagonal path should actually be blocked, the algorithm will still pick the shortest diagonal path, instead of going around the wall.

Any ideas on how to prevent this? Maybe add more weights to tiles surrounded by multiple walls? Of course, technically this diagonal path shouldn't really count as a valid shortest path, right?

Attachments

Login to view attachments
PSY
Valued Member
2
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 8th Nov 2018 02:18 Edited at: 8th Nov 2018 03:35
Hey,

That's easy to prevent. I already built in the option.
Squeezing around corners is enabled by default.
To deactivate it, just uncomment the don't squeeze around corners code block in the FindPath ( startX, startY, targetX, targetY ) function.

Also uncomment the ENDIF in line 434 in pathfinding.agc


(edit) Or just uncomment both parts and make the squeeze flag global to switch it on and off easily

PSY


PSY LABS Games
Coders don't die, they just gosub without return
PHeMoX
User Offline
Joined: 9th Jan 2018
Location:
Posted: 8th Nov 2018 11:58
Thanks, oh I see!

Login to post a reply

Server time is: 2018-12-14 05:45:25
Your offset time is: 2018-12-14 05:45:25