path: root/maze.py

#!/usr/bin/python
# coding=utf-8
"""A simple command-line maze game.

This game is designed as a tutorial of how to break a problem down into
components and tackle each individually. The game itself is pretty boring and
lacks a nice interface.

In the game, there is a single player stuck in a randomly-generated maze. The
player only knows their name, current location, and the paths available to them
from their current location. The graph is represented as a network of links
between nodes, stored as a dictionary mapping a node to a list of nodes it's
linked to. Every link is directional but the graph is symmetric. Cycles and
reflexive links are permitted. All nodes are addressed as a tuple giving their
X and Y position on an integer grid of given size where (0, 0) is the start
node and (size, size) is the finish node. This is a standard way to represent
a graph in a program.


Finally, the MazeGame class needs to be implemented to tie together both Maze
and Player. This class needs to implement the user interface, repeatedly asking
the player which move they'll make, then updating the Player's location
accordingly.

Implementing this requires a method to be added to Maze to retrieve a list of
the nodes which the player can legitimately move to from their current
location. To avoid breaking compartmentalisation and encoding the player's
behaviour in the Maze class, the method takes a node as a parameter rather than
accessing the player's location directly.

One language feature to note is the use of "while...else" in MazeGame.run().
The code in the 'else' block will be executed immediately after the final
iteration of the 'while' loop, but won't be executed if execution leaves the
loop by executing the 'break' statement. This means the "you've won" message
won't be printed if the user quits the game prematurely.
"""

import random


class Player(object):
    """A player in the game.

    This stores the player's current location as an (X, Y) coordinate tuple,
    and also the player's name. The player's name cannot be changed after
    construction.
    """
    def __init__(self, name):
        self._name = name
        self._location = (0, 0)

    def get_location(self):
        """Get the player's current location."""
        return self._location

    def set_location(self, location):
        """Set the player's current location."""
        self._location = location

    location = property(get_location, set_location)

    def get_name(self):
        """Get the player's name."""
        return self._name

    name = property(get_name)


