User Tag List

Page 1 of 4 1 2 3 ... LastLast
Results 1 to 10 of 37

Thread: Polygon-based A* Pathfinding Example (extensionless)

  1. #1
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLC

    Join Date
    Jul 2008
    Location
    UK
    Posts
    1,490
    Mentioned
    16 Post(s)
    Tagged
    0 Thread(s)

    Polygon-based A* Pathfinding Example (extensionless)

    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 )

  2. #2
    Forum Moderator Fusion 2.5 MacFusion 2.5 DeveloperAndroid Export ModuleHTML5 Export ModuleiOS Export Module
    Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Fusion 2.5+ DLC (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)iOS Export Module (Steam)Universal Windows Platform Export Module (Steam)Firefly 3D Module (Steam)
    NaitorStudios's Avatar
    Join Date
    May 2010
    Location
    Brazil
    Posts
    1,123
    Mentioned
    9 Post(s)
    Tagged
    0 Thread(s)
    Thank you so much for this update!
    Your examples are always the best

  3. #3
    Clicker Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)iOS Export Module (Steam)Universal Windows Platform Export Module (Steam)

    Join Date
    Aug 2020
    Location
    Canada
    Posts
    97
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by MuddyMole View Post
    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

  4. #4
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLCAndroid Export ModuleHTML5 Export ModuleiOS Export ModuleUniversal Windows Platform Export ModuleSWF Export ModuleFirefly 3D ModuleInstall Creator Pro
    aenever's Avatar
    Join Date
    Jun 2013
    Posts
    1,651
    Mentioned
    34 Post(s)
    Tagged
    0 Thread(s)
    I was excited when you hinted that your original pathfinding idea could be improved for Click & Point games. This is very impressive, thank you.

  5. #5
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLCAndroid Export ModuleHTML5 Export ModuleiOS Export ModuleUniversal Windows Platform Export ModuleSWF Export ModuleFirefly 3D ModuleInstall Creator Pro
    aenever's Avatar
    Join Date
    Jun 2013
    Posts
    1,651
    Mentioned
    34 Post(s)
    Tagged
    0 Thread(s)
    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.

  6. #6
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLC

    Join Date
    Jul 2008
    Location
    UK
    Posts
    1,490
    Mentioned
    16 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by aenever View Post
    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...

  7. #7
    Clicker Fusion 2.5Fusion 2.5 Mac
    Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Fusion 2.5+ DLC (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)iOS Export Module (Steam)Universal Windows Platform Export Module (Steam)
    zip2kx's Avatar
    Join Date
    Jun 2015
    Posts
    889
    Mentioned
    18 Post(s)
    Tagged
    0 Thread(s)
    woah, this is amazing

  8. #8
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLC

    Join Date
    Jul 2008
    Location
    UK
    Posts
    1,490
    Mentioned
    16 Post(s)
    Tagged
    0 Thread(s)
    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...


  9. #9
    Forum Moderator Fusion 2.5 MacFusion 2.5 DeveloperAndroid Export ModuleHTML5 Export ModuleiOS Export Module
    Fusion 2.5 (Steam)Fusion 2.5 Developer (Steam)Fusion 2.5+ DLC (Steam)Android Export Module (Steam)HTML5 Export Module (Steam)iOS Export Module (Steam)Universal Windows Platform Export Module (Steam)Firefly 3D Module (Steam)
    NaitorStudios's Avatar
    Join Date
    May 2010
    Location
    Brazil
    Posts
    1,123
    Mentioned
    9 Post(s)
    Tagged
    0 Thread(s)
    Going to the closest point if clicking a obstacle is amazing!

  10. #10
    Clicker Fusion 2.5 DeveloperFusion 2.5+ DLCAndroid Export ModuleHTML5 Export ModuleiOS Export ModuleUniversal Windows Platform Export ModuleSWF Export ModuleFirefly 3D ModuleInstall Creator Pro
    aenever's Avatar
    Join Date
    Jun 2013
    Posts
    1,651
    Mentioned
    34 Post(s)
    Tagged
    0 Thread(s)
    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.

Page 1 of 4 1 2 3 ... LastLast

Similar Threads

  1. New Pathfinding Example (extensionless)
    By MuddyMole in forum Fusion 2.5
    Replies: 28
    Last Post: 17th January 2022, 01:19 PM
  2. Easy Pathfinding Widget (extensionless)
    By schrodinger in forum Fusion 2.5
    Replies: 206
    Last Post: 31st December 2019, 04:22 AM
  3. Pathfinding using nodes of a polygon
    By voodooidiot in forum Fusion 2.5
    Replies: 4
    Last Post: 6th August 2018, 04:35 PM
  4. Polygon-based Shadowcaster
    By MuddyMole in forum File Archive
    Replies: 9
    Last Post: 31st October 2013, 01:41 PM
  5. Tree-Based Pathfinding Example (VERY basic WIP)
    By Dines in forum File Archive
    Replies: 15
    Last Post: 11th July 2007, 06:09 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •