作者 :刘丰恺

作者博客:若梦浮生

转载需征得作者本人同意

之前试着在Android平台封装了一个轻量级的游戏开发框架JustWeEngine ,因为是轻量级的所以也没想太多,很多地方的处理都不太够,比如关于碰撞事件的处理,就是一个简单的On2的遍历,前一阵还被吐槽了233333。

其实优化On2碰撞的思路是一而贯之的,就是不去处理根本不可能撞在一起的对象。所以就文章讨论一下我了解的在游戏开发中经常被使用的碰撞机制。

示例图

bird

图示是使用了四叉树进行碰撞判断的一个图示,变成紫色的是从四叉树中拿取的离我最近的可能碰撞对象,这里我们只需要处理最近的四个对象就可以了,这个demo感谢FriceEngine的demo。

物体分组

对Engine所加载的对象进行分层处理,每层维护一个对象列表,对可能根本不需要进行碰撞处理的对象不去处理,不会发生碰撞的层也不去处理,这样我们的O2的复杂度没变,但是我们减少了很多无用的碰撞对象,而我们想要他们碰撞也可以非常简单的切换。

我在JustWeEngine里面就试着用了物体分组的方式

public enum LayerType {
        Button,
        Default
    }

    public interface LayerListener {
        boolean Touch(MotionEvent event);

        void Collision(BaseSub baseSub);

        void Update();

        void Draw();
    }

    protected LayerType layerType;

    protected String layerName;
    // Layer的刷新范围也是绘制范围
    protected Rect layerField;

    protected Screen layerScreen;

    public Layer(LayerType layerType, Screen layerScreen, Rect layerField) {
        this.setLayerType(layerType);
        this.layerField = layerField;
        this.layerScreen = layerScreen;
    }

通过引入Layer的概念,把不同的对象放到不同的组里面,分别进行碰撞处理。

    private ArrayList<Layer> e_layers;
    public interface ScreenListener {
        void Init();

        void Load();

        void Update();

        void Touch(MotionEvent event);
    }

然后在Screen类里面就不再处理碰撞事件,而是统一的在Layer中进行处理。

但是这种东西的缺点也很明显,就是On2没有从实质上被解决,只是缩小了基数,对于一层的数据量大的时候仍然无效。

屏幕分割

相比于通过对象的遍历拿到具体坐标进行对应的比较,使用屏幕分割明显是一种更为正常的方式,通过将屏幕分割成一些小的格子,每个格子管理在自己区域内的操作对象。

主要的碰撞检测方法是划分区域的时候,把格子放大到超过所操作对象的最大值,使格子能够包含最大的对象(以中心点来判定),然后的判定逻辑就十分简单了,每个格子内部进行比较判断是否有碰撞事件,然后在邻近的格子之间进行判断碰撞事件。这里有的人是比较临近各方位的八个方块,但其实遍历的话从左上角开始,只需要比较右侧,下方,和右下的放块就可以了。

那么如何判断物体在哪个方块呢,使用简单的屏幕分割是没有办法动态处理方块分配的,所以在每一帧的开始都会进行一次On的遍历分配,其实这也是一个耗时操作。

四叉树

相比于屏幕分割的方法,四叉树的方法会更加灵活一些。四叉树的构成大概遵循这样几个条件:

  • 每个非叶子节点有四个节点
  • 四个节点对应一个区域的四个象限,每个象限可以再分
  • 在象限内的对象被归属于此节点,跨象限的对象被归到父节点

一个简单的四叉树实现如下:

(下面的代码有一点Kotlin的风格,但是对于Javaer 是能简单看懂的程度)

import org.frice.game.obj.PhysicalObject
import org.frice.game.utils.quad.RectF
import java.util.*

/**
 * QuadTree
 * @author lfkdsk
 * Created by liufengkai on 2016/10/4.
 */
class QuadTreeKT {

	val MAX_OBJECTS = 3

	val MAX_LEVELS = 5

	var level: Int

	private var bounds: RectF

	private val objects: ArrayList<PhysicalObject>

	private val nodes: Array<QuadTreeKT?>


	constructor(level: Int, bounds: RectF) {
		this.level = level
		this.bounds = bounds
	}

	init {
		this.nodes = kotlin.arrayOfNulls<QuadTreeKT>(4)
		this.objects = ArrayList<PhysicalObject>()
	}

	fun clear() {
		objects.clear()
		for (i in nodes.indices) {
			if (nodes[i] != null) {
				nodes[i] = null
			}
		}
	}

