- Рейтинг
- 900 pts
⚡ Дерева QuadTree у Lua: оптимізація пошуку найближчих елементів за O(log N)
Якщо на сервері 5000 будинків або радарів, звичайний перебір
Швидкість пошуку найближчих об'єктів навколо гравця зростає у 50-80 разів!
Якщо на сервері 5000 будинків або радарів, звичайний перебір
for _, v in ipairs(houses) на кожен кадр або тік створює величезне навантаження. QuadTree розбиває карту San Andreas 6000x6000 на 4 квадранти рекурсивно.
Код:
QuadTree = {}
QuadTree.__index = QuadTree
function QuadTree.new(boundary, capacity)
local self = setmetatable({}, QuadTree)
self.boundary = boundary -- {x, y, w, h}
self.capacity = capacity or 4
self.points = {}
self.divided = false
return self
end
Швидкість пошуку найближчих об'єктів навколо гравця зростає у 50-80 разів!