Well it's not entirely a generic problem, but that's why we're here after all.
A bit of background
My task is to create a tetris like simulation with an AI playing it. The lines do not disappear when they are completed. The end result should be a matrix filled with the neatly placed blocks, with very few or no gaps.
What I chose to do, was a genetic approach, with constant weights and methods for evaluation. The AI would try to place the blocks in all possible places, rotations, evaluate the temporary matrices, and go with the best one.
The problem
In tetris, you can move to the left or right even when the block is on the ground. This allows to solve many positions that would otherwise be impossible. The real problem however, that these holes can even occur mid-air, something like this:
falling J shape, with optimal choice occurring mid-air
The only solution I see here, would be trying all positions, rotations, and all possible combinations of mid-air moves, which I assume is "not an optimal solution" to say it formally.
My question
Is if someone has an idea or another approach, to find these possibilities for placement with realistic amounts of computing power
A single piece can be positioned in a maximum of 10x20x4 = 800 positions on a single board. These will be the nodes of your graph. Where you can move from one node to another in a single move, there is an edge. You can then prune nodes that are illegal (e.g. overlap with existing obstacles on the board). You can also mark nodes as "final" - there, the tile has an obstacle directly under at least one part of it (but they can still have nodes connected to them).
You can then check which final nodes are reachable from the initial node, which is a standard problem.
You could optimize this further by ignoring nodes where the piece is above the current height of the board.
Example code:
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)