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/AppGameKit Studio Showcase / A* Pathfinding

Author
Message
PSY
Developer
8
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
Link
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
Back to top
Profile PM Website
Golelorn
8
Years of Service
User Offline
Joined: 20th Nov 2016
Location:
Posted: 12th Jun 2018 23:41
Link
Thanks, Psy! I am sure I will find this handy. My own A* is far too slow, and I was struggling with heap optimization.
Back to top
Profile PM
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 13th Jun 2018 03:09
Link
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
Back to top
Profile PM Email Website
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 13th Jun 2018 06:49
Link
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
Back to top
Profile PM Website
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 13th Jun 2018 21:05
Link
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
Back to top
Profile PM Email Website
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 14th Jun 2018 06:43
Link
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
Back to top
Profile PM Website
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 15th Jun 2018 16:26
Link
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
Back to top
Profile PM Email Website
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 17th Jun 2018 17:10
Link
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
Back to top
Profile PM Website
george++
AGK Tool Maker
17
Years of Service
User Offline
Joined: 13th May 2007
Location: Thessaloniki, Hellas
Posted: 17th Jun 2018 22:00
Link
Hi PSY,
Do you have a download link of your astar lib?
Back to top
Profile PM Email
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 17th Jun 2018 23:51
Link
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
Back to top
Profile PM Website
george++
AGK Tool Maker
17
Years of Service
User Offline
Joined: 13th May 2007
Location: Thessaloniki, Hellas
Posted: 18th Jun 2018 20:22
Link
Why not use a type to encapsulate all variables of the lib?
Back to top
Profile PM Email
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 19th Jun 2018 18:27
Link
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
Back to top
Profile PM Website
GarBenjamin
AGK Developer
7
Years of Service
User Offline
Joined: 30th Nov 2016
Location: USA
Posted: 12th Sep 2018 15:43
Link
This should be a quite useful api when released.
My Projects Most With Full Source...
[Attack of the Crows] [Christmas Command 2016]
[Simple Sprite Shaders Example] [Old School Style 3D FPS]
[Playable 2D Shmup Template] [2D Single Screen Platformer]
[FixSpriteToSprite System & Demo]
[Mutant Invaders 3D Shmup] [Unity - Atlantic Crisis]
[Unity - Treasures of Ali-Gar] [My YouTube Videos] [Twitter]
[AppGameKit BASIC Extended API]
Back to top
Profile PM
PSY
Developer
8
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
Link
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
Back to top
Profile PM Website
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 1st Oct 2018 22:38
Link
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.
Back to top
Profile PM
PSY
Developer
8
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
Link
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
Back to top
Profile PM Website
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 1st Nov 2018 22:45
Link
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
Back to top
Profile PM
PSY
Developer
8
Years of Service
User Offline
Joined: 3rd Jul 2016
Location: Laniakea Supercluster
Posted: 2nd Nov 2018 20:52
Link
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
Back to top
Profile PM Website
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 6th Nov 2018 22:55
Link
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
Back to top
Profile PM
PSY
Developer
8
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
Link
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
Back to top
Profile PM Website
PHeMoX
6
Years of Service
User Offline
Joined: 9th Jan 2018
Location:
Posted: 8th Nov 2018 11:58
Link
Thanks, oh I see!
Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2024-11-21 13:04:32
Your offset time is: 2024-11-21 13:04:32