我尝试根据视频并改进其代码，在 Unity 中实现游戏的寻路。为了提高多线程的效率，我想实现 Unity Jobs，但由于这是我第一次这样做，我得到了一些有趣的结果。
使用下面的代码，我的性能比没有工作时差得多，并且崩溃了，我不明白为什么。在分析器上（在 Unity 编辑器中进行分析）至少需要 14 毫秒才能找到新路径，这比应有的情况要糟糕得多，因为没有作业时速度要快得多。这仅是两个单位在节点数低于 1000 的关卡上对同一目标进行寻路的情况。由于我在互联网上找到了同一寻路主题的代码，因此我认为它应该具有更高的性能。即使在这些情况下，观看视频的性能影响也应低于 1 毫秒。我发现甚至 github 仓库都有更大的地图和超过 100 个代理，性能也好得多。
也许我不理解作业系统的某些内容，或者在代码中的某个地方犯了错误，但无法弄清楚是什么导致了性能下降。
首先，我有一个单元，每次目标对象移动一定距离并在指定时间后调用 PathRequestManager。这将创建一个新的 PathRequest，其中包含当前位置、目标位置、计算路径时应调用的回调以及当前单位。然后在一个方法中，我将请求的位置添加到单独的 NativeList 中。这些将包含应在下一个 Update() 中调用的路径请求参数。
在更新中，我查看是否应该使用 shouldDoPathFinding 变量来完成寻路，当添加新路径请求时，该变量设置为 true。如果是真的，我调用 StartFindPathJobifiedHash 方法。将所需的本机数组、哈希映射、多哈希映射传递给作业并调度它。
public void StartFindPathJobifiedHash()
{
CopyNextAttributesToCurrent(); //Copies the next pathfinding attributes to the current list
ClearNextPathfindingAttributes(); //Clears next pathfinding attributes
//unitList contains the units which should do pathfinding in current Update
for (int i = 0; i < unitList.Count; i++)
{
NodeStruct startNode = grid.NodeFromWorldPointJobified(startPosList[i]);
int startNodeID = startNode.nodeID;
NodeStruct endNode = grid.NodeFromWorldPointJobified(endPosList[i]);
int endNodeID = endNode.nodeID;
//startNodeList and endNodeList are native lists
startNodeList.Add(startNodeID);
endNodeList.Add(endNodeID);
}
//node neighbours are calculated when grid is created on main thread
NativeParallelMultiHashMap<int, int> neighboursMap = grid.neighboursMapJobified;
//originalPathNodeArray is a native array which contains all the nodes in the grid, populated when the grid is calculated
// neighboursMap is a native parallel multi hashmap, with node ids as keys and neighbour ids as values, populated when the grid is calculated
// waypointsHash native parallel multi hashmap with node ids as keys and positions as values
FindPathJobParallel findPathJob = new FindPathJobParallel { pathRequestIDList = pathRequestIDList, originalPathNodeArray = originalPathNodeArray, neighboursMap = neighboursMap, startNodeList = startNodeList, endNodeList = endNodeList, waypointsHash = waypointsHash, pathSuccessHash = pathSuccessHash, originalPathNodeArrayHash = originalPathNodeHash, unitIDs = unitIDs };
JobHandle jobHandle = findPathJob.Schedule(unitList.Count, 1);
jobhandle = jobHandle;
}
这是工作：
[BurstCompile]
public struct FindPathJobParallel : IJobParallelFor
{
[ReadOnly, NativeDisableParallelForRestriction] public NativeArray<NodeStruct> originalPathNodeArray;
[ReadOnly, NativeDisableParallelForRestriction] public NativeParallelHashMap<int, NodeStruct> originalPathNodeArrayHash;
[ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> pathRequestIDList;
[ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> startNodeList;
[ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> endNodeList;
[ReadOnly, NativeDisableParallelForRestriction] public NativeList<int> unitIDs;
[WriteOnly, NativeDisableParallelForRestriction] public NativeParallelMultiHashMap<int, float3> waypointsHash;
[NativeDisableParallelForRestriction] public NativeParallelHashMap<int, bool> pathSuccessHash;
[ReadOnly, NativeDisableParallelForRestriction] public NativeParallelMultiHashMap<int, int> neighboursMap;
public void Execute(int i)
{
NativeList<NodeStruct> openList = new NativeList<NodeStruct>(Allocator.Temp);
NativeList<NodeStruct> closedList = new NativeList<NodeStruct>(Allocator.Temp);
NativeParallelMultiHashMap<int, int> openHashMap = new NativeParallelMultiHashMap<int, int>(100, Allocator.Temp);
NativeParallelMultiHashMap<int, int> closedHashMap = new NativeParallelMultiHashMap<int, int>(1000, Allocator.Temp);
NativeList<int> neighbourIndexes = new NativeList<int>(10, Allocator.Temp);
NativeArray<NodeStruct> pathNodeArray = new NativeArray<NodeStruct>(originalPathNodeArray.Length, Allocator.Temp);
NativeParallelHashMap<int, NodeStruct> pathNodeHash = new NativeParallelHashMap<int, NodeStruct>(originalPathNodeArray.Length, Allocator.Temp);
NodeStruct startNodeStruct = originalPathNodeArray[0];
NodeStruct endNodeStruct = originalPathNodeArray[0];
NativeParallelHashMap<int, bool> successList = new NativeParallelHashMap<int, bool>(100, Allocator.Temp);
NodeStruct nodeStruct = new NodeStruct();
nodeStruct = originalPathNodeArrayHash[startNodeList[i]];
startNodeStruct = nodeStruct;
startNodeStruct.parentID = startNodeStruct.nodeID;
NodeStruct endNodeStructNew = new NodeStruct();
endNodeStructNew = originalPathNodeArrayHash[endNodeList[i]];
endNodeStruct = endNodeStructNew;
if (!pathNodeHash.ContainsKey(startNodeList[i]))
{
pathNodeHash.Add(startNodeList[i], startNodeStruct);
}
if (!pathNodeHash.ContainsKey(endNodeList[i]))
{
pathNodeHash.Add(endNodeList[i], endNodeStruct);
}
startNodeStruct.gCost = 0;
openList.Add(startNodeStruct);
openHashMap.Add(startNodeStruct.nodeID, startNodeStruct.nodeID);
while (openList.Length > 0)
{
NodeStruct currentNodeStruct = GetLowestCostFNodeIndex(openList, openHashMap);
closedList.Add(currentNodeStruct);
closedHashMap.Add(currentNodeStruct.nodeID, currentNodeStruct.nodeID);
if (currentNodeStruct.nodeID == endNodeStruct.nodeID)
{
pathSuccessHash[unitIDs[i]] = true;
successList[i] = true;
break;
}
var neighboursOnIndexEnumerator = neighboursMap.GetValuesForKey(currentNodeStruct.nodeID);
while (neighboursOnIndexEnumerator.MoveNext())
{
neighbourIndexes.Add(neighboursOnIndexEnumerator.Current);
}
NodeStruct neighbourStruct = originalPathNodeArray[0];
for (int neighbourIndex = 0; neighbourIndex < neighbourIndexes.Length; neighbourIndex++)
{
int currentNeighbourIndex = neighbourIndexes[neighbourIndex];
neighbourStruct = originalPathNodeArray[currentNeighbourIndex];
if (!neighbourStruct.walkable)
{
continue;
}
if (closedHashMap.ContainsKey(currentNeighbourIndex))
{
continue;
}
int newMovementCostToNeighbour = currentNodeStruct.gCost + (int)GetDistanceJobified(currentNodeStruct.worldPosition, neighbourStruct.worldPosition, currentNodeStruct.gridX, currentNodeStruct.gridY, neighbourStruct.gridX, neighbourStruct.gridY) + neighbourStruct.movementPenalty;
if (newMovementCostToNeighbour < neighbourStruct.gCost || !openHashMap.ContainsKey(currentNeighbourIndex))
{
NodeStruct newNodeStruct = new NodeStruct();
newNodeStruct.gridX = neighbourStruct.gridX;
newNodeStruct.gridY = neighbourStruct.gridY;
newNodeStruct.walkable = neighbourStruct.walkable;
newNodeStruct.worldPosition = neighbourStruct.worldPosition;
newNodeStruct.movementPenalty = neighbourStruct.movementPenalty;
newNodeStruct.walkable = neighbourStruct.walkable;
newNodeStruct.gCost = newMovementCostToNeighbour;
newNodeStruct.hCost = (int)GetDistanceJobified(neighbourStruct.worldPosition, endNodeStruct.worldPosition, neighbourStruct.gridX, neighbourStruct.gridY, endNodeStruct.gridX, endNodeStruct.gridY);
newNodeStruct.nodeID = neighbourStruct.nodeID;
newNodeStruct.parentID = currentNodeStruct.nodeID;
newNodeStruct.angle = neighbourStruct.angle;
newNodeStruct.normal = neighbourStruct.normal;
newNodeStruct.modifiedWorldPosition = neighbourStruct.modifiedWorldPosition;
if (!pathNodeHash.ContainsKey(newNodeStruct.nodeID))
{
pathNodeHash.Add(newNodeStruct.nodeID, newNodeStruct);
}
else
{
pathNodeHash[newNodeStruct.nodeID] = newNodeStruct;
}
if (!openHashMap.ContainsKey(currentNeighbourIndex))
{
openList.Add(neighbourStruct);
openHashMap.Add(neighbourStruct.nodeID, neighbourStruct.nodeID);
}
}
}
}
if (pathSuccessHash[unitIDs[i]])
{
NativeList<float3> waypointsList = new NativeList<float3>(100, Allocator.Temp);
waypointsList = RetracePathJobifiedHash(originalPathNodeArrayHash[startNodeStruct.nodeID], pathNodeHash[endNodeStruct.nodeID], pathNodeHash);
for (int j = 0; j < waypointsList.Length; j++)
{
waypointsHash.Add(unitIDs[i], waypointsList[j]);
pathSuccessHash[unitIDs[i]] = waypointsList.Length > 0;
}
waypointsList.Dispose();
}
openList.Dispose();
closedList.Dispose();
pathNodeArray.Dispose();
neighbourIndexes.Dispose();
}
public NodeStruct GetLowestCostFNodeIndex(NativeList<NodeStruct> openList, NativeParallelMultiHashMap<int, int> openHashMap)
{
NodeStruct lowestCostNode = openList[0];
int lowestIndex = 0;
for (int i = 0; i < openList.Length; i++)
{
NodeStruct currentCostNode = openList[0];
if (currentCostNode.fCost < lowestCostNode.fCost)
{
lowestCostNode = currentCostNode;
lowestIndex = i;
}
}
openList.RemoveAt(lowestIndex);
openHashMap.Remove(lowestCostNode.nodeID);
return lowestCostNode;
}
float GetDistanceJobified(float3 nodeAPos, float3 nodeBPos, int nodeAGridX, int nodeAGridY, int nodeBGridX, int nodeBGridY)
{
int dstX = math.abs(nodeAGridX - nodeBGridX);
int dstY = math.abs(nodeAGridY - nodeBGridY);
float dstZ = math.abs(nodeAPos.y - nodeBPos.y);
if (dstZ != 0)
{
dstZ = dstZ * 10;
}
if (dstX > dstY)
return 14 * dstY + 10 * (dstX - dstY) + (int)dstZ;
return 14 * dstX + 10 * (dstY - dstX) + (int)dstZ;
}
NativeList<float3> RetracePathJobifiedHash(NodeStruct startNode, NodeStruct endNode, NativeParallelHashMap<int, NodeStruct> pathNodeArray)
{
NativeList<NodeStruct> path = new NativeList<NodeStruct>(100, Allocator.Temp);
NodeStruct currentNode = endNode;
while (currentNode.nodeID != startNode.nodeID)
{
path.Add(currentNode);
currentNode = pathNodeArray[currentNode.parentID];
}
NativeList<float3> pathVector3List = new NativeList<float3>(100, Allocator.Temp);
for (int i = 0; i < path.Length; i++)
{
pathVector3List.Add(path[i].worldPosition);
}
NativeList<float3> waypoints = new NativeList<float3>(pathVector3List.Length, Allocator.Temp);
for (int i = 0; i < path.Length; i++)
{
waypoints.Add(path[i].worldPosition);
}
path.Dispose();
pathVector3List.Dispose();
pathNodeArray.Dispose();
return waypoints;
}
}
这项工作是一个简单的 A* 寻路脚本，用原生列表和数组重写。我在开始时创建网格节点并在每次寻路时使用它。为了不覆盖节点，当发现新节点时，我创建一个新的节点结构并将其用于当前作业的未来。它工作得很好，但我不明白为什么一项工作至少需要 14 毫秒才能完成。在探查器中，我可以看到多个线程正在工作。
您能看一下代码并尝试告诉我问题出在哪里吗？尝试对代码进行注释以使其更容易理解，但如果有任何问题，我很乐意回答。
编辑：使用Unity 2021.3.16版本，尝试关闭突发选项中的安全检查，性能是相同的。当我关闭作业时，寻路工作会在 1 毫秒内完成。问题应该出在 FindPathJobParallel 代码中，就像在分析器中花费最多时间一样。
Burst 编译器做了一件事——它很好地优化了数学运算。但 Burst 对您设计的数据布局和内存访问模式没有影响。这意味着 3 个 CPU 性能因素中有 2 个掌握在程序员手中。
NodeStructMatrix4x4NativeArray<Cost> costsNativeArray<ID> idsNativeArray<float3> worldPositions归根结底是为了避免不可预测的随机访问模式。