I develop game server and want to keep real-time objects positions on the maps. For this purpose I'm using octree algorithm. But for now my implementation engages a lot of RAM, for test I tried to populate several maps and even without objects octree engages about 1 GB + about 1 GB per map for objects (I store all objects in the dict and separately store list of guids for each octree nodes according to their coordinates).
Below my implementation:
class OctreeNode(object):
MAX_CHILD_NODES = 8
def __init__(self, **kwargs):
self.x0 = kwargs.pop('x0')
self.x1 = kwargs.pop('x1')
self.y0 = kwargs.pop('y0')
self.y1 = kwargs.pop('y1')
self.z0 = kwargs.pop('z0')
self.z1 = kwargs.pop('z1')
self.root_node: OctreeNode = None
self.parent_node: OctreeNode = None
self.child_nodes = None
self.objects = None
self.guids = None
def get_root_node(self) -> 'OctreeNode':
return self.root_node
def set_root_node(self, node: 'OctreeNode') -> None:
self.root_node = node
def get_parent_node(self) -> 'OctreeNode':
return self.parent_node
def set_parent_node(self, node: 'OctreeNode') -> None:
self.parent_node = node
def get_child_nodes(self) -> List['OctreeNode']:
return self.child_nodes
def set_child_nodes(self, nodes: List['OctreeNode']) -> None:
self.child_nodes = nodes
def can_contain_child_nodes(self) -> bool:
update_dist = Config.World.Gameplay.update_dist
return ((self.x1 - self.x0) > update_dist and
(self.y1 - self.y0) > update_dist and
(self.z1 - self.z0) > update_dist)
def get_object(self, guid: int):
return self.objects.get(guid, None)
def set_object(self, obj: Union[Unit, Player]) -> None:
if self.get_child_nodes():
node = self._get_nearest_child_node(obj)
node.set_object(obj)
else:
self.objects[obj.guid] = obj
def should_contain_object(self, obj: Union[Unit, Player]) -> bool:
return (self.x0 <= obj.x <= self.x1 and
self.y0 <= obj.y <= self.y1 and
self.z0 <= obj.z <= self.z1)
def _get_nearest_child_node(self, obj: Union[Unit, Player]):
for i in range(0, OctreeNode.MAX_CHILD_NODES):
if self.child_nodes[i].should_contain_object(obj):
return self.child_nodes[i]
And builder for this:
class OctreeBuilder(object):
def __init__(self, **kwargs):
self.x0 = kwargs.pop('x0')
self.x1 = kwargs.pop('x1')
self.y0 = kwargs.pop('y0')
self.y1 = kwargs.pop('y1')
# FIXME: should get actual height for each map (use ADT, WDT, WMO for this purpose)
self.z0 = -2000
self.z1 = 2000
self.root_node = OctreeNode(x0=self.x0, x1=self.x1, y0=self.y0, y1=self.y1, z0=self.z0, z1=self.z1)
self.objects = kwargs.pop('objects', {})
def build(self) -> OctreeNode:
self._build_child_nodes(self.root_node, self.root_node)
self.root_node.objects = self.objects
return self.root_node
def _set_objects(self) -> None:
for obj in self.objects.values():
self.root_node.set_object(obj)
def _build_child_nodes(self, node: OctreeNode, root_node: OctreeNode) -> None:
middle_x = (node.x0 + node.x1) / 2
middle_y = (node.y0 + node.y1) / 2
middle_z = (node.z0 + node.z1) / 2
x = ((node.x0, middle_x), (middle_x, node.x1))
y = ((node.y0, middle_y), (middle_y, node.y1))
z = ((node.z0, middle_z), (middle_z, node.z1))
child_nodes = []
for i in range(1, OctreeNode.MAX_CHILD_NODES + 1):
x0, x1 = x[i % 2 == 0]
y0, y1 = y[(i & 3) % 3 == 0]
z0, z1 = z[i > 4]
child_node = OctreeBuilder._build_node(x0, x1, y0, y1, z0, z1)
child_node.set_root_node(root_node)
child_node.set_parent_node(node)
if child_node.can_contain_child_nodes():
self._build_child_nodes(child_node, root_node)
else:
child_node.guids = []
child_nodes.append(child_node)
node.set_child_nodes(child_nodes)
@staticmethod
def _build_node(x0: float, x1: float, y0: float, y1: float, z0: float, z1: float) -> OctreeNode:
return OctreeNode(x0=x0, x1=x1, y0=y0, y1=y1, z0=z0, z1=z1)
I have spent a lot of time to find the ways to optimize memory usage. So, I tried to using tuple where possible (for example on the middle_x line of OctreeBuilder). Also I'm using __slots__ (removed from the code above due to big code example). And so on. But it seems my optimizations are not enough. And for now my code can't be working because of a lot of engaged memory. Please, help me to optimize it!
P.S. to see the full code example you can visit my project on https://github.com/sergio-ivanuzzo/idewave-core (dev branch)
NOTICE!: I want (if possible) to keep object-oriented approach in my project. So, it will be very nice if answer for this question will contain class-based solution.
Also, according to @zch comment I tried to replace my OctreeNode class with namedtuple, but this approach only increased used memory.
I want to keep in nodes next information:
if node is leaf node it also should keep list of objects ids.
UPDATED For building octree for each map I load map coords from db. As test we can use next data:
x0 = -1277.08
x1 = 3814.58
y0 = 8437.5
y1 = 11831.2
builder = OctreeBuilder(x0=x0, x1=x1, y0=y0, y1=y1, objects=objects)
octree = builder.build()
# attach octree to map object to save it in memory
The object example:
{'max_rage': None, 'char_class': None, 'min_damage': None, 'stamina': None, 'resistance_arcane': 0, 'max_ranged_damage': None, 'unit_template_id': 11183, 'id': 2897, 'focus': None, 'gender': None, 'max_damage': None, 'intellect': None, 'armor': 20, 'x': 1940.93, 'region_id': 1, 'health': 300, 'max_focus': None, 'level': 1, 'min_offhand_damage': None, 'spirit': None, 'attack_power': None, 'y': -4322.39, 'max_health': 300, 'energy': None, 'unit_flags': None, 'max_offhand_damage': None, 'resistance_fire': 0, 'base_mana': 0, 'z': 27.7612, 'mana': 0, 'max_energy': None, 'display_id': 11686, 'unit_bytes_1': None, 'resistance_nature': 0, 'base_health': 300, 'orientation': None, 'scale_x': 1.0, 'max_mana': None, 'happiness': None, 'native_display_id': 11686, 'mod_cast_speed': None, 'resistance_frost': 0, 'unit_bytes_2': None, 'map_id': None, 'rage': None, 'max_happiness': None, 'faction_template': 35, 'strength': None, 'resistance_shadow': 0, 'ranged_attack_power': None, 'power_type': None, 'race': None, 'agility': None, 'min_ranged_damage': None, '_tracked_guids': set(), '_target': None}
Well, I have fixed the problem. First, I have decided to increase minimal size for nodes, thus OctreeBuilder returned less nodes. So, from 2 GB memory usage was reduced to 200 MB. Next, I have removed methods from OctreeNode class. So, I have left class without methods:
class OctreeNode(object):
__slots__ = (
'x0',
'x1',
'y0',
'y1',
'z0',
'z1',
'parent_node',
'child_nodes',
'guids'
)
def __init__(self, **kwargs):
self.x0: float = kwargs.pop('x0')
self.x1: float = kwargs.pop('x1')
self.y0: float = kwargs.pop('y0')
self.y1: float = kwargs.pop('y1')
self.z0: float = kwargs.pop('z0')
self.z1: float = kwargs.pop('z1')
self.parent_node: Union[OctreeNode, None] = kwargs.pop('parent_node', None)
self.child_nodes: Union[List, None] = None
self.guids: Union[List, None] = None
Thanks to all for hints and for discussion. If you have another approaches for optimizing please let me know in the comments.