JavaScript的棋盘游戏:寻找优化

我之前发布了这个问题在stackoverflow但没有收到答案,所以我决定在这里发布,看看有人可以建议我的东西。

我正在为Android的HTML / JavaScript游戏工作。 这是一个棋盘游戏,它执行以下操作。 它具有不同颜色的瓷砖,用户可以在电路板上放置一块瓷砖(以编程方式select)。 如果我们得到4个或更多相同的颜色/形状的瓷砖,我们得分点,这些瓷砖将消失。 被移除的瓷砖上方的瓷砖将replace它们,新的瓷砖将被添加到空的地方。 下面的图片显示了它是如何工作的(这只是一个例子,真正的电路板可以有不同的尺寸)

在这里输入图像描述

瓷砖是<img>元素与他们的ids存储在一个数组中,我用它来检查匹配和replace。

这一切都工作得很好,但一旦新的瓷砖添加到董事会,我需要检查整个董事会,以检查是否有新的匹配可用。 我想在这里提供一些建议,因为检查整个董事会可能会很慢。 有没有办法可以有效地做到这一点? 以下是我想要做的事情: 在这里输入图像描述

考虑到前面的例子,我想只考察红色区域的元素,也就是只有被移动或添加的元素。 它可以是有效的,如果瓷砖垂直移动,因为我只需要检查移动/添加瓷砖,它会给我新的比赛。 但是如果我把水平方向的水平方向去掉的话,这可能会造成问题,因为如果这些水平方向的水平在底部,我将不得不检查整个水泥板,我也面临同样的问题。

任何意见或建议将不胜感激。

注意:我没有添加任何代码,因为它只是检查给定拼贴的行和列并查找匹配。 但如果需要,我可以提供。

编辑:添加horizontalMatchCheck函数,为给定的索引检查水平匹配。 垂直检查是一样的。

 function horizontalMatchCheck(itemId) { hArray = new Array(); if (rightMatch(itemId)) { var index = itemId + 1; hArray.push(itemId + 1); while (rightMatch(index)) { hArray.push(index + 1); index++; } } if (leftMatch(itemId)) { var index = itemId - 1; hArray.push(itemId - 1); while (leftMatch(index)) { hArray.push(index - 1); index--; } } //if >=4 matches found I replace the indexes with 5 (because no other tile can have this id) which'll then be removed and shifted. if (hArray.length >= 3) { hArray.push(itemId); for (var i = 0; i < hArray.length; i++) { board[hArray[i]] = items.length; } } else hArray = new Array(); } function rightMatch(pos) return (!isRight(pos) && board[(pos+1)] == current) ? 1 : 0 ; function leftMatch(pos) return (!isLeft(pos) && board[(pos-1)] == current) ? 1 : 0 ; 

我承认,我现在还不完全明白你的algorithm是用来寻找匹配的,但是我可以告诉你,有一个简单的O(n)方法可以让你通过棋盘上的棋子所有你想要检查的是直线。 如果您希望这些匹配包含所有相同颜色或形状的触摸形状,则这不是您正在查找的内容,只会检查出现在一条直线上的那些形状。

假设你的board是二维数组,其中每个形状都有一个颜色,形状和属性“isInRun”,它是:

 var shapeRun = []; var colorRun = []; for (var i = 0; i < boardX; i++) { for (var j = 0; j < boardY; j++) { var cell = board[i][j]; if (i == 0 && j == 0) { var currentShape = cell.shape; var currentColor = cell.color; shapeRun.push(cell); colorRun.push(cell); } else { if (j > 0 && cell.shape == currentShape) { shapeRun.push(cell); } else { if (shapeRun.length >= runLength) { for (var k = 0; k < shapeRun.length; k++) { shapeRun[k].isInRun = true; } } currentShape = cell.shape; shapeRun = [cell]; } if (j > 0 && cell.color == currentColor) { colorRun.push(cell); } else { if (colorRun.length >= runLength) { for (var k = 0; k < colorRun.length; k++) { colorRun[k].isInRun = true; } } currentColor = cell.color; colorRun = [cell]; } } } } 

这将扫描每行的运行长度超过runLength形状,并通过将isInRun设置为true将它们标记为属于一组匹配。 再次这样做,但切换

 var cell = board[i][j]; 

 var cell = board[j][i]; 

检查另一个方向。

查看这个JSFiddle的例子(只在Chrome中testing过)。 这样每5秒就会创建一个随机的棋盘,三种形状和三种颜色,然后突出显示所有匹配的4个或更多。 您可以使用javascript顶部的参数来改变棋盘的尺寸或颜色和形状的数量。

我已经在我的手机(Galaxy Nexus)上运行了这个function,而且我必须将其尺寸提高到50×50,以便衡量所需的时间。

它看起来像你正在使用DOM作为通用数据结构。 我不会推荐这种方法。

你应该将游戏状态和渲染分离成彼此独立的逻辑块。 不要将DOM用作数据存储,也不要将引用存储到“游戏状态”数据中。

话虽如此,我还建议您考虑使用canvas而不是DOM元素。 但这是一个实现细节,可能与您的问题无关。

如果你有一个简单的2d JS数组,使用原始types(整数是好的)作为元素,即使是大网格,查找也不会很慢。

综上所述:

  • 将你的开发板作为二维数组(array-of-arrays)存储。 原始types(整数)是最好的,但对象也可以。
  • 不要将DOM引用保存在游戏状态中(如果您select使用DOM元素来渲染切片,请在每次需要时查看它们)

这不是codereview.stackexchange.com,但…

hArray没有明显的理由存在。 你可以使用两个局部variables,一个下界和一个上界,这两个variables都被初始化为itemId (它肯定应该被称为itemIndex ?),并用简化版本的循环向不同的方向展开。

OTOH这个方法本身看起来有点可疑。 对整行进行一次扫描肯定比每个单元的填充速度快。

如果你真的想要速度高于一切,我相信JavaScript的正则expression式支持是相当不错的…