8 votes

I made a video to showcase / explain my free space pathfinding algorithm.

8 comments

  1. [4]
    Emerald_Knight
    Link
    I could be off the mark, but this sounds to me like a version of hierarchical path finding. If we consider that even "free space", when represented digitally, has a finite amount of granularity,...

    I could be off the mark, but this sounds to me like a version of hierarchical path finding.

    If we consider that even "free space", when represented digitally, has a finite amount of granularity, then even a "free space" system is really just a grid system with sufficiently small unit size. So we're definitely still working with a grid here. The sheer quantity of grid nodes in such a system would be far too numerous to reasonably process, however, so in order to more efficiently process them it's better to group them into distinct clusters (in your case, the concept of "node boundaries"). The initial path is planned out for travel between clusters, then the final path is laid out by planning out the paths within the individual clusters. Fewer nodes to process from the very beginning, then each of the nodes involved in the final solution represent much smaller, easier to solve problems that can be handled very quickly.

    You appear to be subdividing the space into rectangular boundaries, plotting the top-level path between those boundaries, then plotting the path within the individual boundaries by considering details like boundary intersection and whether the start and end points are both contained within the same boundary space. This definitely seems to qualify as hierarchical path finding to me.

    I think one of the most important considerations for your approach, however, is that your maps are very grid-like. Not having tons of tiny, densely-packed, irregularly-placed obstacles, or many smooth-curve paths--more generally, regions that can't be easily subdivided into rectangular sub-regions--makes the boundary-intersection strategy effective. I'd be curious to see how your algorithm benchmarks when stress-tested.

    Cool to see that you independently developed your own hierarchical path finding strategy, in any case. Nice work!

    4 votes
    1. [3]
      Apos
      Link Parent
      I looked into hierarchical pathfinding, but I don't think it is quite right to call this algorithm a version of that. Hierarchical pathfinding requires 2 steps. Step 1, you find a high level...

      I looked into hierarchical pathfinding, but I don't think it is quite right to call this algorithm a version of that. Hierarchical pathfinding requires 2 steps. Step 1, you find a high level abstract path. Step 2, you find the actual path by looking precisely over where you're walking. My algorithm only does step 2. (Though it would be interesting to add a hierarchical layer over my pathfinding for really large maps. (How to do that and preserve the shortest path property is another matter.))

      I think the confusion comes because I explained the concept of node boundaries badly. A node boundary is a mechanism that tries to request your attention when you exit them. That's pretty much all they do. This behavior is useful because of the way I divide the map. In other words. You do pathfinding as usual, but as soon as you exit a node boundary, that's when you "stop" the algorithm and start thinking. This thinking is what ends up finding the map features such as corners.

      About your first comment:

      If we consider that even "free space", when represented digitally, has a finite amount of granularity, then even a "free space" system is really just a grid system with sufficiently small unit size.

      This is like saying everything is a 1 or a 0 but it's not particularly interesting. Here I'm talking about free space in the "mathematical" sense. (If I'm allowed to say that.) My algorithm isn't limited to a specific implementation. I can move at infinite precision. In theory, you can have an infinite area to explore. With the version I explain in the video, I can have rectangle obstacles that have any arbitrary sizes.

      Thanks for your feedback. If this still isn't clear, I can explain it better and make images so you can run the algorithm mentally.

      2 votes
      1. [2]
        Emerald_Knight
        Link Parent
        My reply to this is a bit late. I apologize for that, as I've been a bit busy. I seem to have misunderstood the way your algorithm works, probably because of how late it was when I wrote the...

        My reply to this is a bit late. I apologize for that, as I've been a bit busy.

        I seem to have misunderstood the way your algorithm works, probably because of how late it was when I wrote the original comment. It sounds like instead you perform either boundary-based or edge-based traversing of your map, possibly in the form of a depth-first search. During this search, your boundary intersections effectively act as a sort of "pseudo-node", and it's along these pseudo-nodes that you perform the actual movement. The exiting of these boundaries is what allows you to calculate these intersections.

        Does that sound accurate? I don't actually have any code to look at, so I only have the high-level overview to work with. The actual underlying details I can only speculate at. I'd be interested in a more detailed explanation if I'm still off about the details! :)

        This is like saying everything is a 1 or a 0 but it's not particularly interesting. Here I'm talking about free space in the "mathematical" sense.

        I completely understand what you meant. That being said, the real world can only be expressed digitally to some defined resolution. For instance, the quantity of real numbers between 1 and 2 is infinite, yet digitally we can only express an infinitely small subset of the real numbers between 1 and 2. You can certainly redefine the resolution at any given point, and we can even make the assumption that we utilize your algorithm in a space with infinite resolution. But ultimately we have to define some resolution, which makes the space you're operating on a grid system.

        Because the space you're operating on is always a grid system, there are some important implications. For instance, imagine if you tried to apply these rectangular boundaries to a series of interconnected circular areas--there could be potentially infinitely many boundaries in order to obtain full map coverage, because a rectangle that doesn't spill out of a circle can never cover the entire area of the circle and vice versa. Because of this, the number of boundaries required could end up being proportional to the resolution of your space, depending on how that space is shaped. The fact that your boundaries work as well as they do could very well be because your maps are shaped as interconnected rectangles and don't contain any high-resolution curves. This is clearly a point that you're already aware of, since you've explicitly qualified your explanation with "I can have rectangle obstacles", but I just want to emphasize why it is that I'm focusing so much on the underlying notion of "free space" when contrasting mathematical free space and digital free space.

        This doesn't, in any way, detract from the idea of utilizing the algorithm in mathematical free space. In fact, it suggests that your algorithm could be incredibly effective for determining shortest paths within rectangular-shaped maps because of the usefulness of the clustering and event-driven processing. It's only a re-framing of the problem to allow us to point to similar problem spaces and to better consider the strengths and potential limitations of the algorithm.

        I feel like we're both on the same page, but what we're emphasizing is different. I apologize for being so unclear previously.

        2 votes
        1. Apos
          (edited )
          Link Parent
          This is good, I think you have a good understanding. I plan on releasing a white paper. Your feedback is really important so I can explain it better. I haven't done the full research yet, but I...

          This is good, I think you have a good understanding. I plan on releasing a white paper. Your feedback is really important so I can explain it better.


          I haven't done the full research yet, but I believe the algorithm can be expanded for various shapes like circles. I can divide a circle into 4 quadrants. Instead of having the nodes be rectangle, they could define the circle's shape better. https://i.imgur.com/KE1GXFG.png
          Or triangles: https://i.imgur.com/j0FZ8lZ.png
          (My drawings look similar, but the yellow shape defined by a circle would not be the same as a triangle.)

          If my theory is right, I wouldn't need to divide space infinitely.

          Bonus: (Horrible drawing I know...) https://i.imgur.com/b9RNBoN.png (Normally the nodes would line up.)


          Something else that can be interesting. You could add an extra layer on top of my space division with terrain cost values. Then you could calculate shortest path (Water, mud, road, forest, etc.). Now the straightest path wouldn't always be the shortest. The extra layer would handle that.


          I also believe this algorithm could be applied to moving terrain.


          Out of the box, the algorithm can handle unit sizes. A big fat tank will naturally not be able to pass through a small hallway. I get that for free from the map division.


          As you can see, my current game only handles the simplest case. In my next game, I would most likely try to see how I can push it with the ideas above.

          1 vote
  2. Apos
    Link
    I recorded this the other day. I started working on this algorithm back in 2013. At that point, I figured out a cool way to divide the search space. I worked on a first implementation, but it...

    I recorded this the other day.

    I started working on this algorithm back in 2013. At that point, I figured out a cool way to divide the search space. I worked on a first implementation, but it wasn't conclusive.

    In 2016, I decided to start from scratch, building on my previous research. That's when I discovered how to create nodes from my search space optimization. That started to give me some good results.

    In 2017, I found a way to massively simplify the algorithm using what I call "node boundaries".

    What's nice with this algorithm is that it finds paths in free space meaning that movement isn't limited to a grid. There are ways to expand it to handle different unit sizes, moving obstacles, and terrain with various shapes but I didn't go into that in this video.

    2 votes
  3. [3]
    vektor
    Link
    I'm gonna touch on visualization real quick here: Those dark green overgrown tiles don't exactly scream blocked to me. Took me two or three takes to realize that it was indeed finding the shortest...

    I'm gonna touch on visualization real quick here: Those dark green overgrown tiles don't exactly scream blocked to me. Took me two or three takes to realize that it was indeed finding the shortest path when it was pathing around "invisible" walls.

    2 votes
    1. Apos
      Link Parent
      Good point. I made the game, so I don't even think about that anymore. Just looks obvious to me. That's something I am still trying to figure out. How to justify not being able to walk everywhere....

      Good point. I made the game, so I don't even think about that anymore. Just looks obvious to me.

      That's something I am still trying to figure out. How to justify not being able to walk everywhere. Not sure if the puzzle element is enough to justify this art direction.

      2 votes
    2. Apos
      Link Parent
      I actually had a video from a while ago that is easier on the visualization: https://www.youtube.com/watch?v=97uk5ABxGVs Can't believe I forgot about it the other day.

      I actually had a video from a while ago that is easier on the visualization: https://www.youtube.com/watch?v=97uk5ABxGVs

      Can't believe I forgot about it the other day.

      1 vote