1

我正在开发一个名为“Pogo Painter”的小游戏，我需要一些数学解决方案。下面是一张图片（用 Paint 制作）来说明它的全部内容。

四名不同颜色的玩家必须占领方格才能获得积分。小游戏将与此类似：http ://www.youtube.com/watch?v=rKCQfAlaRrc ，但略有不同。玩家将被允许在操场上跑来跑去，并要求任何一个方格，当一个模式关闭时，就会收集点数。例如，在 A3 上声明蓝色方块将创建一个封闭的蓝色图案。

在此处输入图像描述

我应该声明什么样的变量以及如何检查模式是否关闭？

如果您有解决方案，请回答:)

4

2 回答 2

2

这是为您的问题建模的另一种（离散优化）方法。

符号

将您的网格视为具有 n^2 个节点和长度为 1 的边（边连接两个相邻节点）的“图”。让节点编号为 1:n^2。（为了便于表示，如果您愿意，可以使用双数组 (x,y) 来表示每个节点。）

决策变量

有 k 种颜色，每个玩家一种（1 到 4）。0 是无人认领的单元格（白色）

X_ik = 1 if player k has claimed node i.  0 otherwise.

开始

X_i0 = 1 for all nodes i.

所有节点都以白色 (0) 开始。

相邻集：如果两个节点 i 和 j 彼此相邻，则它们是“邻居”。（任何给定的节点我最多可以有 4 个邻居：上下左右。）

边变量： 我们现在可以定义一组新的边变量Y_ijk，这些变量将两个相邻节点（i 和 j）与一个共同的颜色 k 连接起来。

Y_ijk = 1 if neighboring nodes i and j are both of color k. 0 Otherwise.
(That is, X_ik = X_jk) for non-zero k.

我们现在有一个无向图。检查“闭合模式”与检测周期相同。

检测周期：

一个简单的 DFS搜索就可以了，因为我们有无向循环。从每个彩色节点 i 开始，并检查循环。如果路径将您带回访问的节点，则存在循环。您可以相应地奖励积分。

最后，在您设计游戏时提出一个建议。您可以根据您检测到的“最长周期”奖励积分。最短的循环得到 4 分，每条边得到 1 分（或循环中的每个节点得到 1 分），以最适合您的为准。

1 1
1 1    scores 4 points

1 1 1
1 1 1 scores 6 points

1 1 1
1 1 1
1 1    scores 8 points

希望有帮助。

于 2013-06-25T23:00:30.883 回答
0

好的，
这是很多文字，但很简单。

一个 N×N 方格将满足作为游戏板。

  • 每次玩家占领一个方格时，
    • 如果该方格未连接到该玩家的任何方格，则您必须为该方格指定一个唯一 ID。
    • 如果附上正方形，
      • 计算每个 ID 有多少个邻居。（请参阅我在下面放置的演示，以了解这意味着什么）
      • 对于每组
        • patterns_count += group_size - 1
      • 如果组数大于 1
        • 更改该组的 ID 以及与之相连的所有其他方格，以便它们都共享相同的 ID

您必须记住哪些 ID 属于哪些玩家。

这就是您在示例中所拥有的 

1 1 1 0 0 0 0 2 2
1 0 0 0 1 3 3 0 0
1 1 0 0 3 3 0 0 0
0 1 0 0 4 5 0 0 0
0 0 0 6 4 0 0 0 0
7 7 0 0 0 0 8 8 8 
0 7 7 0 9 8 8 0 8
A A 7 0 9 8 0 0 8
A 0 7 0 0 0 8 8 8

这就是蓝色抓住A-3之后的结果

1 1 1 0 0 0 0 2 2
1 0 0 0 1 3 3 0 0
1 1 0 0 3 3 0 0 0
0 1 0 0 4 5 0 0 0
0 0 0 6 4 0 0 0 0
7 7 0 0 0 0 8 8 8 
0 7 7 0 9 8 8 0 8
A A 7 0 9 8 0 0 8
A 0 7 0 0 8 8 8 8

更多使用中的算法示例

1 1 1 0
1 0 1 0 
1 1   0
0 0 0 0
  2 neighbours. 2x'1'
  1x closed pattern.
1 1 1 0 
1 0 1 0
1 1 1 0
0 0 0 0

--

1 1 1 0 0
1 0 1 0 0
1 1   0 0
1 0 1 0 0
1 1 1 0 0
  3 neighbours: 3x'1'
  2x closed patterns
1 1 1 0 0
1 0 1 0 0
1 1 1 0 0
1 0 1 0 0
1 1 1 0 0

--

1 1 1 0 0
1 0 1 0 0
1 1   2 2
0 0 2 0 2
0 0 2 2 2
  4 neighbours: 2x'1', 2x'2'
  2 Closed patterns
1 1 1 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
0 0 1 1 1

但我也认为这些是封闭的模式。你没有给出任何关于什么应该被认为是一个和什么不应该是的描述。

1 1 0
1 1 0
0 0 0

1 1 1
1 1 1
0 0 0

1 1 1
1 1 1
1 1
于 2013-06-25T16:04:19.860 回答