Объединение множества маленьких коллайдеров в более крупные

13

Я создаю игру, используя плитку-карту, составленную из многих тысяч квадратов сетки. На данный момент каждый квадрат имеет квадратный коллайдер для проверки столкновений.

введите описание изображения здесь

Тем не менее, для многих тысяч крошечных блоков проверка их всех на наличие коллизий неэффективна. Если бы я знал, что плитка будет выглядеть так, я бы просто использовал 3 или 4 больших коллайдера, а не тысячи крошечных:

введите описание изображения здесь

Существует ли какой-то стандартный алгоритм объединения множества маленьких соседних плиток в максимально большие? Если да, может ли кто-нибудь описать это здесь или указать литературу по таким алгоритмам?

В качестве альтернативы, возможно, предварительная обработка мозаичных коллайдеров таким образом является совершенно неправильным подходом. Если да, то как правильно бороться с эффективностью чрезвычайно большого числа коллайдеров?

Крейг Иннес
источник
Планируете ли вы иметь разрушаемую местность?
jgallant
@ Джон. Я не учел это. Я полагаю, что возможность разрушения значительно усложнит проблему (поскольку один из маленьких коллайдеров может быть уничтожен, а это значит, что большие комбинированные коллайдеры необходимо будет пересчитать, верно?)
Крейг Иннес,
Да. Вот почему я спрашивал. Обычно вы объединяете всю свою местность в сетку. Если вы планируете разрешить разрушение вашей местности, вы можете использовать альтернативный метод, который устанавливает коллайдеры только на внешние блоки. Вы должны предварительно рассчитать, какие блоки являются «краевыми блоками», а затем назначить эти блоки с помощью объединяемого коллайдера. ( jgallant.com/images/uranus/chunk.png - изображение старое и не идеальное, но демонстрирует технику) Что вы используете для игрового движка / платформы?
jgallant
@Jon Я использую Unity в качестве игрового движка с компонентами BoxCollider2D для коллизий плиток. Я не упомянул свою конкретную платформу, так как думал, что она может быть более полезной для обмена стеками игровых разработок, чтобы получить более общий ответ на эту проблему. Что касается вашего метода «краевых блоков», не могли бы вы представить ответ с точными деталями алгоритма для этого метода? Или у вас есть ссылка на ресурсы о таких методах?
Крейг Иннес
1
У меня есть реализация Unity для этого, мне понадобится некоторое время, чтобы сделать рецензию, так как она не очень сложная. Я сейчас на работе, а исходный код дома. Если вы можете дождаться ответа сегодня вечером. Вот как это выглядит: jgallant.com/images/landgen.gif
jgallant

Ответы:

5

Я нашел этот алгоритм полезным для двигателя love2d ( 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

Вот следуйте примеру love2d на моем текущем проекте. В красном вы можете увидеть мои стены коллайдеров.

введите описание изображения здесь

dnk drone.vs.drones
источник
Есть ли версия C #? Есть ли версия с комментариями к документации? Может ли этот алгоритм быть адаптирован для 3D?
Аарон Франке
3

Если вы хотите создать разрушаемую местность, то, как я это сделал в Unity, - это устанавливать коллайдеры только на краевые блоки вашего мира. Например, вот что вы хотели бы достичь:

Зеленые блоки указывают плитки, которые содержат коллайдер

Все эти зеленые блоки содержат коллайдер, а остальные нет. Это экономит массу вычислений. Если вы уничтожите блок, вы можете легко активировать коллайдеры на соседних блоках. Имейте в виду, что активация / деактивация коллайдера является дорогостоящей и должна выполняться экономно.

Итак, ресурс Tile выглядит так:

Ресурс плитки в единстве

Это стандартный игровой объект, но он также может быть объединен. Также обратите внимание, что коллайдер бокса по умолчанию отключен. Мы активируем только если это край плитки.

Если вы статически загружаете свой мир, вам не нужно объединять свои плитки. Вы можете просто загрузить их все за один выстрел, рассчитать их расстояние от края и при необходимости применить коллайдер.

Если вы загружаете динамически, лучше всего использовать пул плиток. Вот отредактированный пример моего цикла обновления. Он загружает плитки в зависимости от текущего вида камеры:

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;
}

В идеале я бы написал гораздо более подробный пост, поскольку за кулисами происходит гораздо больше. Тем не менее, это может помочь вам. Если есть вопросы, не стесняйтесь спрашивать или свяжитесь со мной.

jgallant
источник
Принимается ответ dnkdrone, поскольку он более прямо отвечает на поставленный вопрос. Тем не менее, проголосовали за этот ответ, поскольку он дает ценное направление к эффективной альтернативе
Крейг Иннес
@CraigInnes Нет проблем, парень. Просто хотел помочь. Очки не имеют значения :)
jgallant