乐趣区

关于c++:算法游戏内AOI视野算法十字链表

作者：

jiezi

在

为什么要有这个算法？

对于一个游戏场景内的实体来说，当战斗频繁的时候，可能存在上千实体的数据同步，例如上千实体挪动时的坐标同步，大型战斗场景时全场景实体的属性的同步等等，这样就会造成一个问题，同步数据量十分多，然而对于客户端来说，咱们能够看到的屏幕视线大小是固定的，对于视线之外的实体的所有数据咱们并不需要晓得，所以就不须要同步，这时候就须要一种算法，能够让咱们疾速定位到在我视线范畴内的实体有哪些，而后为这些玩家同步相干的音讯。

算法数据结构设计

1、为了保障链表元素的查找速度，链表应用跳表实现。
2、须要xlist，ylist两条链表，须要将玩家的x，y坐标别离有序的存储到这两个链表上。

实现细节

注：目前的设计仅仅基于二维

public AoiZone(float xLinksLimit, float yLinksLimit)
{
    _xLinks = new AoiLinkedList(limit: xLinksLimit);//x轴链表
    _yLinks = new AoiLinkedList(limit: yLinksLimit);//y轴链表
}

public AoiLinkedList(int maxLayer = 8, float limit = 0)
{
    _limit = limit;//坐标比拟时的容错值
    _maxLayer = maxLayer;//跳表层数
    Add(float.MinValue);
}

public AoiNode Add(float target, AoiEntity entity = null)
{
    var rLayer = 1;

    if (_header == null)
    {
        //创立跳表
        rLayer = _maxLayer;

        var tempHeader = _header = new AoiNode(rLayer, target, entity);//头结点

        for (var layer = _maxLayer - 1; layer >= 1; --layer)
        {
            _header = _header.Down = new AoiNode(layer, target, top: _header);  //top：pre指针 down：next指针
        }

        _header = tempHeader;
        return null;
    }
    
    //随机选取某层插入节点
    while (rLayer < _maxLayer && _random.Next(2) == 0) ++rLayer;    
    //最高的一层（节点起码的一层）头结点
    AoiNode cur = _header, insertNode = null, lastLayerNode = null;

    for (var layer = _maxLayer; layer >= 1; --layer)
    {
        while (cur.Right != null && cur.Right.Value < target) cur = cur.Right;//与要插入地位的x/y值比拟大小（可能有新插入数据，每次都得比拟）

        if (layer <= rLayer)    //
        {
            insertNode = new AoiNode(layer, target, entity: entity, left: cur, right: cur.Right);   //

            if (cur.Right != null) cur.Right.Left = insertNode;
            cur.Right = insertNode;//节点插入

            if (lastLayerNode != null)    //跳表上上层指针保护
            {
                lastLayerNode.Down = insertNode;
                insertNode.Top = lastLayerNode;
            }

            lastLayerNode = insertNode;
        }

        cur = cur.Down;//下一层
    }

    Count++;//减少节点数目
    return insertNode;
}

游戏中的update函数实现：

//key:实体ID
//area:视线范畴
//enter:此帧玩家坐标视线内的玩家
public AoiEntity Refresh(long key, Vector2, out HashSet<long> enter)
{
    var entity = Refresh(key, area);
    enter = entity?.ViewEntity;
    return entity;
}

public AoiEntity Refresh(long key, float x, float y, Vector2 area)
{
    if (!_entityList.TryGetValue(key, out var entity)) return null;

    var isFind = false;

    if (Math.Abs(entity.X.Value - x) > 0)
    {
        isFind = true;
        _xLinks.Move(entity.X, ref x);
    }

    if (Math.Abs(entity.Y.Value - y) > 0)
    {
        isFind = true;
        _yLinks.Move(entity.Y, ref y);
    }

    if (isFind) Find(entity, ref area);
    return entity;
}

