1 files changed, 174 insertions, 0 deletions
diff --git a/src/world/proposal.js b/src/world/proposal.js
new file mode 100644
index 0000000..d1f2eb0
--- /dev/null
+++ b/src/world/proposal.js
@@ -0,0 +1,174 @@
+import { pairs, deepEqual } from '../util.js';
+
+/* agent structure:
+ * {
+ *   id: string
+ *   net: network
+ *   state: network_state
+ *   x, y: number
+ *   flags: object
+ * }
+ */
+
+/* action structure:
+ * {
+ *   name: string,
+ *   propose: (agent) => proposal[]
+ * }
+ */
+
+
+/* proposal structure
+ * all proposed world and agent changes must be included for the proposed action to be valid
+ * similarly, if any world or agent change creates merge conflicts, the proposal cannot be merged
+ * and must be removed
+ * {
+ *   world_changes: proposal_world_change[]?
+ *   agent_changes: proposal_agent_change[]?
+ * }
+ */
+
+/* proposal_world_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) {
+  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 world_changes are incompatible
+// merge is true if the two world changes are identical
+// otherwise they are false
+function world_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 world_change and agent_change conflict/merge tuples for a pair of proposals
+function proposal_conflict_merge(a, b) {
+  const [world_conflict, world_merge] = pairs(a.world_changes || [], b.world_changes || []).reduce(
+    (acc, [a, b]) => {
+      const [conflict, merge] = world_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 [world_conflict || agent_conflict, world_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];
+  }
+}