Puyo Puyo!! 20th Anniversary/Upcoming Pair Randomizer
The pair randomization algorithm for Puyo Puyo!! 20th Anniversary Tsuu mode has been carried forward in nearly every Puyo game since release, including Puyo Puyo Champions, the competitive standard currently used by SEGA's professional championship circuit.
Methodology
Reverse engineering was performed on an NDS rom of Puyo Puyo!! 20th Anniversary using a combination of Ghidra and DeSmuME's debugging capabilities. Hints for important memory addresses were taken from this tweeter, who appears to have previously reverse engineered the algorithm in 2017 but did not publish the full process.
Summary
The basic algorithm is:
- Map the random colors used this game
- Fill and shuffle the 3-color puyo pool
- Fill and shuffle the 4-color puyo pool
- Fill and shuffle the 5-color puyo pool
- Copy the first 4 puyos from the 3-color pool to the 4- and 5-color pools
Memory offsets are all stored relative to the address stored in the pointer located at 0x211a6dc. Most of the time, this contains the address 0x0216fad8, but may sometimes lead elsewhere. All memory offsets in the writeup assume 0x0216fad8 as the base pointer.
Random Number Generator
The RNG is a linear congruential generator of the following form:
seed = seed * 0x5d588b65 + 0x00269ec3
The actual function that performs the shift is located at 0x02049b9c, and also performs a modulo operation on the new seed by way of a multiply-and-shift calculation. The seed is stored as a uint32 at the address 0x0216fb00. However, the initial seed sent at the start of the pair generation operation is a uint16, and the result of the modulo operation is a uint16. Therefore, the total number of possible games is 0xffff+1=65536.
Color Mapping
The puyos in the pair pools are stored as integers from 0-4. These indicies are translated to colors by way of the map generated by the function at 0x02041c74. For example, a colormap of YBGRP means that a raw int sequence of 01201333 corresponds to a piece sequence of YB,GY,BR,RR.
The map is generated by randomly popping an element from the sequence RGBYP until no elements remain. The RNG is called 5 times in total. The results are stored at 0x0216fc9c with each element taking up 32 bits and shifted up by 1 (so instead of 0-4, they range from 1-5).
Fill and Shuffle
The fill and shuffle function is found at 0x02041968. Each puyo is stored as one byte, with pair pools for each color stored at the following locations:
0x0216fcb0 - 3 colors 0x0216fdb0 - 4 colors 0x0216feb0 - 5 colors
First, the pool is filled in sequential order with its relative offset modulo the number of colors, up to 256 puyos. For example, the 4 color pool is filled with 0,1,2,3,0,1,2,3,0,1,2,3,etc...
Then, a check is performed *(0x0216FB74) >= 0x8000. This controls whether an alternate shuffle algorithm is used (appears to be unused for Tsuu).
Shuffling begins at 0x02041aa4, and is done in 3 passes. Each pass consists of swapping 2 random puyos in adjacent "rows", where each row 0x10 bytes long in the first pass, 0x20 bytes long in the second pass, and 0x40 bytes long in the final pass. Choose 1 random puyo in the upper row and 1 random puyo in the lower row. Swap the 2 values. Repeat this N times, where N is half the length of the row. Then shift down by 1 row, then perform the series of swaps again. Continue the down shifts until the end of the pool has been reached.
In total, the number of swaps performed is 15*8 in the first pass, 7*16 in the second pass, and 3*32 in the third pass. Given 2 calls to the RNG per swap, 3 separate pools, and 5 calls to the RNG during the color mapping process, a total of 1973 RNG calls are made over the course of the pair generation process.
Pseudocode
The following Python code can be used to exactly create and search through all possible games generated by the algorithm. It closely matches the disassembled NDS code, with some liberties and Pythonic shortcuts taken for brevity.
import ctypes
import random
import argparse
import pickle
def rand_mod(seed_init, modulo=0):
uint32_seed = ctypes.c_uint32(seed_init).value
seed = (uint32_seed * 0x5D588B65 + 0x00269EC3) & 0xFFFFFFFF
result = seed >> 0x10
if modulo != 0:
result = (result * modulo) >> 0x10
return seed, result
def shuffle(seed_init, n_colors):
seed = seed_init
puyos = [i % n_colors for i in range(0x100)]
# swap 2 random elements from adjacent rows of varying length
for length in [0x10*2**exp for exp in range(3)]: # 0x10, 0x20, 0x40
n_rows = 0x100 // length
for row in range(n_rows - 1):
for n_swaps in range(length >> 1):
seed, i1 = rand_mod(seed, length)
i1 = row * length + i1
seed, i2 = rand_mod(seed, length)
i2 = (row + 1) * length + i2
temp = puyos[i1]
puyos[i1] = puyos[i2]
puyos[i2] = temp
return seed, puyos
def create_table(seed_init):
seed = seed_init
puyos = {}
for n_colors in range(3,6):
seed, puyos[n_colors] = shuffle(seed, n_colors)
# ensure first two pairs are 3-color by copying from 3-color table
puyos[4][:4] = puyos[3][:4]
puyos[5][:4] = puyos[3][:4]
return seed, puyos
def create_colormap(seed_init):
seed = seed_init
colors = '_RGBYP' # this starts at 1, for Reasons
cmap = ''
c_left = 5
for _ in range(5):
seed, i = rand_mod(seed, c_left)
i = i + 1
cmap += colors[i]
colors = colors[:i] + colors[i+1:]
c_left = c_left - 1
return seed, cmap
def create_rainbow(num_seeds):
table = {}
for seed_init in range(num_seeds):
seed, cmap = create_colormap(seed_init)
seed, puyos = create_table(seed)
table[seed_init] = (cmap, puyos)
return table
if __name__ == "__main__":
parser = argparse.ArgumentParser(
prog='PP20th RNG Tool',
description='Displays and searches RNG seeds for Puyo Puyo!! 20th Anniversary Tsuu'
)
parser.add_argument('-s', '--seed', type=lambda x: int(x,0), default=None,
help='display the puyos for this (uint16 hex) seed')
parser.add_argument('--rand', action='store_true',
help='use a random seed instead')
parser.add_argument('-f', '--find', type=str, default=None,
help='list of puyos to search for in the rainbow table')
parser.add_argument('-n', '--ncolors', type=int, default=4,
help='number of colors to get')
parser.add_argument('--raw', action="store_true",
help='display results as raw numbers instead of mapped colors')
parser.add_argument('--filename', type=str, default="puyo20_seeds.p",
help='filename to load the seeds from')
args = parser.parse_args()
disp = lambda p: str(p[0])+str(p[1]) if args.raw else cmap[p[0]]+cmap[p[1]]
# print the table for a given seed
if args.seed is not None or args.rand:
seed_init = random.randint(0x10000) if args.rand else args.seed
seed, cmap = create_colormap(seed_init)
seed, puyos = create_table(seed)
print(f'seed: 0x{args.seed:04x} -> 0x{seed:08x}')
print(f"colormap: {cmap[:args.ncolors]}({cmap[args.ncolors:]})")
print(','.join(disp(p) for p in zip(*[iter(puyos[args.ncolors])]*2)))
# search for the corresponding starting puyos
if args.find:
try:
table = pickle.load(open(args.filename, "rb"))
# generate rainbow table if it doesnt already exist
except FileNotFoundError:
print(f"Saving rainbow table to {args.filename}, this may take a while...")
table = create_rainbow(0x10000)
pickle.dump(table, open(args.filename, "wb"))
found = 0
searchterm = args.find
for seed, (cmap,puyos) in table.items():
as_color = ''.join(cmap[p] for p in puyos[args.ncolors])
if as_color[:len(searchterm)] == searchterm:
as_fmt = ','.join(disp(p) for p in zip(*[iter(puyos[args.ncolors])]*2))
print(f'{seed:04x},{as_fmt}')
found = found + 1
if found == 0:
print("No matches found.")