Python3。八叉树实现占用大量内存。如何优化？
Python3. Octree implementation engages a lot of memory. How to optimize?
我开发游戏服务器，想在地图上保持实时物体位置。为此，我使用八叉树算法。但是现在我的实现占用了大量的 RAM，为了测试我尝试填充几个地图，即使没有对象八叉树也占用大约 1 GB + 每个地图大约 1 GB 的对象（我将所有对象存储在 dict 中并单独存储 guids 列表根据坐标为每个八叉树节点）。
下面是我的实现：
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]
为此建造者：
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)
我花了很多时间来寻找优化内存使用的方法。因此，我尝试尽可能使用元组（例如在 OctreeBuilder 的 middle_x 行）。此外，我正在使用 __slots__（由于代码示例较大，已从上面的代码中删除）。等等。但似乎我的优化还不够。现在我的代码因为占用了大量内存而无法工作。请帮我优化一下！
P.S。要查看完整的代码示例，您可以在 https://github.com/sergio-ivanuzzo/idewave-core（开发分支）
上访问我的项目
注意！：我希望（如果可能的话）在我的项目中保持面向对象的方法。所以，如果这个问题的答案包含基于 class 的解决方案，那就太好了。
此外，根据@zch 的评论，我尝试用 namedtuple 替换我的 OctreeNode class，但这种方法只会增加使用的内存。
我想在节点中保留下一个信息：
- 父节点
- 子节点
- 坐标（x0 x1 y0 y1 z0 z1）
如果节点是叶节点，它还应该保留对象 ID 列表。
已更新
为了为每个地图构建八叉树，我从数据库加载地图坐标。作为测试，我们可以使用下一个数据：
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
对象示例：
{'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}
好的，我已经解决了这个问题。首先，我决定增加节点的最小大小，因此 OctreeBuilder 返回更少的节点。因此，内存使用量从 2 GB 减少到 200 MB。接下来，我从 OctreeNode class 中删除了方法。所以，我离开 class 没有方法：
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
感谢大家的提示和讨论。如果您有其他优化方法，请在评论中告诉我。
我开发游戏服务器，想在地图上保持实时物体位置。为此，我使用八叉树算法。但是现在我的实现占用了大量的 RAM，为了测试我尝试填充几个地图，即使没有对象八叉树也占用大约 1 GB + 每个地图大约 1 GB 的对象（我将所有对象存储在 dict 中并单独存储 guids 列表根据坐标为每个八叉树节点）。
下面是我的实现：
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]
为此建造者：
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)
我花了很多时间来寻找优化内存使用的方法。因此，我尝试尽可能使用元组（例如在 OctreeBuilder 的 middle_x 行）。此外，我正在使用 __slots__（由于代码示例较大，已从上面的代码中删除）。等等。但似乎我的优化还不够。现在我的代码因为占用了大量内存而无法工作。请帮我优化一下！
P.S。要查看完整的代码示例，您可以在 https://github.com/sergio-ivanuzzo/idewave-core（开发分支）
上访问我的项目注意！：我希望（如果可能的话）在我的项目中保持面向对象的方法。所以，如果这个问题的答案包含基于 class 的解决方案，那就太好了。
此外，根据@zch 的评论，我尝试用 namedtuple 替换我的 OctreeNode class，但这种方法只会增加使用的内存。
我想在节点中保留下一个信息：
- 父节点
- 子节点
- 坐标（x0 x1 y0 y1 z0 z1）
如果节点是叶节点，它还应该保留对象 ID 列表。
已更新 为了为每个地图构建八叉树，我从数据库加载地图坐标。作为测试，我们可以使用下一个数据：
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
对象示例：
{'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}
好的，我已经解决了这个问题。首先，我决定增加节点的最小大小，因此 OctreeBuilder 返回更少的节点。因此，内存使用量从 2 GB 减少到 200 MB。接下来，我从 OctreeNode class 中删除了方法。所以，我离开 class 没有方法：
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
感谢大家的提示和讨论。如果您有其他优化方法，请在评论中告诉我。