Last active
November 20, 2020 09:01
-
-
Save nmay231/415538e6a1de4b75e8988087282b6772 to your computer and use it in GitHub Desktop.
Knights Tour Example
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python3 | |
""" | |
A puzzle game based on the Knight's Tour problem. | |
Requires Python 3.6+ and PyGame ($ pip3 install pygame) | |
Instructions: | |
* Left-click to move a knight's move away from the starting cell (highlighted blue) | |
* Right-click anywhere to undo | |
* Visit each of the gray cells the number of times the cell has in the center. (empty cells are visited once) | |
* When you solve it, close the window and restart it to generate a new puzzle. | |
* Change the random seed and grid size parameters after the import statements (line 28). | |
""" | |
from collections import defaultdict | |
from random import randint, shuffle, seed | |
from typing import DefaultDict, List, Tuple | |
try: | |
import pygame as pg | |
except ImportError: | |
print("Must have pygame installed") | |
exit() | |
# ========== PARAMETERS ============ | |
GRID_COUNT = (4, 4) # (ncols, nrows) | |
seed(6) | |
all_moves: List[Tuple[int, int]] = [ | |
(-1, -2), | |
(1, -2), | |
(2, -1), | |
(2, 1), | |
(1, 2), | |
(-1, 2), | |
(-2, 1), | |
(-2, -1), | |
] | |
def attempt_move(x: int, y: int, dx: int, dy: int, width: int, height: int): | |
x += dx | |
y += dy | |
if 0 <= x < width and 0 <= y < height: | |
return x, y, True | |
return x - dx, y - dy, False | |
def gen_puzzle(width: int, height: int): | |
""" | |
Generate a knight puzzle where you have to fill in the grid using only knights moves | |
""" | |
grid = [[0] * width for _ in range(height)] | |
x, y = startx, starty = randint(0, width - 1), randint(0, height - 1) | |
grid[y][x] = 1 | |
ms = all_moves[:] | |
max_steps = int(1.05 * width * height) | |
steps = 0 | |
moves = [(0, 0)] | |
while steps < max_steps: | |
shuffle(ms) | |
for move in ms: | |
if move[0] == -moves[-1][0] and move[1] == -moves[-1][1]: | |
continue | |
x, y, valid = attempt_move(x, y, *move, width, height) | |
if not valid: | |
continue | |
if grid[y][x] == -1: | |
x -= move[0] | |
y -= move[1] | |
continue | |
if grid[y][x] >= 0: | |
grid[y][x] += 1 | |
steps += 1 | |
moves.append(move) | |
break | |
else: | |
# Start backtracking (ran into a corner) | |
if grid[y][x] == 1: | |
grid[y][x] = -1 | |
else: | |
grid[y][x] -= 1 | |
move = moves.pop() | |
x -= move[0] | |
y -= move[1] | |
return (startx, starty), grid | |
def cell_rect(x, y): | |
return pg.Rect( | |
OFFSET[0] + x * CELL_SIZE + 2, | |
OFFSET[1] + y * CELL_SIZE + 2, | |
CELL_SIZE - 3, | |
CELL_SIZE - 3, | |
) | |
def coords2grid(x: int, y: int): | |
return ( | |
(x - OFFSET[0]) // CELL_SIZE, | |
(y - OFFSET[1]) // CELL_SIZE, | |
) | |
def tiny_font(surface: pg.Surface, x: int, y: int, text: str, color=pg.Color("black")): | |
text_render = _tiny_font.render(text, True, color) | |
rect = cell_rect(x, y) | |
surface.blit( | |
text_render, | |
( | |
rect.centerx - text_render.get_width() // 2, | |
rect.centery - text_render.get_height() // 2, | |
), | |
) | |
OverlayGroup = pg.sprite.Group() | |
class TransCell(pg.sprite.Sprite): | |
def __init__(self, x, y, color, a=128): | |
pg.sprite.Sprite.__init__(self, OverlayGroup) | |
self.rect = cell_rect(x, y) | |
self.image = pg.Surface(self.rect.size) | |
self.image.set_alpha(a) | |
self.image.fill(color) | |
pos, puzzle = gen_puzzle(*GRID_COUNT) | |
goal = -1 + sum(sum(row) for row in puzzle) | |
pg.init() | |
pg.display.init() | |
WIDTH = 1500 | |
HEIGHT = 900 | |
CELL_SIZE = 60 | |
GRID_SIZE = (GRID_COUNT[0] * CELL_SIZE, GRID_COUNT[1] * CELL_SIZE) | |
OFFSET = ((WIDTH - GRID_SIZE[0]) // 2, (HEIGHT - GRID_SIZE[1]) // 2) | |
screen = pg.display.set_mode((WIDTH, HEIGHT)) | |
background = pg.Surface((WIDTH, HEIGHT)) | |
# Used in tiny_font() | |
_tiny_font = pg.font.Font(None, 24) | |
# Draw background and grid | |
pg.draw.rect(background, pg.Color("white"), pg.Rect(0, 0, WIDTH, HEIGHT)) | |
pg.draw.rect(background, pg.Color("gray"), pg.Rect(OFFSET, GRID_SIZE)) | |
for x in range(GRID_COUNT[0] + 1): | |
x = OFFSET[0] + x * CELL_SIZE | |
pg.draw.line( | |
background, pg.Color("black"), (x, OFFSET[1]), (x, OFFSET[1] + GRID_SIZE[1]), 3 | |
) | |
for y in range(GRID_COUNT[1] + 1): | |
y = OFFSET[1] + y * CELL_SIZE | |
pg.draw.line( | |
background, pg.Color("black"), (OFFSET[0], y), (OFFSET[0] + GRID_SIZE[0], y), 3 | |
) | |
# Fill in unused squares | |
for y, row in enumerate(puzzle): | |
for x, val in enumerate(row): | |
if val in (-1, 0): | |
pg.draw.rect(background, pg.Color(30, 30, 30), cell_rect(x, y)) | |
elif val > 1: | |
tiny_font(background, x, y, str(val)) | |
jumps: DefaultDict[Tuple[int, int], int] = defaultdict(int) | |
jumps[pos] = 1 | |
current = TransCell(*pos, color=pg.Color(0, 0, 255)) | |
overlay: DefaultDict[Tuple[int, int], List[TransCell]] = defaultdict(list) | |
positions = [cell_rect(*pos)] | |
killed = False | |
while not killed and goal > 0: | |
for event in pg.event.get(): | |
if event.type == pg.QUIT: | |
killed = True | |
break | |
elif event.type == pg.MOUSEBUTTONDOWN and event.button == 1: | |
new_pos: Tuple[int, int] = coords2grid(*event.pos) | |
if 0 <= new_pos[0] < GRID_COUNT[0] and 0 <= new_pos[1] < GRID_COUNT[1]: | |
dx, dy = new_pos[0] - pos[0], new_pos[1] - pos[1] | |
if sorted([abs(dx), abs(dy)]) != [1, 2]: | |
continue | |
x, y = new_pos | |
if ( | |
puzzle[y][x] != -1 | |
and jumps[new_pos] < puzzle[y][x] | |
and ( | |
len(positions) < 2 | |
or new_pos != coords2grid(*positions[-2].center) | |
) | |
): | |
overlay[pos].append(TransCell(*pos, pg.Color("black"))) | |
pos = new_pos | |
jumps[pos] += 1 | |
current.rect = cell_rect(*pos) | |
positions.append(current.rect) | |
goal -= 1 | |
elif ( | |
event.type == pg.MOUSEBUTTONDOWN | |
and event.button == 3 | |
and len(positions) > 1 | |
): | |
current.rect = positions[-2] | |
del positions[-1] | |
jumps[pos] -= 1 | |
pos = coords2grid(*current.rect.center) | |
overlay[pos].pop().kill() | |
goal += 1 | |
screen.blit(background, (0, 0)) | |
OverlayGroup.draw(screen) | |
if len(positions) > 1: | |
pg.draw.lines( | |
screen, pg.Color("black"), False, [rect.center for rect in positions], 2 | |
) | |
pg.display.flip() | |
if goal > 0: | |
quit() | |
large_font = pg.font.Font(None, 200) | |
win_message = large_font.render("You won!", True, pg.Color("green")) | |
screen.blit( | |
win_message, | |
((WIDTH - win_message.get_width()) // 2, (HEIGHT - win_message.get_height()) // 2), | |
) | |
pg.display.flip() | |
pg.event.set_allowed(pg.QUIT) | |
pg.event.clear() | |
while True: | |
for event in pg.event.get(): | |
if event.type == pg.QUIT: | |
quit() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment