Graal Forums - Flood fill issue

Graal Forums (https://forums.graalonline.com/forums/index.php)

- New Scripting Engine (GS2) (https://forums.graalonline.com/forums/forumdisplay.php?f=153)

- - Flood fill issue (https://forums.graalonline.com/forums/showthread.php?t=134262845)

Flood fill issue

well I attempted two methods to create a tile flood fill, first method is working fine, but is slow, second seems to be fast but stops after 3 'lines', the queue is updated in it but is temp.queue for the for-each loop updated?

PHP Code:


		
			
function floodFill( temp.tile, temp.targetTile, temp.replaceTile)
{

  /*//Method 1 - SUCCESS -
  temp.queue = { temp.tile};

  while (( @ temp.queue) != ( @ {{ NULL, NULL}}))
  {
  
    temp.n = temp.queue[ 0];
    
    if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.n[ 0], temp.n[ 1]] == temp.targetTile)
      triggerServer( "weapon", name, "PlaceTiles", Tile_Editor_Layer.text, { temp.replaceTile}, { temp.n[ 0], temp.n[ 1], 1, 1}); 

    temp.queue.delete( 0);
    
    for ( temp.a = 0; temp.a < 4; temp.a ++;)
    {
    
      if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.n[ 0] + ( !temp.a? -1: temp.a == 1? 1: 0), temp.n[ 1] + ( temp.a == 2? -1: temp.a == 3? 1: 0)] == temp.targetTile)
      {
    
        triggerServer( "weapon", name, "PlaceTiles", Tile_Editor_Layer.text, { temp.replaceTile}, { temp.n[ 0] + ( temp.a == 0? -1: temp.a == 1? 1: 0), temp.n[ 1] + ( temp.a == 2? -1: temp.a == 3? 1: 0), 1, 1}); 
        temp.queue.add({ temp.n[ 0] + ( !temp.a? -1: temp.a == 1? 1: 0), temp.n[ 1] + ( temp.a == 2? -1: temp.a == 3? 1: 0)});

      }
    }
    
    sleep( 0.05); //Added to prevent freeze
    
  }
  */
  
  // Method 2 - BROKEN
  
  temp.queue = { temp.tile};
  
  for ( temp.n: temp.queue)
  {
  
    if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.n[ 0], temp.n[ 1]] == temp.targetTile)
      temp.w = temp.e = temp.n[ 0];
      
    while ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.w - 1, temp.n[ 1]] == temp.targetTile)
      temp.w --;
        
    while ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.e, temp.n[ 1]] == temp.targetTile)
      temp.e ++;
   
    for ( temp.a = temp.w; temp.a < temp.e; temp.a ++;)
    {

      if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.a, temp.n[ 1]] == temp.targetTile)   
        triggerServer( "weapon", name, "PlaceTiles", Tile_Editor_Layer.text, { temp.replaceTile}, { temp.a, temp.n[ 1], 1, 1}); 
        
      if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.a, temp.n[ 1] - 1] == temp.targetTile)  
        temp.queue.add({ temp.a, temp.n[ 1] - 1});
        
      if ( player.level.tilelayers[ Tile_Editor_Layer.text].tiles[ temp.a, temp.n[ 1] + 1] == temp.targetTile)  
        temp.queue.add({ temp.a, temp.n[ 1] + 1});
        
    }
    
    sleep( 0.05); //Added to prevent client from freezing
    
  }
  
  return;  

}

It's slow because you're sending a trigger for every tile.

It'd be faster if you just built the list of tiles that need to be changed, looped through the list altering each tile as required as well as find the top-left and bottom-right most tiles in the process, and updated the resulting rectangle.

Edit: This was fun.

PHP Code:


		
			
//#CLIENTSIDE



function onMouseDown() {

  floodFill(int(mousex), int(mousey));

}



// Flooding Fill (Works better)

function floodFill(tx, ty) {



  temp.queue.add({tx, ty});

  temp.tile = player.level.tiles[tx, ty];

  maxlooplimit = 100000;

  

  while (temp.queue.size() > 0) {

  

    tx = temp.queue[0][0];

    ty = temp.queue[0][1];

    temp.queue.delete(0);

    

    for (temp.i = 0; temp.i < 4; temp.i++) {

      temp.nx = tx + vecx(temp.i);

      temp.ny = ty + vecy(temp.i);

      if (checkTile(nx, ny, temp.tile)) {

        if (!((@{nx, ny}) in temp.queue)) {

          temp.queue.add({nx, ny});

        }

      }

    }

    

    floodTile(tx, ty);

  }

}



// West-to-East then North-to-South method.

function floodFill2(tx, ty) {



  temp.queue.add({tx, ty});

  temp.tile = player.level.tiles[tx, ty];

  maxlooplimit = 100000;

  

  while (temp.queue.size() > 0) {

  

    tx = temp.queue[0][0];

    ty = temp.queue[0][1];

    temp.queue.delete(0);

    

    temp.west = tx - 1;

    while (checkTile(west, ty, temp.tile)) {  

      temp.west--;

    }

    

    temp.east = tx + 1;

    while (checkTile(east, ty, temp.tile)) {

      temp.east++;

    }

    

    for (temp.tx = temp.west + 1; temp.tx < temp.east; temp.tx++) {

      if (checkTile(tx, ty, temp.tile)) {

        floodTile(tx, ty);

      }

      if (checkTile(tx, ty - 1, temp.tile)) {

        temp.queue.add({tx, ty - 1});

      }

      if (checkTile(tx, ty + 1, temp.tile)) {

        temp.queue.add({tx, ty + 1});

      }

    }

  }

}



function checkTile(tx, ty, tile) {

  if (tx in |0,64| && ty in |0,64|) {

    if (player.level.tiles[tx, ty] == tile) return true;

  }

  return false;

}



function floodTile(tx, ty, nosleep) {

  player.level.tiles[tx, ty] = 322;

  updateboard(tx, ty, 1, 1);

  if (!nosleep) sleep(0.05);

}