DEV Community

Tiny
Tiny

Posted on • Originally published at tinygame.dev on

Spawn actors at random location on landscape

Intro

We’re working with Unreal Engine and we have a large open map with a landscape. The landscape is heightmap based and naturally it’s not going to be a flat polygon. How can we spawn actors dynamically on this landscape and place them correctly on the terrain so it doesn’t look horrible? If you’re asking this question, you’ve come to the right place!

We can place our chests on most of the map and have it look good

An important assumption we’re making is the terrain being relatively low frequency. If that’s not true for your case and you have a super high resolution landscape grid you may get worse results. Imagine you want to place something like a chest on a piece of land that has peaks and dips smaller than the chest. You may not get the bottom of the chest to align very well with the ground. Maybe the result will be acceptable regardless, but I felt I needed to point this out.

We will deal with some edge cases and build a system that’s trying its best to pick good spots to place the actors.

Finding a spot

In Magivoid we occasionally spawn chests that are meant to be close to the player, but not too close. When we initiate this spawn we randomize a target location that’s within a min and max distance from the player.

const float MinDist = 10000.f; // 100m
const float MaxDist = 20000.f; // 200m
FVector Direction(FMath::RandRange(-1.0, 1.0), FMath::RandRange(-1.0, 1.0), 0.0);
Direction.Normalize();
Direction *= FMath::RandRange(MinDist, MaxDist);

ACharacter* Character = UGameplayStatics::GetPlayerCharacter(this, 0);
Location = Character->GetActorLocation() + Direction;
Enter fullscreen mode Exit fullscreen mode

With a potential target location for the chest, we now check to make sure we have suitable terrain there to place the object. We do this with a vertical line trace that checks against WorldStatic geometry in an attempt to find the Z coordinate of the landscape. If the trace fails it means we don’t have terrain here, or otherwise messed up our trace. It’s important to pick a long enough line segment to make sure you’re guaranteed to hit your landscape geometry with it. You’ll have to pick this based on what your landscape looks like. If the trace does fail, we just exit our function and try again next frame. We’re not in a rush to spawn the object at a specific frame and can absorb this time slicing to avoid potential spikes in CPU cost.

This is a good opportunity to do a second type of location culling based on the normal of the terrain. Below we check to see if the line trace hit normal is larger than 40 degrees, in which case we also abort. We don’t want to place a chest on a very steep slope. Presumably it would slide off if we pretended physics worked like in real life. This may or may not be important to you.

We skip locations that are too steep

FCollisionQueryParams QueryParams;
QueryParams.AddIgnoredActors(PCGActors);
FCollisionObjectQueryParams ObjectQueryParams;
ObjectQueryParams.AddObjectTypesToQuery(ECC_WorldStatic);

FHitResult Hit;
FVector TraceStart = Location + FVector(0, 0, 1800);
FVector TraceEnd = Location + FVector(0, 0, -1800);

UWorld* World = GetWorld();
if (!World->LineTraceSingleByObjectType(Hit, TraceStart, TraceEnd, ObjectQueryParams, QueryParams))
{
    UE_LOG(LogTemp, Error, TEXT("Failed to find terrain for chest location"));
    return false;
}

float TerrainAngle = FMath::RadiansToDegrees(FMath::Acos(FVector::DotProduct(Hit.ImpactNormal, FVector(0, 0, 1))));
if (TerrainAngle > 40.f)
{
    UE_LOG(LogTemp, Error, TEXT("Terrain too steep for chest location"));
    return false;
}

Location = Hit.ImpactPoint;
Enter fullscreen mode Exit fullscreen mode

We have now updated our target location with the Z coordinate of the landscape where we might want to place the chest. Let’s go ahead and spawn it.

Spawning the chest

We have a potentially valid location to spawn a chest at and can now continue with placing our actor. But first, I’d like to make the small addition of randomizing the rotation along the Z-axis. The chest can end up more or less anywhere on the map, we might as well have random rotations for it too.

FRotator Rotation = FRotator::ZeroRotator;
Rotation.Yaw = FMath::RandRange(0, 360);
Enter fullscreen mode Exit fullscreen mode

A simple yaw rotation is all that’s needed. Let’s spawn the chest next.

FActorSpawnParameters SpawnParams;
SpawnParams.SpawnCollisionHandlingOverride = ESpawnActorCollisionHandlingMethod::AlwaysSpawn;
AActor* Chest = GetWorld()->SpawnActor<AActor>(ChestClass, Location, Rotation, SpawnParams);

