为什么要有这个算法？
对于一个游戏场景内的实体来说，当战斗频繁的时候，可能存在上千实体的数据同步，例如上千实体挪动时的坐标同步，大型战斗场景时全场景实体的属性的同步等等，这样就会造成一个问题，同步数据量十分多，然而对于客户端来说，咱们能够看到的屏幕视线大小是固定的，对于视线之外的实体的所有数据咱们并不需要晓得，所以就不须要同步，这时候就须要一种算法，能够让咱们疾速定位到在我视线范畴内的实体有哪些，而后为这些玩家同步相干的音讯。
算法数据结构设计
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:4X:5 Y:5X:2 Y:2X:1 Y:1---------------id为3玩家挪动后来到玩家视线范畴的玩家列表--------------X:4 Y:4X:5 Y:5X:2 Y:2X:1 Y:1---------------id为3玩家挪动后新退出玩家视线范畴的玩家列表--------------X:20 Y:20X:21 Y:21X:22 Y:22X:19 Y:19X:18 Y:18现存问题
此十字链表设计目前存在一个问题：当我的项目中实体数目十分多，每帧实体挪动频繁，每帧都会去进行x,y链表坐标排序，对性能耗费还是蛮大的，还在思考单纯用链表如何解决此问题。
援用：https://github.com/qq362946/A...