Быстро найти объект в массиве

Question

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

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

Я планирую добавить в свою игру несколько тысяч объектов (включая маркеры), сами объекты будут только кругами и прямоугольниками, причем маркеры будут представлены в виде отрезка.

Answer 1

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

Что касается вопроса о траектории пули между «кусками», я бы порекомендовал записать точку происхождения пули, то есть точку, где она была выпущена, и точка, где он столкнулся с объектом. Этого можно достичь с помощью какого-либо обнаружения столкновений, которое зависит от системы координат вашего игрового мира, какой бы она ни была. Я бы порекомендовал создать класс Bullet. Это быстрое подтверждение концепции, которое я придумал, и которое можно загрузить как модуль с require:

local Bullet = {__type = "Bullet"}

-- This function could take bullet information as parameters, such as its point of origin
-- and calibre.
function Bullet.new(start_pos_in, calibre_in)
    -- Record start and ending positions in this table, probably represented by some 
    -- (x, y) coordinate pairs, assuming your game is 2D. I just used a generic 
    -- placeholder here called 'Point'.
    local self = {
        calibre = calbibre_in,
        start_pos = start_pos_in
        end_pos = Point.new(0, 0)
    }
    local mt = {
        __metatable = "metatable",
        __newindex = function(t, k, v)
            local e = string.format("type Bullet has no member '%s'", k)
            return error(e, 2)
        end,
        __index = self
    }
    return setmetatable(self, mt)
end

return Bullet

. Используя мой пример выше, объект Bullet может быть создан следующим образом:

-- Using .50 calibre as an example.
-- 'x' and 'y' represent the bullet's point of origin in the game world.
local bullet = Bullet.new(Point.new(x, y), ".50")

Как только объект Bullet столкнулся с чем-то в игровом мире, вы можете записать его точку удара, используя внутреннюю переменную end_pos, рассчитать пройденное расстояние и т. Д. В зависимости от того, как будет работать ваша система «чанков», вы также можете записать «чанк» происхождения пули.

В качестве примечания я бы порекомендовал попытаться реализовать пул объектов для сохранения ваших частиц пули. наверху. (См. эту статью для справки, если вы заинтересованы.)