游戏中你能看见我不代表我能看见你

假设这是一款普通的2D游戏。屏幕被划成9个格子,一般来说人站在最中间那个格子。它能看见自己周围一圈这8个格子里的东西。

我在这里

如果如下两个假设成立,

  1. 角色一定站在屏幕正中间。必须是正中心,丝毫不差。
  2. 每个角色的视野的宽和高都是一样的(而不是像WOW那样可以让玩家自己调整)。

那么,如果A能看见B,则B一定能看见A。

所以,当一个角色上线的时候,只需要告诉它视野内的人即可。同理,这个角色的所有状态改变,如移动啊、下线啊、进入离开视野啊,也只需要按照它的视野来算。在我移动中,凡是有角色进入我的视野,我就应该告诉它,嘿,哥们,我出现了,我的横坐标是xxx,纵坐标是yyy,我在往哪哪哪走。

视野广播,从来都不是为了发给我能看见的那些人,而是为了发给能看见我的人!

其实很难保证这个人就是在正中心,因为如果人的位置是按像素坐标存的,那么他的视野未必恰好就是跨越整格子数。要么不是让人站正中心,而是让人所在的格子在正中心。要么就得把一些视野外的人也算进来。

可是,可是!角色并非总是站在屏幕中间。当角色走到地图边缘附近的时候,有两种做法

  1. 让角色依然站在屏幕中央。让超出地图边界的部分显示成黑色
  2. 让地图边界与屏幕边界对齐。

如果是后一种做法,请看下图:

(0,0) 角色A (1,0) (2,0) (3,0)
(0,1) (1,1) (2,1) (3,1)
(0,2) (1,2) (2,2)角色B的终点 (3,2)
(0,3) (1,3) (2,3) (3,3)角色B的起点

假设角色A站在地图的左上角,(0,0)位置。而另一个角色B从(3,3)往(2,2)走。那么当它走到(2,2)停下来的时候,它看不到A,所以不会告诉A说我进入你视野啦!所以A就看不见B。但实际上B却站在A的视野内。这会造成一种不可接受的现象:两个人约了在仓库门口交易,一个人(A)先到了,站在旁边的武器店挑选武器。另一个人接着(B)也到了。

玩家B说: 我到了。邀请我交易。
玩家A说: 我也到了。你站哪的?
玩家B说: 我就站在仓库门口啊!有棵树这
玩家A说: 不对啊,仓库门口明明没有人啊!

……

把这个问题抽象出来,就是平面上有很多大小相等的矩形,给定一个点,问这个点在哪些矩形内?一般化一点,可能有的矩形大,比如人物视野,有些矩形小,比如npc的主动攻击范围。

解决这个问题,最笨的办法就是把地图上所有的对象都去问一遍,嘿,我在你的视野范围内不?但是,假如地图上有1000人,就因为人有时候可能不是站在屏幕中央(这么小一个设计),就导致运算量增加了1000倍!别闹了,不可能!

稍微好一点的做法就是打补丁的做法,算完自己的视野范围后,根据视野左上角和右下角点的坐标,加上或减去屏幕宽或者高的一半,然后看是否超出地图边界,如果超出则补格子进来。然后根据最终这个结果发广播。但是假设矩形大小不相等,如果我们假设角色的视野范围是最大的矩形,一定是最宽的,也一定是最高的,那么这个方式依然可用。并且怪物的AOI范围并不需要像处理视野广播这样按地图边界处理,所以很简单。

但是,更一般的情况呢?如果有的矩形比屏幕大呢?用RTree来存储这些数据?还是我想的太远了?

你是怎么做的?

此博客中的热门博文

在windows下使用llvm+clang

少写代码,多读别人写的代码

tensorflow distributed runtime初窥