Например, в вашей игре бегают 100 врагов (в разных командах), и их ИИ хочет осмотреть ближайшие объекты, чтобы определить, на кого он должен атаковать. Как быстро организовать эти объекты так, чтобы каждому врагу не приходилось рассчитывать расстояние между собой и всеми другими объектами?
Короче говоря, как быстро ИИ-сущность может ответить на вопрос "Кто рядом со мной?"
3d
ai
entity-system
data-structure
khayman218
источник
источник
Ответы:
Вам нужен пространственный индекс, такой как квадри (2D) или октодерево (3D).
источник
Самое простое решение - это сетка . Положите 2D сетку над своим уровнем. Каждая ячейка в сетке содержит коллекцию объектов, которые в настоящее время занимают ее. Когда сущности перемещаются, вытащите их из клетки, из которой они выходят, и добавьте их к той, в которую они входят.
Затем вы можете найти близлежащие объекты, просто осмотрев соседние ячейки. Квадродерево уточняет это путем рекурсивного деления сетки, но иногда достаточно плоского, особенно если размер вашего уровня фиксирован и относительно мал.
источник