//此函数次要是玩家每帧挪动后，x,y坐标变换后将链表从新变成有序的过程
public void Move(AoiNode node, ref float target)
{
    var cur = node;

    #region Left

    if (target > cur.Value) //挪动后的值大于以后节点的值
    {
        while (cur != null)
        {
            if (cur.Right != null && target > cur.Right.Value)
            {
                var findNode = cur;
                // Find the target node to be moved to.
                //此处如果节点很多，遍历可能会耗费一些性能
                while (findNode.Right != null && findNode.Right.Value < target) findNode = findNode.Right;    
                // Fuse the current node.
                CircuitBreaker(cur);//从以后地位移除
                // Move to the target node location
                cur.Left = findNode;
                cur.Right = findNode.Right;//退出到新的地位
                if (findNode.Right != null) findNode.Right.Left = cur;
                findNode.Right = cur;
            }

            cur.Value = target;
            cur = cur.Top;//调整跳表下面层的节点程序
        }

        return;
    }

    #endregion Left

    #region Right

    while (cur != null)////挪动后的值小于以后节点的值
    {
        if (cur.Left != null && target < cur.Left.Value)
        {
            // Find the target node to be moved to.
            var findNode = cur;
            while (findNode.Left != null && findNode.Left.Value > target) findNode = findNode.Left;
            // Fuse the current node.
            CircuitBreaker(cur);
            // Move to the target node location
            cur.Right = findNode;
            cur.Left = findNode.Left;
            if (findNode.Left != null) findNode.Left.Right = cur;
            findNode.Left = cur;
        }

        cur.Value = target;
        cur = cur.Top;
    }

    #endregion Right
}
private void Find(AoiEntity node, ref Vector2 area)
{
    //将上帧的可视实体存到备份HashSet汇合里
    SwapViewEntity(ref node.ViewEntity, ref node.ViewEntityBak);

    #region xLinks
    
    //定位到此实体，而后再xlist,ylist上别离进行left、right指针遍历，将distance在指定范畴内的实体存入此帧ViewEntity
    for (var i = 0; i < 2; i++)
    {
        var cur = i == 0 ? node.X.Right : node.X.Left;

        while (cur != null)
        {
            if (Math.Abs(Math.Abs(cur.Value) - Math.Abs(node.X.Value)) > area.X)    //cur.value为aoi网格节点的value
            {
                break;
            }

            if (Math.Abs(Math.Abs(cur.Entity.Y.Value) - Math.Abs(node.Y.Value)) <= area.Y)  //cur.Entity.Y.Value为以后网格节点上的实体value
            {
                if (Distance(
                    new Vector2(node.X.Value, node.Y.Value),
                    new Vector2(cur.Entity.X.Value, cur.Entity.Y.Value)) <= area.X)
                {
                    node.ViewEntity.Add(cur.Entity.Key);//在范畴内的话
                }
            }

            cur = i == 0 ? cur.Right : cur.Left; //别离在左右进行遍历
        }
    }

    #endregion xLinks

    #region yLinks

    for (var i = 0; i < 2; i++)
    {
        var cur = i == 0 ? node.Y.Right : node.Y.Left;

        while (cur != null)
        {
            if (Math.Abs(Math.Abs(cur.Value) - Math.Abs(node.Y.Value)) > area.Y)
            {
                break;
            }

            if (Math.Abs(Math.Abs(cur.Entity.X.Value) - Math.Abs(node.X.Value)) <= area.X)
            {
                if (Distance(
                    new Vector2(node.X.Value, node.Y.Value),
                    new Vector2(cur.Entity.X.Value, cur.Entity.Y.Value)) <= area.Y)
                {
                    node.ViewEntity.Add(cur.Entity.Key);
                }
            }

            cur = i == 0 ? cur.Right : cur.Left;
        }
    }

    #endregion yLinks
}
//用于函数回调
//本帧绝对上帧来到视线的人
public IEnumerable<long> Leave => ViewEntityBak.Except(ViewEntity);
//本帧绝对上帧进入视线的人
public IEnumerable<long> NewEnter => ViewEntity.Except(ViewEntityBak);//本帧绝对上帧进入视线的人

测试代码

private static void Main(string[] args)
  {
  var zone = new AoiZone(.001f, .001f);
  var area = new Vector2(3, 3);

  // 增加500个玩家。

  for (var i = 1; i <= 500; i++) zone.Enter(i, i, i);

  // 刷新key为3的信息。

  zone.Refresh(3, area, out var enters);

  Console.WriteLine("---------------id为3玩家以后视线范畴的玩家列表--------------");

  foreach (var aoiKey in enters)
  {
      var findEntity = zone[aoiKey];
      Console.WriteLine($"X:{findEntity.X.Value} Y:{findEntity.Y.Value}");
  }

  // 更新key为3的坐标为(20,20)。

  var entity = zone.Refresh(3, 20, 20, new Vector2(3, 3), out enters);

  Console.WriteLine("---------------id为3玩家挪动后来到玩家视线范畴的玩家列表--------------");

  foreach (var aoiKey in entity.Leave)
  {
      var findEntity = zone[aoiKey];
      Console.WriteLine($"X:{findEntity.X.Value} Y:{findEntity.Y.Value}");
  }

  Console.WriteLine("---------------id为3玩家挪动后新退出玩家视线范畴的玩家列表--------------");

  foreach (var aoiKey in entity.NewEnter)
  {
      var findEntity = zone[aoiKey];
      Console.WriteLine($"X:{findEntity.X.Value} Y:{findEntity.Y.Value}");
  }

  // 来到以后AOI

  zone.Exit(50);}

测试后果

---------------id为3玩家以后视线范畴的玩家列表--------------
X:4 Y:4
X:5 Y:5
X:2 Y:2
X:1 Y:1
---------------id为3玩家挪动后来到玩家视线范畴的玩家列表--------------
X:4 Y:4
X:5 Y:5
X:2 Y:2
X:1 Y:1
---------------id为3玩家挪动后新退出玩家视线范畴的玩家列表--------------
X:20 Y:20
X:21 Y:21
X:22 Y:22
X:19 Y:19
X:18 Y:18

现存问题

此十字链表设计目前存在一个问题：当我的项目中实体数目十分多，每帧实体挪动频繁，每帧都会去进行x,y链表坐标排序，对性能耗费还是蛮大的，还在思考单纯用链表如何解决此问题。

援用：https://github.com/qq362946/A…

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章