Day 12 is a path-finding problem. You would think Unreal would help with this, but it’s tooled for working with NavMesh. Writing a Breadth First Search in C++ is totally in my wheel house, and I am still trying to catch up, so I go with that.
I start with a new test. It’s the one from the problem description:
#include "Misc/AutomationTest.h"
#include "AoC22BPFunctionLibrary.h"
IMPLEMENT_SIMPLE_AUTOMATION_TEST(AoC2022D12_Test, "AoC_2022.AoC_2022.AoC2022D12_Test",
EAutomationTestFlags::EditorContext | EAutomationTestFlags::EngineFilter)
bool AoC2022D12_Test::RunTest(const FString& Parameters)
{
// Make the test pass by returning true, or fail by returning false.
TArray< FString > Example = {
TEXT("Sabqponm"),
TEXT("abcryxxl"),
TEXT("accszExk"),
TEXT("acctuvwj"),
TEXT("abdefghi")
};
TestEqual(TEXT("Part 1 route is 31 steps"),
UAoC22BPFunctionLibrary::D12_Calculate(Example), 31);
return true;
}Then I implement the D12_Calculate function for part 1 (not shown) which worked first time. Part 2 asked for us to find not a route from a fixed Start to Finish, but from the “best” start out of many options, to the specified finish. The Breadth First Search is a great fit for this. First I reversed the search so instead of going Start to End, it goes from End to Start. Verified the unit test still passed, then added the optional “Strict” argument (default true, for Part 1), and then exit the search as soon as the ‘a’ is found if Strict is set.
// static
int UAoC22BPFunctionLibrary::D12_Calculate(const TArray<FString>& Input, bool Strict)
{
int DY = Input.Num();
ensure(DY>0);
int DX = Input[0].Len();
ensure(DX>0);
TArray< TArray<FVector2d> > Previous;
Previous.AddDefaulted(DY);
FVector2d Start;
FVector2d Goal;
for(int Y=0;Y!=DY;++Y)
{
ensure(Input[Y].Len()==DX);
Previous[Y].AddZeroed(DX);
for (int X=0;X!=DX;++X)
{
Previous[Y][X]=FVector2d(X,Y);
if (Input[Y][X]=='S')
{
Start=FVector2d(X,Y);
}
else if (Input[Y][X]=='E')
{
Goal=FVector2d(X,Y);
}
}
}
auto Height = []( TCHAR h )
{
if (h=='S') h='a';
if (h=='E') h='z';
return h;
};
const FVector2d Scan[]
{
{1,0}, {-1,0}, {0,1}, {0,-1},
};
TArray< FVector2d > Open;
Open.Add(Goal);
int Visited = 0;
FVector2d Current;
do
{
Current = Open[Visited];
if (Current.Equals(Start)) break;
int H1 = Height(Input[Current.Y][Current.X]);
if (Strict==false && H1=='a') break;
Visited++;
for (int S=0;S!=4;++S)
{
FVector2d Next = Current+Scan[S];
if (Next.X >= 0 && Next.X < DX && Next.Y >= 0 && Next.Y < DY)
{
int H2 = Height(Input[Next.Y][Next.X]);
if (H2>=H1-1)
{
// not previously visited
if (Previous[Next.Y][Next.X]==Next)
{
Previous[Next.Y][Next.X]=Current;
Open.Add(Next);
}
}
}
}
}
while (true);
int Result = 0;
while(Current!=Goal)
{
Current = Previous[Current.Y][Current.X];
Result++;
}
return Result;
}
If you have questions or feedback, feel fee to use the comments or message me on Mastodon: https://mastodon.gamedev.place/@codemonkey_uk