数组
DiscoveredTileIndexed 和 DiscoveredTileSortingCosts
这两个数组是用来存储遍历的方格的，DiscoveredTileSortingCosts存储的是每个方格的消耗，DiscoveredTileIndexed存储的是每个方格的位置即(x,y)。
DiscoveredTileSortingCosts中的消耗和DiscoveredTileIndexed位置是一一对应的，也即是DiscoveredTileIndexed中方格位置是按照消耗排序的
AnalysedTileIndex
每次从DiscoveredTileIndexed中取出第一个元素，即消耗最小的元素压入到该数组中，压入后表示该点已经走过，后面的点如果周围点出现在这个数组中那么就会跳过
PathFindingData
其为一个Map结构，存储的就是最短路径，由当前方格坐标和方格参数组成，
CurrentNeighbors
用来存储每次遍历一个节点其的下一步可以到达的点
方格的结构体
和蓝图中一样存放几个必须的参数
USTRUCT(BlueprintType)
struct FPathFindingData : public FTableRowBase
{
GENERATED_USTRUCT_BODY()
FPathFindingData() {}
FPathFindingData(FIntPoint index, int costtoentertile, int costfromstart, int minimumcosttotarget, FIntPoint previousindex) :
Index(index), CostToEnterTile(costtoentertile), CostFromStart(costfromstart),MinimumCostToTarget(minimumcosttotarget),PreviousIndex(previousindex)
{}
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Data")
FIntPoint Index = { -999, -999 };
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Data")
int CostToEnterTile = 1;
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Data")
int CostFromStart = 999999;
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Data")
int MinimumCostToTarget = 999999;
UPROPERTY(EditAnywhere, BlueprintReadWrite, Category = "Data")
FIntPoint PreviousIndex = { -999, -999 };
};
寻路函数
TArray<FIntPoint> AXGridPathFinding::FindPath(const FIntPoint& start, const FIntPoint& target, bool Diagonals)
返回PathFindingData中Key值组成的数组。
首先向函数中传入起点和终点以及是否考虑沿着对角线移动，然后清除上次寻路的结果，检验输入坐标是否合理
StartIndex = start;
TargetIndex = target;
bIncludeDiagonals = Diagonals;
//清除之前的路径
ClearGenerateData();
//判断输入的合理性
if (!IsInputDataValid())
{
UE_LOG(LogTemp, Warning, TEXT("Input No Valid"));
return TArray<FIntPoint>();
}
计算起点的方格参数
int MinCostToEnd = GetMinimumCostBetweenTwoTiles(StartIndex, TargetIndex, bIncludeDiagonals);
FPathFindingData StartData;
StartData.Index = StartIndex;
StartData.CostToEnterTile = 1;
StartData.CostFromStart = 0;
StartData.MinimumCostToTarget = MinCostToEnd;
对起点进行计算得到初始的DiscoveredTileIndexed 和 DiscoveredTileSortingCosts并将起点压入到PathFindingData中
DiscoverTile(StartData);
if(DiscoveredTileIndexed.Num() == 0) UE_LOG(LogTemp, Warning, TEXT("No DiscoveredTileIndexed"));
当起点的可移动点求出，遍历DiscoveredTileIndexed数组，对每个点进行分析，直到DiscoveredTileIndexed数组长度为0，如果在分析中返回了true表示可以到终点，返回对应数组
while (DiscoveredTileIndexed.Num() > 0)
{
//寻路
if (AnalyseNextDiscoveredTile())
{
UE_LOG(LogTemp, Warning, TEXT("Find Way"));
return GerneratePath();
}
}
return TArray<FIntPoint>();
计算当前点的可到达方格
void AXGridPathFinding::DiscoverTile(const FPathFindingData& TilePathData)
通过传入当前节点的属性，将当前节点压入到PathFindingData中，然后从当前点计算更新DiscoveredTileIndexed 和 DiscoveredTileSortingCosts
void AXGridPathFinding::DiscoverTile(const FPathFindingData& TilePathData)
{
PathFindingData.Add(TilePathData.Index, TilePathData);
InsertTileInDiscoveredArray(TilePathData);
}
更新DiscoveredTileIndexed 和 DiscoveredTileSortingCosts
void AXGridPathFinding::InsertTileInDiscoveredArray(const FPathFindingData& TileData)
首先计算从起点经过该点TileData到终点所需要的路径消耗SortingData，利用TileData结构体中的数据进行计算。
当DiscoveredTileIndexed数组为空时，可以直接压入节点坐标，如果不为空，要比较DiscoveredTileSortingCosts中的最后一个元素和SortingData的大小，如果SortingData大，那么也可以直接压入，如果SortingData小，那么需要从DiscoveredTileSortingCosts寻找到合理的位置进行插入，而DiscoveredTileSortingCosts与DiscoveredTileIndexed是一一对应的所以可以使用同一个下标进行插入
void AXGridPathFinding::InsertTileInDiscoveredArray(const FPathFindingData& TileData)
{
//计算当前点的消耗
int SortingData = TileData.CostFromStart + TileData.MinimumCostToTarget;
//如果排序数组长度为0，或者当前点的SortingData比排序数组中都大，那么直接压入
if (DiscoveredTileSortingCosts.Num() == 0)
{
//都是在对应的队尾加入元素，保证顺序
DiscoveredTileSortingCosts.Add(SortingData);
DiscoveredTileIndexed.Add(TileData.Index);
}
else
{
if (SortingData >= DiscoveredTileSortingCosts.Last())
{
DiscoveredTileSortingCosts.Add(SortingData);
DiscoveredTileIndexed.Add(TileData.Index);
}
else
{
for (int i = 0;i<DiscoveredTileSortingCosts.Num();i++)
{
if (SortingData < DiscoveredTileSortingCosts[i])
{
DiscoveredTileSortingCosts.Insert(SortingData, i);
DiscoveredTileIndexed.Insert(TileData.Index,i);
break;
}
}
}
}
}
对每个遍历到的节点的处理
bool AXGridPathFinding::AnalyseNextDiscoveredTile()
该函数不仅涉及到对每个节点的处理，还需要对每个节点进行判断是否为终点
每次处理的节点一定是当前消耗最小的节点，即首先需要从DiscoveredTileIndexed取出第一个元素，加入到AnalysedTileIndex数组中，然后每次取出一个就需要将其从DiscoveredTileIndexed 和 DiscoveredTileSortingCosts移除。
然后根据下标从PathFindingData中获取当前节点的结构体，然后计算当前节点下一步会到达哪些点，存储在CurrentNeighbors数组中，然后对数组中每个元素进行遍历，寻找其在DiscoveredTileIndexed 和 DiscoveredTileSortingCosts的合适位置进行插入，然后判断是否为终点。
bool AXGridPathFinding::AnalyseNextDiscoveredTile()
{
//首先将消耗最小的节点取出，从存储数组和排序数组中移除（一定是第一个元素），然后加入到分析数组中
CurrentDiscoveredTile = PullCheapestTileOutOfDiscoveredList();
//获取当前点的下一步可移动的点
CurrentNeighbors = GetValidTileNeighbor(CurrentDiscoveredTile.Index, bIncludeDiagonals);
if(CurrentNeighbors.Num() == 0) UE_LOG(LogTemp, Warning, TEXT("No CurrentNeighbors"));
while (CurrentNeighbors.Num() > 0)
{
if (DiscoverNextNeighbor())
{
return true;
}
}
return false;
}
获取消耗最小点作为接下来的起始点
FPathFindingData AXGridPathFinding::PullCheapestTileOutOfDiscoveredList()
{
FIntPoint TileIndex = DiscoveredTileIndexed[0];
DiscoveredTileIndexed.RemoveAt(0);
DiscoveredTileSortingCosts.RemoveAt(0);
AnalysedTileIndex.Add(TileIndex);
//获取存在于结果Map中的数据，如果没有就返回空
FPathFindingData res = PathFindingData[TileIndex];
return res;
}
对当前点的下一步可到达点进行处理
bool AXGridPathFinding::DiscoverNextNeighbor()
每次获取CurrentNeighbors中的第一个元素，然后移除它
首先对其下标进行判断，判断它是否之前出现在了AnalysedTileIndex数组中，如果出现过，说明如果现在到该点会向回走，跳过对该点的处理
接下来计算从起点到下一步点的消耗CostFromStart，然后判断下一步点是否之前存在DiscoveredTileIndexed中，如果存在那说明下一步点之前作为过其他点的下一步可移动点，但是并不是消耗最少的点。
那么就需要从PathFindingData中取出下一步点的起点到该点的数据，来和CostFromStart比较。如果CostFromStart较大，说明下一步点不是最优点，可以直接返回了。
如果CostFromStart较小，那么下一步点就可以作为下一步可到达点，首先从DiscoveredTileIndexed 和 DiscoveredTileSortingCosts移除它。
接下来的处理逻辑是公用的（CostFromStart较小或者该点之前不存在DiscoveredTileIndexed中）
首先就是计算下一步点的结构体数据，然后对下一步点进行压入PathFindingData和更新DiscoveredTileIndexed 和 DiscoveredTileSortingCosts的操作。
接着判断下一步点是否为终点，从而返回bool值
bool AXGridPathFinding::DiscoverNextNeighbor()
{
CurrentNeighbor = CurrentNeighbors[0];
CurrentNeighbors.RemoveAt(0);
//如果在分析数组中已经存在说明之前遍历过，即往回走了，直接返回false
if(AnalysedTileIndex.Contains(CurrentNeighbor.Index)) return false;
//计算起点到当前点的消耗，就是起点到前一个点的消耗 + 前一个点到目前点的消耗
int CostFromStart = CurrentDiscoveredTile.CostFromStart + CurrentNeighbor.CostToEnterTile;
//判断该点是否存在于之前点的邻接点但还未遍历的数组中
//如果在
int IndexInDiscovered = DiscoveredTileIndexed.Find(CurrentNeighbor.Index);
if (IndexInDiscovered != -1)
{
CurrentNeighbor = PathFindingData[CurrentNeighbor.Index];
if (CostFromStart >= CurrentNeighbor.CostFromStart)
{
return false;
}
else
{
DiscoveredTileIndexed.RemoveAt(IndexInDiscovered);
DiscoveredTileSortingCosts.RemoveAt(IndexInDiscovered);
}
}
//如果不在，那么直接加入就行了
int MinimumCostToTarget = GetMinimumCostBetweenTwoTiles(CurrentNeighbor.Index, TargetIndex, bIncludeDiagonals);
UE_LOG(LogTemp, Warning, TEXT("CurrentNeighbor:%d,%d,CostFromStart:%d,MinimumCostToTarget:%d"), CurrentNeighbor.Index.X, CurrentNeighbor.Index.Y, CostFromStart, MinimumCostToTarget);
FPathFindingData temp(CurrentNeighbor.Index, CurrentNeighbor.CostToEnterTile, CostFromStart, MinimumCostToTarget, CurrentDiscoveredTile.Index);
DiscoverTile(temp);
if (CurrentNeighbor.Index == TargetIndex)
{
return true;
}
else return false;
}
生成路径
对PathFindingData进行从后向前遍历，通过存放在结构体中的前一个点坐标这个成员进行迭代直到退回到起点，然后再翻转数组即可。
TArray<FIntPoint> AXGridPathFinding::GerneratePath()
{
FIntPoint Current = TargetIndex;
TArray<FIntPoint> InvertedPath, Res;
while (Current != StartIndex)
{
InvertedPath.Add(Current);
Current = PathFindingData[Current].PreviousIndex;
}
for (int i = InvertedPath.Num() - 1; i >= 0; i--)
{
//UE_LOG(LogTemp, Warning, TEXT("InvertedPath[i]:%d,%d"), InvertedPath[i].X, InvertedPath[i].Y);
Res.Add(InvertedPath[i]);
}
return Res;
}
