Chinaunix首页 | 论坛 | 博客
  • 博客访问: 4970154
  • 博文数量: 921
  • 博客积分: 16037
  • 博客等级: 上将
  • 技术积分: 8469
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-05 02:08
文章分类

全部博文(921)

文章存档

2020年(1)

2019年(3)

2018年(3)

2017年(6)

2016年(47)

2015年(72)

2014年(25)

2013年(72)

2012年(125)

2011年(182)

2010年(42)

2009年(14)

2008年(85)

2007年(89)

2006年(155)

AOI

分类: C/C++

2016-03-04 12:08:23

AOI服务作为网络游戏中的中的一个重要组件,用于为地图中的对象根据当前坐标更新关注列表.对于玩家而言,在A关注列表中的对象,其状态发生改变时,需要通知A,这样A才能看到在视野内

其它对象的移动,战斗等。对于NPC而且,关注列表中的对象表示在自己一定范围内的对象,可作为AI选择的攻击目标。

典型的AOI算法包括格子,十字链表等,关于十字链表法可参考:

本文介绍一种基于格子的算法.

本算法实现的目标是支持可变长视距,根据视距半径,计算出一个包围这个视野圆的最小正方形,然后计算出这个正方形包含在哪些格子中,这些格子中的对象都有可能是可见对象.

首先介绍基本的数据结构:

单元格:

  1. struct map_block
  2. {
  3.     struct double_link aoi_objs;
  4.     uint32_t x;
  5.     uint32_t y;
  6. };
地图中的所有对象都归属于一个单元格管理,所以单元格中有一个双向链表,方便对象的添加和删除.x和y表示单元格在地图中的行列坐标.


  1. struct aoi_object
  2. {
  3.     struct double_link_node block_node; //??????map_block???????ó??????????±í
  4.     struct map_block *current_block;
  5.     uint32_t aoi_object_id;
  6.     struct bit_set self_view_objs; //×??????ì???????ó????
  7.     struct point2D current_pos; //?±?°×?±ê
  8.     uint32_t view_radius; //????°???
  9. };

aoi_object代表地图中对象,view_radius表示其实际可视半径,self_view_objs记录了当前关注的对象集,用一个bit_set实现,目前我将位集的大小设置为65536,也就是地图中最多可容纳65536个对象,

这样,当对象进入视野时就根据aoi_object_id设置相应的位,离开时清除相应的位,还可以快速的判断一个对象是否在自己的视野中.

基本算法如下:

1)当对象A进入地图时,以标准视距作为半径,算出相关的单元格,遍历单元格中的对象,计算出两对象A和B的distance,如果distance < A->view_radius则B进入A的视野,如果distance < B->view_radius

则A也进入B的视野.

2) 对象A离开地图时,以标准视距作为半径,算出相关的单元格,遍历单元格中的对象,计算出两对象A和B的distance,如果distance < B->view_radius则A离开B的视野.

3)当对象A在地图中移动时,以标准视距作为半径,分别为老坐标和新坐标计算出相关的单元格,这里的单元格会被分成三类,1:新进入的,2:离开的,3:无变化的.对于1,2类分别按1),2)处理即可.

对于第3类,格子中的对象需要做进一步的判断(参看后面贴出的实现代码)

上面提出了一个标准视距的概念,主要用于处理以下问题,A视距为100,B为50,A静止B向A移动,如果以B的实际视距做计算,则只有当B在A的50范围内时A才能看到B,而实际上B在A的100范围

内时A就应该看到B了。如果将标准视距设置为100就不存在这样的问题了.

但是,标准视距离设置得过大,会导致计算更多的格子,所以标准视距一般设置为玩家的可视距离.这又出现了另一个问题,游戏设定中,可能会出现少数超远视距的对象。例如,标准视距是50

但某些对象的视距是100,超视距对象在地图中相对来说是稀少的,所以对超视距的对象可做特殊处理.首先,超视距对象有一个更新间隔,每次更新视野后,记录下变更时间.触发视野变更的条件之

一是执行move,但如果超视距对象长时间静止就需要主动调用一个函数,以触发其视野变更.处理代码如下:


  1. static inline tick_super_object(struct map *m,struct aoi_object *o)
  2. {
  3.     uint32_t now = GetCurrentMs();
  4.     if(now - o->last_update_tick >= UPDATE_INTERVAL)
  5.     {
  6.         //remove out of view object first
  7.         uint32_t i = 0;
  8.         for( ; i < MAX_BITS; ++i)
  9.         {
  10.             if(o->self_view_objs.bits[i] > 0)
  11.             {
  12.                 uint32_t j = 0;
  13.                 for( ; j < sizeof(uint32_t); ++j)
  14.                 {
  15.                     if(o->self_view_objs.bits[i] & (1 << j))
  16.                     {
  17.                         uint32_t aoi_object_id = i*sizeof(uint32_t) + j;
  18.                         struct aoi_object *other = m->all_aoi_objects[aoi_object_id];
  19.                         uint64_t distance = cal_distance_2D(&o->current_pos,&other->current_pos);
  20.                         if(distance > o->view_radius)
  21.                             leave_me(m,o,other);
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         //process enter view
  27.         uint32_t x1,y1,x2,y2;
  28.         cal_blocks(m,&o->current_pos,o->view_radius,&x1,&y1,&x2,&y2);
  29.         uint32_t y = y1;
  30.         uint32_t x;
  31.         for( ; y <= y2; ++y)
  32.         {
  33.             for( x=x1; x <= x2; ++x)
  34.             {
  35.                 struct map_block *bl = get_block(m,y,x);
  36.                 struct aoi_object *cur = (struct aoi_object*)bl->aoi_objs.head.next;
  37.                 while(cur != (struct aoi_object*)&bl->aoi_objs.tail)
  38.                 {
  39.                     if(is_set(&o->self_view_objs,cur->aoi_object_id) == 0)
  40.                     {
  41.                         uint64_t distance = cal_distance_2D(&o->current_pos,&cur->current_pos);
  42.                         if(o->view_radius >= distance)
  43.                             enter_me(m,o,cur);
  44.                     }
  45.                     cur = (struct aoi_object *)cur->block_node.next;
  46.                 }
  47.             }
  48.         }
  49.         o->last_update_tick = now;
  50.     }
  51.     
  52. }

完整代码如下:

原文链接


阅读(1016) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~