Jump to content
  • Advertisement
3dmodelerguy

Optimization Is my room detection algorithm optimal?

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement

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.

Edited by Zakwayda

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!