diff options
Diffstat (limited to 'src/world/proposal.js')
-rw-r--r-- | src/world/proposal.js | 183 |
1 files changed, 0 insertions, 183 deletions
diff --git a/src/world/proposal.js b/src/world/proposal.js deleted file mode 100644 index 8baca06..0000000 --- a/src/world/proposal.js +++ /dev/null @@ -1,183 +0,0 @@ -import { pairs, deepEqual } from '../util.js'; - -/* agent structure: - * { - * id: string - * net: network - * state: network_state - * x, y: number - * flags: object - * } - */ - - -/* cell structure: - * { - * type: string - * flags: object - * } - */ - -/* action structure: - * { - * name: string, - * propose: (agent, output) => proposal[] - * } - */ - - -/* proposal structure - * all proposed lattice and agent changes must be included for the proposed action to be valid - * similarly, if any lattice or agent change creates merge conflicts, the proposal cannot be merged - * and must be removed - * { - * lattice_changes: proposal_lattice_change[]? - * agent_changes: proposal_agent_change[]? - * } - */ - -/* proposal_lattice_change - * { - * x, y: number - * from: string - * to: string - * flags: object? - * } - */ - -/* proposal_agent_change - * { - * agent_id: string - * x, y: number? - * flags: object? - * } - */ - - -// check that two flags objects are compatible -// flags are considered compatible if they do not have any common keys with different values -function flags_compatible(a, b) { - if (a === undefined || b === undefined) { return true; } - const keys = [...new Set(Object.keys(a).concat(Object.keys(b)))]; - return keys.reduce( - (acc, key) => { - const eq = (a[key] === undefined || b[key] === undefined) ? true : deepEqual(a[key], b[key]); - return acc && eq; - }, - true - ); -} - - -// return a tuple [conflict, merge] -// conflict is true if the two lattice_changes are incompatible -// merge is true if the two lattice changes are identical -// otherwise they are false -function lattice_change_conflict(a, b) { - if (deepEqual(a, b)) { - // merge - return [false, true]; - } - if ( - a.x === b.x && - a.y === b.y && - (a.to != b.to || !flags_compatible((a.flags || {}), (b.flags || {}))) - ) { - // conflict! - return [true, false]; - } else { - // no conflict c: - return [false, false]; - } -} - - -// returns true as long as x & y are both defined -function pos_exists(a) { - if (a.x !== undefined && a.y !== undefined) { - return true; - } else { - return false; - } -} - - -// check the equality of two objects with (x,y) keys -function pos_equal(a, b) { - if (a.x !== b.x) { return false; } - if (a.y !== b.y) { return false; } - return true; -} - - -// agent changes merge if they are identical -// they conflict if two agents are trying to move to the same tile, or -// if the same agent is trying to move to two different tiles, or if an agent -// is being updated to incompatible flags -// -// -function agent_change_conflict(a, b) { - if (deepEqual(a, b)) { - // identical: merge - return [false, true]; - } else if (a.agent_id === b.agent_id) { - if ( - pos_exists(a) && pos_exists(b) && !pos_equal(a, b) - ) { - // same agent, different positions: conflict - return [true, false]; - } else if (!flags_compatible(a.flags, b.flags)) { - // same agent, incompatible flags: conflict - return [true, false]; - } else { - // no conflict c: - return [false, false]; - } - } else { - // different agents - if (pos_exists(a) && pos_exists(b) && pos_equal(a, b)) { - // different agents, same position: conflict - return [true, false]; - } else { - // no conflict c: - return [false, false]; - } - } -} - - -// combine lattice_change and agent_change conflict/merge tuples for a pair of proposals -function proposal_conflict_merge(a, b) { - const [lattice_conflict, lattice_merge] = pairs(a.lattice_changes || [], b.lattice_changes || []).reduce( - (acc, [a, b]) => { - const [conflict, merge] = lattice_change_conflict(a, b); - return [acc[0] || conflict, acc[1] || merge]; - }, - [false, false] - ); - const [agent_conflict, agent_merge] = pairs(a.agent_changes || [], b.agent_changes || []).reduce( - (acc, [a, b]) => { - const [conflict, merge] = agent_change_conflict(a, b); - return [acc[0] || conflict, acc[1] || merge]; - }, - [false, false] - ); - return [lattice_conflict || agent_conflict, lattice_merge || agent_merge]; -} - - -// merge proposals -// if two sub-updates conflict, they are both omitted from the final merged proposal -export function proposal_merge(arr, proposal) { - const conflict_merge = arr.map(x => proposal_conflict_merge(x, proposal)); - - // if any conflicts are detected then don't merge - if (conflict_merge.reduce((acc, [c, m]) => acc || c, false)) { - const conflict_free = arr.filter((x, i) => !conflict_merge[i][0]); - return conflict_free; - } else { - // no conflicts, but need to merge identical actions - const no_merge = arr.filter((x, i) => !conflict_merge[i][1]); - return [...no_merge, proposal]; - } -} |