算法Trax获胜条件

Question

我试着用C++实现了游戏Trax。对于那些不知道的人：http://www.traxgame.com/about_rules.php

到目前为止，我已经建立了棋盘，并创建了规则，我可以在哪里放置我的下一个磁贴，以及我可以设置哪个磁贴。但现在，我正在与获胜的条件作斗争。如你所见，我需要至少8块瓷砖的线..

我的第一个解决方案尝试包含了许多如果条件的方法。这根本是不可能的。所以我需要实现一个合适的算法..

我的第二次尝试使用位板变得相当复杂，所以我的问题是，如果有更简单的方法，我只是目前还没有找到。

大家好，MC

Answer 1

我可以建议你使用递归。我可能会误解你的意思，但不管怎样：

bool isWin(int i, int j, int length) {
    if (length >= 8)
        return true;

    if (canMoveTo(i + 1, j)) {
        if (isWin(i + 1, j, length + 1))
            return true;
    }
    if (canMoveTo(i - 1, j)) {
        if (isWin(i - 1, j, length + 1))
            return true;
    }
    if (canMoveTo(i, j + 1)) {
        if (isWin(i, j + 1, length + 1))
            return true;
    }    
    if (canMoveTo(i, j - 1)) {
        if (isWin(i, j - 1, length + 1))
            return true;
    }      
    return false;
}

bool isWin(int i, int j) {
    int length = 0;
    isWin(i, j, length);
}

..

main() {
    for (int i = 0; i < HEIGHT; ++i) {
        for (int j = 0; j < WIDTH; ++j) {
            if (isTilePresent(i, j)) {
                if (isWin(i, j)) {
                    if (isRed(i, j))
                        std::cout << "Red is won!" << std::endl;
                    else
                        std::cout << "White is won!" << std::endl;
                }
            }
        }
    }
}

Answer 2

对于这类游戏，为了让事情变得简单，我会添加一个小的位图来表示瓦片

1. create切片地图

能够表示所有切片的最小分辨率，如此

我认为也可能是3x3的解决方案也是可行的。你需要4种颜色：

- Gray - wall
- Red - path plr1
- White - path plr2
- Magenta - path plr1,plr2

​

1. after each turn

从棋盘位图创建棋盘位图，并使用A*从最后编辑的棋盘开始(也可以是4个邻居)，并为每个球员/路径起点(黄色)创建do路径。当A*完成后，分析地图数据(橙色)，找到地图中最大的数字(绿色中点)。这是A*填充停止的地方(不需要搜索它)。然后重建返回起点的最短路径(棕色)，将使用过的地图点设置为不可用。然后尝试重新构建路径，如果可以，则闭环存在

​

1. while重建路径

计算使用的点的边界框，因此您将需要min,max x，y坐标x0,x1,y0,y1 (以平铺为单位)。从下面的if循环中你可以知道：

列= x1-x0+1行= y1-y0+1

因此，win条件就是来自此的单个if

希望这对我有所帮助，我在我的Carcassonne游戏中开发了这个闭环路径查找/计数技术