SpidurMelon

Category: Games

  • Rubber Duck Debugging via Blog

    Rubber duck debugging never worked for me, at least not when using actual rubber ducks or other inanimate objects.

    Turns out this blog helps wonderfully, because the added pressure of someone reading this someday makes me articulate my ideas better and therefore develop a better understanding myself.

  • Grid Islands

    I am running into a performance issue in my new game, so instead of optimizing it directly I thought it’d be fun to write about it.

    Imagine you have a grid of cells, which can either be filled ([X]) or empty ([ ]):

       A  B  C  D  E  F  G
1 [X][ ][X][X][ ][X][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

    This grid has 3 “islands”. An island is defined as a set of cells all filled, separated by empty cells. I need a way for each cell to know what island they are a part off.

    My original implementation was a recursive approach, effectively flood-filling from whichever cell queried their island. The problem here is that although this isn’t super slow, for a grid of 7*7, =I’d have to do this 49 times. And in the worst case scenario – a grid completely filled – this would result in visiting 49*49=2401 cells.

    The first idea is to calculate the islands once for the whole grid, instead of doing it for every cell. This should definitely give me the speed up I desire, as I would only have to visit 98 cells in the worst case scenario. It would do this as follows:

    It would go over every cell in reading order, starting with A1:

       A  B  C  D  E  F  G
1 [O][ ][X][X][ ][X][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

    It would use the same flood-fill algorithm to find the whole island.

       A  B  C  D  E  F  G
1 [O][ ][X][X][ ][X][X]
2 [O][ ][X][X][ ][X][X]
3 [O][ ][ ][ ][ ][ ][X]
4 [O][O][O][ ][ ][ ][X]
5 [O][O][O][ ][X][X][X]
6 [O][O][O][ ][X][X][X]

    It would then continue in reading order from A1, skipping B1 because it’s already empty. It would also skip any cells that are already part of an island. So secondly it would land on C1, and flood-fill that one.

       A  B  C  D  E  F  G
1 [O][ ][O][O][ ][X][X]
2 [O][ ][O][O][ ][X][X]
3 [O][ ][ ][ ][ ][ ][X]
4 [O][O][O][ ][ ][ ][X]
5 [O][O][O][ ][X][X][X]
6 [O][O][O][ ][X][X][X]

    And finally get to F1.

       A  B  C  D  E  F  G
1 [O][ ][O][O][ ][O][O]
2 [O][ ][O][O][ ][O][O]
3 [O][ ][ ][ ][ ][ ][O]
4 [O][O][O][ ][ ][ ][O]
5 [O][O][O][ ][O][O][O]
6 [O][O][O][ ][O][O][O]

    It would continue over the entire grid finding that no other cells are island-less, and terminate there.

    But I am curious if there is an algorithm that would intelligently and dynamically update the islands. Visiting no other cells than the one changed. Like what would happen if we were to fill D6?

       A  B  C  D  E  F  G
1 [O][ ][O][O][ ][O][O]
2 [O][ ][O][O][ ][O][O]
3 [O][ ][ ][ ][ ][ ][O]
4 [O][O][O][ ][ ][ ][O]
5 [O][O][O][ ][O][O][O]
6 [O][O][O][X][O][O][O]

    I feel like it should be possible to directly update join the left island with the right, without having to go over each and every cell. I do not have a solution for this at present time, but maybe I’ll come back here if I ever stumble across it.

    EDIT: Turns out using recursion is just not the way to go, it is still rather slow. Instead I’m opting for the following iterative approach:

    • Go over every cell,
      • If the cell has a neighbour with an “island” value, set the value of this cell to that value.
      • If the cell has no neighbour with an “island” value, set it to highest value +1

    In practice (skipping empty cells):

       A  B  C  D  E  F  G
1 [1][ ][X][X][ ][X][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

   A  B  C  D  E  F  G
1 [1][ ][2][X][ ][X][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

   A  B  C  D  E  F  G
1 [1][ ][2][2][ ][X][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

   A  B  C  D  E  F  G
1 [1][ ][2][2][ ][3][X]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

   A  B  C  D  E  F  G
1 [1][ ][2][2][ ][3][3]
2 [X][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

   A  B  C  D  E  F  G
1 [1][ ][2][2][ ][3][3]
2 [1][ ][X][X][ ][X][X]
3 [X][ ][ ][ ][ ][ ][X]
4 [X][X][X][ ][ ][ ][X]
5 [X][X][X][ ][X][X][X]
6 [X][X][X][ ][X][X][X]

etc...

   A  B  C  D  E  F  G
1 [1][ ][2][2][ ][3][3]
2 [1][ ][2][2][ ][3][3]
3 [1][ ][ ][ ][ ][ ][3]
4 [1][1][1][ ][ ][ ][3]
5 [1][1][1][ ][3][3][3]
6 [1][1][1][ ][3][3][3]

    EDIT 2: I’ve noticed a problem with this approach. Imagine the following scenario:

       A  B  C 
1 [X][ ][X]
2 [X][ ][X]
3 [X][X][X]

    How should this be resolved? Because they’re part of the same island, but following the steps as described before will result in the following:

       A  B  C 
1 [1][ ][2]
2 [1][ ][2]
3 [1][1][?]

    So we need to revise the rules based on the amount of neighbours already assigned to an island:

    • 0 neighbours with a value: Set to MAX + 1
    • 1 neighbour with a value, or 2 neighbours with the same value: Set to neighbours value
    • 2 neighbours with a unique value: Pick one of the two values, then replace all instances of the other value with the picked value

    EDIT 3: It seems this last approach has its flaws too, so I’m reverting back to approach number 2.