Mercurial > sypikslang

comparison gamelib/lab.py @ 151:372d886f9e70

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
New suggest_research() method on Lab.
author Jeremy Thurgood <firxen@gmail.com>
date Fri, 11 May 2012 20:06:36 +0200
parents 14917385a0fd
children a644f6b64a6d
comparison
equal deleted inserted replaced
150:0090ecf08544 151:372d886f9e70
1 # -*- test-case-name: gamelib.tests.test_lab -*- 1 # -*- test-case-name: gamelib.tests.test_lab -*-
2 2
3 from random import random, choice 3 from random import random, choice, sample
4
5 import networkx
4 6
5 from gamelib import research, schematics 7 from gamelib import research, schematics
6 from gamelib.game_base import get_subclasses 8 from gamelib.game_base import get_subclasses
9
10
11 class ScienceGraph(object):
12 def __init__(self, all_science, known_science):
13 self.graph = networkx.DiGraph()
14 self.all_science = all_science
15 self.known_science = known_science
16 self.add_all_science()
17 self.tag_known_science()
18 assert networkx.is_directed_acyclic_graph(self.graph)
19
20 def add_all_science(self):
21 # Add level 0 of everything to the graph.
22 for science in self.all_science:
23 self.graph.add_node((science, 0), known=False)
24
25 # Walk dependencies and fill in intermediate nodes.
26 for science in self.all_science:
27 for dep in science.PREREQUISITES:
28 self.add_node_string(*dep)
29 self.graph.add_edge(dep, (science, 0))
30
31 def add_node_string(self, science, level):
32 node = (science, level)
33 if node in self.graph:
34 return node
35
36 # We prepopulate with level 0 of eveything.
37 assert level >= 0
38
39 self.graph.add_node(node, known=False)
40 parent = self.add_node_string(science, level - 1)
41 self.graph.add_edge(parent, node)
42 return node
43
44 def tag_known_science(self):
45 for science in self.known_science:
46 # We may know more of this than the graph has.
47 self.add_node_string(type(science), science.points + 1)
48 for i in range(science.points + 1):
49 self.graph.node[(type(science), i)]['known'] = True
50
51 def is_known(self, node):
52 return self.graph.node[node]['known']
53
54 def distances_to_known(self, science):
55 nodes = set()
56 nodes_to_check = [(science, 0)]
57
58 while nodes_to_check:
59 node = nodes_to_check.pop()
60 if self.is_known(node) or node in nodes:
61 continue
62 nodes.add(node)
63 nodes_to_check.extend(self.graph.predecessors(node))
64
65 distances = {}
66 for node in nodes:
67 distances.setdefault(node[0], 0)
68 distances[node[0]] += 1
69
70 return distances
71
72 def count_unknown(self, sciences):
73 return len([s for s in sciences if not self.is_known((s, 0))])
74
75 def find_prospects(self):
76 prospects = {'research': [], 'schematic': []}
77 for science in self.all_science:
78 distances = self.distances_to_known(science)
79 if not distances:
80 # We already know this thing.
81 continue
82 # Remove the thing we're trying to get from the distance.
83 distances.pop(science)
84 if self.count_unknown(distances.keys()) > 0:
85 # We only want direct breakthroughs.
86 continue
87 prospects[science.SCIENCE_TYPE].append(
88 (sum(distances.values()), science, distances))
89 return dict((k, sorted(v)) for k, v in prospects.items())
90
91 def find_promising_areas(self, size=3):
92 basic_science = False
93 areas_for_research = set()
94 areas_for_schematics = set()
95 prospects = self.find_prospects()
96
97 for points, target, distances in prospects['schematic']:
98 if points > 0:
99 # We need nonzero points in these things.
100 areas_for_schematics.update(distances.keys())
101 else:
102 # Any of these things qualify us.
103 areas_for_schematics.update(p for p, _ in target.PREREQUISITES)
104
105 for points, target, distances in prospects['research']:
106 if points == 0:
107 basic_science = True
108 else:
109 areas_for_research.update(distances.keys())
110
111 suggestions = []
112 k = min(size, len(areas_for_schematics))
113 suggestions.extend(sample(areas_for_schematics, k))
114 if len(suggestions) < size:
115 k = min(size - len(suggestions), len(areas_for_research))
116 suggestions.extend(sample(areas_for_research, k))
117
118 return basic_science, suggestions
7 119
8 120
9 class Lab(object): 121 class Lab(object):
10 BASIC_RESEARCH_SUCCESS_RATE = 0.05 122 BASIC_RESEARCH_SUCCESS_RATE = 0.05
11 BASIC_RESEARCH_SUCCESS_MULTIPLIER = 2 123 BASIC_RESEARCH_SUCCESS_MULTIPLIER = 2
12 124
13 def __init__(self, init_data=None): 125 def __init__(self, init_data=None):
14 self.science = [] 126 self.science = []
15 self.new_research = get_subclasses(research.ResearchArea) 127 self.new_research = get_subclasses(research.ResearchArea)
16 self.new_schematics = get_subclasses(schematics.Schematic) 128 self.new_schematics = get_subclasses(schematics.Schematic)
129 self.all_science = [s for s in self.new_research + self.new_schematics]
17 130
18 if init_data is not None: 131 if init_data is not None:
19 # Load stored state. 132 # Load stored state.
20 self._load_data(init_data) 133 self._load_data(init_data)
21 else: 134 else:
47 physics = research.Physics() 160 physics = research.Physics()
48 self._gain_science(physics) 161 self._gain_science(physics)
49 new_science = [physics] 162 new_science = [physics]
50 163
51 # We get two other random sciences with no prerequisites. 164 # We get two other random sciences with no prerequisites.
52 for _ in range(2): 165 for science in sample(self.find_new_research(), 2):
53 science = choice(self.find_new_research())() 166 science = science()
54 self._gain_science(science) 167 self._gain_science(science)
55 new_science.append(science) 168 new_science.append(science)
56 169
57 # Add a point to each of our sciences, and see if we get schematics. 170 # Add a point to each of our sciences, and see if we get schematics.
58 self.spend_points(new_science, 0) 171 self.spend_points(new_science, 0)
139 if breakthroughs: 252 if breakthroughs:
140 breakthrough = choice(breakthroughs)(1) 253 breakthrough = choice(breakthroughs)(1)
141 self._gain_science(breakthrough) 254 self._gain_science(breakthrough)
142 breakthroughs = [breakthrough] 255 breakthroughs = [breakthrough]
143 return breakthroughs 256 return breakthroughs
257
258 def suggest_research(self):
259 """Suggest research areas to pursue.
260
261 Return value is a tuple of (bool, list), where the first element
262 indicates whether basic research might pay off and the second contains
263 Science classes that can be profitably pursued.
264 """
265 graph = ScienceGraph(self.all_science, self.science)
266 return graph.find_promising_areas()