13
\$\begingroup\$

I am creating a game using a tile-map made of many thousands of grid squares. At the moment, each square has a square collider on it for checking collisions.

enter image description here

However, with many thousands of tiny blocks, checking them all for collisions is inefficient. If I had known the tilemap was going to look like this in advance, I could have just used 3 or 4 big colliders rather than thousands of tiny ones:

enter image description here

Is there some sort of standard algorithm for combining many small adjacent tiles into maximally large ones? If so, could someone describe it here, or point to literature on such algorithms?

Alternatively, maybe pre-processing the tile colliders in this way is completely the wrong approach. If so, what is the correct one to deal with the efficiency of an extremely large number of colliders?

\$\endgroup\$
  • \$\begingroup\$ Are you planning on having the terrain destructible? \$\endgroup\$ – jgallant Oct 14 '15 at 13:08
  • \$\begingroup\$ @Jon. I had not considered this. I imagine allowing destructibility would make the problem significantly harder (because one of the little colliders may be destroyed, meaning the big combined colliders would need to be re-calculated, right?) \$\endgroup\$ – Craig Innes Oct 14 '15 at 13:34
  • \$\begingroup\$ Yes. This is why I was asking. Typically, you would combine all your terrain into a mesh. If you plan on allowing your terrain to be destructible, there is an alternate method you can use, which sets colliders on only the outer blocks. You would pre-calc what blocks are "edge blocks" and then assign those blocks with a poolable collider. (jgallant.com/images/uranus/chunk.png -- Image is old and not perfect, but demonstrates the technique) What are you using for a game engine/platform? \$\endgroup\$ – jgallant Oct 14 '15 at 13:37
  • \$\begingroup\$ @Jon I am using Unity as my game engine, with BoxCollider2D components for tile collisions. I did not mention my specific platform as I thought it might be of more use to the game dev stack exchange to get a more general answer to this problem. With regards to your "edge blocks" method, could you submit an answer with precise details of the algorithm for this method? Or do you have a link to resources about such techniques? \$\endgroup\$ – Craig Innes Oct 14 '15 at 13:53
  • 1
    \$\begingroup\$ I do have a Unity implementation for this, it will take me some time to do a write up, as it is not really cut and dry. I am at work at the moment, and the source code is at home. If you can wait for till tonight for an answer. Here is what it looks like: jgallant.com/images/landgen.gif \$\endgroup\$ – jgallant Oct 14 '15 at 13:57
5
\$\begingroup\$

I found usefull this algoritm for love2d engine (lua language)

https://love2d.org/wiki/TileMerging

-- map_width and map_height are the dimensions of the map
-- is_wall_f checks if a tile is a wall

local rectangles = {} -- Each rectangle covers a grid of wall tiles

for x = 0, map_width - 1 do
    local start_y
    local end_y

    for y = 0, map_height - 1 do
        if is_wall_f(x, y) then
            if not start_y then
                start_y = y
            end
            end_y = y
        elseif start_y then
            local overlaps = {}
            for _, r in ipairs(rectangles) do
                if (r.end_x == x - 1)
                  and (start_y <= r.start_y)
                  and (end_y >= r.end_y) then
                    table.insert(overlaps, r)
                end
            end
            table.sort(
                overlaps,
                function (a, b)
                    return a.start_y < b.start_y
                end
            )

            for _, r in ipairs(overlaps) do
                if start_y < r.start_y then
                    local new_rect = {
                        start_x = x,
                        start_y = start_y,
                        end_x = x,
                        end_y = r.start_y - 1
                    }
                    table.insert(rectangles, new_rect)
                    start_y = r.start_y
                end

                if start_y == r.start_y then
                    r.end_x = r.end_x + 1

                    if end_y == r.end_y then
                        start_y = nil
                        end_y = nil
                    elseif end_y > r.end_y then
                        start_y = r.end_y + 1
                    end
                end
            end

            if start_y then
                local new_rect = {
                    start_x = x,
                    start_y = start_y,
                    end_x = x,
                    end_y = end_y
                }
                table.insert(rectangles, new_rect)

                start_y = nil
                end_y = nil
            end
        end
    end

    if start_y then
        local new_rect = {
            start_x = x,
            start_y = start_y,
            end_x = x,
            end_y = end_y
        }
        table.insert(rectangles, new_rect)

        start_y = nil
        end_y = nil
    end
end
Here's how the rectangles would be used for physics.
-- Use contents of rectangles to create physics bodies
-- phys_world is the world, wall_rects is the list of...
-- wall rectangles

for _, r in ipairs(rectangles) do
    local start_x = r.start_x * TILE_SIZE
    local start_y = r.start_y * TILE_SIZE
    local width = (r.end_x - r.start_x + 1) * TILE_SIZE
    local height = (r.end_y - r.start_y + 1) * TILE_SIZE

    local x = start_x + (width / 2)
    local y = start_y + (height / 2)

    local body = love.physics.newBody(phys_world, x, y, 0, 0)
    local shape = love.physics.newRectangleShape(body, 0, 0,
      width, height)

    shape:setFriction(0)

    table.insert(wall_rects, {body = body, shape = shape})
