基于行为树的MOBA技能系统：碰撞系统

前言

基于行为树的Moba技能系统系列文章总目录：https://www.lfzxb.top/nkgmoba-totaltabs/

一些游戏中简单的碰撞系统，可能就是手写几个圆形，矩形，扇形就够用了，但是Moba类游戏很多技能碰撞体是畸形的，比如派克的R，男枪的Q，R等都是不规则的，所以我们需要一个稳健的物理库来支持这些，自己处理碰撞体顶点数据，创建碰撞体到物理世界中，因为游戏类型原因，我选择了Box2D：https://github.com/erincatto/Box2D，对于FPS游戏，只有Bullet（3D物理库）：https://github.com/bulletphysics/bullet3 可选，这里就不多说了。

由于碰撞系统本身需要和技能系统产生非常紧密的联系，所以涉及到的内容也会比较多，主要包括

Box2D物理库介绍
Box2D碰撞体编辑器拓展，负责制作碰撞体和导出碰撞体数据：https://www.lfzxb.top/box2d-unityvistualeditor/
Box2D碰撞关系编辑器拓展，负责维护碰撞体之间的碰撞关系，并自动生成代码：https://www.lfzxb.top/box2d-collisionrelationvisualeditor/
碰撞系统架构设计

Box2D物理库

Box2D介绍

Box2D是一款开源的基于C++开发的2D游戏物理引擎，本项目使用的是C#版本的：https://github.com/Zonciu/Box2DSharp

然后是Box2D使用的动态AABB树碰撞检测算法：

A dynamic AABB tree broad-phase, inspired by Nathanael Presson’s btDbvt. A dynamic tree arranges data in a binary tree to accelerate queries such as volume queries and ray casts. Leafs are proxies with an AABB. In the tree we expand the proxy AABB by b2_fatAABBFactor so that the proxy AABB is bigger than the client object. This allows the client object to move by small amounts without triggering a tree update.

Nodes are pooled and relocatable, so we use node indices rather than pointers.

The Dynamic tree is the cross between a classic avl binary tree and a quadtree. The end effect is a quadtree that that only splits each node in half, and the split line isn’t fixed (the two halves aren’t equal sized like a quad tree). AVL comes in because quadree with dynamic splits can degenerate to essentially a list (O(n) lookup speed). The AVL is used to rebalance subtrees so to ensure O lg(N) lookup speed.

Best of all the code is MIT so feel free to copy / derived / shamelessly-steal / etc.

对于Box2D具体的文档，我之前有写过几篇文章，其实都是从《BOX2D物理游戏编程初学者指南》上摘录的

Box2D基础知识点

Box2D进阶知识整合

Box2D性能测试

使用

//------------------------------------------------------------
// Author: 烟雨迷离半世殇
// Mail: 1778139321@qq.com
// Data: 2020年4月24日 18:17:11
//------------------------------------------------------------

using System;
using System.Diagnostics;

namespace ETModel
{
    /// <summary>
    /// 压测辅助类
    /// </summary>
    public class BenchmarkHelper
    {
        /// <summary>
        /// 当前帧步进数
        /// </summary>
        public static long CurrentFrameCount = 1;

        /// <summary>
        /// 开始压测
        /// </summary>
        /// <param name="description">描述</param>
        /// <param name="action">要压测的函数</param>
        /// <param name="iterations">迭代次数</param>
        /// <returns></returns>
        public static double Profile(string description, Action action, int iterations = 100)
        {
            // clean up
            GC.Collect();
            GC.WaitForPendingFinalizers();
            GC.Collect();
            // from: http://stackoverflow.com/questions/1047218/benchmarking-small-code-samples-in-c-can-this-implementation-be-improved
            //Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.High;
            //Thread.CurrentThread.Priority = ThreadPriority.Highest;
            // warm up 
            action();

            var watch = new Stopwatch();

            watch.Start();
            for (int i = 0; i < iterations; i++)
            {
                action();
            }

            watch.Stop();

            Log.Info(string.Format("[Profile] {0} took {1}ms (iters: {2} ; avg: {3}ms).", description,
                watch.Elapsed.TotalMilliseconds, iterations, watch.Elapsed.TotalMilliseconds / iterations));
            return watch.Elapsed.TotalMilliseconds;
        }
    }
}

测试创建1000个重叠圆形碰撞体

public void UnitTest_CreateCollision()
{
	BodyDef bodyDef = new BodyDef { BodyType = BodyType.DynamicBody };
	Body m_Body = Game.Scene.GetComponent<B2S_WorldComponent>().GetWorld().CreateBody(bodyDef);
	CircleShape m_CircleShape = new CircleShape();
	m_CircleShape.Radius = 5;
	m_Body.CreateFixture(m_CircleShape, 5);
}

1	BenchmarkHelper.Profile("测试创建1000个碰撞体", UnitTest_CreateCollision, 999);

测试结果如下

1k碰撞体重叠在一起，进行了约50w次碰撞响应，耗时3000ms，平均每次碰撞计算需要耗时0.006ms，但是游戏中不可能会出现这种极端情况，如果4个碰撞体堆叠在一起，就要进行4 * (4 - 1) / 2 = 6次碰撞响应，如果依次零距离排开就只需要4 - 1 = 3次碰撞响应（这种情况依旧少见），以此类推，考虑到我们逻辑的处理，单个进程单帧纯碰撞检测耗时5ms的话，就是至少830个左右的碰撞体依次零距离排开，并且很多情况下我们游戏内的碰撞体是离散的，这个碰撞体最大数量还可以再大胆提升2~3倍，完全满足绝大多数游戏需求