So I have the following method to generate rooms using what I assume is a flood fill algorithm:

private void SetupRooms() {
  SimpleTimer t = new SimpleTimer();
  List<Vector2> tilesToFloodFill = new List<Vector2>();

  // first figure out which tiles need to be flood filled
  for (int x = 0; x < _worldWidth; x++) {
    for (int y = 0; y < _worldHeight; y++) {
      if (_hasColliders[x, y]) {
        _tiles[x, y].RoomIndex = WorldRoom.NO_ROOM_VALUE;

        continue;
      }

      tilesToFloodFill.Add(new Vector2(x, y)); 
    }
  }

  t.LogRunningTimeMilliseconds($"room flood fill first pass: ");
  t.ResetStart();

  Queue<Vector2> tilesToCheckAdjacentFor = new Queue<Vector2>();
  int currentRoomIndex = 0;
  int tilesProcessed = 0;

  while (tilesToFloodFill.Count > 0) {
    tilesToCheckAdjacentFor.Enqueue(tilesToFloodFill[0]);
    tilesToFloodFill.Remove(tilesToFloodFill[0]);

    while (tilesToCheckAdjacentFor.Count > 0) {
      tilesProcessed++;
      Vector2 tileToCheck = tilesToCheckAdjacentFor.Dequeue();
      List<Vector2> adjacentTiles = GetAdjacentTilePositions(tileToCheck);

      _tiles[(int) tileToCheck.x, (int) tileToCheck.y].RoomIndex = currentRoomIndex;

      for (int i = 0; i < adjacentTiles.Count; i++) {
        if (
          _tiles[(int) adjacentTiles[i].x, (int) adjacentTiles[i].y].RoomIndex != WorldRoom.UNASSIGNED_ROOM_VALUE
        ) {
          continue;
        }

        tilesToCheckAdjacentFor.Enqueue(adjacentTiles[i]);
        tilesToFloodFill.Remove(adjacentTiles[i]);
        _tiles[(int) adjacentTiles[i].x, (int) adjacentTiles[i].y].RoomIndex = currentRoomIndex;
      }
    }

    _worldRooms.Add(new WorldRoom());

    // current room should be filled, clean up for next room
    currentRoomIndex++;
  }

  t.LogRunningTimeMilliseconds($"room flood fill (tiles processed: {tilesProcessed}): ");

  Debug.Log($"total rooms: {currentRoomIndex}");
}

The general timing for this is:

• room flood fill first pass: : 1.8787ms
• room flood fill (tiles processed: 58463): : 6069.9302ms

While I only expect to have to run this algorithm on the entire map on the initial load of the map (and maybe a few special cases) I am still wondering if there is any way to optimize it to take less than 6 seconds to do it (I would ideally like to have maps 2 - 4 times bigger than the one I am currently testing on so I imagine it would be at 2 - 4 times slower on those maps).

Are there any optimization I can make here (including using a different algorithm) to optimize this process?

This may be obvious, but one suggestion is to make sure your environment is set up for more or less optimal performance. In e.g. C/C++ this would entail getting the timings from a release rather than debug build. I don't know exactly what environment you're working in (Unity? standalone?), but it might be worth double-checking that it's set up optimally for performance (whatever that means for your particular environment).

Another fairly obvious suggestion is to use a profiler.

For the record, I realize you may have already considered all of the above - I'm just trying to be thorough.

This is tangential, but your use of 'continue' seems a little atypical. It seems like the same thing could be accomplished with if-else, which I think would be easier to read.

You didn't include the code for GetAdjacentTilePositions(), but in any case it looks like that aspect of things could be done in place, eliminating the function call and the (presumed) creation of a new 'List' object each iteration.

It looks like you do this:

_tiles[(int) adjacentTiles[i].x, (int) adjacentTiles[i].y].RoomIndex

