迷宫墙上的按位逻辑

Question

我有一个枚举，代表迷宫中某个单元格的当前状态，如下所示：

[Flags]
public enum CellInfo : ushort
{
    None = 0,
    NorthWall = 1,
    EastWall = 2,
    SouthWall = 4,
    WestWall = 8,
    AllWalls = NorthWall | EastWall | SouthWall | WestWall
}

有了它，我可以很容易地跟踪每个单元格墙的当前状态，例如，如果我想打开一堵东边的墙。

var myCell = CellInfo.AllWalls; // initialise a cell with all walls up
myCell ^= CellInfo.EastWall; // east wall now down!

简单！但是，每个单元格都紧挨着另一个单元格，后者有自己的墙，所以实际上我一直都知道我正在从单元格 a 移动到单元格 b，为了争论起见，让我们说这是向东的移动，我需要拆除 a 的东墙和 b 的 west 墙：

var a = CellInfo.AllWalls;
var b = CellInfo.AllWalls;
// assume a->b is eastwards
a ^= CellInfo.EastWall;
b ^= CellInfo.WestWall;

现在，我有一种处理此运动的通用方法，但我不喜欢它，它有代码味！ if 语句太多，我想知道我是否遗漏了一些明显的东西 - 一些我可能没有发现的按位逻辑？我在下面粘贴了我的 KnockDownWall 方法，它采用单元格网格 (CellInfo[,]) 以及 a 和 [=15] 的网格 position =]表示为Tuple<int,int>（x,y位置）

protected static void KnockDownWall(CellInfo[,] cells, Tuple<int, int> target, Tuple<int, int> neighbour)
{
    var offsetTarget = Tuple.Create(neighbour.Item1 - target.Item1, neighbour.Item2 - target.Item2);
    if(offsetTarget.Item1 == 0)
    {
        if(offsetTarget.Item2 == -1)
        {
            cells[target.Item1, target.Item2] ^= CellInfo.NorthWall;
            cells[neighbour.Item1, neighbour.Item2] ^= CellInfo.SouthWall;
        }
        else
        {
            cells[target.Item1, target.Item2] ^= CellInfo.SouthWall;
            cells[neighbour.Item1, neighbour.Item2] ^= CellInfo.NorthWall;
        }
    }
    else
    {
        if (offsetTarget.Item1 == -1)
        {
            cells[target.Item1, target.Item2] ^= CellInfo.WestWall;
            cells[neighbour.Item1, neighbour.Item2] ^= CellInfo.EastWall;
        }
        else
        {
            cells[target.Item1, target.Item2] ^= CellInfo.EastWall;
            cells[neighbour.Item1, neighbour.Item2] ^= CellInfo.WestWall;
        }
    }
}

更新

到目前为止，有很多有用的信息可以回答 - 但是我担心我一开始就把问题简单化了。 CellInfo 有更多的值存储诸如 N/S/E/W 边界（允许我自由塑造迷宫和围栏区域），N/S/E/W 解决方案和回溯信息 - 这些都输入到模型中绘制迷宫。将一切都视为细胞而不是墙壁有一些好处。

Answer 1

您对迷宫进行建模的方法存在的问题是每个内壁都被表示两次，需要付出大量努力才能保持内部一致性。更好的方法是通过在南侧额外增加一排并在东侧增加一列来扩展迷宫，并使用两种墙类型而不是四种 - 即单元格北侧的墙和单元东侧的墙:

这张图片显示了一个 2 行 3 列的网格，扩展为 3 行 4 列。红线表示要拆除的墙。

为了处理来自特定单元格的所有四个方向的墙壁，制定一种将南墙和西墙识别为相邻单元格的北墙和东墙的方法。

最后，您可以制作两个 bool 的二维数组 - 一个代表水平墙，一个代表垂直墙。这样各个单元格就根本不需要存储自己的墙，迷宫将始终保持内部一致：

private const int rows = 10;
private const int cols = 15;
private bool northWalls[,] = new bool[rows+1, cols+1];
private bool westWalls[,] = new bool[rows+1, cols+1];
public bool HasWall(int cellRow, int cellCol, CellInfo dir) {
    switch(dir) {
        case CellInfo.NorthWall:
            return northWalls[cellRow,cellCol];
        case CellInfo.WestWall:
            return westWalls[cellRow,cellCol];
        case CellInfo.EasthWall:
            return westWalls[cellRow,cellCol+1];
        case CellInfo.SouthhWall:
            return northWalls[cellRow+1,cellCol];
    }
}

如果您必须使用当前设计，但想摆脱 KnockDownWall 中的条件，您可以从您的实现中创建两个值为 CellInfo.XyzWall 的 3×3 数组，并用 offsetTarget.Item1+1, offsetTarget.Item2+1:

索引它们

protected static void KnockDownWall(CellInfo[,] cells, Tuple<int, int> target, Tuple<int, int> neighbour) {
    var offsetTarget = Tuple.Create(neighbour.Item1 - target.Item1, neighbour.Item2 - target.Item2);
    cells[target.Item1, target.Item2] ^= targetLookup[offsetTarget.Item1+1, offsetTarget.Item2+1];
    cells[neighbour.Item1, neighbour.Item2] ^= neighborLookup[offsetTarget.Item1+1, offsetTarget.Item2+1];
}

Answer 2

你的模型说每个单元格都有 4 面墙，都是单独的。但这并不准确，因为这些墙可能与其他细胞共享。您正在看到模型问题的痛点。此外，您的细胞没有任何关于它们的其他信息（根据您向我们展示的信息）：您实际上只有墙。而且他们只有一个属性：无论是起立还是倒下。

我建议你的模型应该基于墙壁，而不是单元格。

这是您的细胞和细胞壁的 ASCII 表示，正如我想象的那样。

 ─ ─ ─ ─ ─ ─  // wall row 0, walls 0-5
│ │ │ │ │ │ │ // wall row 1, walls 0-6; cell row 0, cells 0-5
 ─ ─ ─ ─ ─ ─  // wall row 2, walls 0-5
│ │ │ │ │ │ │ // wall row 3, walls 0-6; cell row 1, cells 0-5
 ─ ─ ─ ─ ─ ─  // wall row 4, walls 0-5

请注意，墙的数量在交替的行中是不同的。处理此问题的一种方法是使用锯齿状数组而不是多维数组。

bool[][] walls = // whatever

因此，要推倒第 1 行的最后一堵垂直墙，只需执行以下操作：

walls[1][6] = false;

或切换它：

walls[1][6] = !walls[1][6];

如果您需要计算 walls 中相对于单元格的索引（例如单元格 1,2 以东的墙），您可以创建一个简单的方法来执行此操作。

如果你有关于每个单元格和墙的属性要存储，你可以有这样的东西：

Wall[][] walls;
Cell[,] cells;

Wall 可能有一个 Active 或 Standing 属性可以切换。如果 Wall 和 Cell 对象知道它们的位置，您甚至可以拥有 Cell.Walls、Cell.NorthWall（等）或 Wall.Cells 属性周围的元素。

迷宫墙上的按位逻辑

Bitwise logic on maze walls

c#

bit-manipulation

maze