On the 14th day of Advent we simulate a sand flow. My solution today will be an Actor written in C++, using Begin Play to initialize, and the Tick virtual overload to drop sand.
Starting with the class definition:
UCLASS()
class AOC_2022_API AD14Actor : public AActor
{
GENERATED_BODY()
public:
// Sets default values for this actor's properties
AD14Actor();
protected:
// Called when the game starts or when spawned
virtual void BeginPlay() override;
public:
// Called every frame
virtual void Tick(float DeltaTime) override;
UPROPERTY(EditAnywhere)
UPlainTextAsset* PuzzleInput;
UPROPERTY(EditAnywhere)
FVector2D Source;
UPROPERTY(BlueprintReadOnly)
FBox2D Bounds;
UPROPERTY(BlueprintReadOnly)
int FloorY = 0;
UPROPERTY(BlueprintReadOnly)
int Resting = 0;
UPROPERTY(EditAnywhere)
bool bVerbose = false;
UPROPERTY(EditAnywhere)
bool bPart2 = false;
private:
TBitArray<> Buffer;
bool Blocked( FVector2D P )const;
void Set( FVector2D P, bool V=true );
void SetSpan( FVector2D A, FVector2D B, bool V=true );
void DebugLog() const;
inline int Stride() const {return FMath::CeilToInt( Bounds.GetSize().X )+1;}
};
The puzzle input doesn’t include any massive spans that make allocating a single buffer unreasonable, especially as I only need to store each location as blocked, or not, so I am using a TBitArray sized to the bounding box of the space I need to care about.
// Called when the game starts or when spawned
void AD14Actor::BeginPlay()
{
Super::BeginPlay();
// Parse the puzzle input into an array of paths where each path is an array of points
ensure(PuzzleInput);
typedef TArray< FVector2D > Path;
TArray< Path > Structures;
Structures.Reserve(PuzzleInput->Lines.Num());
for(auto Line : PuzzleInput->Lines)
{
Path TempPath;
TArray<FString> PathStrings;
Line.ParseIntoArray(PathStrings, TEXT(" -> "));
TempPath.Reset();
for(auto Point : PathStrings)
{
FString Left, Right;
Point.Split(TEXT(","), &Left, &Right);
TempPath.Add( FVector2d(FCString::Atoi(*Left), FCString::Atoi(*Right)) );
}
Structures.Add(TempPath);
}
// determine the bounding box for the structures
FBox2D LocalBounds(Structures[0]);
for (int i=1;i<Structures.Num();++i)
{
LocalBounds += Structures[i];
}
LocalBounds += Source;
// In Part 2 we are told to "assume the floor is an infinite horizontal line
// with a y coordinate equal to two plus the highest y coordinate of any point in your scan."
// But the buffer (allocated below) doesnt need to be infinitely wide, just 2x the drop
//
if (bPart2)
{
FloorY = LocalBounds.Max.Y + 2;
auto FX1 = Source.X - FloorY;
auto FX2 = Source.X + FloorY;
LocalBounds += FVector2d(FX1,FloorY);
LocalBounds += FVector2d(FX2,FloorY);
}
Bounds = LocalBounds;
// Allocate the grid space to store blocking features (rocks and sand)
Buffer.Add(false,Stride() * FMath::CeilToInt( Bounds.GetSize().Y+1 ));
// Write the rock-spans into the buffer
for (const Path& P : Structures)
{
FVector2D V1 = P[0];
for (int i=1;i<P.Num();++i)
{
SetSpan(V1, P[i]);
V1 = P[i];
}
}
DebugLog();
}A couple of helper functions for writing into the buffer.
void AD14Actor::SetSpan( FVector2D A, FVector2D B, bool V)
{
FVector2D AB(B-A);
AB.Normalize();
while(FVector2D::DistSquared(A,B)>=1)
{
Set(A,V);
A+=AB;
}
Set(A,V);
}
void AD14Actor::Set(FVector2D P, bool V)
{
if (Bounds.IsInsideOrOn(P))
{
P -= Bounds.Min;
int X = FMath::FloorToInt( P.X );
int Y = FMath::FloorToInt( P.Y );
int I = X + Y*Stride();
Buffer[I] = V;
}
}Without my usual test automation – which is a bit more complex to set up for Actors than Functions – the DebugLog is an important step to helps visually verify my set up is correct and my “Blocked” (read) matched my “Set” (write):
bool AD14Actor::Blocked(FVector2D P) const
{
if (bPart2)
{
if (P.Y>=FloorY) return true;
}
if (Bounds.IsInsideOrOn(P))
{
P -= Bounds.Min;
int X = FMath::FloorToInt( P.X );
int Y = FMath::FloorToInt( P.Y );
int I = X + Y*Stride();
return Buffer[I];
}
return 0;
}
void AD14Actor::DebugLog() const
{
UE_LOG(LogTemp, Log, TEXT("AD14Actor::DebugLog ---" ) );
for (int Y=Bounds.Min.Y; Y<=Bounds.Max.Y; ++Y )
{
FString Line;
for (int X=Bounds.Min.X; X<=Bounds.Max.X; ++X )
{
auto c = (FVector2D::DistSquared(Source,FVector2D(X,Y))<1)
? '+'
: Blocked(FVector2D(X,Y) ) ? '#' : '.';
Line.AppendChar( c );
}
UE_LOG(LogTemp, Log, TEXT("%s"), *Line);
}
}After working through some boundary condition bugs, I have something that looks like the example in the Output Log:
All that’s left to do now is write the sand simulation. I drop 1 grain of sand per tick:
// Called every frame
void AD14Actor::Tick(float DeltaTime)
{
Super::Tick(DeltaTime);
FVector2d Sand;
FVector2d Next = Source;
do
{
Sand = Next;
Next = Sand + FVector2d(0,1);
if (Blocked(Next)) Next = Sand + FVector2d(-1,1);
if (Blocked(Next)) Next = Sand + FVector2d( 1,1);
}
while (!Blocked(Next) && (Bounds.IsInsideOrOn(Next)));
if (Blocked(Next))
{
Set(Sand,true);
Resting ++;
if (bVerbose) DebugLog();
if (FVector2D::DistSquared(Sand,Source)<1)
{
UE_LOG(LogTemp, Log, TEXT("Finshed Part 2 after %i came to rest."), Resting);
SetActorTickEnabled(false);
}
}
else
{
DebugLog();
UE_LOG(LogTemp, Log, TEXT("Finshed Part 1 after %i came to rest."), Resting);
SetActorTickEnabled(false);
}
}
My tick rate is capping out at 120 fps, so the solution took just under 4 minutes, dropping 1 grain of sand per tick to solve part 2.
1 thought on “Advent of Code in Unreal Day 14”