-
Notifications
You must be signed in to change notification settings - Fork 1
/
WFC.py
187 lines (170 loc) · 9.07 KB
/
WFC.py
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
179
180
181
182
183
184
185
186
187
import numpy as np
from typing import Tuple
from image_distribution import ImageDistribution
from utility import in_bound
class WeightingOptions:
UNIFORM = 1 # Uniform Distribution
TILE_FREQUENCY = 2 # based on the frequency of units #Gumin's
CONTEXT_SENSITIVE = 3 # based on the conditional prbability (conditioned by context around it)
class UpdatingOptions:
NEIGHBOR = 1 # Experimental, propagates the constraints only to immediate neighbors
CHAIN = 2 #Gumin's
class EntropyOptions:
NUMBER_OF_OPTIONS = 1
SHANNON = 2 #Gumin's
TOP_LEFT = 3
TOP_RIGHT = 4
class ExistingTile:
def __init__(self, pos: Tuple[int, int], tile_number: int):
self.pos = pos
self.tile_number = tile_number
class WFC:
def __init__(self, dist: ImageDistribution, weighting_option, updating_option, entropy_option):
self.dist = dist
self.updating_option = updating_option
self.entropy_option = entropy_option
self.weighting_option = weighting_option
def _get_updated_possibilities(self, possibilities, collapsed_value, move_number):
if possibilities.shape[0] == 1:
return possibilities
return possibilities[np.array(list(map(lambda p: (collapsed_value, p, move_number) in self.dist.exists, possibilities)))]
def _get_options(self):
return np.array(list(self.dist.unit_numbers), dtype=np.int64)
# not int because of possible overflow: OverflowError: Python int too large to convert to C long
# https://stackoverflow.com/questions/38314118/overflowerror-python-int-too-large-to-convert-to-c-long-on-windows-but-not-ma
def _get_context(self, supermap, unit_number, x, y):
context = [unit_number, None, None, None, None]
for k in range(len(ImageDistribution.MOVESET)):
dx, dy = ImageDistribution.MOVESET[k]
if in_bound(x+dx, y+dy, supermap) and len(supermap[x+dx, y+dy]) == 1:
context[k+1] = supermap[x+dx, y+dy][0]
return (context[0], context[1], context[2], context[3], context[4])
def _get_weights(self, supermap, x, y):
if self.weighting_option == WeightingOptions.TILE_FREQUENCY:
return np.array(list(map(lambda u: self.dist.get_unit_frequency(u), supermap[x, y])))
elif self.weighting_option == WeightingOptions.UNIFORM:
return np.ones(supermap[x, y].shape)
elif self.weighting_option == WeightingOptions.CONTEXT_SENSITIVE:
weights = np.array(list(map(lambda u: self.dist.get_context_frequency(self._get_context(supermap, u, x, y)), supermap[x, y])))
if np.sum(weights) == 0:
return np.array(list(map(lambda u: self.dist.get_unit_frequency(u), supermap[x, y]))) # fall-back: return frequency weighted
return weights
raise Exception("weighting option not implemented!")
def _get_probabilities(self, supermap, x, y):
weights = self._get_weights(supermap, x, y)
return weights/np.sum(weights)
def _get_entropy(self, supermap, x, y, map_size):
if self.entropy_option == EntropyOptions.SHANNON:
weights = self._get_weights(supermap, x, y)
return np.log(np.sum(weights)) - (np.sum(weights * np.log(weights)) / np.sum(weights))
elif self.entropy_option == EntropyOptions.NUMBER_OF_OPTIONS:
return len(supermap[x, y])
elif self.entropy_option == EntropyOptions.TOP_LEFT:
return x * map_size[1] + y
elif self.entropy_option == EntropyOptions.TOP_RIGHT:
return x * map_size[1] + (map_size[0] - y)
raise Exception("entropy option not implemented!")
def _get_position_to_collapse(self, supermap, map_size):
entropies = []
for i in range(supermap.shape[0]):
for j in range(supermap.shape[1]):
entropies.append(self._get_entropy(supermap, i, j, map_size) if len(supermap[i, j]) > 1 else np.Inf)
entropies = np.array(entropies)
min_entropy = np.argmin(entropies, axis=None)
if entropies[min_entropy] == np.Inf:
return None, None
return np.unravel_index(np.argmin(entropies, axis=None), supermap.shape)
def _collapse(self, supermap, x, y, map_size):
probabilities = self._get_probabilities(supermap, x, y)
supermap[x, y] = np.array([np.random.choice(supermap[x, y], p=probabilities)])
def _update_supermap(self, changed_x, changed_y, supermap):
changed_queue = [(changed_x, changed_y)]
invalid = False
while len(changed_queue) > 0:
x, y = changed_queue[0]
changed_queue = changed_queue[1:]
if len(supermap[x, y]) != 1:
continue # TODO WHY? -> because we need the collapsed value to get possibilities
for k in range(len(ImageDistribution.MOVESET)):
dx, dy = ImageDistribution.MOVESET[k]
if in_bound(x+dx, y+dy, supermap) and len(supermap[x+dx, y+dy]) > 1:
new_possibilities = self._get_updated_possibilities(supermap[x+dx, y+dy], supermap[x, y][0], k)
if len(new_possibilities) != len(supermap[x+dx, y+dy]):
supermap[x+dx, y+dy] = new_possibilities
if len(new_possibilities) < 1:
invalid = True
if self.updating_option == UpdatingOptions.NEIGHBOR:
pass
elif self.updating_option == UpdatingOptions.CHAIN:
changed_queue.append((x+dx, y+dy))
return not invalid
def _get_initial_supermap(self, map_size, existing_tiles):
options = self._get_options()
supermap = np.array([[None for _ in range(map_size[1])] for _ in range(map_size[0])], dtype=object)
for i in range(map_size[0]):
for j in range(map_size[1]):
supermap[i, j] = options.copy()
for existing_tile in existing_tiles:
i, j = existing_tile.pos
supermap[i, j] = np.array([existing_tile.tile_number])
self._update_supermap(i, j, supermap)
return supermap
def generate_bt(self, map_size, existing_tiles=[], gif_maker=None):
self._bt_counter = 0
supermap = self._get_initial_supermap(map_size, existing_tiles)
tested = np.array([[None for _ in range(map_size[1])] for _ in range(map_size[0])], dtype=object)
for i in range(map_size[0]):
for j in range(map_size[1]):
tested[i, j] = []
checkpoints = [(supermap.copy(), tested.copy())]
while True:
if len(checkpoints) == 0:
raise Exception('Not possible')
# copy supermap and tested
supermap, tested = checkpoints[-1]
supermap, tested = supermap.copy(), tested.copy() # TODO deep copy supermap (not really needed)
for i in range(map_size[0]):
for j in range(map_size[1]):
tested[i, j] = [val for val in tested[i, j]]
# find position to collapse
x, y = self._get_position_to_collapse(supermap, map_size) # why not remove tested: because then maybe len == 1 for some positions
if x is None or y is None:
break
#use untested ones at [x, y] to collapse(x, y)
options = supermap.copy()
options[x, y] = np.delete(options[x, y], np.where(np.in1d(options[x, y], tested[x, y])))
if len(options[x, y]) == 0:
checkpoints = checkpoints[:-1]
continue
if len(options[x, y]) > 1:
self._collapse(options, x, y, map_size)
supermap[x, y] = options[x, y]
#update tested
tested[x, y].append(supermap[x, y][0])
checkpoints[-1][1][x, y].append(supermap[x, y][0])
if self._update_supermap(x, y, supermap):
# checkpoint
checkpoints.append((supermap, tested))
self._bt_counter += 1
if gif_maker is not None:
for checkpoint in checkpoints:
c_supermap, _ = checkpoint
gif_maker.add_frame(c_supermap)
gif_maker.add_frame(supermap)
map = np.array([[possibilities[0] if len(possibilities) > 0 else None for possibilities in row] for row in supermap])
return map
def generate(self, map_size, seed=0, existing_tiles=[], backtrack=False, gif_maker=None):
np.random.seed(seed)
if backtrack:
return self.generate_bt(map_size, existing_tiles, gif_maker)
supermap = self._get_initial_supermap(map_size, existing_tiles)
if gif_maker is not None: gif_maker.add_frame(supermap)
while True:
x, y = self._get_position_to_collapse(supermap, map_size)
if x is None or y is None:
break
self._collapse(supermap, x, y, map_size)
self._update_supermap(x, y, supermap)
if gif_maker is not None: gif_maker.add_frame(supermap)
map = np.array([[possibilities[0] if len(possibilities) > 0 else None for possibilities in row] for row in supermap])
return map