flood-fill and path-finding

1 favourites
From the Asset Store
An educational game for Fill in the Blanks. An easy to use template for developers to build larger games
  • After searching for simplest algorithm to perform pathfinding over tiles, came the solution: flood-find_path.capx

    Note that the logic was build from scratch not using existing pathfinding behavior.

    An article which gave me the concept: http://www.gamasutra.com/blogs/AdamSalt ... rtists.php

  • Hey alextro, <img src="{SMILIES_PATH}/icon_e_smile.gif" alt=":)" title="Smile">

    Just in case you're interested, a while back I found a really cool interactive demo of various path finding algorithms.

    https://qiao.github.io/PathFinding.js/visual/

    At the site listed above, I believe the "breadth-first-search" algorithm is equivalent to the "flood-fill-search" algorithm. (3rd in the list.)

    Construct 2's built in path-finding algorithm is A*, (which is pronounced "A Star"). (1st in the list.)

    One other special case path finding solution that can be handy is "Goal-Based" path-finding. This one is usually only good when you want to have a massive number of objects path their way to a single goal location.

    This is a video that does a nice job of explaining it.

    Subscribe to Construct videos now
  • fisholith

    Great references you got there. Interactive demo from Pathfinding.js sure teach a lot with various algorithms.

    And cool video demonstrates alternative method to achieve it.

    I am about to implement the case for existing flood-fill range demo: https://dl.orangedox.com/UkkZMMQmTfgSKdbeYx

    Actually that would be first part of tutorial (perhaps in future).

  • I would like to improve the searching time by implement bidirectional search with dual floodfill.

    Say A is starting point and B is the goal. Both point will flooding their neighbour until they flooded certain point that will act as an intersection, let's call it "C". Then The result is path cost/step to reach C for both that bring us to total cost by sum up them:

    Total_cost = A_cost + B_cost

    Now we just need to traceback from A. However the traces from B need to be converted to cost "how far them from A". We need to write new value from existing b_cost towards the goal.

    Total_cost-B_cost = A_cost

    So now early traces from B got an A_cost in correct order to complete entire node path. That should relatively fast in theory.

    Time to implement the idea.

  • It's tricky to improve performance with events. In my experience simpler is better and when doing something more complex to improve performance you also get more event and picking overhead which reduces overall improvement.

    That said you'll probably want to measure it with wallclocktime to get a good idea if you're getting any improvements. "best first" might be a better choice than bi-directional or even going full A* might reduce the amount of cells to search through.

    There are other things you can do too. One I tried is to not use the overlapping condition. Instead i populated an array with uid's so I could pick the neighbors directly so it wouldn't have to check all the instances if they're overlapping. That roughly made it twice as fast. I say roughly because it would take anywhere from 0.01 to 0.05, whereas before it was 0.03 to 0.08 seconds with my test. I can provide that capx if you'd like.

    A next iteration could be to do all of it in an array and do no picking. That would give further improvements but would be harder to read. I'd imagine you may be able to half the time again, but that's just a guess. The only problem is it's less visual and more abstract at that point and if you change the tiles around you'd need to update the arrays accordingly.

    The ultimate for speed would be to use js for most of it. Basically send the array or tile positions to some js code, then tell it a start and end tile. This is by far the most awkward and least flexible, but the performance improvement of calculating the path itself will be around 10x faster, or more with more tuning on the js side. This can be done with the browser object, since making a plugin would require a good design idea and take longer.

    Another thing i've done elsewhere is to not do it in just one frame, but instead do it over multiple frames so it doesn't affect the framerate.

  • Thanks R0J0hound for cover every possibility with it's pros and cons. A* seems fair enough for fixed same distance (grid). I always think there must be other way than using overlapping test. Since JS not my thing, I'd like to see an example that utilizing array like you said.

  • alextro

    That's probably not every possibility. Here's three different ways:

    This uses normal pick logics:

    https://dl.dropboxusercontent.com/u/542 ... kstra.capx

    This does it all in an array:

    https://dl.dropboxusercontent.com/u/542 ... array.capx

    This does the same as above but in js. There is some overhead of copying the map to and from js, and likely something more efficient could be done on the js side.

    https://dl.dropboxusercontent.com/u/542 ... ra_js.capx

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • That's a lot of example R0J0. I think I need extra time to understand them. I red that dijkstra algorithm is the most shortest possible route calculation.

  • alextro

    The dijkstra algorithm is what your capx is doing and is the algorithm used it the article you referenced.

  • With this, i just marked the this treath for future reference, now i can find it back. Sort to disturb.

  • Ok, i tried out that "Goal-Based" path-finding, mentioned earlyer.

    https://

    drive.google.com/open?id=0B1SSuCVV8v74QndqaUFQT2I3R0k

    Aynyone know how to manage the movements better ?

  • 99Instances2Go

    I can't read your variables, but if you stored the direction to move for each grid in the flood fill step then it's just a matter of moving the enemies in the same direction as the grid they are on.

  • That is what they do, they just overshoot, and when they move in a dense pack, they tend to get stuck. I choosed for fysics to get them moving by force aligning to the grid.

    Only one gets alignd / tick.

  • Updated my sample (first page) with better optimization.

    Also made interactive version from R0J0 example: pathfind_drag.capx

  • Add path direction visualization. Finally corner detection tackled!

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)