Flood Fill Path Finder

[kevin]

  Flood Fill Path Finder


      This code is a version of my flood fill path finding routine that was    originally written way back in the late Amiga days, some 20 odd years ago    now. The raw concept was inspired by the game Chaos Engine by the Bitmap    Brothers, which featured a cooperative mode with a second AI player, even    when playing in single player modes.   What struck me was how well the AI    player could fight and locate power ups, which seemed just like the a    human player at the time.  Today this kind of AI has is almost common    place, but it seemed new back in the 16bit days.  I don't actually know    how Chaos Engine's AI algorithms work, just that it was seed for this    idea. But like a lot of good ideas, this just ended up gathering dust on    my legacy hard drive until now.  


    HOW IT WORKS:

      The search routine bellow works likes a flood filling routine, which    you've probably already guessed.   The concept behind this routine breaks    down to this.  We can find any target cell within the map, by filling out    from the starting coordinate in 1 cell steps in all directions (Left, Up,
   Right & Down), and then in turn filling out around those.  So when a map cell    around a starting point is empty say (Walkable), then we add those    coordinates to a list of cells to be search next pass and most importantly    store the coordinates of the parent cell in those locations.   We repeat this    process over and over until we reach the target or there no more open map    cells to check.
       
       It's probably best explained by an example.  Bellow we have a map showing    the solid walls as ##, empty space as -- and our start and end points     as SP (START POINT) and EP (END POINT).  
       
       Key:

           SP  = STARTING point
           EP  = END / TARGET Point
           ##  = WALL
           --  = CLEAR PATH

           Linked Coordinates will be represented as 2 numeric digits XY,
           so a 34 in a cell means that cell links to 3X,4Y on the grid.
           That is to say, that it's the child of that parent cell.

Code Select Expand


       
       0  1  2  3  4  5  6  7  8  9 X
    0 ## ## ## ## ## ## ## ## ## ##
    1 ## -- -- -- -- -- -- -- -- ##
    2 ## -- -- -- ## ## -- EP -- ##
    3 ## -- ## ## ## ## -- -- -- ##
    4 ## -- -- -- -- ## -- -- -- ##
    5 ## -- -- -- -- ## -- -- ## ##
    6 ## -- SP -- -- ## -- -- ## ##
    7 ## -- -- -- -- -- -- -- ## ##
    8 ## -- -- -- -- -- -- -- ## ##
    9 ## ## ## ## ## ## ## ## ## ##
    Y
     
         Map Cells To be searched list: 26  

     
     
       So if we look at the map after one search sweep, it'd look like this.    The cells around the starting point have been searched and added to the    list of cells to search next sweep.  The previously empty cells    around the starting point all now have a parent cell number of 26 (2x,6y).    All those empty cells were added to the to be search next sweep list.          

Code Select Expand



       0  1  2  3  4  5  6  7  8  9 X
    0 ## ## ## ## ## ## ## ## ## ##
    1 ## -- -- -- -- -- -- -- -- ##
    2 ## -- -- -- ## ## -- EP -- ##
    3 ## -- ## ## ## ## -- -- -- ##
    4 ## -- -- -- -- ## -- -- -- ##
    5 ## -- 26 -- -- ## -- -- ## ##
    6 ## 26 SP 26 -- ## -- -- ## ##
    7 ## -- 26 -- -- -- -- -- ## ##
    8 ## -- -- -- -- -- -- -- ## ##
    9 ## ## ## ## ## ## ## ## ## ##
    Y
     
      To be searched list: 16, 25 , 36, 27  

     

       Now since the to be search list contains 4 pairs of search coordinates     from the previous sweep and none of those is the END point, we must repeat     the previous process for each those coordinates.   So we grab the first     pair 16 (1x,6y) and check the tiles left/above/right and bellow it.      If any of those is empty, we add that cell to the to be searched list and tag it with the 16 (1x,6y) as it's parent and then move onto     the  25 (2x,5y) , 36 (3x,6y) and 27 (2x,7y)  
     
       So the map after this round of checks the map looks like this.
       

Code Select Expand



       0  1  2  3  4  5  6  7  8  9 X
    0 ## ## ## ## ## ## ## ## ## ##
    1 ## -- -- -- -- -- -- -- -- ##
    2 ## -- -- -- ## ## -- EP -- ##
    3 ## -- ## ## ## ## -- -- -- ##
    4 ## -- 25 -- -- ## -- -- -- ##
    5 ## 16 26 25 -- ## -- -- ## ##
    6 ## 26 SP 26 36 ## -- -- ## ##
    7 ## 16 26 36 -- -- -- -- ## ##
    8 ## -- 27 -- -- -- -- -- ## ##
    9 ## ## ## ## ## ## ## ## ## ##
    Y
   
      To be searched list:  15, 17 , 24, 35, 46, 37, 28    

           
     
      Ok, you'll notice the routine is flooding out from the START point evenly    only stopping when there's something blocking the path of the step such as    a wall or a tile that's already been examined.  

       Now if we skip ahead a few sweeps over the map, it will ends up looking      like this (Bellow).   In this case, since we found the END point during a     sweep the routine stops searching.   You need to keep sweeping until you    either find the END point or there are no new locations to be search.  The     latter means that all possible steps from the START have been examined     and none of them have panned out.  So the END can't be located from that      particular START point within the map.  
   

