#!/usr/bin/env python3 import networkx import operator from PIL import Image WALL, CELL, PLAYER, TARGET = ('8', ' ', 'o', '0') UP, DOWN, LEFT, RIGHT = (8, 2, 4, 6) color_map = { WALL: (0, 0, 0), CELL: (255, 255, 255), PLAYER: (34, 177, 76), TARGET: (237, 28, 36) } def is_valid_cell(cell): """basically check if we're able to go to the specified cell.""" return cell == CELL or cell == PLAYER or cell == TARGET def get_2d_pos(index, width): """convert an index into a (x, y) position based on the matrix width.""" return (index % width, index // width) def sub_tuple(a, b): return tuple(map(operator.sub, a, b)) def convert_path_to_moves(path): """convert path to moves ("DIRECTION+STEPS" notation).""" moves = [] current_pos = path[0] for next_pos in path: move = sub_tuple(next_pos, current_pos) if move != (0, 0): # check if we're actually moving. if move[0] == 0: # UP or DOWN if move[1] > 0: # DOWN dir_ = DOWN elif move[1] < 0: # UP dir_ = UP steps = abs(move[1]) elif move[1] == 0: # LEFT or RIGHT if move[0] > 0: # RIGHT dir_ = RIGHT elif move[0] < 0: # LEFT dir_ = LEFT steps = abs(move[0]) if len(moves) == 0 or moves[-1][0] != dir_: # player has not moved in this direction yet. moves.append([dir_, 0]) next_move = (moves[-1][1] + steps) for _ in range(next_move // 0xf): # we can't do more than 0xf steps in the same direction at a time. moves[-1][1] = 0xf moves.append([dir_, (next_move % 0xf)]) else: moves[-1][1] = next_move current_pos = next_pos return moves def draw(board: list, width: int, out_fname: str = '', path: list = [], color_map: dict = color_map): img = None if out_fname: img_size = (width, (len(board) // width)) img = Image.new(mode='RGB', size=img_size, color=(0, 0, 0)) # draw board cells. for cell_i, cell in enumerate(board): node = get_2d_pos(cell_i, width) img.putpixel(node, color_map[cell]) # draw additional path. if len(path) > 2: prev_move = path[0] for i in range(1, len(path)): move = path[i] if prev_move[0] == move[0]: # move on y-axis. direction = -1 if prev_move[1] > move[1] else 1 for intermov in [(move[0], y) for y in range(prev_move[1], move[1]+direction, direction)]: img.putpixel(intermov, (255, 255, 86)) elif prev_move[1] == move[1]: # move on x-axis. direction = -1 if prev_move[0] > move[0] else 1 for intermov in [(x, move[1]) for x in range(prev_move[0], move[0]+direction, direction)]: img.putpixel(intermov, (255, 255, 86)) prev_move = move # draw player and target. img.putpixel(path[0], color_map[PLAYER]) img.putpixel(path[-1], color_map[TARGET]) img.save(f'{out_fname}.png') else: print('Missing output filename!') return img def print_board(board: list, width: int, player_pos: int): for cell_i, cell in enumerate(board): if cell_i == player_pos: cell = PLAYER print(f'{cell} ', end='') if (cell_i + 1) % width == 0: print() def get_printable_path(path): buf = '' moves = convert_path_to_moves(path) for move in moves: buf += f'{move[0]:x}{move[1]:x}' return buf def get_short_exit_path(board: list, width: int, player_node: tuple, target_node: tuple): """create a graph with adjacent cells then compute the shortest path from start to end node.""" graph = networkx.DiGraph() for cell_i, cell in enumerate(board): if is_valid_cell(cell): node = get_2d_pos(cell_i, width) # check if we can go to an adjacent cell. for dir_ in (width, -1, 1): # DOWN, LEFT, RIGHT (we are traversing the maze) adj_cell_i = cell_i+dir_ # if we can go to the adjacent cell, # create a bidirectional path between the current and the adjacent cell if adj_cell_i >= 0 and adj_cell_i <= len(board): # check board boundaries. adj_cell = board[adj_cell_i] adj_node = get_2d_pos(adj_cell_i, width) if is_valid_cell(adj_cell): graph.add_edge(node, adj_node) graph.add_edge(adj_node, node) paths = networkx.all_shortest_paths(graph, player_node, target_node) return paths def get_direct_exit_path(board: list, width: int, player_node: tuple, target_node: tuple): """create a graph with accessible cells then compute the shortest path from start to end node.""" graph = networkx.DiGraph() for cell_i, cell in enumerate(board): if is_valid_cell(cell): node = get_2d_pos(cell_i, width) # check if we can go to an adjacent cell. for dir_ in (width, -1, 1): # DOWN, LEFT, RIGHT (we are traversing the maze) for i in range(1, 0x10): near_cell_i = cell_i+(dir_*i) if near_cell_i >= 0 and near_cell_i <= len(board): # check board boundaries. near_cell = board[near_cell_i] near_node = get_2d_pos(near_cell_i, width) if is_valid_cell(near_cell): graph.add_edge(node, near_node) graph.add_edge(near_node, node) else: break paths = networkx.all_shortest_paths(graph, player_node, target_node) return paths def main(): for level_i, level in enumerate(levels): level_name = f'level_{level_i+1}' player_node = get_2d_pos(level['board'].index(PLAYER), level['width']) target_node = get_2d_pos(level['board'].index(TARGET), level['width']) print(f'[+] level: {level_name}') print(f'[+] player node: {player_node}') print(f'[+] target node: {target_node}') # draw the level board. draw(level['board'], level['width'], level_name) # get short exit paths for the board. paths = get_short_exit_path(level['board'], level['width'], player_node, target_node) # print and draw exit paths. for i, path in enumerate(paths): print(f'SP{i}: {get_printable_path(path)}') draw(level['board'], level['width'], f'{level_name}_short_path_{i}', path) # get paths with the lowest direction changes. paths = get_direct_exit_path(level['board'], level['width'], player_node, target_node) # print and draw exit paths. for i, path in enumerate(paths): print(f'DP{i}: {get_printable_path(path)}') draw(level['board'], level['width'], f'{level_name}_direct_path_{i}', path) if __name__ == '__main__': from levels import * main()