game.py

import sys
import json
import copy
import Board
import Piece
import Block

board = Board.Board()
exit_tiles = {'red':[(3,-3),(3,-2),(3,-1),(3,0)]}

def main():
    with open(sys.argv[1]) as file:
        
        # Load initial board state
        data = json.load(file)
        bdict = {}

        # Add pieces and blocks to the board
        for p in data['pieces']:
            piece = Piece.Piece(tuple(p), data['colour'])
            board.tiles[piece.pos[1]+3][piece.pos[0]+3] = piece
            board.pieces.append(piece)
        
        for b in data['blocks']:
            block = Block.Block(tuple(b))
            board.tiles[block.pos[1]+3][block.pos[0]+3] = block
        
        # Run a* search and print solution if one exists
        path = A_Star(board)
        if path is None:
            print("No path found")
        else:
            for node in path:
                bdict = make_bdict(node)
                print_board(bdict)


def A_Star(start):

    # Initialise open and closed sets
    closedSet = []
    openSet = [start]
    
    # Initial path length and heuristic
    start.g = 0

    start.f = heuristic(start)
    
    while openSet:

        # Find node in open set with lowest f value and set it as the "current" node
        minF = 1000000
        for node in openSet:
            if node.f <= minF:
                current = node
                minF = current.f 
        
        # If found node is the goal, retrace the path, and return the solution
        if checkGoal(current):
            return retrace(current) 

        # Remove the current node from the open set and add it to the closed set
        openSet.remove(current)
        closedSet.append(current)
        
        #Find all neighbors of the current node
        neighbors = getNeighbors(current)
        
        # Iterate through the neighbors of the current node
        for neighbor in neighbors: 
            
            # If the neighbor is already in the closed set, skip it
            inClosed = False
            for node in closedSet:
                if listCompare(neighbor.tiles, node.tiles):
                    inClosed = True
            if inClosed:
                continue
            
            tentative_gScore = current.g + 1
            
            # Check if the neighbor is in the open set
            inOpen = False
            for node in openSet:
                if listCompare(neighbor.tiles, node.tiles):
                    inOpen = True
            
            # If not, add it
            if not inOpen:
                openSet.append(neighbor)
            
            # If it is, but the neighbor has a higher g score than the node already in the list, skip it
            elif tentative_gScore >= neighbor.g:
                continue

            # Set the parent and g and f scores of the node
            neighbor.parent = current
            neighbor.g = tentative_gScore
            neighbor.f = neighbor.g + heuristic(neighbor)

# Compare two board states
def listCompare(list1, list2):
    for i in range(0,7):
        for j in range(0,7):
            if type(list1[i][j]) is not type(list2[i][j]):
                return False

    return True

# Calculates the heuristic for a given board state
def heuristic(node):
    h = 0
    for piece in node.pieces:
        min_dist = 10
        for tile in exit_tiles['red']:
            if board.distance(piece.pos, tile) <= min_dist:
                min_dist = board.distance(piece.pos, tile)
        h += (min_dist + 1) / 2
    return h

# Check if the goal has been reached
def checkGoal(state):
    if not state.pieces:
        return True
    else:
        return False

# Retrace the path from the goal state to the initial state
def retrace(goal):
    path = []
    cur = goal
    while cur.parent is not None:
        path.insert(0,cur)
        cur = cur.parent
    path.insert(0,cur)
    return path

# Find the neighbor states of a given board state
def getNeighbors(current):
    neighbors = []
    moves = current.getMoves()
    
    # getMoves returns only a Piece object if a piece is on an exit tile
    # In that case, the only neighbor is the same board with that piece removed
    if isinstance(moves, Piece.Piece):
        neighbor = copy.deepcopy(current)
        
        for piece in neighbor.pieces:
            if piece.pos == moves.pos:
                neighbor.pieces.remove(piece)
                break

        neighbor.tiles[moves.pos[1]+3][moves.pos[0]+3] = None
        
        neighbors.append(neighbor)
        return neighbors
    
    # Otherwise, it returns a list of possible moves
    # In that case, return a list of board states with those moves applied
    for move in moves:
        neighbor = copy.deepcopy(current)
        neighbor.move(move[0], move[1])
        neighbors.append(neighbor)
    return neighbors

# Functions for printing board state
def make_bdict(state):

    bdict = {}

    for row in state.tiles:
        for col in row:
            if isinstance(col, Piece.Piece):
                bdict[col.pos] = 'p'
            elif isinstance(col, Block.Block):
                bdict[col.pos] = 'b'

    return bdict

