Polygon-based A* Pathfinding Example (extensionless)

[MuddyMole]

This is an improved and commented version of the pathfinding example that I posted in a different thread (just trying to make it more searchable). I do have ideas for future improvements, but this is probably going to be it for a while.

It uses the A* (A-star) pathfinding algorithm, but unlike most other examples, it is not grid based. Instead, it uses polygons as obstacles, and these are defined by a list of vertices.
This means that it is pixel-perfect (not restricted by the resolution of the tile-grid) and objects can move smoothly in 360 degrees. It should also be much faster in many situations, since it uses far fewer nodes (it's currently limited to 100 nodes, which is the same number that a grid-based system would need for a map just 10x10 tiles in size, but I think I need to increase that to 1000).



Download: https://1drv.ms/u/s!Atq7cUIJ7uextBsC...0xv-z?e=3pcRAg
(as always, feel free to share, use and modify it any way you please )

[NaitorStudios]

Thank you so much for this update!
Your examples are always the best

[punchbird]

This is an improved and commented version of the pathfinding example that I posted in a different thread (just trying to make it more searchable). I do have ideas for future improvements, but this is probably going to be it for a while.

It uses the A* (A-star) pathfinding algorithm, but unlike most other examples, it is not grid based. Instead, it uses polygons as obstacles, and these are defined by a list of vertices.
This means that it is pixel-perfect (not restricted by the resolution of the tile-grid) and objects can move smoothly in 360 degrees. It should also be much faster in many situations, since it uses far fewer nodes (it's currently limited to 100 nodes, which is the same number that a grid-based system would need for a map just 10x10 tiles in size, but I think I need to increase that to 1000).



Download: https://1drv.ms/u/s!Atq7cUIJ7uextBsC...0xv-z?e=3pcRAg
(as always, feel free to share, use and modify it any way you please )

man, you should join a basketball team cause it's slam dunk after slam dunk. nice work again

[aenever]

I was excited when you hinted that your original pathfinding idea could be improved for Click & Point games. This is very impressive, thank you.

[aenever]

Just wondering how hard it would be to implement a feature if you wanted a click inside a polygon to move the player to the nearest node; rather than ignoring any click inside a polygon.

The reason I ask is that in some point and click games you can press on an empty space, like say on a wall. The player will move to the closest point with in the moveable area. Don't worry if it's not something you want to implement, it just an idea.

[MuddyMole]

Just wondering how hard it would be to implement a feature if you wanted a click inside a polygon to move the player to the nearest node; rather than ignoring any click inside a polygon.

Probably not that hard, actually
The point-in-polygon test already returns the id of the polygon, so it should just be a case of looping through every wall in that polygon, and doing a "point-on-line-segment-closest-to-another-point" test.
Happily, I already have an example of that kicking around: https://1drv.ms/u/s!Atq7cUIJ7uexhSeV...UV5-Y?e=fF20pC

I'll have a look...

[zip2kx]

woah, this is amazing

[MuddyMole]

Just another quick update, which you can download here: https://1drv.ms/u/s!Atq7cUIJ7uextB3V...jbTHY?e=MHiZCR

Unless I get more (easy to implement) suggestions, this really should be it for a while!

The changes include:

* Increased the node limit from 100 to 1000 (although you're bound to run into performance issues long before that).
* Optimized map loading/processing, so the delay at the start of the frame is reduced by about half.
* Clicking on an obstacle will now find a path to the closest reachable point on the edge of the polygon (as per Aenever's request).
* The "player" now rotates to face the direction it's moving.
* Other minor tweaks here and there...

[NaitorStudios]

Going to the closest point if clicking a obstacle is amazing!

[aenever]

Wow, I wasn't expecting this, let alone so soon. Thank you so much MuddyMole, this has reinvigorated my drive to finish making a point and click game.