返回 登录
7

二叉树算法应用案例

笔者简介:姜雪伟,网名海洋,资深程序,IT高级讲师,CSDN社区专家,CSDN特邀编辑,畅销书作者,已出版书籍《手把手教你架构3D游戏引擎》、《Unity3D实战核心技术详解》等书籍。
笔者在1月4号将在CSDN学院开设一门公开课《算法与游戏实战》,在这里先把课程内容透露一部分给读者。首先讲述二叉树算法,二叉树在IT领域应用是非常广泛的,它不仅在游戏开发中,在当前比较火的人工智能上也得到了广泛的应用。作为使用者,首先要清楚二叉树的特性:它是n(n≥0)个结点的有限集;它的孩子节点做多是2个;它的遍历有先序,中序,后序;它的存储结构分为线性和链式存储等等;还有一种是最优二叉树也称为哈夫曼树,下面开始案例的分享。
在游戏开发中美术会制作很多图片,这些图片一方面是用于UI界面,另一方面是用于模型的材质。大部分网络游戏使用的图片数量是非常多的,图片要展示出来,它首先要加载到内存中,内存大小是有限制的,它除了加载图片还需要加载数据或者是模型。当跟随玩家的摄像机在场景中移动时,场景会根据摄像机的移动一一展现出来,这就需要不断的把不同的场景加入到内存中,这无疑会增加内存的吞吐负担,如果我们把图片归类把它们做成一张大的图片,这样一旦加入到内存中,就不用频繁的加载了,提高了效率。
现在大家都使用Unity开发或者使用虚幻开发,它自己实现了一个打成图集的功能,或者使用TexturePack工具也可以将其打包成图集。虽然我们看不到它们的代码实现,但是我们自己可以使用二叉树将其打包成图集,给读者展示利用二叉树实现的UI打成图集的效果图:
图片描述
下面给读者展示核心代码,首先是创建二叉树,目的是将图片插入到二叉树的结点中,包括判断二叉树结点是否为空,代码中采用递归的方式,代码如下所示:

public AtlasNode Insert(Texture2D image, int index) {
            if (image == null) // Obviously an error!
                return null;

            if (child != null) {// If this node is not a leaf, try inserting into first child.
                AtlasNode newNode = child[0].Insert(image, index);
                if (newNode != null)
                    return newNode;

                // No more room in first child, insert into second child!
                return child[1].Insert(image, index);
            }
            else {
                // If there is already a lightmap in this node, early out
                if (hasImage)
                    return null;

                // If this node is too small for the image, return
                if (!ImageFits(image, rc))
                    return null;

                // If the image is perfect, accept!
                if (PerfectFit(image, rc)) {
                    hasImage = true;
                    imageRef = image;
                    name = imageRef.name;
                    sortIndex = index;
                    return this;
                }

                // If we made it this far, this node must be split.
                child = new AtlasNode[2];
                child[0] = new AtlasNode();
                child[1] = new AtlasNode();

                // Decide which way to split image
                float deltaW = rc.width - image.width;
                float deltaH = rc.height - image.height;

                if (deltaW > deltaH) {
                    child[0].rc = new Rect(rc.xMin, rc.yMin, image.width, rc.height);
                    child[1].rc = new Rect(rc.xMin + image.width + TEXTURE_PADDING, rc.yMin, rc.width - (image.width + TEXTURE_PADDING), rc.height);
                }
                else {
                    child[0].rc = new Rect(rc.xMin, rc.yMin, rc.width, image.height);
                    child[1].rc = new Rect(rc.xMin, rc.yMin + image.height + TEXTURE_PADDING, rc.width, rc.height - (image.height + TEXTURE_PADDING));
                }

                // Lets try inserting into first child, eh?
                return child[0].Insert(image, index);
            }
        }

最后一步就是创建图集了,核心代码如下所示:

public static Atlas[] CreateAtlas(string name, Texture2D[] textures, Atlas startWith = null) {
        List<Texture2D> toProcess = new List<Texture2D>();
        toProcess.AddRange(textures);
        int index = toProcess.Count - 1;
        toProcess.Reverse(); // Because we index backwards

        List<Atlas> result = new List<Atlas>();

        int insertIndex = 0;
        if (startWith != null) {
            insertIndex = startWith.root.sortIndex;
        }

        while(index >= 0) {
            Atlas _atlas = startWith;
            if (_atlas == null) {
                _atlas = new Atlas();
                _atlas.texture = new Texture2D(AtlasSize, AtlasSize, TextureFormat.RGBA32, false);
                _atlas.root = new AtlasNode();
                _atlas.root.rc = new Rect(0, 0, AtlasSize, AtlasSize);
            }
            startWith = null;

            while (index >= 0 && (_atlas.root.Contains(toProcess[index].name) || _atlas.root.Insert(toProcess[index], insertIndex++) != null)) {
                index -= 1; 
            }
            result.Add(_atlas);
            _atlas.root.sortIndex = insertIndex;
            insertIndex = 0;
            _atlas = null;
        }

        foreach(Atlas atlas in result) {    
            atlas.root.Build(atlas.texture);
            List<AtlasNode> nodes = new List<AtlasNode>();
            atlas.root.GetBounds(ref nodes);
            nodes.Sort(delegate (AtlasNode x, AtlasNode y) {
                if (x.sortIndex == y.sortIndex) return 0;
                if (y.sortIndex > x.sortIndex) return -1;
                return 1;
            });

            List<Rect> rects = new List<Rect>();
            foreach(AtlasNode node in nodes) {
                Rect normalized = new Rect(node.rc.xMin / atlas.root.rc.width, node.rc.yMin / atlas.root.rc.height, node.rc.width / atlas.root.rc.width, node.rc.height / atlas.root.rc.height);
                // bunp everything over by half a pixel to avoid floating errors
                normalized.x += 0.5f / atlas.root.rc.width;
                normalized.width -= 1.0f / atlas.root.rc.width;
                normalized.y += 0.5f / atlas.root.rc.height;
                normalized.height -= 1.0f / atlas.root.rc.height;
                rects.Add(normalized);
            }

            atlas.uvRects = new AtlasDescriptor[rects.Count];
            for (int i = 0; i < rects.Count; i++) {
                atlas.uvRects[i] = new AtlasDescriptor();
                atlas.uvRects[i].width = (int)nodes[i].rc.width;
                atlas.uvRects[i].height = (int)nodes[i].rc.height;
                atlas.uvRects[i].name = nodes[i].name;
                atlas.uvRects[i].uvRect = rects[i];
            }

            atlas.root.Clear();
            #if DEBUG_ATLASES
            atlas.texture.Apply(false, false);
            SaveAtlas(atlas, name);     
            #else   
            if (atlas != result[result.Count - 1])
                atlas.texture.Apply(false, true);
            else
                atlas.texture.Apply(false, false);
            #endif
        }

        return result.ToArray();
    }

当然这种技术也可以使用3D模型材质的处理,只是在制作的过程中要保存其图片的UV值也就是图片在图集中的坐标,这样程序在加载时可以“对号入座”,避免模型的材质出现“张冠李戴”。
二叉树另一种形式是-哈夫曼树,哈夫曼树定义:在权为wl,w2,…,wn的n个叶子所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。我们利用哈夫曼树的特性可以帮助我们优化程序代码,特别适用于游戏中怪物面对玩家的AI表现,在网上比较流行的案例,游戏中也会使用到:设主角的生命值d,在省略其他条件后,有这样的条件判定:当怪物碰到主角后,怪物的反应遵从下规则:
图片描述
根据条件,我们可以用如下普通算法来判定怪物的反应:

if(d<100) state=嘲笑,单挑;
  else if(d<200) state=单挑;
    else if(d<300) state=嗜血魔法;
      else if(d<400) state=呼唤同伴;
        else state=逃跑;

上面的算法适用大多数情况,但其时间性能不高,我们可以通过判定树来提高其时间性能。首先,分析主角生命值通常的特点,即预测出每种条件占总条件的百分比,将这些比值作为权值来构造最优二叉树(哈夫曼树),作为判定树来设定算法。假设这些百分比为:
图片描述
构造好的哈夫曼树为:
图片描述
对应算法如下:

 if(d>=200)&&(d<300) state=嗜血魔法;
  else if(d>=300)&&(d<500) state=呼唤同伴;
    else if(d>=100)&&(d<200) state=单挑;
      else if(d<100) state=嘲笑,单挑;
        else state=逃跑;

通过计算,两种算法的效率大约是2:3,很明显,改进的算法在时间性能上提高不少。这种改进也可以归结到代码重构或者说是优化程序,它虽然没有使用二叉树的存储节点,但是我们可以使用二叉树的思想解决问题。
在人工智能中,二叉树使用也是非常广泛的,不同的分支指令对应的是不同的动作等等,在遇到AI方面的问题时可以优先考虑二叉树算法。

总结

在使用算法解决问题时,并不是照搬硬套,其思想是最重要的,代码只是编程工具,语言不是重点,思路才是最重要的,万变不离其宗。

评论