USkeletalMeshComponent* SkelMeshComp = Chest->GetComponentByClass<USkeletalMeshComponent>();
if (SkelMeshComp)
{
    UWorld* World = GetWorld();
    auto LineTrace = [&](FVector Point, FVector& Target, FVector& Normal) -> bool
    {
        FCollisionQueryParams QueryParams;
        QueryParams.AddIgnoredActor(Chest);

        FCollisionObjectQueryParams ObjectQueryParams;
        ObjectQueryParams.AddObjectTypesToQuery(ECC_WorldStatic);

        FHitResult Hit;
        FVector TraceStart = Point;
        FVector TraceEnd = Point + FVector(0, 0, -500);

        FVector TargetLocation = TraceStart;
        if (World->LineTraceSingleByObjectType(Hit, TraceStart, TraceEnd, ObjectQueryParams, QueryParams))
        {
            Target = Hit.ImpactPoint;
            Normal = Hit.ImpactNormal;

            AActor* Actor = Hit.GetActor();
            if (Actor && Actor->ActorHasTag(TEXT("PCG")))
            {
                return false;
            }
            return true;
        }
        return false;
    };

    FTransform CToW = SkelMeshComp->GetComponentTransform();
    FBoxSphereBounds Bounds = SkelMeshComp->CalcBounds(FTransform::Identity);
    FVector P0 = CToW.TransformPosition(Bounds.Origin + FVector(Bounds.BoxExtent.X, Bounds.BoxExtent.Y, 100));
    FVector P1 = CToW.TransformPosition(Bounds.Origin + FVector(Bounds.BoxExtent.X, -Bounds.BoxExtent.Y, 100));
    FVector P2 = CToW.TransformPosition(Bounds.Origin + FVector(-Bounds.BoxExtent.X, -Bounds.BoxExtent.Y, 100));
    FVector P3 = CToW.TransformPosition(Bounds.Origin + FVector(-Bounds.BoxExtent.X, Bounds.BoxExtent.Y, 100));

    bool bTraceSuccess = true;
    FVector T0, T1, T2, T3, N0, N1, N2, N3;
    bool bTraceSuccess = LineTrace(P0, T0, N0);
    bTraceSuccess &= LineTrace(P1, T1, N1);
    bTraceSuccess &= LineTrace(P2, T2, N2);
    bTraceSuccess &= LineTrace(P3, T3, N3);

    if (!bTraceSuccess)
    {
        UE_LOG(LogTemp, Error, TEXT("Failed to find chest location, destroying this chest."));
        Chest->Destroy();
        return false;
    }

    double TotalDot = N0.Dot(N1) + N0.Dot(N2) + N0.Dot(N3);
    if (TotalDot < 2.7) // 3.0 is all normals equal, we leave a bit of wiggle room
    {
        UE_LOG(LogTemp, Error, TEXT("Terrain normals too dissimilar to place chest, destroying actor: %.2f"), TotalDot);
        Chest->Destroy();
        return false;
    }

    FVector V0 = T1 - T0;
    FVector V1 = T2 - T0;
    FVector V2 = T3 - T0;
    FVector TN0 = V1.Cross(V0);
    TN0.Normalize();
    FVector TN1 = V2.Cross(V1);
    TN1.Normalize();

    FVector AvgPosition = (T0 + T1 + T2 + T3) * 0.25;
    FVector AvgNormal = (TN0 + TN1) * 0.5;

    TotalDot = AvgNormal.Dot(N0) + AvgNormal.Dot(N1) + AvgNormal.Dot(N2) + AvgNormal.Dot(N3);
    if (TotalDot < 3.8) // 4.0 is all normals equal, we leave a bit of wiggle room
    {
        UE_LOG(LogTemp, Error, TEXT("Terrain discontinuity found, destroying actor: %.2f"), TotalDot);
        Chest->Destroy();
        return false;
    }

    FRotator NewRotation = FRotationMatrix::MakeFromZY(AvgNormal, Chest->GetActorRightVector()).Rotator();

    Chest->SetActorLocationAndRotation(AvgPosition, NewRotation);
    UE_LOG(LogTemp, Display, TEXT("Successfully spawned chest!"));
}
Enter fullscreen mode Exit fullscreen mode

