nes游戏“Quarth”的算法

问题描述 投票:1回答:1

在游戏“Quath”中,您填充块并使其成为矩形。块将被删除。

Normal Erase

Normal Erase

[
 [1,1,1,1,1],
 [1,0,0,0,0]
]
// when rectangle complete ⤵️
[
 [1,1,1,1,1],
 [1,1,1,1,1]
]

Chain Erase

Chain Erase

但是,如果连接两个块,当它们变成一个大矩形时,它们将一起擦除。

[
  [1,1,1,1],
  [1,0,0,1],
  [1,2,2,1],
  [0,0,2,0],
  [0,0,2,0]
]
//when rectangle complete,two block erase at same time
[
  [1,1,1,1],
  [1,0,0,1],
  [1,2,2,1],
  [1,2,2,1],
  [1,2,2,1]
]

在实际游戏中,块布局似乎更复杂。

我想知道如何判断地图中封闭的最大矩形是什么。

Youtube: A playing video for this game

algorithm puzzle nes
1个回答
0
投票

erase target image 我自己找到了这个问题的解决方案。 例如,使用上面的图片。 给每个块一个id,然后地图可以表示为下面的数组

[
  [a,a,a,a,a,b,b,b,0,0,0,0]
  [d,d,a,c,c,c,c,b,0,i,i,i]
  [d,0,0,0,0,0,0,b,h,h,h,i]
  [d,0,0,0,0,0,0,g,g,g,h,i]
  [d,0,0,0,0,f,f,f,f,g,h,0]
  [d,e,e,e,e,0,0,0,0,g,0,0]
]

尝试填补块“f”

[
  [a,a,a,a,a,b,b,b,0,0,0,0]
  [d,d,a,c,c,c,c,b,0,i,i,i]
  [d,0,0,0,0,0,0,b,h,h,h,i]
  [d,0,0,0,0,0,0,g,g,g,h,i]
  [d,0,0,0,0,f,f,f,f,g,h,0]
  [d,e,e,e,e,f,f,f,0,g,0,0]
]

将光标向4方向移动,如果找到0,则减小矩形高度或宽度 得到一个矩形下面,我称之为“绑定步行者”

[
  [a,a,a,a,a,b,b,b]
  [d,d,a,c,c,c,c,b]
  [d,0,0,0,0,0,0,b]
  [d,0,0,0,0,0,0,g]
  [d,0,0,0,0,f,f,f]
  [d,e,e,e,e,f,f,f]
]

但是“块i”的部分仍然在大矩形的外面 我们可以删除地图数组中的矩形区域, 并且发现是否有剩余的块部分

如果没有剩下的部分,我们可以删除大矩形

继续填充“块f”“绑定步行者”可以很容易地找到它成为一个填充矩形并擦除它

然后尝试填写“块g” 我们会得到一个像这样的矩形

[
    [b,h,h]
    [g,g,g]
    [g,g,g]
    [g,g,g]
]

矩形包括需要擦除的矩形 所以我们需要删除多余的部分,然后擦除正确的区域

判断步骤: 1.shoot块,块将成为块集的一部分 2.run“绑定步行者” 3.如果结果矩形只有一列或一行,则它不是一个有效的矩形(结束判断) 4.find是矩形中的额外部分 5.如果没有,擦除矩形(结束判断) 6.如果是,删除额外的部分,找到左边的矩形,再次运行绑定的步行者(结束判断)

我认为这不是解决这个问题的最佳方式。 它可能很慢,任何人都有一些想法?

© www.soinside.com 2019 - 2024. All rights reserved.