«demo: backtracking constraint solver» by jamshark70
on 24 Sep'11 09:30 inA quick and dirty recursive approach to finding valid solutions for a set of constraints by backtracking.
The constraints are: Given a set of phrases (defined as Pbinds), randomly string them together so that the total duration is one "bar" (where the bar could have any number of beats, of course -- here it's 9). A phrase can be truncated, but it's not valid to change the duration of a note.
That's for the first version of the ~backtracking function. The second version adds one more constraint: the bar must not end with a 16th note. The only difference between the two versions is an additional condition in the 'case' statement, which causes the solution to be rejected if the last duration is 0.25.
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
(
~phrases = [
Pbind(
\degree, Pseq([0, -2, 1, 2, 1, 6, 4]),
\dur, Pseq([0.75, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])
),
Pbind(
\degree, Pseq([7, 4, 3, 1, -2, 0, 1]),
\dur, Pseq([0.5, 0.75, 0.25, 0.5, 0.25, 0.25, 0.75])
),
Pbind(
\degree, Pseq([2, 1, 0, 1, 2, 4, 5, 1]),
\dur, Pseq([0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.25, 0.75])
),
Pbind(
\degree, Pseq([4, 5, 4, 5, 7, 8, 7, 9, 6]),
\dur, Pseq([0.5, 0.5, 0.25, 0.25, 0.25, 0.5, 0.25, 0.75, 0.75])
)
];
~addNotesToBar = { |list, pattern, beatInBar, beatsPerBar = 4|
var stream = Pbindf(pattern, \amp, Pseq([0.3, Pn(0.1, inf)])).asStream,
beatsToAdd = (beatInBar + 0.01).roundUp(beatsPerBar) - beatInBar,
event;
while { beatsToAdd > 0 and: {
event = stream.next(Event.new);
event.notNil
} } {
list.add(event);
beatsToAdd = beatsToAdd - event[\dur];
};
beatsToAdd // return value; 0 if exactly the bar line, negative otherwise
};
)
(
~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|
var tryPhraseOrder = ~phrases.scramble,
remaining, localList, saveBacktrackList;
remaining = block { |break|
tryPhraseOrder.do { |phr|
localList = list.copy;
remaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);
case
{ remaining == 0 } { break.value(remaining) } // success! early exit
// bar is not full; recursion to add another phrase
{ remaining > 0 } {
beatInBar = (beatInBar + 0.01).roundUp(beatsPerBar) - remaining;
saveBacktrackList = localList.copy;
remaining = ~backtracking.value(localList, beatInBar, beatsPerBar);
if(remaining == 0) {
break.value(0) // success
} {
// return to previous state before trying the next phrase
localList = saveBacktrackList;
};
};
// remaining < 0: failed, try the next phrase
};
-1 // we are using a negative result for "failed"
};
// update parent's list with new contents from localList
if(remaining == 0) {
list.clear;
list.addAll(localList);
} {
remaining = -1; // bar is not complete is also a failure
};
remaining
};
)
// test
~backtracking.value(l = List.new, beatInBar: 0, beatsPerBar: 8);
Pseq(l).play;
l.sum(_.dur); // test resulting duration
// play many bars
// Penvir stuff was for debugging, don't worry about it
(
p = Ppar([
// metronome
Pbind(
\degree, Pseq([21, Pn(14, 8)], inf),
\dur, 1,
\legato, 0.2,
\amp, Pseq([0.1, 0.05, 0.05], inf)
),
Pn(Plazy({
var list = List.new, remain;
if(~time.isNil) { ~time = thisThread.beats };
(thisThread.beats - ~time).debug("elapsed");
remain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);
[remain, list.sum(_.dur)].debug("remain, total");
if(remain == 0) { Pseq(list) } { "failed".debug; nil };
}), inf)
]).play;
)
p.stop;
// too slow...
TempoClock.default.tempo = 1.5;
// 2nd version: no 1/16-notes at the end of the bar
(
~backtracking = { |list, beatInBar = 0, beatsPerBar = 4|
var tryPhraseOrder = ~phrases.scramble,
remaining, localList, saveBacktrackList, localBeatInBar;
remaining = block { |break|
tryPhraseOrder.do { |phr|
localList = list.copy;
localBeatInBar = beatInBar;
remaining = ~addNotesToBar.value(localList, phr, beatInBar, beatsPerBar);
case
// "fail" (loop around to try the next phrase) if last note is 1/16
{ localList.last.dur <= 0.25 } { nil }
{ remaining == 0 } { break.value(remaining) } // success! early exit
// bar is not full; recursion to add another phrase
{ remaining > 0 } {
localBeatInBar = (localBeatInBar + 0.01).roundUp(beatsPerBar) - remaining;
saveBacktrackList = localList.copy;
remaining = ~backtracking.value(localList, localBeatInBar, beatsPerBar);
if(remaining == 0) {
break.value(0) // success
} {
// return to previous state before trying the next phrase
localList = saveBacktrackList;
};
};
// remaining < 0: failed, try the next phrase
};
-1 // we are using a negative result for "failed"
};
// update parent's list with new contents from localList
if(remaining == 0) {
list.clear;
list.addAll(localList);
} {
remaining = -1; // bar is not complete is also a failure
};
remaining
};
)
(
p = Ppar([
// metronome
Pbind(
\degree, Pseq([21, Pn(14, 8)], inf),
\dur, 1,
\legato, 0.2,
\amp, Pseq([0.1, 0.05, 0.05], inf)
),
Pn(Plazy({
var list = List.new, remain;
if(~time.isNil) { ~time = thisThread.beats };
(thisThread.beats - ~time).debug("elapsed");
remain = ~backtracking.value(list, beatInBar: 0, beatsPerBar: 9);
[remain, list.sum(_.dur)].debug("remain, total");
if(remain == 0) { Pseq(list) } { "failed".debug; nil };
}), inf)
]).play;
)
p.stop;
reception
comments