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
|
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?
* }
*/
// 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]; }
if (a.to != b.to) { return [true, false]; }
// x, y, and to all match -- merge
return [false, true];
}
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(
(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];
}
}
|