背包大乱斗算法设计

keyle_xiao

前一段时间写了一篇背包大乱斗与俄罗斯方块(设计篇) ，具体的实现思路在这一文中已经讲清楚了，后来我抽空去实现了一版。目前看效果还不错。

已经实现，形状的变换，定位，移动，消除，障碍判定等。
本篇稍微讲一下具体的实现过程，以及如何去优化这个算法。

基于池去实现节点的创建与回收

一开始就基于这个池模板去管理所有数量上较多的对象，后期优化的压力会小一些。

public interface IReset
{
    void Reset();
}

public interface IPool<T> where T : IReset
{
    Stack<T> nodesPool { get; }

    T CreateOne<W>() where W : T, new();
    void ReturnOne(T item);
}


public class BasePool<T> : IPool<T> where T : IReset
{
    Stack<T> _nodesPool = new Stack<T>();
    public Stack<T> nodesPool { get { return _nodesPool; } }

    public virtual T CreateOne<W>() where W : T, new()
    {
        if (nodesPool.Count > 0)
        {
            return nodesPool.Pop();
        }
        return new W();
    }

    public virtual void ReturnOne(T node)
    {
        node.Reset();
        nodesPool.Push(node);
    }
}

分离算法与表现

我们的算法是需要适应不同的场景的，如果基于一套UI或者3D/2D渲染，混写代码，就会导致这个代码复用性低，迁移起来费时费力。

TileInfo.cs 作为管理单个形状( 物品) 渲染信息的最小单位。我们并不需要在这里书写任何如何去渲染的逻辑。

public class TileInfo :  IReset
{
    public List<GameObject> Cubes = new List<GameObject>();
    public GameObject Tile;
    public Color BaseColor;

    public void Reset()
    {
        BaseColor = Color.white;

        if (Cubes.Count > 0)
        {
            for (int i = 0; i < Cubes.Count; i++)
                PrefabPoolManager.GetInstance().PushGameObjectByType(PrefabPoolManager.PrefabType.Cube, Cubes[i]);
            Cubes.Clear();
        }
        PrefabPoolManager.GetInstance().PushGameObjectByType(PrefabPoolManager.PrefabType.Tile, Tile);
        Tile = null;
    }
}

将这个逻辑放到一个单独的Render脚本中，这样处理现在我们已经将渲染画面的功能完全隔离到了 BlockRender。
如果我们有3D的画面，就可以写一个3DBlockRender 或者是 UIBlockRender ，只需要抽象出接口做新的实现即可。

public class BlockRender 
{
    public TileInfo UpdatePreSelectNode(PreSelect node, LogicMap map)
    {
        return UpdateTile(node, node.Shape, node.x, node.y, map);
    }

    public TileInfo UpdatePreSelectNode(PreSelect node, IShape shap, LogicMap map) 
    {
        return UpdateTile(node, shap, node.x,node.y,map);
    }
 
    ...

至此我们已经完成了基础逻辑，他包含一个通用的池实现，与一个通用的渲染层。

核心算法

一般来说游戏的业务逻辑复杂度都不高，真要说复杂的，那肯定是渲染逻辑。
这段放置图形的代码，就是背包大乱斗最复杂的业务逻辑了。

通过当前节点的相对点加图形的数据结构中存储的x与y值，就可以推算出逻辑节点的坐标。
注意这边的逻辑节点，需要配置map的信息，比如map的位置信息与缩放进行一个定位，才能换算出真实坐标。

当然下面的代码并没有添加，是否这个位置有阻挡或者已经被占用的判定，由于我们的玩法尚未定型，则将这个判定放到了渲染层，在最后的演示中，你可以看到如果两个图形有重叠部分，重叠部分的区域会变成红色。

    public INode PlaceShape(INode node,IShape shape) 
    {
        node.Shape = shape;

        //解析data
        var data = shape.Data;
        var rows = data.GetLength(1);
        var columns = data.GetLength(0);

        for (int y = 0; y < rows; y++)
        {
            for (int x = 0; x < columns; x++)
            {
                if (data[x, y] == 0)
                    continue;

                INode usedNode = GetNodeWithXY(node.x + x, node.y + y);
                usedNode.State = NodeState.CUBE;
            }
        }

        return node;
    }

演示

通过空格键可以在左下角创建出方块，wasd去移动，qe可以转换方向，再次空格键可以放下方块。

页面有9M大小，加载较慢。演示地址： https:px.vrast.cn/index.html

</iframe>
</html>