1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
#!/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.
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.
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)
|
