Initial implementation of the Maze class

This covers maze generation, but no functions for interfacing between the
Maze and Player.

1 files changed, 131 insertions, 23 deletions

diff --git a/maze.py b/maze.py
index 380ed9c..c1f8c07 100644
--- a/maze.py
+++ b/maze.py
@@ -16,31 +16,27 @@ 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.
 
-The first task is to decide how to split the problem up into classes. One
-approach is to have four classes:
- - Player, representing the player
- - Maze, storing the maze
- - Node, representing a single node in the maze
- - MazeGame, encapsulating the game as a whole
-However, having a class to represent each Node is wasteful. Each node has to
-store a pair of coordinates, and there are no methods which need to be executed
-on a node. Therefore, it would save memory to implement nodes as tuples.
-
-Hence, the following classes are needed:
- - Player
- - Maze
- - MazeGame
-
-We can start by implementing Player, since it's the easiest class. It needs to
-store the player's name and current location, and needs to allow the location
-to be updated.
-
-Note that the Player code doesn't check whether the player's location is a
-valid node in the maze; to do so would break the compartmentalisation between
-Maze and Player. It is better for this validation to be done in MazeGame, which
-controls both the Maze and the Player.
+The next class to implement is Maze. To keep separation between the components
+in the program, it must not include any code which handles players or their
+behaviour --- that should be in the Player class.
+
+The code in the Maze class should implement a fairly standard symmetric graph,
+as explained here:
+    http://en.wikipedia.org/wiki/Symmetric_graph
+There is not enough space to explain graph theory in these notes; please see
+Wikipedia for details on graphs (as distinct from data plots), reflexivity,
+graph symmetry and planarity.
+
+The graph is stored as an adjacency list, since it is a moderately sparse
+graph:
+    http://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29
+
+Note that the Maze class has been designed to be entirely immutable: the size
+and shape of the graph cannot be changed after the Maze has been constructed.
 """
 
+import random
+
 
 class Player(object):
     """A player in the game.
@@ -68,3 +64,115 @@ class Player(object):
         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)