Best way to flood fill a tilemap?

  • Hi there! I'm starting to tinker around with new projects, and I'm interested in making a puzzle game where creating closed-off spaces on a tilemap is part of the gameplay - as such, I'm experimenting with flood fill methods, but I can't seem to get one that works efficiently and instantly.

    Here's my quick and dirty example - left click places walls, right click erases them, and middle click wipes the board and checks for enclosed spaces. (adjacent corners don't count as enclosed for my purposes!)

    battlestudio.com/tilefill

    And here's the .capx file:

    battlestudio.com/tilefill/TileFlood.capx

    As you can see, it works, and you can watch it work, but it's definitely way too slow. I'm sure there must be some ideal, optimal way of doing this - I'm hoping for something efficient enough that I can check it every time a piece is placed on the board without bogging things down. Any help would be appreciated!

    -- EDIT: UPDATE --

    I did a bit more tinkering and I think I found a solution! I'd still appreciate having my work double-checked though:

    battlestudio.com/tilefill-2

    And the .capx:

    battlestudio.com/tilefill-2/TileFloodFill-v2.capx

    This time around, instead of creating a sprite that multiplies itself, it adds the tiles to change represented by coordinate strings in an array - the array serves as a queue of tiles to check, and behaves much like the flood fill object did, but this time it runs in a 'while' loop and thus happens instantly. It seems to work well! Is this the best way to go, or are there even more efficient solutions? I noticed if I add any animated elements, it does hitch slightly upon flood-filling, so any even more optimized solutions would be appreciated.

  • Here is a much simpler and faster version:

    dropbox.com/s/mog16tzisjy0ddj/TileFloodFill-v3.capx

  • Woah, neat...! Is there any way to tweak it to where diagonally adjacent tiles don't count as enclosed?

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • You can add 4 more events to check tiles at (x-1, y-1), (x+1, y-1) etc.

  • Got it! Thanks a lot for your help - it looks like I was on the right track generally, but this implementation is much more elegant.

  • It's probably not the most efficient, as it checks the same tiles multiple times. But it works fast enough, so maybe not worth optimizing it further.

  • Checking it against my own current method, which actually does account for checking tiles multiple times, it seems about the same - in any case, there's probably more optimization gains to be made elsewhere besides the flood fill method itself (like restricting it to only relevant areas on a bigger map, or only checking when potential loop-closing pieces are placed). One thing I've done to make it a little less CPU-intensive is to only run the loop ~200x a frame instead of making it a 'while' loop and having the tilemap update visually after it's complete (using a separate tilemap object) - that way, it doesn't cause the game to hitch and the delay can easily be worked into the animation aspect with ample time for the logic to complete before it updates the map visually.

    That said, seeing your example did help me clean it up in places and eliminate some unnecessary variables, so I appreciate the help all the same!

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)