PureBasic Array Flood Fill

PureBasic CartographPC - Click to Enlarge

I'm coding a mapping application in PureBasic for my group Arkanix Labs, that will be used to produce maps for a C64 RPG called 'Crimson Twilight'.

Actually, a mapping application already exists called 'CartographPC', produced by Arkanix Labs to do just that job, but it is coded in VisualBasic 6, itself no longer supported by Microsoft and increasingly difficult to run on more modern OS's.

At some point (and I can't remember when or why), I started rewriting the application in PureBasic.  All the basic features are included so far, but then it was suggested that I add a 'flood fill' feature to randomly fill areas of the map with selected graphics, to produce random looking patches of dirt, grass, paths and so on, without having to manually fill whole areas.  Hmmm...  flood fill.

A bit of research on the internet about flood fill turned up quite a few theories, the most common being 'recursion'.  Basically, a routine repeatedly calls itself until a certain stage is reached at which point the routine exits itself.

In CartographPC (at least in the PureBasic version) the map data is held in an array, so I needed to find a way to fill an array with certain numbers (which represent graphic blocks) which observed other existing graphics and potential boundaries such as the edge of the map or enclosed area.  To the more seasoned coder, this may present no issue, but I'm new(ish) to PureBasic coding so it was a bit of a challenge and this is what I came up with:

Procedure floodfill(x, y)
  
If a_MAPDATA(x, y) <> blnkchar
 ProcedureReturn 0
EndIf
  
If a_MAPDATA(x,y) = blnkchar
 rnd = Random(rancharsel)
 rnd = rnd - 1
If rnd < 0
 rnd = 0 
EndIf
 a_MAPDATA(x, y) = a_RNDCHARS(rnd)
EndIf
  
If x > 0  ; fill left
 floodfill(x - 1, y)
EndIf
  
If y > 0 ; fill up
 floodfill(x, y - 1)
EndIf
  
If x < mcw ; fill right
 floodfill(x + 1, y)
EndIf
  
If y < mch ; fill down
 floodfill(x, y + 1)
EndIf
 
EndProcedure

The routine is contained in a 'procedure' called 'floodfill(x, y)' that can be called from the main program.  A quick explanation of some of the things in the code above:

• a_MAPDATA(x, y) is my array holding the map layout with 'x' and 'y' being a location in the 2D array (matrix).
• 'blnkchar' is a variable which holds the number of the graphic block which is 'blank' on the map.
• 'rancharsel' is a variable containing the number of graphic blocks the user wants to use in the random fill.
• a_RNDCHARS(rnd) is an array that contains the graphic blocks the user wants to use in the flood fill.
• 'mcw' and 'mch' are variables holding the width and height of the map.

So what does each part of that routine do?

If a_MAPDATA(x, y) <> blnkchar
 ProcedureReturn 0
EndIf

The above is the base case which basically says that if the map or area being filled is no longer 'empty', then exit the procedure, or in PureBasic terminology 'ProcedureReturn 0'.

If a_MAPDATA(x,y) = blnkchar
 rnd = Random(rancharsel)
 rnd = rnd - 1
If rnd < 0
 rnd = 0 
EndIf
 a_MAPDATA(x, y) = a_RNDCHARS(rnd)
EndIf

This section checks if the element of the array we are currently on is empty (blnkchar) and if so, it generates a random number (rnd) between 0 and the number variable held by 'rancharsel'. The element in the map array is then changed to contain the number held in the random chars array (previously filled with graphic blocks selected by the user) at position 'rnd'.

If x > 0  ; fill left
 floodfill(x - 1, y)
EndIf

Now some magic (at least in my eyes) starts to happen.  The above checks to see if we are at the far left of the array and therefore map (x > 0).  If not, our 'x' position in the array is moved left (x -1) and the procedure returns to the beginning to change the map array and draw a graphic block on the map.  If we are at the far left of the array / map (x = 0), then we proceed to the next section in the procedure.

If y > 0 ; fill up
 floodfill(x, y - 1)
EndIf

Now we start moving up the map / array, checking and drawing until our 'y' position is '0', the top of the map.  Each time the routine loops around, it check left in the array first and then up in the array.  But of course, we could also move right or down in the array until we reach the far right or bottom of the map / array.  This is checked by the following:

If x < mcw ; fill right
 floodfill(x + 1, y)
EndIf
  
If y < mch ; fill down
 floodfill(x, y + 1)
EndIf

So each time the routine loops, the array is checked left, up, right then down from the current position.  If the drawing was updated on the screen slowly for every graphic block, which in the application it isn't because that would be too slow, the fill would snake around the screen up, left, right and down until boundaries or existing graphics are encountered, eventually leading to the array / map being filled with the desired graphics.

I'm sure that more seasoned coders could refine the code further and make it better / more efficient, but in this state it works for my application and that is fine by me!

If you want the raw code to copy and paste into PureBasic, grab it from Pastebin here...