	private fun split() {
		// width & height
		val subWidth = (bounds.width() / 2)
		val subHeight = (bounds.height() / 2)
		// x & y
		val x = bounds.left
		val y = bounds.top
		// split to four nodes
		nodes[0] = QuadTreeKT(level + 1, RectF((x + subWidth), y, subWidth, subHeight))
		nodes[1] = QuadTreeKT(level + 1, RectF(x, y, subWidth, subHeight))
		nodes[2] = QuadTreeKT(level + 1, RectF(x, (y + subHeight), subWidth, subHeight))
		nodes[3] = QuadTreeKT(level + 1, RectF((x + subWidth), (y + subHeight), subWidth, subHeight))
	}


	/**
	 * 获取rect 所在的 index

	 * @param rectF 传入对象所在的矩形
	 * *
	 * @return index 使用类别区分所在象限
	 */
	private fun getIndex(rectF: PhysicalObject): Int {
		var index = -1
		val verticalMidpoint = bounds.left + bounds.width() / 2
		val horizontalMidpoint = bounds.top + bounds.height() / 2

		// contain top
		val topQuadrant = rectF.y < horizontalMidpoint && rectF.y + rectF.height < horizontalMidpoint
		// contain bottom
		val bottomQuadrant = rectF.y > horizontalMidpoint

		// contain left
		if (rectF.x < verticalMidpoint && rectF.x + rectF.width < verticalMidpoint) {
			if (topQuadrant) {
				index = 1
			} else if (bottomQuadrant) {
				index = 2
			}
			// contain right
		} else if (rectF.x > verticalMidpoint) {
			if (topQuadrant) {
				index = 0
			} else if (bottomQuadrant) {
				index = 3
			}
		}

		return index
	}

	/**
	 * insert object to tree

	 * @param rectF object
	 */
	fun insert(rectF: PhysicalObject) {
		if (nodes[0] != null) {
			val index = getIndex(rectF)

			if (index != -1) {
				nodes[index]?.insert(rectF)
				return
			}
		}

		objects.add(rectF)

		if (objects.size > MAX_OBJECTS && level < MAX_LEVELS) {
			// don't have subNodes
			// split node
			if (nodes[0] == null) {
				split()
			}

			var i = 0
			while (i < objects.size) {

				val index = getIndex(objects[i])

				if (index != -1) {

					nodes[index]?.insert(objects.removeAt(i))

				} else {

					// don't in subNode save to parent node.
					// eq: object on line
					i++
				}
			}
		}
	}

	/**
	 * return all the object collision with the object

	 * @param returnObjects return list
	 * *
	 * @param rectF         object
	 * *
	 * @return list of collision
	 */
	fun retrieve(returnObjects: ArrayList<ArrayList<PhysicalObject>>, rectF: PhysicalObject): List<List<PhysicalObject>> {
		val index = getIndex(rectF)

		if (index != -1 && nodes[0] != null) {
			nodes[index]?.retrieve(returnObjects, rectF)
		}

		returnObjects.add(objects)
		return returnObjects
	}
}

上面的这段代码比较的对象是一个叫PhysicalObject的实体对象,当然这是有耦合的问题,但是细读代码会发现其实我们只要提供一个带有坐标(相对于游戏世界)的对象就可以了,下面我们来解释一下这段代码。

首先,MAX_OBJECTS 和 MAX_LEVELS 定义了这颗四叉树的所能存储的最多对象和最高层级。每个层级节点含有一个RectF对象保存当前层级对应的屏幕区域,每个节点最多可以被分为四个子节点(要么不分作为叶节点,要么分成四个对应四个象限)。

接下来看方法,我们先从最重要的插入函数开始:

	fun insert(rectF: PhysicalObject) {
		if (nodes[0] != null) {
			val index = getIndex(rectF)

			if (index != -1) {
				nodes[index]?.insert(rectF)
				return
			}
		}

		objects.add(rectF)

		if (objects.size > MAX_OBJECTS && level < MAX_LEVELS) {
			// don't have subNodes
			// split node
			if (nodes[0] == null) {
				split()
			}

			var i = 0
			while (i < objects.size) {

				val index = getIndex(objects[i])

				if (index != -1) {

					nodes[index]?.insert(objects.removeAt(i))

				} else {

					// don't in subNode save to parent node.
					// eq: object on line
					i++
				}
			}
		}
	}

插入一个可以处理的对象的时候,首先判断是否有子对象,如果有子对象的话,就通过getIndex()方法获取次对象所在的象限,并直接插入。如果我们没有子节点,就会把这个对象加入到此节点的List中,当此节点的存储对象满了的时候就会进行分裂,并通过一个循环将此节点的对象“下放”到四个子节点中。

我们接着来看分裂splite()分裂的过程特别的简单,就是把此节点对应的RectF分裂成四个子画布,对应的生成

四个子节点。

