This is a picture of Stepmania, a free-software rhythm video game. You play by following along with footwork shown on-screen. It's good fun. Part of the intellectual fun is the presence of patterns—actually, there's room for a theory about what makes good choreography. Something about motifs that recur and resolve, load balancing the left and right feet, keeping within physiological limits, and creating interesting combinations out of a finite set of moves.

Where is this theory? There are some online tutorials on the
*mechanics* of making choreography for these games—what software to
use, for example. But I can't find anything on the craft of it—how
to not just make a song, but make a *satisfying* song.

This article is a small step in that direction. I present a theory
about how players choose which foot to step on which arrow. I argue
that the choice of foot varies based on how you've positioned your
body up to that point, and where you'll need to move next. The theory
consists of three constraints that I developed by observing what I
naturally do during play. I believe they accurately and completely
capture how *I* decide what foot to use, although I suspect other more
advanced players may be less constrained.

The constraints are simple, but powerful. They capture one piece of what it means to be a good song. Whenever they're violated, the result is awkward choreography. So if you're a choreography designer, you can use these constraints as a rubric. That is the key contribution of this work: clearly articulated rules that, when followed, produce more elegant dance patterns.

I'll explain the three principles, then show an implementation in
Python that can read choreography from a stepmania `.sm`

file and
assign footwork to it. It produces footwork by resolving the three
constraints.

## 1 Three constraints

The three contraints are:^{1}

- The home principle
- Step on L with the left foot and R with the right foot.
- The alternation principle
- As a rule, you should alternate stepping with the left and right foot. You may, however, step on the same arrow repeatedly with the same foot; see below.
- The min-spin principle
- When the same foot must step twice consecutively, it is especially good to keep it on the same arrow and especially bad to make it leap to the arrow on the opposite side (e.g. U to D).

Here are some follow-up remarks:

- Note that the home principle incidentally constrains you to always orient toward the screen.
- While the home principle establishes the footwork for L and R, the
alternation principle helps disambiguate the footwork for U and D.
For example, if you have the sequence L-U, you step it as
L
^{ʟ}-U^{ʀ}. - Together, these two rules explain why stepping a pattern like L-U-R feels so awkward: you must violate either the home principle or the alternation principle. This is the smallest possible awkward step sequence; uncovering it is one special achievement of the theory.
- Sometimes, large sections of a song can remain technically ambiguous: if your song begins U, D, U, D, U, D, U, D, L, then the Us and Ds remain ambiguous until you finally see the L. Note that this also implies that future arrows can influence choreography earlier in the song. (The constraints are about neighboring notes, independent of temporal order.) Hence repeated practice trials are sometimes necessary in order to obtain optimal constraint-satisfying footwork.
- There are six double-arrow combinations: UL UR UD LR DL DR. Note that the home principle completely determines footwork for all of these except UD. The min-spin principle helps disambiguate footwork for the UD case.
- For example, if you have to step DR-UD, the footing on DR is
D
^{ʟ}R^{ʀ}by the home principle. The footing on UD is initially ambiguous on its own: U^{ʟ}D^{ʀ}or U^{ʀ}D^{ʟ}? But the min-spin principle says D^{ʟ}R^{ʀ}-U^{ʟ}D^{ʀ}would be bad because the left foot would go from D to U in a single step. So the correct transition is D^{ʟ}R^{ʀ}-D^{ʟ}U^{ʀ}, which satisfies all the constraints. - You can prove to yourself that if UD follows one of the other six
double-arrow combinations, its footwork is often completely
determined:
- LR-UD (ambiguous)
- LU-UD (left foot on D)
- LD-UD (left foot on U)
- UR-UD (left foot on U)
- UD-UD (ambiguous)
DR-UD (left foot on D)

UD remains ambiguous in only two cases (preceded by LR or UD). In the rest, the footwork is completely determined by the home and min-spin principles.

