乐趣区

关于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…

退出移动版