电视游戏UI面板中如何快速查找附近控件

Posted by 鸿杰 on November 13, 2015

电视游戏中只能通过上下左右四个按键进行UI控件的选择,那么如何知道当前控件的上下左右分别是哪个控件呢? 首先想到的是使用四叉树算法将面板容器进行分割,获得当前控件所在节点A,通过A节点找到附近的节点B,然后再获取B节点中的控件,于是大功告成。

四叉树结构图

将ui容器进行四叉树分割,深度控制为让每个节点最多包含1个控件为宜,一般来说深度设为3就够了,方便起见,这里我们先按深度为2进行分割,如上图所示,R节点中记录左上角节点为R1,右上角为R2,左下角为R3,右下角为R4,R1、R2、R3、R4节点中又分别记录四个方向的子节点,以此类推,直到无法分割为止。在每个子节点都记录了自己的父节点,比如R1、R2、R3、R4节点的父节点都是R。当面板当前焦点控件在R41时,按下右方向键,先找到R41的父节点R4,在R4中找到R41右边的节点R42,获取R42中的控件,便是我们想要得到的控件了。那么问题来了,R42中没有控件呢?R42已经是R4的子节点中最靠右的节点了,那么就要再获取到R4的父节点R,找到R4右边的节点,再获取其距离R42最近的子节点,然后判断其中有无控件,如果还没有,那么又是一个循环,直到找到控件或者碰到边缘节点为止。

四叉树的lua代码我已经实现了点击打开

思路不复杂,但是在实际编码中发现要完整实现这套逻辑还是挺麻烦的。 为了测试方便,我将每个节点用红线画了出来,如图: 四叉树分割图

当看到分割图的时候,我就暗骂自己sb了。这尼玛不就是一个个的矩形小格组成的网格嘛?那我使用一个二维数组来保存这些小格,小格里记录着控件,那通过简单的二维数组查询不就可以很方便地找到目标控件了吗? 那么开始编码吧。 第一步是创建小格子类,很简单,记录了格子范围和格子中的控件数据。

local Cell = class("Cell")

function Cell:ctor(rect)
	-- 图形范围
	self._rect = rect
	-- 数据
	self._dataList = { }
end

--- 判断坐标是否在界限内
function Cell:isIn(x, y)
	return cc.rectContainsPoint(self._rect, {x = x, y = y})
end

function Cell:addData(data)
	self._dataList[#self._dataList + 1] = data
end

function Cell:hasData(data)
	for i, v in ipairs(self._dataList) do
		if v == data then
			return true
		end
	end
end

function Cell:getData()
	return self._dataList
end

return Cell

第二步就是创建Grid类,保存了所有的Cell。 构造函数里根据容器的长宽和深度deep生成所有的Cell实例

self._cellList = { }
	
self._nums = deep
local cellWidth, cellHeight = checkint(container:actualWidth() / self._nums), checkint(container:actualHeight() / self._nums)
local x, y = 0, container:actualHeight() - cellHeight
for row = 1, self._nums do
	self._cellList[row] = { }
	for col = 1, self._nums do
		self._cellList[row][col] = Cell.new({x = x, y = y, width = cellWidth, height = cellHeight})
		x = x + cellWidth
	end
	x, y = 0, y - cellHeight
end

然后将需要交互的控件添加到对应的Cell中

function Grid:addData(data, x, y)
	for row, colList in ipairs(self._cellList) do
		for col, cell in ipairs(colList) do
			if cell:isIn(x, y) then
				cell:addData(data)
				return self
			end
		end
	end
end

格子和控件都准备好了,那么为了方便测试,也把网格用线画出来吧。 此处输入图片的描述 如上图所示,面板大小是600*600,用黄色线条画出,面板进行了深度为5的Grid分割,以保证每个Cell中最多只包含一个控件,总共是25个Cell,在遍历寻找中是不怎么耗性能的。每个格子上的数字,第1位表示所在行index,第2位表示所在列索引。接下来就是怎么个找法了。拿4444控件说来,按下方向右按键时,先在同一行找到右边一列的格子(42格),判断其中是否有控件数据,有的话就算是找到了,没有的话,就以42格为中心,向上一行(32格)和向下一行(52格)进行寻找,还没有?那就继续找22格和。。。咦,没有62格,那就只找22格,还没有???那继续吧,12格,又没有?那么列数加1,从43格开始找,按照这个逻辑进行寻找,直到找到或者遍历完右边所有格子为止。其他三个方向也是同样的逻辑进行查找。这段逻辑的代码编写起来比四叉树方便许多,而且性能上也丝毫没有影响,真是小巧又好用。

Grid是基于容器进行分割的,当一个大容器A中有两个小容器a、b,A、a、b都有各自的Grid,假设a在b的左边,在a里无法寻找到源控件的右边控件时,就转到A中寻找a的右边控件,也就是b控件,然后在b中找到最左边的控件,就是我们想要的目标控件了,这样也就实现跨容器寻找,非常方便。 大家看完有什么意见或者建议的话,欢迎找我讨论。

Grid完整代码浏览