一尘不染

连续四逻辑

algorithm

我目前正在为自己开发一款基本的连续四人游戏,但我相当乐于坚持其背后的逻辑。

目前,我有代表董事会的多维数组

[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0]
]

0将是一个空的插槽,而12代表的球员。因此,让我们说一段时间后,您会得到以下数组:

[
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 0, 0],
    [0, 0, 0, 1, 1, 0, 0],
    [0, 0, 1, 2, 2, 2, 0],
    [0, 1, 2, 2, 1, 2, 0]
]

如何编写逻辑来检查是否连续有四个?对于水平和垂直方向的计算似乎很容易(尽管仍在寻找最佳方法),但是我该如何对角线呢?


阅读 198

收藏
2020-07-28

共1个答案

一尘不染

最好的选择是将搜索空间分为四个部分:

  • 垂直;
  • 水平
  • 右下
  • 对和向上。

然后根据方向限制您的开始和结束坐标。

例如,假设你的阵列是board[row=0-5][col=0-6]board[0][0]左上方。

第一垂直(环都包括在 这两个 在这个伪代码结束):

for row = 0 to 2:
    for col = 0 to 6:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col] and
           board[row][col] == board[row+2][col] and
           board[row][col] == board[row+3][col]:
               return board[row][col]

这将可能性限制为仅那些不延伸到板边缘之外的可能性,这是大多数解决方案在简单地开始检查每个单元并从那里向各个方向伸出时所遇到的问题。那样的话,我的意思是没有必要检查3的开始行,仅仅因为它会涉及3、4、5和6行(后者不存在)。

同样,对于水平:

for row = 0 to 5:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row][col+1] and
           board[row][col] == board[row][col+2] and
           board[row][col] == board[row][col+3]:
               return board[row][col]

对于右下,接着是右上:

for row = 0 to 2:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col+1] and
           board[row][col] == board[row+2][col+2] and
           board[row][col] == board[row+3][col+3]:
               return board[row][col]

for row = 3 to 5:
    for col = 0 to 3:
        if board[row][col] != 0 and
           board[row][col] == board[row-1][col+1] and
           board[row][col] == board[row-2][col+2] and
           board[row][col] == board[row-3][col+3]:
               return board[row][col]

现在,您实际上可以通过制作外循环并仅执行一次而不是两次来 组合 这两者,for col = 0 to 3但是我实际上更喜欢将它们分开(带有适当的注释),以便于理解。但是,如果您沉迷于性能,可以尝试:

for col = 0 to 3:
    for row = 0 to 2:
        if board[row][col] != 0 and
           board[row][col] == board[row+1][col+1] and
           board[row][col] == board[row+2][col+2] and
           board[row][col] == board[row+3][col+3]:
               return board[row][col]
    for row = 3 to 5:
        if board[row][col] != 0 and
           board[row][col] == board[row-1][col+1] and
           board[row][col] == board[row-2][col+2] and
           board[row][col] == board[row-3][col+3]:
               return board[row][col]

然后,如果在四个可能的方向上均未找到获胜者,则只需返回0而不是获胜者1或即可2

因此,例如,您的示例板:

row
 0   [0, 0, 0, 0, 0, 0, 0]
 1   [0, 0, 0, 0, 0, 0, 0]
 2   [0, 0, 0, 1, 1, 0, 0]
 3   [0, 0, 0, 1, 1, 0, 0]
 4   [0, 0, 1, 2, 2, 2, 0]
 5 > [0, 1, 2, 2, 1, 2, 0]
         ^
      0  1  2  3  4  5  6 <- col

将检测优胜者在右和上环,其中起始细胞是{5,1}因为{5,1}{4,2}{3,3}并且{2,4}都被设置为1

2020-07-28