end

Here follow the love2d example on my current project. In red you can see my wall colliders.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Is there a C# version? Is there a version with documentation comments? Can this algorithm be adapted for 3D? \$\endgroup\$ – Aaron Franke Aug 25 '17 at 20:51
3
\$\begingroup\$

If you are looking to create destructible terrain, the way I did this in Unity, is to only set colliders on the edge blocks of your world. So for example, this is what you would like to accomplish:

Green blocks indicate the tiles that contain a collider

All those green blocks contain a collider, and the rest of them don't. That saves a ton on computations. If you destroy a block, you can activate the colliders on adjacent blocks pretty easily. Keep in mind that activating/deactivating a collider is costly and should be done sparingly.

So, the Tile resource looks like this:

Tile Resource In Unity

It is a standard gameobject, but it is also poolable. Also notice that the box collider is set to be disabled by default. We would only activate if it is an edge tile.

If you are statically loading your world, there is no need to pool your tiles. You can just load them all in one shot, calculate their distance from the edge, and apply a collider if required.

If you are loading dynamically, it is best to use a tile pool. Here is an edited example of my refresh loop. It loads tiles based on the current camera view:

public void Refresh(Rect view)
{       
    //Each Tile in the world uses 1 Unity Unit
    //Based on the passed in Rect, we calc the start and end X/Y values of the tiles presently on screen        
    int startx = view.x < 0 ? (int)(view.x + (-view.x % (1)) - 1) : (int)(view.x - (view.x % (1)));
    int starty = view.y < 0 ? (int)(view.y + (-view.y % (1)) - 1) : (int)(view.y - (view.y % (1)));

    int endx = startx + (int)(view.width);
    int endy = starty - (int)(view.height);

    int width = endx - startx;
    int height = starty - endy;

    //Create a disposable hashset to store the tiles that are currently in view
    HashSet<Tile> InCurrentView = new HashSet<Tile>();

    //Loop through all the visible tiles
    for (int i = startx; i <= endx; i += 1)
    {
        for (int j = starty; j >= endy; j -= 1)
        {
            int x = i - startx;
            int y = starty - j;

            if (j > 0 && j < Height)
            {
                //Get Tile (I wrap my world, that is why I have this mod here)
                Tile tile = Blocks[Helper.mod(i, Width), j];

                //Add tile to the current view
                InCurrentView.Add(tile);

                //Load tile if needed
                if (!tile.Blank)
                {
                    if (!LoadedTiles.Contains(tile))
                    {                           
                        if (TilePool.AvailableCount > 0)
                        {
                            //Grab a tile from the pool
                            Pool<PoolableGameObject>.Node node = TilePool.Get();

                            //Disable the collider if we are not at the edge
                            if (tile.EdgeDistance != 1)
                                node.Item.GO.GetComponent<BoxCollider2D>().enabled = false;

                            //Update tile rendering details
                            node.Item.Set(tile, new Vector2(i, j), DirtSprites[tile.TextureID], tile.Collidable, tile.Blank);
                            tile.PoolableGameObject = node;
                            node.Item.Refresh(tile);

                            //Tile is now loaded, add to LoadedTiles hashset
                            LoadedTiles.Add(tile);

                            //if Tile is edge block, then we enable the collider
                            if (tile.Collidable && tile.EdgeDistance == 1)
                                node.Item.GO.GetComponent<BoxCollider2D>().enabled = true;
                        }
                    }                       
                }                  
            }
        }
    }

    //Get a list of tiles that are no longer in the view
    HashSet<Tile> ToRemove = new HashSet<Tile>();
    foreach (Tile tile in LoadedTiles)
    {
        if (!InCurrentView.Contains(tile))
        {
            ToRemove.Add(tile);
        }
    }

    //Return these tiles to the Pool 
    //this would be the simplest form of cleanup -- Ideally you would do this based on the distance of the tile from the viewport
    foreach (Tile tile in ToRemove)
    {
        LoadedTiles.Remove(tile);
        tile.PoolableGameObject.Item.GO.GetComponent<BoxCollider2D>().enabled = false;
        tile.PoolableGameObject.Item.GO.transform.position = new Vector2(Int32.MinValue, Int32.MinValue);
        TilePool.Return(tile.PoolableGameObject);            
    }

    LastView = view;
}

Ideally, I'd write a much more detailed post, as there is quite a bit more going on behind the scenes. However, this may help you out. If there are questions feel free to ask or contact me.

\$\endgroup\$
  • \$\begingroup\$ Accepted dnkdrone's answer as it more directly answers the original question posed. However, have upvoted this answer as it gives valuable direction towards an efficient alternative \$\endgroup\$ – Craig Innes Oct 15 '15 at 11:03
  • \$\begingroup\$ @CraigInnes No issues man. Just like to help out. Points don't matter :) \$\endgroup\$ – jgallant Oct 15 '15 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.