- When footings remain ambiguous, they're equally easy to do either way. For example LR-UD-LR can do footing for UD any which way. This is consistent with my experience.
- As predicted by the theory, LD-UD-DR is an awkward double-step
transition. One way to look at it is that UD has conflicting
footing cues from each side: Based on L
^{ʟ}D^{ʀ}-UD-DR, it should be left foot on U. Based on LD-UD-D^{ʟ}R^{ʀ}, it should be left foot on down. Another way of looking at it is the progression forces an awkward move: L^{ʟ}D^{ʀ}-UD-DR forces L^{ʟ}D^{ʀ}-U^{ʟ}D^{ʀ}-DR, which when you continue to DR, requires either a violation of the home principle (*left on R) or violation of the min-spin principle (*left goes from U to D in a single step) - Technical aside: In terms of automata theory, the footing
constraints form a
*regular language*; you can assign footing using a finite state machine.^{2}

## 2 Python code

The code consists of utilities for (1) extracting note data out of
stepmania `.sm`

song files, and (2) assigning footing to the notes by
applying our three principles. Note extraction involves some careful
parsing, but the program for assigning footwork is pretty
straightforward:

There are three constraint checkers, corresponding to the three enumerated principles. Each one has the same form: it takes in a beat of the song as well as the most recent beat that came before it. Here, a beat is an arrow or arrow pair, along with a footing assignment. The constraint checker returns True if the assignment follows the rule, or False if it violates it.

# Throughout, feet is a dictionary assigning a single arrow or arrow # pair to footing, e.g. {"U" : "L", "R" : "R"} def enforce_home_principle(feet, _) : if feet.get("L") == "R" or feet.get("R") == "L" : return False return True def enforce_alternation_principle(feet, feet_prev) : if feet_prev is None : return True if len(feet) > 1 or len(feet_prev) > 1 : return True # Double steps reset the alternation counter # Strong version: # If the arrows are the same, the footing must be the same. # If the arrows are different, the footing must be different. return (list(feet.values()) == list(feet_prev.values())) == (list(feet.keys()) == list(feet_prev.keys())) def enforce_minspin_principle(feet, feet_prev) : if feet_prev is None : return True pairs = [(feet.get("L"), feet_prev.get("L")), (feet.get("R"), feet_prev.get("R"))] # Neither foot may go immediately between U and D. if ("U","D") in pairs or ("D", "U") in pairs : return False return True

There is also code for iterating over all of the beats in the song, passing pairs of consecutive notes to a constraint checker, and returning the valid assignments. I run the iterator once for each individual constraint, and then again in the reverse direction (since the constraint checker is direction-specific, but the principle is not).

# Here, domain_steps is an ordered list of arrows or arrow-pairs in a # song; the arrows are paired with a list of all possible footing # assignments. The iterate function applies a constraint checker to # consecutive arrow pairs, eliminating any incompatible footing # assignments. def iterate(domain_steps, constraint_fn) : labeled_steps = [(index, step, domain) for (index, (step, domain)) in zip(range(len(domain_steps)), domain_steps)] prev_feet = None for (index, step, domain) in labeled_steps : if len(step.arrows()) == 0 : continue new_domain = list(filter(lambda x: constraint_fn(x, prev_feet), domain)) if not new_domain : print("! Unsatisfiable constriant at "+str((index,domain))+" "+str(prev_feet), constraint_fn.__name__) elif len(new_domain) == 1 : prev_feet = new_domain[0] labeled_steps[index] = (index, step, new_domain) else : prev_feet = None return [(step, domain) for (_, step, domain) in labeled_steps]

### 2.1 COMPLETE CODE FILE

