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.
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.
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.
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.
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,
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
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!