刚才我们在这几个函数里使用了一个getIndex()函数:

	private fun getIndex(rectF: PhysicalObject): Int {
		var index = -1
		val verticalMidpoint = bounds.left + bounds.width() / 2
		val horizontalMidpoint = bounds.top + bounds.height() / 2

		// contain top
		val topQuadrant = rectF.y < horizontalMidpoint && rectF.y + rectF.height < horizontalMidpoint
		// contain bottom
		val bottomQuadrant = rectF.y > horizontalMidpoint

		// contain left
		if (rectF.x < verticalMidpoint && rectF.x + rectF.width < verticalMidpoint) {
			if (topQuadrant) {
				index = 1
			} else if (bottomQuadrant) {
				index = 2
			}
			// contain right
		} else if (rectF.x > verticalMidpoint) {
			if (topQuadrant) {
				index = 0
			} else if (bottomQuadrant) {
				index = 3
			}
		}

		return index
	}

这函数的方法也很简单,我们通过对游戏操作的对象的位置,然后通过中心来判断对象在当前层画布的哪个象限。

(这里有个小问题,后面会讲到)。

至此,我们构建四叉树的工作就完事了,我们需要做的,就是在这帧绘制处理碰撞前,把所有的对象注入四叉树,然后我们来做下一步,根据对象,来获取可能与之碰撞的对象,此时我们的O (n^2)的搜索降低到一个O(n)了,并且我们的搜索对象也少了很多。如果我们判断碰撞的对象仅仅只有控制对象一个,这个碰撞的解决办法就会更为合适。

我们在将使用retrieve()函数来获取可能碰撞的对象:

fun retrieve(returnObjects: ArrayList<ArrayList<PhysicalObject>>, rectF: PhysicalObject): List<List<PhysicalObject>> {
		val index = getIndex(rectF)

		if (index != -1 && nodes[0] != null) {
			nodes[index]?.retrieve(returnObjects, rectF)
		}

		returnObjects.add(objects)
		return returnObjects
	}

输入一个用于返回的数组和用于判断的对象,获取所在象限逐层深入去拿和自己最接近象限的对象,再通过相对位置去判断是不是真的进行了碰撞。

现在我们来说说刚才那个问题,那个getIndex()的问题在于并不是所有的对象都能正正好好的被安排在象限里,这时候我们就不得不想个办法去处理这些”卡在线上”的对象,这里我给出两个方法去处理:

  • 第一种就简单的把没办法处理的对象放在父节点的对象池里。
  • 第二种我们的判断就会更精细一点,我们把卡在线上的实体块按照象限分成几块(x,y轴)然后把分出来的对象做好标记,要保证能判断出是一个对象的拆分,然后把分出来的对象,重新getIndex插入,就可以避免了卡线的问题。

动态四叉树

上面是用了四叉树的方式,但是也有一个不足,这个不足在对象少的时候不太明显,但是在对象多的时候,就和发现每一帧都会进行一次四叉树的销毁和重绘,这会消耗大量的系统资源。所以说我们应该去想一种方法去减少四叉树的创建消耗,这里很明显的一点,就是一般的游戏是16ms绘制一帧,在这16ms中其实并没有太多的对象作出太大的移动,甚至还在同一个象限,所以说我们浪费就浪费在这个地方了。那么我们就对四叉树的优化有了一个思路,我们只要对和原来象限不一样的对象进行重新插入就可以了,这里我们可以先判断一下这个对象,在不在原来的象限:

    private fun isInner(ob: PhysicalObject, rectf: RectF): Boolean {
        return ob.x >= rectf.left
                && ob.x + ob.width <= rectf.left + rectf.w
                && ob.y >= rectf.top
                && ob.y + ob.height <= rectf.top + rectf.h;
    }

这个就很简单了,仅仅是一个矩形的判断。

最后使用refresh()方法对四叉树进行刷新:

    fun refresh(root: QuadTreeKT) {

        var ob: PhysicalObject

        var index: Int

        for (i in objects) {
            ob = i
            index = getIndex(i) // get Index 
            if (!isInner(ob, bounds)) {
                // re-insert
                if (this != root) {
                    root.insert(ob)
                } else if (nodes[0] != null) {
                    this.nodes[index]?.insert(ob)
                }
            }
        }

        nodes.forEach { i ->
            i?.refresh(root)
        }
    }

每次对object对应的的bounds判断是否包含,来判断是否已经脱离了原来的象限,如果脱离了就重新插入,接着逐层的深入去refresh就可以了。

这篇文章我们学到了什么?

  • 实体分组减少碰撞对象
  • 屏幕分块减小了碰撞判断的区域
  • 四叉树以及修改版的动态方法去获取

作者 :刘丰恺

作者博客:若梦浮生

转载需征得作者本人同意