# Dance Dance Resolution 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:

1. Note that the home principle incidentally constrains you to always orient toward the screen.
2. 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ʀ.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.

8. 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.
9. 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)
10. 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
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)
def down(self) :
return int(self.quarto)
def up(self) :
return int(self.quarto)
def right(self) :
return int(self.quarto)

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
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))
with open(path) as f:

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] )

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

note_rhythms= [x.subdivs for x in match]
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
# return note_variety, -match

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() :
# 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 - match # difference in match lengths
if diff <= 0 :
continue
if m + diff == match and m + diff == match :
return True
# check for transitive duplicates
potential_duplicates = [m for m in closed_matches if m == match]
for m1 in potential_duplicates :
if m1 != match :
continue
for m2 in potential_duplicates :
if m2 != match or m1 != m2 :
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,x),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 == index :
# all terms in sequence are unlabeled
if all([x is None for x in labeled_steps[m:m+m]]) :
match = m
break
if match is None :
# This note is not part of any pattern
labeled_steps[index] = labeled_steps[index]
#           print(index, "none match")
continue

# Give this pattern a unique identifier
signature = (match, match)
named_patterns[signature] = named_patterns.get(signature) or letters.pop(0)
symbol = named_patterns[signature]
signature = (match, symbol, match[2:])

# Find all other instances of this pattern
all_matches = []
for m in alignments :
if m == match and m == match :
# same from_index and match_length

# all terms in sequence are unlabeled
if all([x is None for x in labeled_steps[m:m+m]]) :
all_matches += [m]

indexes = [match] + [m 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), indexes))
indexes = kept_indexes

# label the match throughout each range
for offset in range(match) :
for index in indexes :
# if labeled_steps[index + offset] :
#     print(symbol, indexes, match, labeled_steps[index + offset])
#     raise Exception
labeled_steps[index + offset] = symbol, index, match

for x in labeled_steps :
print(x)
# map(print,labeled_steps)
print(sorted(freqs.items(), key=lambda x: -x))

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},
{"R" : arrows}])]
else :
domain_steps += [(step, [{"L" : arrows,
"R" : arrows},
{"R" : arrows,
"L" : arrows}])]

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
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)
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)]
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)
#     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)
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, x, x)

# ------------- SANDBOX

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)['notes']
steps = assign_footwork_new(steps)


## Footnotes:

1
Notation: I use single-letter abbreviations for the {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
Specifically, the alphabet symbols are the ten arrow types (L, UR, etc.) and the states are all thirteen legal footing assignments for each arrow type (Uʟ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.)

Date: 2020/May/25

Created: 2020-05-25 Mon 21:20

Validate