Skip to content

Instantly share code, notes, and snippets.

@grechnik

grechnik/spawn.py

Created October 19, 2024 20:27
Show Gist options
  • Save grechnik/59430a2f8fd16a10b1c2faaffc4639fa to your computer and use it in GitHub Desktop.
Save grechnik/59430a2f8fd16a10b1c2faaffc4639fa to your computer and use it in GitHub Desktop.
Download ZIP
reconstructed islands of insight spawn logic
Raw
spawn.py
import time
import cityhash # pip install cityhash
import zlib
import struct
import math
import argparse
from collections import namedtuple, defaultdict
# presumably most or all of this info can be loaded from Puzzles.json,
# but for now, grab already parsed records from https://egrechnikov.store/misc/ioipuzzles.zip
# format:
# "world id=16933 zone=6 type=ghostObject index=4 spawn=2 incompatible=17492,17528"
# "contained id=20264 zone=6 type=klotski index=0"
id2puzzle = {}
zone_and_type2puzzles = defaultdict(lambda: [])
id_field = 1
zone_field = 2
type_field = 3
index_field = 4
spawn_field = 5
incompatible_field = 6
with open('puzzlesdump.log', 'r') as f:
for line in f:
line = line.rstrip('\r\n').split(' ')
assert line[zone_field].startswith('zone=')
zone = int(line[zone_field][len('zone='):])
assert line[type_field].startswith('type=')
type_ = line[type_field][len('type='):]
assert line[id_field].startswith('id=')
id_ = int(line[id_field][len('id='):])
assert line[index_field].startswith('index=')
if line[0] == 'world':
assert line[spawn_field].startswith('spawn=')
assert line[incompatible_field].startswith('incompatible=')
zone_and_type2puzzles[(zone, type_)].append(line)
assert id_ not in id2puzzle
id2puzzle[id_] = line
ZoneAndTypeStat = namedtuple('ZoneAndTypeStat', ['group_size', 'num_groups', 'assignable_count'])
zone_and_type_stats = {
2: {
"hiddenCube": ZoneAndTypeStat(group_size=30, num_groups=8, assignable_count=229),
"followTheShiny": ZoneAndTypeStat(group_size=13, num_groups=7, assignable_count=93),
"fractalMatch": ZoneAndTypeStat(group_size=10, num_groups=9, assignable_count=93),
"ghostObject": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"mirrorMaze": ZoneAndTypeStat(group_size=6, num_groups=13, assignable_count=82),
"lightPillar": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"matchbox": ZoneAndTypeStat(group_size=38, num_groups=7, assignable_count=274),
"lightPattern": ZoneAndTypeStat(group_size=11, num_groups=7, assignable_count=76),
"racingBallCourse": ZoneAndTypeStat(group_size=5, num_groups=7, assignable_count=35),
"racingRingCourse": ZoneAndTypeStat(group_size=2, num_groups=8, assignable_count=16),
"hiddenArchway": ZoneAndTypeStat(group_size=50, num_groups=7, assignable_count=353),
"seek5": ZoneAndTypeStat(group_size=7, num_groups=7, assignable_count=50),
"viewfinder": ZoneAndTypeStat(group_size=7, num_groups=7, assignable_count=50),
"hiddenRing": ZoneAndTypeStat(group_size=52, num_groups=7, assignable_count=363),
"logicGrid": ZoneAndTypeStat(group_size=45, num_groups=14, assignable_count=633),
"gyroRing": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"klotski": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"lockpick": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"match3": ZoneAndTypeStat(group_size=25, num_groups=14, assignable_count=356),
"ryoanji": ZoneAndTypeStat(group_size=5, num_groups=10, assignable_count=52),
"rollingCube": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"memoryGrid": ZoneAndTypeStat(group_size=2, num_groups=12, assignable_count=24),
"completeThePattern": ZoneAndTypeStat(group_size=8, num_groups=14, assignable_count=111),
"musicGrid": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
},
3: {
"hiddenCube": ZoneAndTypeStat(group_size=34, num_groups=6, assignable_count=191),
"followTheShiny": ZoneAndTypeStat(group_size=20, num_groups=6, assignable_count=117),
"fractalMatch": ZoneAndTypeStat(group_size=12, num_groups=8, assignable_count=99),
"ghostObject": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"mirrorMaze": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"lightPillar": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"matchbox": ZoneAndTypeStat(group_size=54, num_groups=6, assignable_count=326),
"lightPattern": ZoneAndTypeStat(group_size=19, num_groups=7, assignable_count=132),
"racingBallCourse": ZoneAndTypeStat(group_size=9, num_groups=8, assignable_count=70),
"racingRingCourse": ZoneAndTypeStat(group_size=5, num_groups=6, assignable_count=32),
"hiddenArchway": ZoneAndTypeStat(group_size=50, num_groups=7, assignable_count=363),
"seek5": ZoneAndTypeStat(group_size=6, num_groups=7, assignable_count=43),
"viewfinder": ZoneAndTypeStat(group_size=26, num_groups=7, assignable_count=181),
"hiddenRing": ZoneAndTypeStat(group_size=43, num_groups=7, assignable_count=307),
"logicGrid": ZoneAndTypeStat(group_size=45, num_groups=14, assignable_count=640),
"gyroRing": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"klotski": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"lockpick": ZoneAndTypeStat(group_size=2, num_groups=6, assignable_count=12),
"match3": ZoneAndTypeStat(group_size=6, num_groups=15, assignable_count=89),
"ryoanji": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"rollingCube": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"memoryGrid": ZoneAndTypeStat(group_size=2, num_groups=11, assignable_count=21),
"completeThePattern": ZoneAndTypeStat(group_size=6, num_groups=15, assignable_count=88),
"musicGrid": ZoneAndTypeStat(group_size=2, num_groups=12, assignable_count=23),
},
4: {
"hiddenCube": ZoneAndTypeStat(group_size=21, num_groups=9, assignable_count=189),
"followTheShiny": ZoneAndTypeStat(group_size=14, num_groups=4, assignable_count=55),
"fractalMatch": ZoneAndTypeStat(group_size=10, num_groups=8, assignable_count=84),
"ghostObject": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"mirrorMaze": ZoneAndTypeStat(group_size=6, num_groups=13, assignable_count=81),
"lightPillar": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"matchbox": ZoneAndTypeStat(group_size=45, num_groups=9, assignable_count=415),
"lightPattern": ZoneAndTypeStat(group_size=22, num_groups=9, assignable_count=194),
"racingBallCourse": ZoneAndTypeStat(group_size=10, num_groups=9, assignable_count=93),
"racingRingCourse": ZoneAndTypeStat(group_size=7, num_groups=9, assignable_count=64),
"hiddenArchway": ZoneAndTypeStat(group_size=57, num_groups=9, assignable_count=537),
"seek5": ZoneAndTypeStat(group_size=8, num_groups=6, assignable_count=46),
"viewfinder": ZoneAndTypeStat(group_size=21, num_groups=10, assignable_count=202),
"hiddenRing": ZoneAndTypeStat(group_size=60, num_groups=9, assignable_count=563),
"logicGrid": ZoneAndTypeStat(group_size=44, num_groups=14, assignable_count=612),
"gyroRing": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"klotski": ZoneAndTypeStat(group_size=2, num_groups=15, assignable_count=29),
"lockpick": ZoneAndTypeStat(group_size=24, num_groups=8, assignable_count=185),
"match3": ZoneAndTypeStat(group_size=4, num_groups=14, assignable_count=55),
"ryoanji": ZoneAndTypeStat(group_size=6, num_groups=15, assignable_count=94),
"rollingCube": ZoneAndTypeStat(group_size=6, num_groups=13, assignable_count=80),
"memoryGrid": ZoneAndTypeStat(group_size=2, num_groups=14, assignable_count=27),
"completeThePattern": ZoneAndTypeStat(group_size=1, num_groups=20, assignable_count=20),
"musicGrid": ZoneAndTypeStat(group_size=8, num_groups=14, assignable_count=115),
},
5: {
"hiddenCube": ZoneAndTypeStat(group_size=39, num_groups=7, assignable_count=291),
"followTheShiny": ZoneAndTypeStat(group_size=12, num_groups=7, assignable_count=89),
"fractalMatch": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"ghostObject": ZoneAndTypeStat(group_size=29, num_groups=7, assignable_count=207),
"mirrorMaze": ZoneAndTypeStat(group_size=5, num_groups=16, assignable_count=81),
"lightPillar": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"matchbox": ZoneAndTypeStat(group_size=42, num_groups=8, assignable_count=338),
"lightPattern": ZoneAndTypeStat(group_size=18, num_groups=8, assignable_count=137),
"racingBallCourse": ZoneAndTypeStat(group_size=6, num_groups=9, assignable_count=54),
"racingRingCourse": ZoneAndTypeStat(group_size=3, num_groups=12, assignable_count=35),
"hiddenArchway": ZoneAndTypeStat(group_size=69, num_groups=7, assignable_count=517),
"seek5": ZoneAndTypeStat(group_size=8, num_groups=8, assignable_count=64),
"viewfinder": ZoneAndTypeStat(group_size=24, num_groups=8, assignable_count=186),
"hiddenRing": ZoneAndTypeStat(group_size=36, num_groups=8, assignable_count=293),
"logicGrid": ZoneAndTypeStat(group_size=43, num_groups=14, assignable_count=590),
"gyroRing": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"klotski": ZoneAndTypeStat(group_size=9, num_groups=14, assignable_count=129),
"lockpick": ZoneAndTypeStat(group_size=9, num_groups=6, assignable_count=50),
"match3": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"ryoanji": ZoneAndTypeStat(group_size=7, num_groups=14, assignable_count=100),
"rollingCube": ZoneAndTypeStat(group_size=8, num_groups=12, assignable_count=103),
"memoryGrid": ZoneAndTypeStat(group_size=8, num_groups=14, assignable_count=111),
"completeThePattern": ZoneAndTypeStat(group_size=1, num_groups=20, assignable_count=20),
"musicGrid": ZoneAndTypeStat(group_size=3, num_groups=16, assignable_count=47),
},
6: {
"hiddenCube": ZoneAndTypeStat(group_size=43, num_groups=7, assignable_count=299),
"followTheShiny": ZoneAndTypeStat(group_size=14, num_groups=7, assignable_count=100),
"fractalMatch": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"ghostObject": ZoneAndTypeStat(group_size=26, num_groups=7, assignable_count=180),
"mirrorMaze": ZoneAndTypeStat(group_size=6, num_groups=13, assignable_count=78),
"lightPillar": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"matchbox": ZoneAndTypeStat(group_size=26, num_groups=7, assignable_count=182),
"lightPattern": ZoneAndTypeStat(group_size=21, num_groups=7, assignable_count=148),
"racingBallCourse": ZoneAndTypeStat(group_size=6, num_groups=7, assignable_count=39),
"racingRingCourse": ZoneAndTypeStat(group_size=13, num_groups=7, assignable_count=89),
"hiddenArchway": ZoneAndTypeStat(group_size=28, num_groups=7, assignable_count=200),
"seek5": ZoneAndTypeStat(group_size=9, num_groups=7, assignable_count=62),
"viewfinder": ZoneAndTypeStat(group_size=21, num_groups=7, assignable_count=150),
"hiddenRing": ZoneAndTypeStat(group_size=58, num_groups=7, assignable_count=400),
"logicGrid": ZoneAndTypeStat(group_size=43, num_groups=14, assignable_count=602),
"gyroRing": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"klotski": ZoneAndTypeStat(group_size=25, num_groups=14, assignable_count=355),
"lockpick": ZoneAndTypeStat(group_size=15, num_groups=7, assignable_count=101),
"match3": ZoneAndTypeStat(group_size=0, num_groups=0, assignable_count=0),
"ryoanji": ZoneAndTypeStat(group_size=7, num_groups=15, assignable_count=109),
"rollingCube": ZoneAndTypeStat(group_size=10, num_groups=13, assignable_count=130),
"memoryGrid": ZoneAndTypeStat(group_size=3, num_groups=12, assignable_count=37),
"completeThePattern": ZoneAndTypeStat(group_size=1, num_groups=20, assignable_count=20),
"musicGrid": ZoneAndTypeStat(group_size=8, num_groups=15, assignable_count=116),
},
}
# TextKeyUtil::HashString
def unrealengine_hash_string(s):
h = cityhash.CityHash64(s.encode('utf-16le'))
return ((h >> 32) * 23 + h) & 0xFFFFFFFF
# FRandomStream
class UnrealEngineRandomStream:
def __init__(self, seed):
self.seed = seed & 0xFFFFFFFF
def _mutate_seed(self):
self.seed = (self.seed * 196314165 + 907633515) & 0xFFFFFFFF
# random number in [0,1)
def FRand(self):
self._mutate_seed()
return struct.unpack('<f', struct.pack('<i', 0x3F800000 | self.seed >> 9))[0] - 1.0
# random integer number in [a,b]
def RandRange(self, a, b):
return a + int((b - a + 1) * self.FRand())
# check your CityHash with an example
assert unrealengine_hash_string('ghostObject') == 0xFE98FA58
# check your CRC with an example
assert zlib.crc32(bytes([6])) == 0x3b614ab8
def whatever_heapsort(array, size, lo, comparator):
assert False, "Not implemented yet"
def whatever_sort(array, comparator):
if len(array) < 2:
return
maxdepth = int(math.log(len(array)) * 2)
stack = [(0, len(array) - 1, maxdepth)] + [(0, 0, 0)] * 31
stackpos = 0
while stackpos >= 0:
cur_lo, cur_hi, cur_depth_limit = stack[stackpos]
lo = cur_lo
hi = cur_hi
size = cur_hi - cur_lo + 1
while cur_depth_limit:
if size > 8:
r8 = hi + 1
mid = size // 2
array[lo], array[mid+lo] = array[mid+lo], array[lo]
rdx = lo
while True:
rdx += 1
while rdx <= hi and comparator():
rdx += 1
r8 -= 1
while r8 > lo and comparator():
r8 -= 1
if rdx > r8:
break
array[rdx], array[r8] = array[r8], array[rdx]
cur_depth_limit -= 1
array[lo], array[r8] = array[r8], array[lo]
if r8 - lo > hi - rdx:
if lo + 1 < r8:
stack[stackpos] = (lo, r8 - 1, cur_depth_limit)
stackpos += 1
if hi <= rdx:
break
cur_lo = lo = rdx
else:
if hi > rdx:
stack[stackpos] = (rdx, hi, cur_depth_limit)
stackpos += 1
if lo + 1 >= r8:
break
cur_hi = hi = r8 - 1
size = cur_hi - cur_lo + 1
else:
r11 = lo + 1
while hi > lo:
r8 = lo
for rdx in range(r11, hi + 1):
if not comparator():
r8 = rdx
array[r8], array[hi] = array[hi], array[r8]
hi -= 1
break
else:
whatever_heapsort(array, size, lo, comparator)
stackpos -= 1
def calc_spawn_jitter(zone_id, puzzle_type):
seed = unrealengine_hash_string(puzzle_type) + zlib.crc32(bytes([zone_id]))
return UnrealEngineRandomStream(seed).RandRange(-43200, 43200)
def calc_current_block(timestamp, zone_id, puzzle_type):
t = timestamp + calc_spawn_jitter(zone_id, puzzle_type)
num_groups = zone_and_type_stats[zone_id][puzzle_type].num_groups
return t // (86400 * num_groups)
def is_floor_puzzle(puzzle_type):
return puzzle_type in ('rollingCube', 'ryoanji', 'mirrorMaze')
def calc_spawn_group(timestamp, zone_id, puzzle_type, puzzle_id):
block = calc_current_block(timestamp, zone_id, puzzle_type)
stat = zone_and_type_stats[zone_id][puzzle_type]
if not is_floor_puzzle(puzzle_type):
seed = zlib.crc32(struct.pack('<i', puzzle_id)) + zlib.crc32(struct.pack('<q', block))
return UnrealEngineRandomStream(seed).RandRange(0, stat.num_groups - 1)
seed = unrealengine_hash_string(puzzle_type) + zlib.crc32(struct.pack('<q', block))
assignable_index = int(id2puzzle[puzzle_id][index_field][len('index='):])
array = [0] * stat.assignable_count
array[assignable_index] = 1
stream = UnrealEngineRandomStream(seed)
whatever_sort(array, lambda: int(stream.FRand() * 2))
return array.index(1) // stat.group_size
def calc_expected_spawn_timestamp(timestamp, zone_id, puzzle_type, puzzle_id):
block = calc_current_block(timestamp, zone_id, puzzle_type)
num_groups = zone_and_type_stats[zone_id][puzzle_type].num_groups
spawn_group = calc_spawn_group(timestamp, zone_id, puzzle_type, puzzle_id)
return (block * num_groups + spawn_group) * 86400 - calc_spawn_jitter(zone_id, puzzle_type)
def find_incompatible(timestamp, zone_id, puzzle_type, puzzle_id, incompatibles):
if not incompatibles:
return []
result = []
my_spawn_timestamp = calc_expected_spawn_timestamp(timestamp, zone_id, puzzle_type, puzzle_id)
for other_id in incompatibles.split(','):
other_id = int(other_id)
other = id2puzzle[other_id]
assert other[0] == 'world'
other_zone_id = int(other[zone_field][len('zone='):])
other_puzzle_type = other[type_field][len('type='):]
other_spawn_timestamp = calc_expected_spawn_timestamp(timestamp, other_zone_id, other_puzzle_type, other_id)
if my_spawn_timestamp < other_spawn_timestamp < my_spawn_timestamp + 86400 or my_spawn_timestamp < other_spawn_timestamp + 86400 < my_spawn_timestamp + 86400:
seed = zlib.crc32(struct.pack('<i', puzzle_id))
r = UnrealEngineRandomStream(seed).FRand()
if r >= 0.5 or puzzle_id >= other_id:
result.append(other_id)
return result
def make_spawn_plan(timestamp, zone_id, puzzle_type):
stat = zone_and_type_stats.get(zone_id, {}).get(puzzle_type)
if stat is None or stat.num_groups == 0:
print("Nothing to plan")
return
block = calc_current_block(timestamp, zone_id, puzzle_type)
block_begin = block * stat.num_groups * 86400 - calc_spawn_jitter(zone_id, puzzle_type)
block_end = block_begin + stat.num_groups * 86400
print("Planning the block from {} aka {} to {} aka {} in zone {} for type {}".format(
block_begin, time.strftime('%Y-%m-%dT%H:%M:%S%z', time.localtime(block_begin)),
block_end, time.strftime('%Y-%m-%dT%H:%M:%S%z', time.localtime(block_end)),
zone_id, puzzle_type))
groups = [[] for _ in range(stat.num_groups)]
for puzzle in zone_and_type2puzzles[(zone_id, puzzle_type)]:
puzzle_id = int(puzzle[id_field][len('id='):])
spawn_group = calc_spawn_group(timestamp, zone_id, puzzle_type, puzzle_id)
if puzzle[0] == 'world':
spawn_type = int(puzzle[spawn_field][len('spawn='):])
if spawn_type < 2: # does not participate in placement mechanics
print("puzzle {} is {} spawned, and that's all for it".format(puzzle_id, ["always", "never"][spawn_type]))
continue
incompatible = find_incompatible(timestamp, zone_id, puzzle_type, puzzle_id, puzzle[incompatible_field][len('incompatible='):])
if incompatible:
print("puzzle {} will not spawn in this block due to conflict with puzzle(s) {}".format(puzzle_id, incompatible))
continue
if spawn_group >= stat.num_groups:
print("puzzle {} will not spawn in this block because there are too few slots".format(puzzle_id))
continue
groups[spawn_group].append(puzzle_id)
for i in range(stat.num_groups):
print("Group #{}\n from {} aka {}\n to {} aka {}\n will try to spawn puzzles {}".format(
i,
block_begin + i * 86400, time.strftime('%Y-%m-%dT%H:%M:%S%z', time.localtime(block_begin + i * 86400)),
block_begin + (i + 1) * 86400, time.strftime('%Y-%m-%dT%H:%M:%S%z', time.localtime(block_begin + (i + 1) * 86400)),
groups[i]))
if __name__ == '__main__':
parser = argparse.ArgumentParser()
parser.add_argument("--timestamp", type=int, help="make spawn plan for this moment of time (default = current time)")
parser.add_argument("--zone", type=int, help="zone id, from 2 to 6 (default = loop over all zones)")
parser.add_argument("--type", help="puzzle type (default = loop over all puzzle types)")
args = parser.parse_args()
if args.timestamp is None:
args.timestamp = int(time.time())
for zone in ([args.zone] if args.zone is not None else range(2, 7)):
zone_stats = zone_and_type_stats.get(zone, {})
zone_types = [k for k in zone_stats if zone_stats[k].num_groups > 0]
for type_ in ([args.type] if args.type is not None else zone_types):
make_spawn_plan(args.timestamp, zone, type_)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment