Yet Another Pathfinder example

[MuddyMole]

Me again, with yet another pathfinding example...

This is mostly a proof-of-concept at this point, and I haven't added the actual movement yet, but it does find a path - look at the bottom of the list output. I left in all the other debugging text, because it might help people understand what the algorithm is doing as it searches for a path. I will hopefully release a more polished example soon...

Download: https://1drv.ms/u/s!Atq7cUIJ7uextEuI...MCZCf?e=L4XdKg



Like my previous example, it's an implementation of the A* algorithm on a non-grid-based map. Unlike my previous example, this one is designed to be extremely simple, but not necessarily efficient or robust (I expect it to be slow on maps with many nodes). It doesn't use any complicated maths, it's only about 35 lines of code (incl. comments) instead of 130, and you don't even have to define polygons any more.

It doesn't use any extensions, and in fact the only objects required are Actives and Backgrounds, so it should (though I have no way of testing this) be compatible with all runtimes.
As always, feel free to share, modify and use it however you want

btw: I only just noticed the new(?) "Pick objects with minimum/maximum expression value" condition, and it's super-useful, so thanks Clickteam!

[NaitorStudios]

You again?! xD
Amazing work! Looking forward for the updates on this.

So, how does it know the shapes exactly?
I know it got nodes, but I wonder how it knows if it's part of one or another...

[MuddyMole]

So, how does it know the shapes exactly?
I know it got nodes, but I wonder how it knows if it's part of one or another...

It doesn't. It just uses normal collision detection with the background obstacles to work out which nodes are connected (you have to put the nodes slightly outside the obstacles).
Normal collision detection is obviously slow, but the advantage of this approach is that you don't need nearly as many nodes, and it's pixel-perfect. This example uses 32 nodes, which is fewer than a 6x6 tile grid (which would use 36) - and most of the collision detection is just done once at the start of the frame, so you don't need to do it each time you search for a path.

[NaitorStudios]

Really interesting, curious to see it actually moving!

[MuddyMole]

Basic unit movement has now been added:



Download: https://1drv.ms/u/s!Atq7cUIJ7uextFDM...l_LRZ?e=6oY2nh

[NaitorStudios]

Awesome!
Hmmm, I wonder why it goes to node 8 instead of 27 in this particular scenario...
Is that really the fastest path?

[MuddyMole]

Nope, you're right. I stumbled upon the same bug, but it shouldn't be too hard to fix. There might be a performance hit though...

[MuddyMole]

Hmmm, I wonder why it goes to node 8 instead of 27 in this particular scenario...
Is that really the fastest path?

Try now: https://1drv.ms/u/s!Atq7cUIJ7uextFEB...IR_wX?e=FZLgad
I'm hoping that should have fixed it... ( some of the code comments might be outdated now, but I'm going to comment everything more thoroughly later anyway)

[NaitorStudios]

Oh yeah, seems a lot better!

[SevenSails]

Great work Muddy! Thanks for sharing!