Twice. If tiles are stored by reference, you could grab the tile once and save the extra indexing. You could probably also avoid the repeated 'adjacentTiles' indexing, although as mentioned earlier you could instead do the 3x3 block iteration in place.

There's one or two other places you do the same indexing more than once, so you could maybe change that as well.

It looks like you might be assigning 'currentRoomIndex' to the same cells more than once (unless I'm misreading the logic), which would represent some unnecessary work. If I'm right about that, you should take out the one in the innermost loop. (Again though, I may not be tracking on the logic accurately.)

It might be faster just to, in the outer loop, skip 'tilesToFloodFill' tiles that don't need to be processed, rather than removing them as you go, since removal might be expensive for various reasons. You might even be able to eliminate the separate first pass that way, although obviously the first pass isn't costing you much.

There may be other obvious algorithmic improvements that could be made, but I'll stop there.

In summary, it looks like there might be some low-hanging fruit you could go after, but ultimately you'll probably want to profile if you haven't already.

I bet the problem is in one of the following lines:

List<Vector2> adjacentTiles = GetAdjacentTilePositions(tileToCheck);

It looks like you're dynamically allocating a container for each tile that you're checking.  Don't do that.  Also bad is this:

tilesToFloodFill.Remove(tilesToFloodFill[0]);

I'm not sure how this List type is implemented, but if it's a contiguous storage type comparable to Python lists and C++ std::vector, then you want to remove from the other end, and you want to use RemoveAt (assuming this is C#), not Remove.

Thanks for the input, let me address some of the points that I can.

About using `continue;`, that might not be common but I generall try to reduce code indention by returning early instead of doing if / else and in loops I do basically the same thing, just continue early. I have found it easier to read code the less indents I have but that is just me.

The reason I am setting `RoomIndex` in 2 different locations is because if I don't do it the second time, when I get adjacent tiles for the first set of adjacent tiles, those might include adjacent tiles for the previous tile I got adjacent tiles for and I need to make sure I do not try to process those tiles multiple times (without that second setting of `RoomIndex`, my game hangs for a really long time, so long that I just kill it). Maybe I can change how I get the adjacent tiles so that wont happen but that seems like it would be more complicated (at least for me with my lack of deep knowledge in algorithms / math of that kind) and wanted to avoid that if possible.

It does seem like @a light breeze was right about the `tilesToFloodFill.Remove()` that was causing most of my performance issues. While I could use `RemoveAt()` for one of the locations, the other location would not be as easy, I would have to `FindIndex()` which I figure would be just as bad as `Remove()`. Looking at the code again and I realized that I really did not need a `List` and instead could use a `HashSet` since I don't care about ordering or anything else a `List` can do that a `HashSet` can't, I just need a collection to make sure all tiles that should be processed are. When I switch to using a HashSet the time drop drom ~6000ms to about ~100ms.

While is what not the main cause, @a light breeze and @Zakwayda were also right that the creation of the a new list for adjacent tiles each time caused a little extra overhead too so instead I made that method take a ref that was passed in to the method for the `List` that way I created it once and just cleared it each loop which took it down further to ~80ms.

While there might be other things I can do to improve that time, I think I got it down to a level that I am more than happy and will save further optimization until and if I really need them.

Thanks for the insight.

1 hour ago, 3dmodelerguy said:

It does seem like @a light breeze was right about the `tilesToFloodFill.Remove()` that was causing most of my performance issues.

I mentioned that as well, but maybe I should have highlighted it more. Anyway, 6000 to 80 ms is a big improvement - glad you were able to fix the issue, more or less at least 

On 9/6/2019 at 2:40 AM, 3dmodelerguy said:

While there might be other things I can do to improve that time, I think I got it down to a level that I am more than happy and will save further optimization until and if I really need them.

For a next time, you may want to play with a profiler tool, which tells you the hot spots, in particular those that are not quite visible by code inspection.

You may even want to try that on the old version of your algorithm. You now know what it should say, making it easier to get some insight in how to read the output of the tool.