Published
Edited
Jun 19, 2022
Insert cell
Insert cell
Markov.string("AAB", [
{from: "X", to: ""},
[{from: "BB", to: "BCB"}, {from: "BB", to: "DD", weight: 0.05}],
{from: "A", to: "XBX"},
])
Insert cell
Insert cell
{
const w = 75;
const h = 15;
const g = gridgraph([w, h], " ");
g["0/0"].state = "C";
return fmt_chargrid_frames(w, h, Markov.fixed_graph(
g,
[{from: ["C", " ", " "], to: ["C", "W", "C"]}],
{filter_matches: ({match}) => gridgraph_points_colinear([w, h], match)}
), {
C: "DarkGrey", // Corner
W: "Grey", // Wall
" ": "White", // Empty
});
}
Insert cell
{
const w = 25;
const h = 15;
const g = gridgraph([w, h], " ", {cyclic: true});
return fmt_chargrid_frames(w, h, Markov.fixed_graph(
g,
[
[
{from: ["T", "F"], to: ["F", "F"]},
{from: ["F"], to: [" "]},
{from: ["T", " "], to: ["T", "T"], weight_frac: 0.02},
{from: ["T"], to: ["F"], weight_frac: 0.0001},
],
{from: [" "], to: ["T"]},
]
), {
F: "OrangeRed", // Fire
T: "DarkGreen", // Tree
" ": "White", // Empty
});
}
Insert cell
{
const w = 20;
const h = 10;
const g = gridgraph([w, h], " ", {cyclic: true});
g["0/0"].state = "A";
g["1/1"].state = "B";
g["1/2"].state = "B";
g["1/2"].state = "B";
g["2/2"].state = "B";
g["2/1"].state = "B";
g["4/4"].state = "B";
g["5/4"].state = "B";
g["6/4"].state = "B";
g["11/7"].state = "B";
g["12/7"].state = "B";
g["9/3"].state = "B";
g["3/3"].state = "W";
g["3/4"].state = "W";
g["3/5"].state = "W";
g["3/6"].state = "W";
return fmt_chargrid_frames(w, h, Markov.fixed_graph(
g,
[[
{from: ["A", " "], to: [" ", "A"], weight_frac: 0.1},
{from: ["A", " "], to: ["A", "A"], weight_frac: 0.03},
{from: ["A", "B", " "], to: [" ", "A", "B"]}, // Since it's a fixed_graph this rule matches in an L shape
]],
{filter_matches: ({match}) => gridgraph_points_colinear([w, h], match)}
), {
B: "Grey", // Block
A: "Red", // Agent
W: "Black", // Wall
" ": "White", // Empty
});
}
Insert cell
Markov.fixed_graph({
"A": {state: 1, edges: ["B"]},
"B": {state: 1, edges: ["C"]},
"C": {state: 1, edges: []},
"D": {state: 1, edges: ["A", "C"]},
},
[ // This is different because the meaning of different length sequences is not defined, but different length strings is.
{from: [1, 1], to: [1, 2]},
{from: [2, 2, 2], to: [3, 3, 3]},
]
)
Insert cell
gridgraph([3, 2], 0, {directed: true})
Insert cell
Insert cell
Insert cell
Markov = {
const algorithm = structure => (start, rules, options={}) => {
// rules: [X, [Y, Z]] -> normalized_union_rules: [[X], [Y, Z]]
const normalized_union_rules = rules.map(rule_or_set => Array.isArray(rule_or_set) ? rule_or_set : [rule_or_set]);
let {step_limit, filter_matches} = Object.assign({
step_limit: 1000,
filter_matches: ({rule, match}) => true,
}, options);
let result = [start];
let clean_rules = 0;
while (step_limit && clean_rules < rules.length) {
const last = result[result.length - 1];
const matches = normalized_union_rules[clean_rules].flatMap(
rule => [...structure.matches(last, rule)].map(
match => ({rule, match})
)
).filter(filter_matches);
if (matches.length === 0) {
clean_rules++;
} else {
step_limit--;
clean_rules = 0; // This 0 can be significantly improved with static analysis

// randomly select matches (downweighting with weight_frac), dropping those that overlap
let overlaps = 0;
let acc = last;
const touched_nodes = {};
while (overlaps < 10) {
let _match = null;
let weight_sum = 0;
for (let m of matches)
weight_sum += m.rule.weight_frac || 1;
weight_sum *= Math.random(); // um..
for (let m of matches) {
weight_sum -= m.rule.weight_frac || 1;
if (weight_sum <= 0) {
_match = m;
break;
}
}
if (_match === null)
throw "Weighted random method failure. weird float bug?";
const match = _match;
let touches = false;
const matchnodes = structure.matchnodes(match.match);
for (let nodename of matchnodes)
touches = touches || touched_nodes[nodename];
if (touches) {
overlaps++;
break; // while(overlaps < ...
}
for (let nodename of matchnodes)
touched_nodes[nodename] = true;
acc = structure.apply(acc, match.rule, match.match);
}
result.push(acc);
}
}
return result;
};

// Strings: variable length sequences of code points
const string_ops = {
matches: function* (str, rule) {
let i = str.indexOf(rule.from);
while (i !== -1) {
yield i;
i = str.indexOf(rule.from, i + 1);
}
},
matchnodes: match => [0], // Because length changes, just make everything overlap
apply: (last, rule, match) => `${last.slice(0, match)}${rule.to}${last.slice(match + rule.from.length)}`,
};

// Fixed Graphs: Arbitrary graphs structures where the only changing thing is the node states, not connectivity.
const fixed_graph_ops = {
matches: function*(graph, rule) {
function* rec(graph, first_key, rule_from) {
if (graph[first_key].state !== rule_from[0])
return;
if (rule_from.length === 1) {
yield [];
return;
}
for (let neighbor of graph[first_key].edges)
for (let m of rec(graph, neighbor, rule_from.slice(1)))
yield [neighbor, ...m];
}
if (rule.from.length !== rule.to.length) throw `Expected ${rule.from} to be the same length as ${rule.to}`;
for (let k in graph)
for (let m of rec(graph, k, rule.from))
yield [k, ...m];
},
matchnodes: match => match,
apply: (last, rule, match) => {
const result = JSON.parse(JSON.stringify(last));
match.forEach((key, index) => {result[key].state = rule.to[index];});
return result;
},
};
return {
algorithm,
string: algorithm(string_ops),
string_ops,
fixed_graph: algorithm(fixed_graph_ops),
fixed_graph_ops,
};
}
Insert cell
Insert cell

Purpose-built for displays of data

Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
Learn more