# 2020/05/24 # PROGRAM FOR READING AND ANALYZING STEPMANIA STEPFILES # (C)2020 Dylan Holmes. Licensed under GPL v3. import re from functools import reduce from itertools import permutations rt re from functools import reduce from itertools import permutations path_example = "/opt/stepmania/Songs/Valex's Magical 4-Arrow Adventure 9/Bass Bomb/Bass Bomb.sm" ARROW_CHAR = {"L" : "l", "D" : "d", "U" : "u", "R" : "r"} MINIMUM_MATCH_SIZE = 4 # ------- BASIC UTILITIES def gcd(a,b) : if a < b : (a,b) = (b,a) r = a % b if r == 0 : return b return gcd(a, r) def lcm(a,b=0) : if b == 0 : return a return int(a*b / gcd(a,b)) PERM4 = list(permutations(range(4))) def permute(indexes, coll) : return [coll[i] for i in indexes] # ------- STEPFILE PARSING FUNCTIONS class Beat : def __init__(self, quarto, subdivs = None) : self.subdivs = subdivs self.quarto = quarto def __repr__(self) : A = self.quarto+'-'+str(self.subdivs) B = ''.join([ARROW_CHAR[direction] if activity != '0' else '' for (direction, activity) in zip("LDUR", self.quarto)]) or '_' return B return self.quarto return A+"\t"+B def is_stasis(self) : return self.quarto == "0000" def simultaneous(self) : return len([x for x in list(self.quarto) if x != '0']) # A+"\t"+B def left(self) : return int(self.quarto[0]) def down(self) : return int(self.quarto[1]) def up(self) : return int(self.quarto[2]) def right(self) : return int(self.quarto[3]) def arrows(self, query=None) : letters = "".join([x*int(self.quarto[i] != '0') for (x,i) in zip(list("LDUR"), range(4))]) if query is None : return letters else : return all([x in letters for x in query]) def stepfile_parse_notes(text) : segments = re.split(r":\n*\s*", text) notes = segments[-1].split("\n") challenge_level = segments[2] debug = print if challenge_level == 'Easy' else lambda x:None # debug(challenge_level) beats = [] current_measure = [] while notes : line = notes.pop(0) line = re.sub(r"\/\/.*", "", line) if not line : continue if re.search(r"[,;]", line) : # END OF MEASURE subdivs = len(current_measure) for b in current_measure: b.subdivs = subdivs beats += current_measure current_measure = [] else : current_measure += [Beat(line)] segments[-1] = beats return dict(zip(('chart-type', 'author', 'difficulty', 'meter','radar','notes'), segments)) def stepfile_read(path) : with open(path) as f: read_data = f.read() # print(read_data) match = re.findall(r"#([A-Z]+):([^;]*);", read_data, re.DOTALL) song_dict = {} for m in match : (key, val) = m if key != "NOTES" : song_dict[key] = val else : song_dict["NOTES"] = song_dict.get("NOTES", []) + [stepfile_parse_notes(val)] return song_dict def stepfile_print_beats(beats) : measure_lengths = set([beat.subdivs for beat in beats]) print(measure_lengths) common_measure = reduce(lcm, measure_lengths) count = 1 beat_index = 0 for b in beats : print(b, "\t\t", beat_index, "\n" * (common_measure // b.subdivs - 1)) # print(b, "\t\t",count, "\n" * (common_measure // b.subdivs - 1)) count += common_measure // b.subdivs beat_index += 1 pass def align_beat(beat1, beat2, permset=None) : if beat1.subdivs != beat2.subdivs : # beats must have the same length return None if sorted(beat1.quarto) != sorted(beat2.quarto) : # beats must have the same activity signature # (number of notes, and how those notes are played) return None if permset is None : permset = PERM4 # print([x for x in x.quarto], [y.quarto[i] for i in PERM4[0]] ) return [abcd for abcd in permset if permute((0,1,2,3), beat1.quarto) == permute(abcd, beat2.quarto)] def interestingness(match) : # (root_index, subject_index, match_length, patterns, beats) match_length = match[2] note_rhythms= [x.subdivs for x in match[4]] note_types = set(note_rhythms) note_variety = sum([1 if a == b else 0 for (a,b) in zip(note_rhythms, note_rhythms[1:])]) return -len(note_types), -match[2] # return note_variety, -match[2] def align_beat_multiple(beats) : """Find patterns of similar rhythms in the song""" closed_matches = [] # format: [root_index, final_index, match_length, match_example?] for root_index in range(len(beats)) : if beats[root_index].is_stasis() : # I've decided to ignore matches that start with 'rest' # notes. continue matching_indexes = [idx for idx in range(root_index+1,len(beats)) if align_beat(beats[root_index], beats[idx])] matches = [(idx, align_beat(beats[root_index], beats[idx]), [beats[idx]]) for idx in matching_indexes] match_length = 1 while matches : match_length += 1 extended_matches = [] for (i, ptns, bs) in matches : if i + match_length - 1 < len(beats) : # no out of bounds error ptns_new = align_beat(beats[root_index + match_length - 1], beats[i + match_length - 1], ptns) if ptns_new : # next beat also matches extended_matches += [(i, ptns_new, bs + [beats[i+match_length-1]])] continue # THE MATCH HAS OVERREACHED; ADD IT TO THE CLOSED LIST. match = (root_index, i, match_length-1, ptns, bs) # --- check for "transitive duplicates" before adding # match1 : its subject index is our root index. # match2 : its subject index is our subject index. # both matches have the same root index. both matches # have the same length, and the same length as our # match. def has_duplicate(closed_matches, match) : # check for subset duplicates for m in closed_matches : diff = m[2] - match[2] # difference in match lengths if diff <= 0 : continue if m[0] + diff == match[0] and m[1] + diff == match[1] : return True # check for transitive duplicates potential_duplicates = [m for m in closed_matches if m[2] == match[2]] for m1 in potential_duplicates : if m1[1] != match[0] : continue for m2 in potential_duplicates : if m2[1] != match[1] or m1[0] != m2[0] : continue return True return False #if has_duplicate(closed_matches, match) : # pass # print(True) if match_length -1 >= MINIMUM_MATCH_SIZE and not has_duplicate(closed_matches, match) : closed_matches += [match] matches = extended_matches closed_matches = sorted(closed_matches, key=interestingness) freq_count = {} for (from_index, to_index, match_length, ptns, bs) in closed_matches : freq_count[(from_index, match_length)] = freq_count.get((from_index, match_length), 0) + 1 closed_matches = sorted(closed_matches, key=lambda x : freq_count.get((x[0],x[2]),0), reverse=True ) return closed_matches, freq_count # return closed_matches # print(beats[root_index]) def chunked_beats(steps) : alignments, freqs = align_beat_multiple(steps) index = 0 letters = list("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz") named_patterns = {} labeled_steps = list(map(list,zip(steps, [None]*len(steps), range(len(steps))))) while 1 : # Find next step that isn't part of a pattern yet index = None for (x, label, i) in labeled_steps : if label is None : index = i break if index is None : break # Pick which pattern it's supposed to be match = None for m in alignments : if m[0] == index : # all terms in sequence are unlabeled if all([x[1] is None for x in labeled_steps[m[0]:m[0]+m[2]]]) : match = m break if match is None : # This note is not part of any pattern labeled_steps[index][1] = labeled_steps[index][0] # print(index, "none match") continue # Give this pattern a unique identifier signature = (match[0], match[2]) named_patterns[signature] = named_patterns.get(signature) or letters.pop(0) symbol = named_patterns[signature] signature = (match[0], symbol, match[2:]) # Find all other instances of this pattern all_matches = [] for m in alignments : if m[0] == match[0] and m[2] == match[2] : # same from_index and match_length # all terms in sequence are unlabeled if all([x[1] is None for x in labeled_steps[m[1]:m[1]+m[2]]]) : all_matches += [m] indexes = [match[0]] + [m[1] for m in all_matches] # greedy principle to ensure that labeling will not clobber # itself kept_indexes = [] while indexes : i = indexes.pop(0) kept_indexes += [i] indexes = list(filter(lambda j: not (i <= j < i+match[2]), indexes)) indexes = kept_indexes # label the match throughout each range for offset in range(match[2]) : for index in indexes : # if labeled_steps[index + offset][1] : # print(symbol, indexes, match[2], labeled_steps[index + offset]) # raise Exception labeled_steps[index + offset][1] = symbol, index, match[4] for x in labeled_steps : print(x) # map(print,labeled_steps) print(sorted(freqs.items(), key=lambda x: -x[1])) def assign_footwork_new(steps) : domain_steps = [] for step in steps: arrows = step.arrows() if not arrows : domain_steps += [(step, [{}])] elif len(arrows) == 1 : domain_steps += [(step, [{"L" : arrows[0]}, {"R" : arrows[0]}])] else : domain_steps += [(step, [{"L" : arrows[0], "R" : arrows[1]}, {"R" : arrows[0], "L" : arrows[1]}])] strict_repetition_mode = True # for alternation def enforce_home_principle(feet, _) : if feet.get("L") == "R" or feet.get("R") == "L" : return False return True def enforce_alternation_principle(feet, feet_prev) : if feet_prev is None : return True if len(feet) > 1 or len(feet_prev) > 1 : return True # I guess double steps reset the alternation counter if strict_repetition_mode : # must step with new foot on new arrow AND # must step with same foot on same arrow return (list(feet.values()) == list(feet_prev.values())) == (list(feet.keys()) == list(feet_prev.keys())) else : # every time you step on a new arrow, you must use a new foot. # if it's the same arrow, you can use any foot return (list(feet.values()) == list(feet_prev.values())) or (list(feet.keys()) != list(feet_prev.keys())) def enforce_minspin_principle(feet, feet_prev) : if feet_prev is None : return True pairs = [(feet.get("L"), feet_prev.get("L")), (feet.get("R"), feet_prev.get("R"))] if ("U","D") in pairs or ("D", "U") in pairs : return False return True def iterate(domain_steps, constraint_fn) : labeled_steps = [(index, step, domain) for (index, (step, domain)) in zip(range(len(domain_steps)), domain_steps)] prev_feet = None for (index, step, domain) in labeled_steps : if len(step.arrows()) == 0 : continue new_domain = list(filter(lambda x: constraint_fn(x, prev_feet), domain)) if not new_domain : print("! Unsatisfiable constriant at "+str((index,domain))+" "+str(prev_feet), constraint_fn.__name__) elif len(new_domain) == 1 : prev_feet = new_domain[0] labeled_steps[index] = (index, step, new_domain) else : prev_feet = None return [(step, domain) for (_, step, domain) in labeled_steps] domain_steps = iterate(domain_steps, enforce_home_principle) domain_steps = iterate(domain_steps, enforce_alternation_principle) domain_steps = iterate(domain_steps, enforce_minspin_principle) domain_steps = iterate(domain_steps[::-1], enforce_home_principle)[::-1] domain_steps = iterate(domain_steps[::-1], enforce_alternation_principle)[::-1] domain_steps = iterate(domain_steps[::-1], enforce_minspin_principle)[::-1] for (step, domain) in domain_steps : if len(domain) == 1 : print (step, domain[0]) else : print (step, "\t", domain) print(domain_steps) return domain_steps def assign_footwork(steps) : labeled_steps = [(step, None) for step in steps] print("footwork") debug = lambda s: print("! "+s) def complete_other_foot(arrows, label) : """If only one foot has been assigned a label, assign the other foot accordingly and return the label.""" if len(arrows) < 2 or len(label) == 2 : return label for (side,other) in [("L","R"), ("R","L")] : if label.get(side) : other_label = [x for x in arrows if x != label.get(side)][0] label[other] = other_label return label def principle_home(labeled_steps) : labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)] # THE HOME PRINCIPLE for (i, s, label) in labeled_steps : if label is not None : # constraint checking for assigned feet if label.get("L") == "R" or label.get("R") == "L" : debug("Home principle violation", (i,s,label)) continue feet = {} # {L : ?, R : ?} if s.left() : feet["L"] = "L" if s.right() : feet["R"] = "R" feet = complete_other_foot(s.arrows(), feet) # if 0 < len(feet) < s.simultaneous() == 2 : # current_foot = list(feet)[0] # other_foot = "R" if current_foot == "L" else "L" # feet[other_foot] = "D" if s.down() else "U" if feet : labeled_steps[i] = (i, s, feet) return [(s, feet) for (i,s,feet) in labeled_steps] def principle_alternation(labeled_steps) : # THE ALTERNATION PRINCIPLE labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)] most_recent_step = None for (i, s, label) in labeled_steps : if s.is_stasis() : labeled_steps[i] = (i, s, {}) continue # ignore "rests" if label is not None : # question: how does alternation principle apply to # double-steps? does the doublestep reset the alternation # counter? ignore it? increment it? # TODO: constraint checking for assigned feet if len(label) > 1 : most_recent_step = None # resets the counter else : most_recent_step = (s,label) continue if most_recent_step and s.simultaneous() == 1 : # everything but UD (prev_step, prev_feet) = most_recent_step # Heavyhanded: /require/ repeated steps to have same foot if prev_step.quarto == s.quarto : # debug # prev_feet["samequarto"] = True labeled_steps[i] = (i, s, prev_feet) continue else : current_foot = list(prev_feet)[0] other_foot = "R" if current_foot == "L" else "L" feet = {} feet[other_foot] = "D" if s.down() else "U" labeled_steps[i] = (i, s, feet) most_recent_step = (s, feet) return [(s, feet) for (i,s,feet) in labeled_steps] def principle_minspin(labeled_steps) : # THE MIN-SPIN PRINCIPLE labeled_steps = [(i, step, label) for (i, (step,label)) in zip(range(len(steps)), labeled_steps)] most_recent_step = None for (i, s, label) in labeled_steps : print(">", (i,s.quarto,label)) if s.is_stasis() : continue # ignore "rests" if label is not None : # TODO: constraint checking for assigned feet most_recent_step = (s,label) continue (prev_step, prev_label) = most_recent_step print(i, most_recent_step, s.arrows()) label = {} for (foot, arrow) in prev_label.items() : if arrow in s.arrows() : label[foot] = arrow label = complete_other_foot(s.arrows(), label) labeled_steps[i] = (i, s, label) return [(s, feet) for (i,s,feet) in labeled_steps] labeled_steps = principle_home(labeled_steps) labeled_steps = principle_alternation(labeled_steps) # labeled_steps = principle_alternation(labeled_steps[::-1])[::-1] labeled_steps = principle_minspin(labeled_steps) # principle_alternation(labeled_steps) labeled_steps = [(i, s, label) for (i, (s,label)) in zip(range(len(labeled_steps)), labeled_steps)] for x in labeled_steps: print("X", x[0], x[1], x[2]) # ------------- SANDBOX steps = stepfile_read(path_example) target_difficulty = 'Easy' print (target_difficulty) # GET THE EASY SONG IF ANY steps = filter(lambda x: x.get('difficulty') == target_difficulty, steps.get("NOTES")) steps = list(steps)[0]['notes'] steps = assign_footwork_new(steps)

## Footnotes:

^{1}

**L**}eft, {

**D**}own, {

**U**}p, and {

**R**}ight arrows. And I indicate footwork with superscripts, so for example stepping on the Up arrow with your right foot is U

^{ʀ}.

^{2}

^{ʟ}D

^{ʀ}, U

^{ʀ}D

^{ʟ}, etc.). A nondeterministic finite state machine enforces the constraints by allowing transitions like \[\mathrm{L^LU^R}\xrightarrow{ud}\mathrm{U^RD^L}\] and forbidding transitions like \[\mathrm{L^LU^R}\xrightarrow{ud}\mathrm{U^LD^R}.\]If the automaton accepts a sequence of arrows, then it's a valid nonawkward choreography, and the suitable footing assignment is given by the sequence of states leading to acceptance. (There may be multiple sequences if the parse is ambiguous.)