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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
|
using UnityEngine;
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using Pathfinding.Jobs;
using UnityEngine.Assertions;
namespace Pathfinding.Graphs.Grid.Jobs {
/// <summary>
/// Calculates erosion.
/// Note that to ensure that connections are completely up to date after updating a node you
/// have to calculate the connections for both the changed node and its neighbours.
///
/// In a layered grid graph, this will recalculate the connections for all nodes
/// in the (x,z) cell (it may have multiple layers of nodes).
///
/// See: CalculateConnections(GridNodeBase)
/// </summary>
[BurstCompile]
public struct JobErosion<AdjacencyMapper> : IJob where AdjacencyMapper : GridAdjacencyMapper, new() {
public IntBounds bounds;
public IntBounds writeMask;
public NumNeighbours neighbours;
public int erosion;
public bool erosionUsesTags;
public int erosionStartTag;
[ReadOnly]
public NativeArray<ulong> nodeConnections;
[ReadOnly]
public NativeArray<bool> nodeWalkable;
[WriteOnly]
public NativeArray<bool> outNodeWalkable;
public NativeArray<int> nodeTags;
public int erosionTagsPrecedenceMask;
// Note: the first 3 connections are to nodes with a higher x or z coordinate
// The last 3 connections are to nodes with a lower x or z coordinate
// This is required for the grassfire transform to work properly
// This is a permutation of GridGraph.hexagonNeighbourIndices
static readonly int[] hexagonNeighbourIndices = { 1, 2, 5, 0, 3, 7 };
public void Execute () {
var slice = new Slice3D(bounds, bounds);
var size = slice.slice.size;
slice.AssertMatchesOuter(nodeConnections);
slice.AssertMatchesOuter(nodeWalkable);
slice.AssertMatchesOuter(outNodeWalkable);
slice.AssertMatchesOuter(nodeTags);
Assert.IsTrue(bounds.Contains(writeMask));
var(outerStrideX, outerStrideY, outerStrideZ) = slice.outerStrides;
var(innerStrideX, innerStrideY, innerStrideZ) = slice.innerStrides;
NativeArray<int> neighbourOffsets = new NativeArray<int>(8, Allocator.Temp, NativeArrayOptions.UninitializedMemory);
for (int i = 0; i < 8; i++) neighbourOffsets[i] = GridGraph.neighbourZOffsets[i] * innerStrideZ + GridGraph.neighbourXOffsets[i] * innerStrideX;
var erosionDistances = new NativeArray<int>(slice.length, Allocator.Temp, NativeArrayOptions.ClearMemory);
var adjacencyMapper = new AdjacencyMapper();
var layers = adjacencyMapper.LayerCount(slice.slice);
var outerOffset = slice.outerStartIndex;
if (neighbours == NumNeighbours.Six) {
// Use the grassfire transform: https://en.wikipedia.org/wiki/Grassfire_transform extended to hexagonal graphs
for (int z = 1; z < size.z - 1; z++) {
for (int x = 1; x < size.x - 1; x++) {
for (int y = 0; y < layers; y++) {
// Note: This is significantly faster than using csum, because burst can optimize it better
int outerIndex = z * outerStrideZ + x * outerStrideX + y * outerStrideY + outerOffset;
var innerIndexXZ = z * innerStrideZ + x * innerStrideX;
int innerIndex = innerIndexXZ + y * innerStrideY;
int v = int.MaxValue;
for (int i = 3; i < 6; i++) {
int connection = hexagonNeighbourIndices[i];
if (!adjacencyMapper.HasConnection(outerIndex, connection, nodeConnections)) v = -1;
else v = math.min(v, erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, connection, nodeConnections, neighbourOffsets, innerStrideY)]);
}
erosionDistances[innerIndex] = v + 1;
}
}
}
for (int z = size.z - 2; z > 0; z--) {
for (int x = size.x - 2; x > 0; x--) {
for (int y = 0; y < layers; y++) {
int outerIndex = z * outerStrideZ + x * outerStrideX + y * outerStrideY + outerOffset;
var innerIndexXZ = z * innerStrideZ + x * innerStrideX;
int innerIndex = innerIndexXZ + y * innerStrideY;
int v = int.MaxValue;
for (int i = 3; i < 6; i++) {
int connection = hexagonNeighbourIndices[i];
if (!adjacencyMapper.HasConnection(outerIndex, connection, nodeConnections)) v = -1;
else v = math.min(v, erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, connection, nodeConnections, neighbourOffsets, innerStrideY)]);
}
erosionDistances[innerIndex] = math.min(erosionDistances[innerIndex], v + 1);
}
}
}
} else {
/* Index offset to get neighbour nodes. Added to a node's index to get a neighbour node index.
*
* \code
* Z
* |
* |
*
* 6 2 5
* \ | /
* -- 3 - X - 1 ----- X
* / | \
* 7 0 4
*
* |
* |
* \endcode
*/
const int DirectionDown = 0;
const int DirectionRight = 1;
const int DirectionUp = 2;
const int DirectionLeft = 3;
// Use the grassfire transform: https://en.wikipedia.org/wiki/Grassfire_transform
for (int z = 1; z < size.z - 1; z++) {
for (int x = 1; x < size.x - 1; x++) {
for (int y = 0; y < layers; y++) {
int outerIndex = z * outerStrideZ + x * outerStrideX + y * outerStrideY + outerOffset;
var innerIndexXZ = z * innerStrideZ + x * innerStrideX;
int innerIndex = innerIndexXZ + y * innerStrideY;
var v1 = -1;
if (adjacencyMapper.HasConnection(outerIndex, DirectionDown, nodeConnections)) v1 = erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, DirectionDown, nodeConnections, neighbourOffsets, innerStrideY)];
var v2 = -1;
if (adjacencyMapper.HasConnection(outerIndex, DirectionLeft, nodeConnections)) v2 = erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, DirectionLeft, nodeConnections, neighbourOffsets, innerStrideY)];
erosionDistances[innerIndex] = math.min(v1, v2) + 1;
}
}
}
for (int z = size.z - 2; z > 0; z--) {
for (int x = size.x - 2; x > 0; x--) {
for (int y = 0; y < layers; y++) {
int outerIndex = z * outerStrideZ + x * outerStrideX + y * outerStrideY + outerOffset;
var innerIndexXZ = z * innerStrideZ + x * innerStrideX;
int innerIndex = innerIndexXZ + y * innerStrideY;
var v1 = -1;
if (adjacencyMapper.HasConnection(outerIndex, DirectionUp, nodeConnections)) v1 = erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, DirectionUp, nodeConnections, neighbourOffsets, innerStrideY)];
var v2 = -1;
if (adjacencyMapper.HasConnection(outerIndex, DirectionRight, nodeConnections)) v2 = erosionDistances[adjacencyMapper.GetNeighbourIndex(innerIndexXZ, innerIndex, DirectionRight, nodeConnections, neighbourOffsets, innerStrideY)];
erosionDistances[innerIndex] = math.min(erosionDistances[outerIndex], math.min(v1, v2) + 1);
}
}
}
}
var relativeWriteMask = writeMask.Offset(-bounds.min);
// Erosion tags are allowed to overwrite the ones the user specifies, as well as the ones that are already reserved for erosion.
for (int i = erosionStartTag; i < erosionStartTag + erosion; i++) erosionTagsPrecedenceMask |= 1 << i;
for (int y = relativeWriteMask.min.y; y < relativeWriteMask.max.y; y++) {
for (int z = relativeWriteMask.min.z; z < relativeWriteMask.max.z; z++) {
for (int x = relativeWriteMask.min.x; x < relativeWriteMask.max.x; x++) {
int outerIndex = x * outerStrideX + y * outerStrideY + z * outerStrideZ + outerOffset;
int innerIndex = x * innerStrideX + y * innerStrideY + z * innerStrideZ;
if (erosionUsesTags) {
var prevTag = nodeTags[outerIndex];
outNodeWalkable[outerIndex] = nodeWalkable[outerIndex];
if (erosionDistances[innerIndex] < erosion) {
if (((erosionTagsPrecedenceMask >> prevTag) & 0x1) != 0) {
nodeTags[outerIndex] = nodeWalkable[outerIndex] ? math.min(GraphNode.MaxTagIndex, erosionDistances[innerIndex] + erosionStartTag) : 0;
}
} else if (prevTag >= erosionStartTag && prevTag < erosionStartTag + erosion) {
// If the node already had a tag that was reserved for erosion, but it shouldn't have that tag, then we remove it.
nodeTags[outerIndex] = 0;
}
} else {
outNodeWalkable[outerIndex] = nodeWalkable[outerIndex] & (erosionDistances[innerIndex] >= erosion);
}
}
}
}
}
}
}
|