def print_board(board_dict, message="", debug=False, **kwargs):
    """
    Helper function to print a drawing of a hexagonal board's contents.
    
    Arguments:

    * `board_dict` -- dictionary with tuples for keys and anything printable
    for values. The tuple keys are interpreted as hexagonal coordinates (using 
    the axial coordinate system outlined in the project specification) and the 
    values are formatted as strings and placed in the drawing at the corres- 
    ponding location (only the first 5 characters of each string are used, to 
    keep the drawings small). Coordinates with missing values are left blank.

    Keyword arguments:

    * `message` -- an optional message to include on the first line of the 
    drawing (above the board) -- default `""` (resulting in a blank message).
    * `debug` -- for a larger board drawing that includes the coordinates 
    inside each hex, set this to `True` -- default `False`.
    * Or, any other keyword arguments! They will be forwarded to `print()`.
    """

    # Set up the board template:
    if not debug:
        # Use the normal board template (smaller, not showing coordinates)
        template = """# {0}
#           .-'-._.-'-._.-'-._.-'-.
#          |{16:}|{23:}|{29:}|{34:}| 
#        .-'-._.-'-._.-'-._.-'-._.-'-.
#       |{10:}|{17:}|{24:}|{30:}|{35:}| 
#     .-'-._.-'-._.-'-._.-'-._.-'-._.-'-.
#    |{05:}|{11:}|{18:}|{25:}|{31:}|{36:}| 
#  .-'-._.-'-._.-'-._.-'-._.-'-._.-'-._.-'-.
# |{01:}|{06:}|{12:}|{19:}|{26:}|{32:}|{37:}| 
# '-._.-'-._.-'-._.-'-._.-'-._.-'-._.-'-._.-'
#    |{02:}|{07:}|{13:}|{20:}|{27:}|{33:}| 
#    '-._.-'-._.-'-._.-'-._.-'-._.-'-._.-'
#       |{03:}|{08:}|{14:}|{21:}|{28:}| 
#       '-._.-'-._.-'-._.-'-._.-'-._.-'
#          |{04:}|{09:}|{15:}|{22:}|
#          '-._.-'-._.-'-._.-'-._.-'"""
    else:
        # Use the debug board template (larger, showing coordinates)
        template = """# {0}
#              ,-' `-._,-' `-._,-' `-._,-' `-.
#             | {16:} | {23:} | {29:} | {34:} | 
#             |  0,-3 |  1,-3 |  2,-3 |  3,-3 |
#          ,-' `-._,-' `-._,-' `-._,-' `-._,-' `-.
#         | {10:} | {17:} | {24:} | {30:} | {35:} |
#         | -1,-2 |  0,-2 |  1,-2 |  2,-2 |  3,-2 |
#      ,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-. 
#     | {05:} | {11:} | {18:} | {25:} | {31:} | {36:} |
#     | -2,-1 | -1,-1 |  0,-1 |  1,-1 |  2,-1 |  3,-1 |
#  ,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-.
# | {01:} | {06:} | {12:} | {19:} | {26:} | {32:} | {37:} |
# | -3, 0 | -2, 0 | -1, 0 |  0, 0 |  1, 0 |  2, 0 |  3, 0 |
#  `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' 
#     | {02:} | {07:} | {13:} | {20:} | {27:} | {33:} |
#     | -3, 1 | -2, 1 | -1, 1 |  0, 1 |  1, 1 |  2, 1 |
#      `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' 
#         | {03:} | {08:} | {14:} | {21:} | {28:} |
#         | -3, 2 | -2, 2 | -1, 2 |  0, 2 |  1, 2 | key:
#          `-._,-' `-._,-' `-._,-' `-._,-' `-._,-' ,-' `-.
#             | {04:} | {09:} | {15:} | {22:} |   | input |
#             | -3, 3 | -2, 3 | -1, 3 |  0, 3 |   |  q, r |
#              `-._,-' `-._,-' `-._,-' `-._,-'     `-._,-'"""

    # prepare the provided board contents as strings, formatted to size.
    ran = range(-3, +3+1)
    cells = []
    for qr in [(q,r) for q in ran for r in ran if -q-r in ran]:
        if qr in board_dict:
            cell = str(board_dict[qr]).center(5)
        else:
            cell = "     " # 5 spaces will fill a cell
        cells.append(cell)

    # fill in the template to create the board drawing, then print!
    board = template.format(message, *cells)
    print(board, **kwargs)

if __name__ == '__main__':
    main()