自定义俄罗斯方块放置算法
Custom tetris block placement algorithm
嗯，这不完全是一个普遍的问题，但这毕竟是我们来这里的原因。
一些背景知识
我的任务是创建一个类似俄罗斯方块的模拟游戏，让 AI 来玩。完成后线条不会消失。最终结果应该是一个由整齐排列的块填充的矩阵，几乎没有或没有间隙。
我选择做的是一种遗传方法，具有恒定的权重和评估方法。 AI 会尝试将块放置在所有可能的位置、旋转、评估临时矩阵，并选择最好的一个。
问题
在俄罗斯方块中，即使方块在地上，您也可以向左或向右移动。这允许解决许多原本不可能的职位。然而，真正的问题是，这些孔甚至可能出现在半空中，如下所示：
falling J shape, with optimal choice occurring mid-air
我在这里看到的唯一解决方案是尝试所有位置、旋转和空中移动的所有可能组合，我认为这不是正式说的“最佳解决方案”。
我的问题
是否有人有想法或其他方法，以实际计算能力找到这些放置的可能性
一块棋子在一块棋盘上最多可以放置10x20x4 = 800个位置。这些将是您图表的节点。在一次移动中可以从一个节点移动到另一个节点的地方，就有一条边。然后，您可以修剪非法节点（例如，与板上现有障碍重叠）。您还可以将节点标记为 "final" - 在那里，瓦片的至少一部分正下方有一个障碍物（但它们仍然可以有连接到它们的节点）。
然后您可以检查哪些最终节点可以从初始节点到达，这是一个标准问题。
您可以通过忽略棋子高于棋盘当前高度的节点来进一步优化。
示例代码：
import copy
import time
from os import system, name
from random import randint
from wrapt import synchronized
from asciimatics.screen import Screen
import asciimatics
from asciimatics.effects import Cycle, Stars
from asciimatics.renderers import FigletText
from asciimatics.scene import Scene
from asciimatics.screen import Screen
class Tile:
shapes = \
[
[
[0, 0, 2],
[2, 2, 2]
],
[
[3, 3, 0],
[0, 3, 3]
],
[
[0, 4, 4],
[4, 4, 0]
],
[
[5, 0, 0],
[5, 5, 5]
],
[
[6, 6],
[6, 6]
],
[
[0, 0, 0, 0],
[7, 7, 7, 7],
[0, 0, 0, 0]
],
[
[0, 8, 0],
[8, 8, 8]
]
]
def __init__(self, id=-1):
if id >= 0:
self.id = id
else:
self.id = randint(0, len(self.shapes)-1)
self.shape = self.shapes[id]
x = 8
y = 0
id = 0
def rotate(self):
self.shape = list(zip(*self.shape[::-1]))
class Model:
_height = 25
_width = 20
_score = 0
def __init__(self):
self._view = None
self._field = [[0] * self._width for i in range(self._height)]
for i in range(5):
for j in range(self._height):
self._field[j][i] = 1
self._field[j][-i-1] = 1
for i in range(5):
for j in range(self._width):
self._field[-i-1][j] = 1
self._tile = Tile()
self._nexttile = Tile()
def set_view(self, view):
self._view = view
def get_height(self):
i = 0
for r in self._field[:-5]:
full_line = True
if sum(r[5:-5]) > 0:
return i
i += 1
return i
def _merge(self, field, tile):
field_copy = copy.deepcopy(field)
for i in range(len(tile.shape)):
for j in range(len(tile.shape[0])):
field_copy[tile.y + i][tile.x + j] += tile.shape[i][j]
return field_copy
@synchronized
def _is_valid(self, field, tile):
for i in range(len(tile.shape)):
for j in range(len(tile.shape[0])):
if tile.shape[i][j] > 0:
if (field[tile.y + i][tile.x + j] > 0):
return False
return True
def get_board(self):
return self._merge(self._field, self._tile)
def rotate(self):
self._tile.rotate()
if not self._is_valid(self._field, self._tile):
self._tile.rotate()
self._tile.rotate()
self._tile.rotate()
if self._view is not None:
self._view.show()
def _which_lines_completed(self):
lines = []
i = 0
for r in self._field[:-5]:
full_line = True
for c in r:
if c == 0:
full_line = False
if full_line:
lines.append(i)
i += 1
return lines
def _remove_lines(self, lines):
for l in lines:
for i in list(range(1, l+1))[::-1]:
self._field[i] = self._field[i-1].copy()
if len(lines) == 4:
self._score += 5000
elif len(lines) == 3:
self._score += 1000
elif len(lines) == 2:
self._score += 500
elif len(lines) == 1:
self._score += 100
@synchronized
def move_down(self):
self._tile.y += 1
if not self._is_valid(self._field, self._tile):
self._tile.y -= 1
self._field = self._merge(self._field, self._tile)
self._tile = self._nexttile
self._nexttile = Tile()
# Check if any lines need to be removed
lines = self._which_lines_completed()
# If lines need to be removed, notify the view
if len(lines) > 0:
self._view.remove_lines(lines)
# Remove the lines
self._remove_lines(lines)
if self._view is not None:
self._view.show()
@synchronized
def move_left(self):
self._tile.x -= 1
if not self._is_valid(self._field, self._tile):
self._tile.x += 1
else:
if self._view is not None:
self._view.show()
@synchronized
def move_right(self):
self._tile.x += 1
if not self._is_valid(self._field, self._tile):
self._tile.x -= 1
if self._view is not None:
self._view.show()
class AsciimaticView:
def __init__(self, model):
self.screen = Screen.open()
self.model = model
def _show_board(self, board):
#self.screen.clear()
b = board
x = 0
y = 0
for r in b[:-4]:
x = 0
for c in r[4:-4]:
if c == 1:
self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
elif c == 2:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 3:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 4:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 5:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 6:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
elif c == 7:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
elif c == 8:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)
else:
self.screen.print_at(u' ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
x += 2
y += 1
self.screen.print_at(u' ', 0, y, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+1, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+2, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+3, Screen.COLOUR_RED, Screen.A_BOLD)
for i in range(len(self.model._nexttile.shape)):
x = 0
if (i == 1):
self.screen.print_at(u'Next: ', x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
x = x + 6
for j in range(len(self.model._nexttile.shape[0])):
c = self.model._nexttile.shape[i][j]
if c == 1:
self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
elif c == 2:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 3:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 4:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 5:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 6:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
elif c == 7:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
elif c == 8:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)
else:
self.screen.print_at(u' ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
x = x + 2
y = y + 1
x = 0
y = 24
self.screen.print_at(u'Score: ' + str(self.model._score), x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
self.screen.refresh()
def show(self):
self._show_board(self.model.get_board())
def remove_lines(self, lines):
b = self.model.get_board()
for i in range(5):
for l in lines:
b[l][5:-5] = [1-el for el in b[l][5:-5]]
self._show_board(b)
time.sleep(0.1)
class Node:
x = 0
y = 0
rot = 0
final = False
edges = []
def __eq__(self, other):
"""Overrides the default implementation"""
if isinstance(other, Node):
return (self.x == other.x) and (self.y == other.y) and (self.rot == other.rot)
return False
def is_neighbour(self, other):
if (abs(self.x - other.x) + abs(self.y - other.y) + abs(self.rot - other.rot) == 1) and (other.y >= self.y):
return True
return False
def __hash__(self):
return hash((self.x, self.y, self.rot))
def get_possible_moves(model, tile):
start_node = Node()
start_node.x = model._tile.x
start_node.y = model.get_height() - len(tile.shape)-1
frontier = [start_node]
visited = {start_node: True}
final_nodes = []
while len(frontier) > 0:
n = frontier.pop()
for dx, dy, rot in [(-1, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)][::-1]:
nn = Node()
nn.x = n.x + dx
nn.y = n.y + dy
nn.rot = (n.rot + rot) % 4
if nn not in visited:
visited[nn] = True
t = Tile(tile.id)
t.x = nn.x
t.y = nn.y
for r in range(nn.rot):
t.rotate()
if model._is_valid(model._field, t):
frontier.append(nn)
# check if node is final
for i in range(len(t.shape)):
for j in range(len(t.shape[0])):
if (t.shape[i][j] > 0) and (model._field[nn.y + i + 1][nn.x + j] > 0):
nn.final = True
final_nodes.append(nn)
break
if (nn.final):
break
print(len(visited))
print(len(final_nodes))
return final_nodes
m = Model()
m._field = [
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
m._tile = Tile(3)
import threading
import keyboard
# define a thread which takes input
class InputThread(threading.Thread):
def run(self):
#self.daemon = True
self.last_user_input = None
while True:
try:
if keyboard.is_pressed('left'):#if key 'q' is pressed
self.last_user_input = 'a'
m.move_left()
elif keyboard.is_pressed('right'):#if key 'q' is pressed
self.last_user_input = 'a'
m.move_right()
elif keyboard.is_pressed('z'):
print('z')
self.last_user_input = 'z'
m.rotate()
elif keyboard.is_pressed('down'):
m.move_down()
elif keyboard.is_pressed('q'):
break
else:
pass
# do something based on the user input here
# alternatively, let main do something with
# self.last_user_input
except:
pass
time.sleep(0.1)
# main
#it = InputThread()
#it.start()
fn = get_possible_moves(m, m._tile)
time.sleep(2)
v = AsciimaticView(m)
m.set_view(v)
v.show()
time.sleep(2)
for n in fn:
m._tile = Tile(m._tile.id)
m._tile.x = n.x
m._tile.y = n.y
for r in range(n.rot):
m._tile.rotate()
v.show()
time.sleep(1)
time.sleep(500)
嗯，这不完全是一个普遍的问题，但这毕竟是我们来这里的原因。
一些背景知识
我的任务是创建一个类似俄罗斯方块的模拟游戏，让 AI 来玩。完成后线条不会消失。最终结果应该是一个由整齐排列的块填充的矩阵，几乎没有或没有间隙。
我选择做的是一种遗传方法，具有恒定的权重和评估方法。 AI 会尝试将块放置在所有可能的位置、旋转、评估临时矩阵，并选择最好的一个。
问题
在俄罗斯方块中，即使方块在地上，您也可以向左或向右移动。这允许解决许多原本不可能的职位。然而，真正的问题是，这些孔甚至可能出现在半空中，如下所示：
falling J shape, with optimal choice occurring mid-air
我在这里看到的唯一解决方案是尝试所有位置、旋转和空中移动的所有可能组合，我认为这不是正式说的“最佳解决方案”。
我的问题
是否有人有想法或其他方法，以实际计算能力找到这些放置的可能性
一块棋子在一块棋盘上最多可以放置10x20x4 = 800个位置。这些将是您图表的节点。在一次移动中可以从一个节点移动到另一个节点的地方，就有一条边。然后，您可以修剪非法节点（例如，与板上现有障碍重叠）。您还可以将节点标记为 "final" - 在那里，瓦片的至少一部分正下方有一个障碍物（但它们仍然可以有连接到它们的节点）。
然后您可以检查哪些最终节点可以从初始节点到达，这是一个标准问题。
您可以通过忽略棋子高于棋盘当前高度的节点来进一步优化。
示例代码：
import copy
import time
from os import system, name
from random import randint
from wrapt import synchronized
from asciimatics.screen import Screen
import asciimatics
from asciimatics.effects import Cycle, Stars
from asciimatics.renderers import FigletText
from asciimatics.scene import Scene
from asciimatics.screen import Screen
class Tile:
shapes = \
[
[
[0, 0, 2],
[2, 2, 2]
],
[
[3, 3, 0],
[0, 3, 3]
],
[
[0, 4, 4],
[4, 4, 0]
],
[
[5, 0, 0],
[5, 5, 5]
],
[
[6, 6],
[6, 6]
],
[
[0, 0, 0, 0],
[7, 7, 7, 7],
[0, 0, 0, 0]
],
[
[0, 8, 0],
[8, 8, 8]
]
]
def __init__(self, id=-1):
if id >= 0:
self.id = id
else:
self.id = randint(0, len(self.shapes)-1)
self.shape = self.shapes[id]
x = 8
y = 0
id = 0
def rotate(self):
self.shape = list(zip(*self.shape[::-1]))
class Model:
_height = 25
_width = 20
_score = 0
def __init__(self):
self._view = None
self._field = [[0] * self._width for i in range(self._height)]
for i in range(5):
for j in range(self._height):
self._field[j][i] = 1
self._field[j][-i-1] = 1
for i in range(5):
for j in range(self._width):
self._field[-i-1][j] = 1
self._tile = Tile()
self._nexttile = Tile()
def set_view(self, view):
self._view = view
def get_height(self):
i = 0
for r in self._field[:-5]:
full_line = True
if sum(r[5:-5]) > 0:
return i
i += 1
return i
def _merge(self, field, tile):
field_copy = copy.deepcopy(field)
for i in range(len(tile.shape)):
for j in range(len(tile.shape[0])):
field_copy[tile.y + i][tile.x + j] += tile.shape[i][j]
return field_copy
@synchronized
def _is_valid(self, field, tile):
for i in range(len(tile.shape)):
for j in range(len(tile.shape[0])):
if tile.shape[i][j] > 0:
if (field[tile.y + i][tile.x + j] > 0):
return False
return True
def get_board(self):
return self._merge(self._field, self._tile)
def rotate(self):
self._tile.rotate()
if not self._is_valid(self._field, self._tile):
self._tile.rotate()
self._tile.rotate()
self._tile.rotate()
if self._view is not None:
self._view.show()
def _which_lines_completed(self):
lines = []
i = 0
for r in self._field[:-5]:
full_line = True
for c in r:
if c == 0:
full_line = False
if full_line:
lines.append(i)
i += 1
return lines
def _remove_lines(self, lines):
for l in lines:
for i in list(range(1, l+1))[::-1]:
self._field[i] = self._field[i-1].copy()
if len(lines) == 4:
self._score += 5000
elif len(lines) == 3:
self._score += 1000
elif len(lines) == 2:
self._score += 500
elif len(lines) == 1:
self._score += 100
@synchronized
def move_down(self):
self._tile.y += 1
if not self._is_valid(self._field, self._tile):
self._tile.y -= 1
self._field = self._merge(self._field, self._tile)
self._tile = self._nexttile
self._nexttile = Tile()
# Check if any lines need to be removed
lines = self._which_lines_completed()
# If lines need to be removed, notify the view
if len(lines) > 0:
self._view.remove_lines(lines)
# Remove the lines
self._remove_lines(lines)
if self._view is not None:
self._view.show()
@synchronized
def move_left(self):
self._tile.x -= 1
if not self._is_valid(self._field, self._tile):
self._tile.x += 1
else:
if self._view is not None:
self._view.show()
@synchronized
def move_right(self):
self._tile.x += 1
if not self._is_valid(self._field, self._tile):
self._tile.x -= 1
if self._view is not None:
self._view.show()
class AsciimaticView:
def __init__(self, model):
self.screen = Screen.open()
self.model = model
def _show_board(self, board):
#self.screen.clear()
b = board
x = 0
y = 0
for r in b[:-4]:
x = 0
for c in r[4:-4]:
if c == 1:
self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
elif c == 2:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 3:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 4:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 5:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 6:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
elif c == 7:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
elif c == 8:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)
else:
self.screen.print_at(u' ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
x += 2
y += 1
self.screen.print_at(u' ', 0, y, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+1, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+2, Screen.COLOUR_RED, Screen.A_BOLD)
self.screen.print_at(u' ', 0, y+3, Screen.COLOUR_RED, Screen.A_BOLD)
for i in range(len(self.model._nexttile.shape)):
x = 0
if (i == 1):
self.screen.print_at(u'Next: ', x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
x = x + 6
for j in range(len(self.model._nexttile.shape[0])):
c = self.model._nexttile.shape[i][j]
if c == 1:
self.screen.print_at(u'██', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
elif c == 2:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 3:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 4:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_GREEN, Screen.A_BOLD)
elif c == 5:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_RED, Screen.A_BOLD)
elif c == 6:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_CYAN, Screen.A_BOLD)
elif c == 7:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_YELLOW, Screen.A_BOLD)
elif c == 8:
self.screen.print_at(u'[]', x, y, Screen.COLOUR_MAGENTA, Screen.A_BOLD)
else:
self.screen.print_at(u' ', x, y, Screen.COLOUR_BLUE, Screen.A_BOLD)
x = x + 2
y = y + 1
x = 0
y = 24
self.screen.print_at(u'Score: ' + str(self.model._score), x, y, Screen.COLOUR_WHITE, Screen.A_BOLD)
self.screen.refresh()
def show(self):
self._show_board(self.model.get_board())
def remove_lines(self, lines):
b = self.model.get_board()
for i in range(5):
for l in lines:
b[l][5:-5] = [1-el for el in b[l][5:-5]]
self._show_board(b)
time.sleep(0.1)
class Node:
x = 0
y = 0
rot = 0
final = False
edges = []
def __eq__(self, other):
"""Overrides the default implementation"""
if isinstance(other, Node):
return (self.x == other.x) and (self.y == other.y) and (self.rot == other.rot)
return False
def is_neighbour(self, other):
if (abs(self.x - other.x) + abs(self.y - other.y) + abs(self.rot - other.rot) == 1) and (other.y >= self.y):
return True
return False
def __hash__(self):
return hash((self.x, self.y, self.rot))
def get_possible_moves(model, tile):
start_node = Node()
start_node.x = model._tile.x
start_node.y = model.get_height() - len(tile.shape)-1
frontier = [start_node]
visited = {start_node: True}
final_nodes = []
while len(frontier) > 0:
n = frontier.pop()
for dx, dy, rot in [(-1, 0, 0), (1, 0, 0), (0, 1, 0), (0, 0, 1)][::-1]:
nn = Node()
nn.x = n.x + dx
nn.y = n.y + dy
nn.rot = (n.rot + rot) % 4
if nn not in visited:
visited[nn] = True
t = Tile(tile.id)
t.x = nn.x
t.y = nn.y
for r in range(nn.rot):
t.rotate()
if model._is_valid(model._field, t):
frontier.append(nn)
# check if node is final
for i in range(len(t.shape)):
for j in range(len(t.shape[0])):
if (t.shape[i][j] > 0) and (model._field[nn.y + i + 1][nn.x + j] > 0):
nn.final = True
final_nodes.append(nn)
break
if (nn.final):
break
print(len(visited))
print(len(final_nodes))
return final_nodes
m = Model()
m._field = [
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 0, 3, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 0, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 0, 0, 0, 3, 3, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
m._tile = Tile(3)
import threading
import keyboard
# define a thread which takes input
class InputThread(threading.Thread):
def run(self):
#self.daemon = True
self.last_user_input = None
while True:
try:
if keyboard.is_pressed('left'):#if key 'q' is pressed
self.last_user_input = 'a'
m.move_left()
elif keyboard.is_pressed('right'):#if key 'q' is pressed
self.last_user_input = 'a'
m.move_right()
elif keyboard.is_pressed('z'):
print('z')
self.last_user_input = 'z'
m.rotate()
elif keyboard.is_pressed('down'):
m.move_down()
elif keyboard.is_pressed('q'):
break
else:
pass
# do something based on the user input here
# alternatively, let main do something with
# self.last_user_input
except:
pass
time.sleep(0.1)
# main
#it = InputThread()
#it.start()
fn = get_possible_moves(m, m._tile)
time.sleep(2)
v = AsciimaticView(m)
m.set_view(v)
v.show()
time.sleep(2)
for n in fn:
m._tile = Tile(m._tile.id)
m._tile.x = n.x
m._tile.y = n.y
for r in range(n.rot):
m._tile.rotate()
v.show()
time.sleep(1)
time.sleep(500)