![algorithm running](https://istack.dev59.com/0kPf9.webp)
我认为一段视频胜过千言万语的图片。
算法演示。
在这个视频中,你可以看到这个算法如何找到周围的正方形,不幸的是,我没有展示整个过程,只展示了好的匹配情况,但我认为你会发现它很有趣,而且你可以通过观察好的匹配情况来注意到整个过程。
你可以使用Processing 3自己运行视频示例,我将整个代码放在
此Gist中。
最相关的代码(用Python编写)如下:
def checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
return areaX1 < 0 or areaY1 < 0 or areaX2 >= gridSize or areaY2 >= gridSize
def isAreaCompatible(type, oldAreaX1, oldAreaY1, oldAreaX2, oldAreaY2, areaX1, areaY1, areaX2, areaY2):
global grid
for y in range(areaY1, areaY2+1):
for x in range(areaX1, areaX2+1):
print "checking point (%s,%s) old area is (%s,%s) (%s,%s) new area is (%s,%s) (%s,%s)" % (x,y,oldAreaX1, oldAreaY1, oldAreaX2, oldAreaY2, areaX1,areaY1,areaX2,areaY2)
if x >= oldAreaX1 and x <= oldAreaX2 and y >= oldAreaY1 and y <= oldAreaY2:
print "This area belongs to previous area, won't check"
else:
if grid[y][x].type != type: print "false"; print "This area have a different color/type so it's not compatible"; return False;
return True;
def explore(type, x1, y1, x2, y2):
print "----- Right and bottom ------"
areaX1 = x1;
areaY1 = y1;
areaX2 = x2+1;
areaY2 = y2+1;
if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
addAnim(areaX1, areaY1, areaX2, areaY2);
addMatch(areaX1, areaY1, areaX2, areaY2);
explore(type, areaX1, areaY1, areaX2, areaY2);
print "----- Bottom and left ------"
areaX1 = x1-1;
areaY1 = y1;
areaX2 = x2;
areaY2 = y2+1;
if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
addAnim(areaX1, areaY1, areaX2, areaY2);
addMatch(areaX1, areaY1, areaX2, areaY2);
explore(type, areaX1, areaY1, areaX2, areaY2);
print "----- Left and top ------"
areaX1 = x1-1;
areaY1 = y1-1;
areaX2 = x2;
areaY2 = y2;
if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
addAnim(areaX1, areaY1, areaX2, areaY2);
addMatch(areaX1, areaY1, areaX2, areaY2);
explore(type, areaX1, areaY1, areaX2, areaY2);
print "----- Top and right ------"
areaX1 = x1;
areaY1 = y1-1;
areaX2 = x2+1;
areaY2 = y2;
if not checkOutBoundaries(areaX1, areaY1, areaX2, areaY2):
if isAreaCompatible(type, x1, y1, x2, y2, areaX1, areaY1, areaX2, areaY2):
addAnim(areaX1, areaY1, areaX2, areaY2);
addMatch(areaX1, areaY1, areaX2, areaY2);
explore(type, areaX1, areaY1, areaX2, areaY2);