implement agent change conflict/merge detection

3 files changed, 108 insertions, 7 deletions

diff --git a/src/util.js b/src/util.js
index 8b85ba7..74233f4 100644
--- a/src/util.js
+++ b/src/util.js
@@ -21,3 +21,23 @@ export function pairs(arr1, arr2) {
     .map((x, i) => arr2.map(y => [x, y]))

     .flat();

 }

+

+

+export function deepEqual(a, b, debug=false) {

+  if (typeof(a) === 'object') {

+    if (typeof(b) === 'object') {

+      // do deep equality

+      return [...new Set(Object.keys(a).concat(Object.keys(b)))].reduce(

+        (acc, key) => {

+          return acc && deepEqual(a[key], b[key]);

+        },

+        true 

+      );

+    } else {

+      // one object, one non-object

+      return false;

+    }

+  } else {

+    return a === b;

+  }

+}

diff --git a/src/world/agent.js b/src/world/agent.js
index 7ab501c..f7e5a63 100644
--- a/src/world/agent.js
+++ b/src/world/agent.js
@@ -1,4 +1,4 @@
-import { pairs } from '../util.js';
+import { pairs, deepEqual } from '../util.js';
 
 /* agent structure:
  * {
@@ -33,6 +33,7 @@ import { pairs } from '../util.js';
  *   x, y: number
  *   from: string
  *   to:   string
+ *   flags: object?
  * }
  */
 
@@ -45,6 +46,10 @@ import { pairs } from '../util.js';
  */
 
 
+// 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 (a.x != b.x) { return [false, false]; }
   if (a.y != b.y) { return [false, false]; }
@@ -54,15 +59,46 @@ function world_change_conflict(a, b) {
 }
 
 
+function agent_change_conflict(a, b) {
+  if (deepEqual(a, b)) {
+    // identical: merge
+    return [false, true];
+  } else if (
+    (a.agent_id === b.agent_id) &&
+    ((a.x != b.x) || (a.y != b.y))
+  ) {
+    // same agent, different tiles: conflict
+    return [true, false];
+  } else if (
+    (a.agent_id != b.agent_id) &&
+    (a.x === b.x) &&
+    (a.y === b.y)
+  ) {
+    // different agents, same tile: conflict
+    return [true, false];
+  } else {
+    // no conflict c:
+    return [false, false];
+  }
+}
+
+
 function proposal_conflict_merge(a, b) {
-  const [world_conflict, world_merge] = pairs(a.world_changes, b.world_changes).reduce(
+  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]
-  )
-  return [world_conflict, world_merge];
+  );
+  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];
 }
 
 
diff --git a/src/world/agent.test.js b/src/world/agent.test.js
index ea64fcb..2a86908 100644
--- a/src/world/agent.test.js
+++ b/src/world/agent.test.js
@@ -9,7 +9,6 @@ test("proposals changing different tiles don't conflict", () => {
   const a = {
     world_changes: [{ x: 4, y: 3, from: 'empty', to: 'mutable' }],
   };
-
   const b = {
     world_changes: [{ x: 4, y: 4, from: 'empty', to: 'flag' }],
   };
@@ -22,7 +21,6 @@ test("proposals changing the same tile to different states conflict", () => {
   const a = {
     world_changes: [{ x: 4, y: 3, from: 'empty', to: 'mutable' }],
   };
-
   const b = {
     world_changes: [{ x: 4, y: 3, from: 'empty', to: 'flag' }],
   };
@@ -35,10 +33,57 @@ test("proposals changing the same tile to the same state merge to a single propo
   const a = {
     world_changes: [{ x: 4, y: 3, from: 'empty', to: 'mutable' }],
   };
-
   const b = {
     world_changes: [{ x: 4, y: 3, from: 'empty', to: 'mutable' }],
   };
 
   expect(proposal_merge([a], b)).toEqual([a]);
 });
+
+
+test("proposals moving two agents to the same tile conflict", () => {
+  const a = {
+    agent_changes: [{ agent_id: 'aaa', x: 4, y: 3 }],
+  };
+  const b = {
+    agent_changes: [{ agent_id: 'bbb', x: 4, y: 3 }],
+  };
+
+  expect(proposal_merge([a], b)).toEqual([]);
+});
+
+
+test("proposals moving two agents to different tiles do not conflict", () => {
+  const a = {
+    agent_changes: [{ agent_id: 'aaa', x: 4, y: 3 }],
+  };
+  const b = {
+    agent_changes: [{ agent_id: 'bbb', x: 3, y: 3 }],
+  };
+
+  expect(proposal_merge([a], b)).toEqual([a, b]);
+});
+
+
+test("proposals moving the same agent to different tiles conflict", () => {
+  const a = {
+    agent_changes: [{ agent_id: 'aaa', x: 4, y: 3 }],
+  };
+  const b = {
+    agent_changes: [{ agent_id: 'aaa', x: 3, y: 3 }],
+  };
+
+  expect(proposal_merge([a], b)).toEqual([]);
+});
+
+
+test("proposals moving the same agent to the same tile merge", () => {
+  const a = {
+    agent_changes: [{ agent_id: 'aaa', x: 4, y: 3 }],
+  };
+  const b = {
+    agent_changes: [{ agent_id: 'aaa', x: 4, y: 3 }],
+  };
+
+  expect(proposal_merge([a], b)).toEqual([a]);
+});