Ope, that’s a lot of code. Let’s try and go through it and see what’s happening.

First, we actually spawn the chest at our preliminary location, noting that we may delete the actor if things go wrong. You can probably do all calculations before spawning the actor, but I’m not sure if that’s worth it. Something to profile if needed but this hasn’t been an issue so far.

Our chest actor has a SkeletalMesh since it’s animated, but this detail isn’t important. The important part once we have our actor is to get the bounds of the visual mesh. We want this to be as accurate as possible to make sure our next calculations give optimal results.

From the bounds we extract four points (P0-P3) that represent the corners of our mesh. We set the Z coordinate to 100 cm above the origin of the actor and will use this to initiate new line traces down towards the landscape. We also transform these points by the component transform to get the location of the corners in world space.

From our four corner points, we trace lines down towards the ground with a helper lambda function. This function returns false if we should discard this spawn location entirely (more about this later), as well as the location of the landscape and its normal where the line trace intersected it.

We do a line trace for each corner of the chest to learn what the terrain looks like

Next we do a quick and dirty check on all normals to make sure they’re mostly the same. We do this with a dot product and use 2.7 as the threshold for skipping this location. Since we’re adding three dot products, the max value would be 3.0 if all normals were identical. We eyeballed 2.7 as a threshold here to leave a bit of wiggle room. Anything below this we consider too much variation between the normals.

Some cases make it impossible to place the chest nicely and the normals will tell us when this happens

We now have four points on a piece of landscape that we consider even enough to spawn a chest on. Since our actor origin is at the center of the bottom of the bounding box, we just use the middle from all four corner points as the spawn location.

It’s important to note these points may not form a plane and we don’t yet know how to orient the chest. To find out what the chest rotation should be we turn the polygon defined by the four corner points into two triangles and independently check their normals. We then use the average of the two normals to orient the chest. This isn’t ideal but there’s not much we can do if there’s a fold at that location.

We split the bottom of the chest plane into two triangle to check their normals

At this point we do one final check to see if we need to skip this location. Since we have our intended orientation for the chest, we compare this to the normals of the landscape at the four points where the corners of the chest will end up. We do this to make sure there’s no surprising difference between the two. The case that could cause this is when there’s a significant discontinuity in the terrain, for example something like stairs.

Stairs are a particularly difficult case we just don't even attempt to spawn on

With stairs we would get a very similar normal, if not identical, for all four corners, but the height for each point would be different, causing the chest to lean too much and its center intersecting with the landscape. We keep it simple and just skip these locations, even though in our map we don’t really have many places that could cause this.

Finally, we create a new rotation from the data we have and update the location and rotation for our already spawned chest actor.

The PCG thing

You may remember from earlier when we do our first landscape line trace we have this line:

QueryParams.AddIgnoredActors(PCGActors);
Enter fullscreen mode Exit fullscreen mode

In addition, once we’re ready to check the four corners we have the following early out in our lamba:

AActor* Actor = Hit.GetActor();
if (Actor && Actor->ActorHasTag(TEXT("PCG")))
{
    return false;
}
Enter fullscreen mode Exit fullscreen mode

So what’s up with this PCG stuff?

Our map uses the new PCG tools from UE 5.2 to populate it with trees, bushes, large rocks, etc. The way this works is, there’s a PCG actor in the level which spawns multiple instanced meshes based on the PCG graph. In our case, we have these large trees in the map:

Our pretty large trees

We don’t want to mess with these when spawning chests in the sense that we’d like to avoid any computation cost while deciding how to properly align chests to these objects. We keep things simple and just avoid placing chests on top of any static meshes created by the PCG system. With one exception. We’d like to see chests under these large trees.

In order to make this possible, when we first run our landscape line trace, we ignore any PCG actors to make sure we only find the landscape and its height for a potential chest spawn location. This is the reason for the first line of code mentioned above.

When we later trace towards the landscape for the chest corners we include the PCG actor but return false in our lambda and fail any attempt that intersects a PCG mesh. The reason this works is because the first line trace is really long to make sure we find our terrain while the corner traces use the height of the terrain with short line segments to avoid hitting any surrounding trees.

A chest under our pretty large tree

This gives us a system that works well enough to place chests in most locations on our map. When we do fail to find a location, which happens rarely, we try again on the next frame and sooner or later we will get a chest.

Hope you found this useful, and thanks for reading this far!

Top comments (0)