class Maze(object):
    """The maze the player must navigate around.

    This represents a maze as a symmetric graph. The graph is not necessarily
    acyclic, and can have reflexive links. It is also not necessarily planar,
    and can contain duplicate links. The graph is confined to an integer grid
    between the start node at (0, 0) and the finish node at (size, size).
    The grid must be of size at least 1.
    """
    def __init__(self, size):
        self._links = {}
        self._finish_node = (size, size)
        self.__generate_maze(size)

    # This attribute specifies that the function doesn't use its 'self'
    # variable at all, and so the variable can be removed.
    @staticmethod
    def __generate_num_nodes(size):
        """Pick a random number of nodes to have in the maze.

        This will be between 0.25*size*size and 0.5*size*size so the maze isn't
        too full or too empty. The start and finish nodes are not included in
        this number.
        """
        max_nodes = size * size  # for a totally full grid
        return random.randint(int(0.25 * max_nodes), int(0.5 * max_nodes))

    @staticmethod
    def __generate_num_links(num_nodes):
        """Pick a random number of links to have between the nodes in the maze.

        This will be between 0.1*num_nodes*num_nodes and
        0.4*num_nodes*num_nodes so the maze isn't completely disjoint or
        completely connected.
        """
        max_links = num_nodes * num_nodes  # for a totally connected graph
        return random.randint(int(0.1 * max_links), int(0.4 * max_links))

    def __generate_maze(self, size):
        """Generate a new maze, overwriting the contents of self._links.

        The maze will use coordinates (0, 0) to (at most) (size, size). It may
        contain reflexive and duplicate links. All connections are guaranteed
        to be symmetric (i.e. a pair of directed links). The maze itself is not
        guaranteed to be planar.
        """

        # Generate a list of nodes which form the nodes of the maze. Ensure
        # that the start and end nodes are in the list. Don't care about
        # duplicates; if a node is duplicated in nodes, it means that it will
        # be twice as likely to be chosen in the link-generation code below.
        nodes = [self.start_node]
        num_nodes = self.__generate_num_nodes(size)
        for _ in range(num_nodes):
            nodes.append((random.randint(0, size), random.randint(0, size)))

        # Put the finish node at the end of the list so we can iterate
        # through the list to generate the winning path, below.
        nodes.append(self.finish_node)

        # Explicitly generate a path from the start to the finish, to ensure
        # that there is at least one solution to the maze. This is guaranteed
        # to include both the start node and the finish node, as the initial
        # value of current_index is 0 (the start node's index); and the loop
        # won't terminate until current_index is at least equal to the index
        # of the finish node, meaning that next_index must've been the index
        # of the finish node at least once.
        self._links = {}
        current_index = 0  # guaranteed to be the start node
        while current_index < len(nodes) - 1:
            step = random.randint(1, len(nodes) - current_index - 1)
            next_index = current_index + step
            self.__add_link(nodes[current_index], nodes[next_index])
            current_index = next_index

        # Add other links between the nodes. These may connect up to the
        # winning path, may form extra winning paths, or may be disconnected.
        for _ in range(self.__generate_num_links(num_nodes)):
            current_index = random.randint(0, num_nodes - 1)
            next_index = random.randint(0, num_nodes - 1)
            self.__add_link(nodes[current_index], nodes[next_index])

    def __add_link(self, point_a, point_b):
        """Add a pair of links between point_a and point_b and vice-versa."""
        self.__add_one_way_link(point_a, point_b)
        self.__add_one_way_link(point_b, point_a)

    def __add_one_way_link(self, point_a, point_b):
        """Add a uni-directional link between point_a and point_b."""
        links = self._links.get(point_a, [])
        links.append(point_b)
        self._links[point_a] = links

    def get_start_node(self):
        """Get the starting node for the player.

        This node is guaranteed to exist in the maze.
        """
        return (0, 0)

    start_node = property(get_start_node)

    def get_finish_node(self):
        """Get the finishing node for the player.

        This node is guaranteed to exist in the maze.
        """
        return self._finish_node

    finish_node = property(get_finish_node)

    def get_adjacents_to_node(self, node):
        """Get a list of nodes which are adjacent to the given node.

        This list may include node itself, as reflexive links are permitted.
        If an invalid node is passed as the parameter, an empty list is
        returned.
        """
        return self._links.get(node, [])


class MazeGame(object):
    """Command-line implementation of the maze game.

    This connects the Player to the Maze and implements the input loop which
    handles the player's movement choices.
    """
    def __init__(self):
        name = raw_input('Please enter your name: ')
        size = int(raw_input('Enter the maze size (between 5 and 20): '))

        self._player = Player(name)
        self._maze = Maze(size)

    def __choose_next_location(self):
        """Ask the user for the next location to move to.

        The chosen location is returned as an (X, Y) tuple, which is guaranteed
        to be a valid node in the maze. If the user chooses to exit the game,
        None is returned.
        """

        # Get a list of the nodes conncted to the player's current location.
        adjacent_nodes = \
            self._maze.get_adjacents_to_node(self._player.location)

        # Print out the options, numbered.
        option = 1
        print('You are at %s. You can move to:' % str(self._player.location))
        for node in adjacent_nodes:
            print(' %u) %s' % (option, str(node)))
            option += 1

        print(' 0) Quit game')

        # Ask the user which option they want.
        chosen_option = int(raw_input('Enter the number of your choice: '))
        if chosen_option == 0:
            return None  # quit the game
        else:
            return adjacent_nodes[chosen_option - 1]

    def run(self):
        """Run the game until the player wins or quits."""
        while self._player.location != self._maze.finish_node:
            chosen_node = self.__choose_next_location()
            if chosen_node is None:
                break  # quit game

            self._player.location = chosen_node
        else:
            print('You have won, %s!' % self._player.name)


# Run the game.
MazeGame().run()