Code Select Expand


           
       0  1  2  3  4  5  6  7  8  9 X
    0 ## ## ## ## ## ## ## ## ## ##
    1 ## 12 11 21 31 -- 62 -- -- ##
    2 ## 13 12 22 ## ## 63 62 -- ##
    3 ## 14 ## ## ## ## 64 63 73 ##
    4 ## 15 25 24 34 ## 65 64 74 ##
    5 ## 16 26 25 35 ## 66 65 ## ##
    6 ## 26 SP 26 36 46 56 66 ## ##
    7 ## 16 26 36 46 56 66 76 ## ##
    8 ## 17 27 37 47 57 67 77 ## ##
    9 ## ## ## ## ## ## ## ## ## ##
    Y      

     
      Since the END was found, we compute the path from START to END,      starting at the END point and working backwards through the series of map     links.  Our END point in this example was at 72 (7x,2y), so we look at     that cell which will give us a link to the previous cell, Which inturn links to the cell before that and so on, until reaching the start.
   
      If you look carefully at the ASCII map above you should be able to     trace this path.
   
        EP->62->63->64->65->66->56->46->36->26->SP
   
   

      Since the core concept is based on flood filling here, then     there are some things the user should consider about this particular     method and its implementation in a real world game.


      1) The first thing that comes to mind, is that the path generated isn't
         necessary the shortest path between the START and END points.  
         This is because the routine doesn't actually bias it's search
         towards the direction of the End point, in favour of scanning out
         in all directions equally.   This means that you could potentially
         tweak the routine to find multiple resources/locations at once.
         Of course this example isn't specifically set up to do that.

      2) Like most filling routines, this method will examine more of the map
         than might otherwise be needed to find a target.  So in terms of
         efficiency this can have some impact on search performance on large
         maps.  Ideally any AI controller code would need to be selective
         about when it needs to recalculate a path.
         
         If you have big maps, then there's few ways to tackle such problems,
         such as splitting the maps into smaller zones/chunks or even splitting
         the search routine up so that can be executed in a serial fashion, which
         would break abnormally long searches down into bite sized mouthfuls per
         frame.  Beyond that you can pre-compute common data about the map
         which might storing the path finding map in a different way in order to
         bring down the cost of searching.
         
         One pre-computation hint would be that rather than storing the map as
         a grid of empty and hard zones, making the pathing routines examine
         all the cells around each cell to see if it can walk in that direction,
         what you could do, is store the empty zones as a direction bitmask.
         Where say LEFT = 8, UP = 4, RIGHT=2 and DOWN=1.  So an empty cell
         with no blocked paths around in all 4 directions would have a value of
         15 (8+4+2+1).   Then we use a select case / jump table to set of hand
         crafted routines compute the path for the known possible directions.
         This makes the code a lot bigger of course, but you'd actually be
         getting rid of many bogus array query comparisons from the search
         routines.  Which would further lower the search cost.

         Another tweak you make would be would changing the map from a 2D array
         to a 1D array, or bank with direct memory access.   The reasoning behind
         this would be to lower the cell reading overhead that 2D arrays have.
         You may or may not  be aware that such a data structure includes at
         least one multiple as well as clipping each of the on the array
         bounds, which can really add up.
         


       3) Diagonals? Now since this example builds a path by limiting movement
          though the map in only 4 directions.  The resulting path will be very
          angular on mostly empty maps.  So in this state it's probably best
          suited to a PAC MAN styled game environments, where the map is tight
          and busy.
         
          You could include diagonal movements though, it'd just require some
          extra map checking for those directions, as it's possible for a
          diagonal step to move between a pair of blocks.  Take a look at this.  
   
          Example,

Code Select Expand


           
       0  1  2  3  4  5  6  X
    0 ## ## ## ## ## ## ##
    1 ## -- -- -- -- -- ##
    2 ## -- -- -- EP -- ##
    3 ## -- ## -- -- -- ##
    4 ## -- SP ## -- -- ##
    5 ## -- -- -- -- -- ##
     6 ## ## ## ## ## ## ##
   Y


            If to look at Starting Point (SP) above then you'll notice that we
          can't move UP or RIGHT, but if it examined the map at UP->RIGHT which is
          the 3x,3y cell, then that's empty.  The routine as it stands would
          allow that step.  Now I guess it depends upon the situation, but if
          you had a tight pac man styled map than that move would normally be
          impossible, where as in other situations such a move might be legal.  
         
   

      Well, that about concludes my thoughts on this code, hopefully it gives  you some ideas about taking the subject further.


    LICENSE:

                  This source code is FREE for use with PlayBASIC only.

Download:

        Attached

[leopardps]

I spent quite a lot of time this year researching different pathfinding routines and various map representations to really understand them.  What you are describing above is basically a Breadth-First search(floodfill), and is almost Djikstra's Algo.  It is also the beginning of creating a full A-STAR routine (which you know because I found an A-STAR example of yours somewhere else).

There are a variety of methods used to make A-STAR work faster, but I am/was never really impressed by its performance overall - except in relatively small areas.  I REALLY like sub-goal pathfinding which basically pre-processes the map, creating waypoints(sub-goals) at all the corners, then finds a path through the sub-goals to the destination - lickitty-splt quick... BUT, its downfall is that it ignores (just like JPS does) movement/terrain costs.  A-Star is really the only thing that also will take into account move/terrain costs in its path determination.

As far as speeding up raw A-Star, Amit (red blob games) has some really good suggestions (binary heaps instead of arrays for open/closed lists) and good tutorials all around.

I do love the above flood-fill techniques, especially when having a bunch of agents searching for the same types of things (for instance, if you make one flood-fill map - basically an influence map - starting with all the 'trees' in the world, then if any agent is searching for the nearest tree, they can just lookup their location on this influence map and immediately have their next movement towards the nearest tree, with no real cost... doesn't slow down from 1 agent doing it to 10k agents doing it.... besides the overhead of handling 10k agents - lol!