AOI系列(2)-十字链表

AOI系列(2)-十字链表

以前说过AOI相关的九宫格的实现原理和方式,也提到了另外一种常见的AOI技术-十字链表。

原理

很多同学不清楚十字链表的实现原理和具体的实现方式,其实十字链表的原理很简单,下面以一个2D场景作为说明:
1、假设场景width*height,也就是x轴的范围是[0, width-1],y轴的范围是[0, height-1]。
2、用两个有序双链表来分别表示x轴和y轴上的实体分布。链表上的每个节点都存着在该点的实体集合,这里为了简单直观,假设只有场景玩家一种实体。
3、每个玩家的位置分别用坐标点(x,y)表示,将玩家分别按照从小到大的规律加入x轴链表和y轴链表。
4、玩家的AOI范围(简单点看作是玩家视野)就是x链表上从自己开始分别向前、向后查找获取x轴视野上的玩家集合xids,y轴也是从自己开始分别向前、向后查找获取y轴上视野内的玩家集合yids, 然后求x轴和y轴视野内玩家的交集,最后就得到了真正视野内玩家的集合view_ids。
5、根据第4点中介绍获取AOI的方法,可以很直观的得到当玩家移动的时候,需要通知的移动集合、进入集合、离开集合,这三个集合的作用和产生的原因在以前介绍九宫格算法的时候详细提到过。

从上面的可以看到,3D场景只需要添加对应的z轴链表,求视野的时候继续和z轴求交集即可。
也很容易处理不同维度视野大小不一致的问题,可以动态调整玩家视野的大小。

实现

弄清楚实现规则和原理之后,就可以着手实现了。
先看场景玩家,假设叫做SceneRole,为了演示,这里只定义很简单的几个必要属性:

class SceneRole
{
public:
   / x坐标
   uint16_t x() const { return x_; }
    void set_x(uint16_t x) { x_ = x; }

   / y坐标
    uint16_t y() const { return y_; }
    void set_y(uint16_t y) { y_ = y; }

   / x轴视野半径
    uint16_t view_x() const { return view_x_; }
    void set_view_x(uint16_t radius) { view_x_ = radius; }

   / y轴视野半径
    uint16_t view_y() const { return view_y_; }
    void set_view_y(uint16_t radius) { view_y_ = radius; }
private:
    uint64_t id_;
    /坐标
    uint16_t x_;
    uint16_t y_;
    /uint16_t z_;
    /视野半径
    uint16_t view_x_;
    uint16_t view_y_;
    /uint16_t view_z_;

};

8145427252

AOI系列(1)-九宫格

AOI系列(1)-九宫格

AOI相关的知识对于游戏开发来说非常重要,所以想到写几篇文章把一些经典的AOI解决方案的原理和实现细节说清楚。

AOI是什么?

AOI(area of interest),也就是游戏对象感兴趣的区域。该区域也可以叫做对象的视野,处在视野内其他的游戏对象的很多行为需要通知到其他对象。比如其他对象的外观、移动、所有可以影响到对象场景外显行为的状态等等,当视野内的这些数据变化的时候,我都需要知道。

AOI的最基本实现

考虑一个情况,一个游戏场景中有20个玩家或者其他拥有“视野”的对象,假设每个对象的视野大小一致,那么当其中一个对象移动的时候,我需要把这条移动消息通知到能看到我的其他对象,为了达到这个目的,可以简单的对这20个对象遍历,将消息通知到能看到我的对象。当20个玩家同时移动的时候,那么时间复复杂基本上等于20*20=400,也就是n^2,因为每个对象的AOI消息都需要对全部对象进行一次遍历才能找到需要通知的对象。

代码实现看起来可能像下面这个样子:


void Move(Entity) 
{
   ...
   /为了获取需要通知的对象,遍历所有对象
   for(auto entity : Entities)
   {
      if(entity.is_in_area(Entity))
      {
         Notity(entity, move_msg);
      }
   }
}

...
#include <cmath>
bool is_in_area(const Entity& entity)
{
   /要落在视野范围内
   std::abs(x_ - entity.x()) <= view_x_ && std::abs(y_ entity.y()) <= view_y_;
}

Read More »

5122292347

报错_pywrap_tensorflow的解决方法

  • windows 中使用import tensorflow报错如下:
No module named "_pywrap_tensorflow"
DLL load failed.

Read More »

Erlang分布式系统设计注意点

Erlang做分布式系统需要注意的细节

dist_auto_connect选项

默认情况下,当一个节点加入集群的时候,这个节点会向集群中所有连接的节点发起连接。如果集群中的某个节点下线了,再次上线后,也会自动加入网络。在一个分布式的游戏服务端系统中,如果某个节点因为异常导致下线,再次上线后,他的状态和数据等等可能都已经不正确了,这个时候我们可能不希望其他节点在我检查、修复、同步必要数据完成之前与他连接,那么就需要设置dist_auto_connect来控制节点之间的连接行为。

先看看dist_auto_connect支持的值:

  1. never

    如果一个节点的dist_auto_connect设置为never,当他加入一个集群的时候,他不会主动和这个集群的其他节点连接,需要显示的调用net_kernel:connect_node/1进行连接。

简单的测试下:

%% 使用下面的命令启动三个分布式节点,都设置为不自动连接
erl -name a@192.168.3.128 -setcookie abc -kernel dist_auto_connect never
erl -name b@192.168.3.128 -setcookie abc -kernel dist_auto_connect never
erl -name c@192.168.3.128 -setcookie abc -kernel dist_auto_connect never

%% 先将a和b节点连接起来
(a@192.168.3.128)>net_kernel:connect_node('b@192.168.3.128').
true
(a@192.168.3.128)>nodes().
['b@192.168.3.128']

%% 默认情况下,如果现在将c节点加入集群的话,随便和a或者b进行一次连接,所有节点就相互连接了
%% 但是我们设置了不自动连接,所以需要新加入的节点自己决定要和谁连接
(c@192.168.3.128)1> net_kernel:connect_node('b@192.168.3.128').
true
(c@192.168.3.128)2> 
=WARNING REPORT==== 1-Nov-2017::19:16:39 ===
global: 'c@192.168.3.128' failed to connect to 'a@192.168.3.128'

(c@192.168.3.128)2> nodes(). %% 看到c并没有和a建立连接
['b@192.168.3.128']

%% 下面主动和a建立连接
(c@192.168.3.128)3> net_kernel:connect_node('a@192.168.3.128').
true
(c@192.168.3.128)4> nodes(). %% 目前为止,这个就是一个全联通的集群了
['b@192.168.3.128','a@192.168.3.128']

probanishment