Flood Fill in TileLayer

#1 Are you clicking on a tile map and wanting it to fill with a specific sprite until it hits boundaries? Or is your program set up a different way? (Just trying to clarify the problem.)

#2 I randomly fill a t2dTileLayer with 1 of 6 colors. Then the user clicks on a button outside the tile layer that corresponds to one of the colors.

This changes the top left tile to that color (and any adajacent tiles if they happened to be generated with the same color as the top left tile) to that newly selected color. These are added to the fill list.

Then I check all neighboring tiles (no diagonols) in the fill list and if their neighbor is the same color, add those to the fill list again. User clicks a button again, repeat...

EDIT: removed link to project

btw, William... Nice shiny new associate label there. :)

#3 That's a pretty fun little game you've got there!

In general, recursion is your friend in these situations. Unfortunately, given the size of your board, you'll exceed the stack depth.

You don't really need to keep a list of tiles either, so go ahead and remove that.

Since we can't use recursion, the next best thing is a stack. Add this code either in its own file or at the top of the fillGrid.cs:

function Stack::onAdd( %this )
{
  %this.len = 0;
}
function Stack::push( %this, %val )
{
  %this.v[%this.len] = %val;
  %this.len++;
}
function Stack::pop( %this )
{
  if( %this.len == 0 )
  {
    error( "Stack Underflow." );
    return "";
  }
  %this.len--;
  return %this.v[%this.len];
}

It's pretty straightforward. You "push" things to the end of a list and "pop" things from the end of the list.

With a stack, you can replace all of your code with the following few lines:

function fillGrid::setCurrentColor( %this, %newColor )
{
  %this.userClicks++;

  // Start in the upper left-hand corner.
  %oldColor = %this.getTileCustomData( 0, 0 );
  %this.floodFill( %oldColor, %newColor, "0 0" );
}

function fillGrid::floodFill( %this, %oldColor, %newColor, %pos )
{
  // Build a stack and push on the starting position.
  %stack = new ScriptObject() { class = Stack; };
  %stack.push( %pos );
  
  // Get the maximum bounds of this tile grid.
  %maxX = %this.getTileCountX();
  %maxY = %this.getTileCountY();
  
  // If there is anything in the stack, we'll process it.
  while( %stack.len > 0 )
  {
    // Get us an item off the stack.
    %top = %stack.pop();
    %x = getWord( %top, 0 );
    %y = getWord( %top, 1 );
    
    // Check that we match the old color.
    %currColor = %this.getTileCustomData( %top );
    if( %currColor !$= %oldColor ) continue;
    
    // Fill the tile and set its custom data.
    %this.fillTile( %top, %newColor );
    
    // Push all adjacent squares onto the stack being
    // careful not to go past the edges of the grid.
    if( %x > 0 )
      %stack.push( (%x - 1) SPC %y );
    if( %x < %maxX - 1 )
      %stack.push( (%x + 1) SPC %y );
    if( %y > 0 )
      %stack.push( %x SPC (%y - 1) );
    if( %y < %maxY - 1 )
      %stack.push( %x SPC (%y + 1) );
  }
}

If you have any questions, don't hesitate to ask!

This is the kind of thing, that while it runs very fast in script, I tend to migrate to C++ over time. I have my own "SList" class in C++ which I use for stacks and queues.

I just got the associaet label last night! It's exciting!

#4 Doh! As always, I forget something silly.

At the end of the "floodFill" function, add this:

%stack.delete();

Later!

#5 That works perfectly! I wish I could say that the idea was mine but I was creating it to get more familiar with how the tile layers work. Still learning a lot about the engine. The game that inspired it was Flood-It! by LabPixies.

Glad to see that GG recognized you - all your help on the forums certainly warranted it!

#6 Even if it isn't your idea, at least you're trying to learn as much as possible. Looking at your code, I can tell that you've got quite a bit of the language under control. You shouldn't be ashamed of it at all. Between you and me, I think you could easily create a star-based, role-playing, iPhone game with purchasable inventories. You know... not to be specific.

#7 Ha! That I could. Thanks again William.

#8 So I've had a little time to tinker with this and am having trouble implementing a win condition.

I think I should track the number of tiles a player occupies then compare to the total number or tiles in the grid...

But I've read through the code dozens of times and stepped through it a ton as well but I can't seem to get a grip on how to track the number of filled tiles the player occupies.

Any help appreciated-
Patrick

#9 "floodFill" doesn't go into squares that match your current color. So even if you did keep track of the number of changes it made, you'd still miss out the the final squares that matched the final color.

I'd just write a function that checks the upper left-hand corner against the other tiles and bails out early on any mismatch. Something like

function fillGrid::isSolid( %this )
{
  %ulData = %this.getTileCustomData( 0, 0 );
  %maxX = %this.getTileCountX();   
  %maxY = %this.getTileCountY();   

  for( %x = 0; %x < %maxX; %x++ )
  {
    for( %y = 0; %y < %maxY; %y++ )
    {
      if( %this.getTileCustomData( %x, %y ) !$= %ulData )
        return false;
    }
  }
  return true;
}

Just call this in the onClick callback or "setCurrentColor" to see if the grid is filled with the same color.

Later!

#10 P.S. That shouldn't be slow, even on a pretty large grid. But if it is, I'd be willing to show you how to convert the logic of the model into C++. Later!

#11 Hey William, Happy Easter if that's your thing. :)

I appreciate the help here. I added in the isSolid function and it works well. I had previously reduced the size of the grid a bit so the code provided is really snappy.

In an effort to not be so 'rip-off-ish' I added a second player and am leaning toward making it a two player turn based strategy game where each player tries to take over more tiles head to head.

So, as of now the issue is determining who has the most tiles filled when there are no more tiles to fill. Am I getting into source-land or do you think I can resolve this in script?

EDIT: removed link to project

Thanks again!

#12 It's not my thing, but I celebrated it anyway with family and had a good time, so it was happy! Hope you had a Happy Easter, too (if that's your thing)!

I'll take a look at your code first thing in the morning (long drive... not so happy). But at first guess, I'd just modify the "isSolid" function into a "countColor" function that takes a parameter of a color (I'm assuming that each player is assigned a unique color) and uses that instead of "%ulData". Now you'll know the score of each player. In addition, when the sum of the two numbers equals the number of squares, you'll know the game is over.

I've downloaded the RAR, so if you don't want to keep it up, you can remove it.

Night!

#13 Thanks Will!

I considered adding an additional color for each player to show territory but I ran into the issue that they then can't see what the current color is to take over...

If I can get this to store a list/stack/etc of captured tiles for each player, I was thinking I could then use an additional tile layer above for per tile effects and such. For instance, it would be cool to play an animated sprite over each of the newly captured tiles, be able to determine the outer set of the player's territory to build a do the same with their entire territory, etc.

Look forward to hearing back from you both on the technical and if you think this two player mode would be fun to play.

EDIT:Removed link.

#14 It's a fun game! The strategy of just trying to take the most number of tiles immediately changes to taking the most number of tiles from your opponent. With the ownership of the squares, you might consider putting a thin border around each player's territory.

Since you've added the player to the tile's custom data, you can make modification to the depth-first search in the "floodFill" function. Now, you can process adjacent tiles if the current tile's color equals the old *OR* the new color. With that minor change in logic, you'll fill into the matching color tiles and mark those for the player.

I feel like this conversation is becoming very game specific, so I'll drop you an email with the 1-line change and more on making the borders.

#15 Excellent, thanks William!