请参阅此链接：http://en.wikipedia.org/wiki/Hex_(board_game)
我正在制作 Hex 游戏，但我不知道要检查给定的游戏是否已结束。
那么给定游戏结束的伟大算法检查是什么？
在这里，结束意味着恰好一个人完全连接一条线。
问题：给定两个玩家的棋子位置，确定“是否有一条完整的线使游戏结束？”的好算法是什么？
问问题
2016 次
3 回答
5
您需要一个等价类数据结构，有时称为“联合查找”结构：http ://en.wikipedia.org/wiki/Disjoint-set_data_structure
当每块石头被放置时，它被赋予一个新的等价类。然后，合并该石头的等价类及其所有相同颜色的邻居。在棋盘的每个边缘都有每种颜色的“虚拟石头”。当相同颜色的对立边石属于相同等价等级时，则建立连接，游戏结束。
希望这可以帮助。
于 2013-06-27T05:39:58.787 回答
2
每一块都有它连接的一侧（或没有一侧），并且是所有连接的小循环的一部分。放置一块时，它会检查是否有任何相邻的块连接到边，然后链接所有相邻的块循环并在必要时调整它们的“边”。如果它看到两个方面，游戏就结束了。
这与 go 中用于确定是否捕获组的算法非常相似。
于 2013-06-27T01:49:45.583 回答
0
我认为 A* 是适合你的算法，
虽然它太直接了，计算机会玩得很无聊。
你可以看看A* Tutorial
或者玩一个实现
于 2013-06-27T09:35:54.820 回答