Devlog 2 - Group Actions

Blobs are the system I came up with when needing to command units that are selected together. At first I thought the simplest solution would be to give each individual XYZActor a TQueue<UXYZAction> and each unit could individually process their queue and once an action is done go onto the next one. As illustrated XYZ

But a race condition occurred which I didn't like. Let's say we have two units in a grid A and B and we queue two move commands one to position 10,10 and the next one to 0,0;

A->Position = 0,0;
B->Postion = 5,5;
MoveAction = 10,10;
MoveAction2 = 0,0;
A->QueueAction(MoveAction);
A->QueueAction(MoveAction2);
B->QueueAction(MoveAction);
B->QueueAction(MoveAction2);

Since A will reach the first position first it would mark the MoveAction as complete and since B shares that same move action it would complete it as well even though it never reached that destination.

NOTE:I could create separate actions for each unit and it would work in that regard, but I did want to handle logic where if units are close together once the center unit reaches the destination it would complete the action.

So my idea was to create some sort of group structure that has a queue of actions and it tracks what units are at each action.

Blob and BlobManager

class Blob : public IProcessable
{
    int32 BlobId;
    TSet<AXYZActor*> AgentsInBlob;
    TMap<AXYZActor*, TSharedPtr<FActionList>> AgentToNodeCache;
    int32 ActionListSize = 0;
    TSharedPtr<FActionList> Head;
    TSharedPtr<FActionList> Tail;

    virtual void Process(float DeltaSeconds);
    void InitializeBlob();
    bool IsBlobProcessable();
    void AddAction(class UXYZAction* Action);
    void RemoveAgent(AXYZActor* Agent);

struct FActionList
{
        class UXYZAction* Action;
        TSharedPtr<FActionList> Next;
        TSharedPtr<FActionList> Previous;
        TSet<AXYZActor*> QueuedAgents;
        TSet<AXYZActor*> ProcessingAgents;
        TSet<AXYZActor*> CompletedAgents;

    void RemoveAgent(AXYZActor* Agent) {
        QueuedAgents.Remove(Agent);
        ProcessingAgents.Remove(Agent);
        CompletedAgents.Remove(Agent);
    }

Let's go through the functions and properties of the blob and the ActionList Struct

has a set of what actors are currently in the blob as we should be able to add and remove units
a Doubly LinkedList of ActionList that will allow us to process the actions that are queued and be able to move units from one node to the next
Action list also contains 3 sets one for each state a unit can be in an action and once they reach the final state they will be moved to the next action
a map that links a unit to what node they reside in this allows us to remove a unit from our blob with ease of access

So why did I need to create a linkedlist, well this reminded me of a leetcode question I did a long time ago LRU Cache while very different my requirements where I need to move a unit through all the actions and then be able to remove a unit from the blob which made this struct actually fall into place quite nicely.

Process Blob

So here is the meat and potatoes of it all

void UXYZBlob::Process(float DeltaSeconds)
{
    if (!IsBlobProcessable()) {
        return;
    }

    TSharedPtr<FActionList> CurrentNodePtr = Head->Next;
    if (!Head.Get()->CompletedAgents.IsEmpty()) {
        if (Head->Next) {
            for (AXYZActor* Agent : Head->CompletedAgents) {
                if (Agent) {
                    Head->Next.Get()->QueuedAgents.Add(Agent);
                    AgentToNodeCache.Add(Agent, Head->Next);
                }
            }
            Head->CompletedAgents.Empty();
        }
    }
    while (CurrentNodePtr != nullptr) {
        FActionList* CurrentNode = CurrentNodePtr.Get();
        UXYZAction* CurrentAction = CurrentNode->Action;
        if (CurrentNodePtr == Tail || !CurrentAction) {
            break;
        }
        // Process all queued Agents
        // Add queued agents to processing set
        // clear queued agent set
        if (!CurrentNode->QueuedAgents.IsEmpty()) {
            CurrentAction->ProcessAction(CurrentNode->QueuedAgents);
            for (AXYZActor* Agent : CurrentNode->QueuedAgents) {
                if (Agent) {
                    CurrentNode->ProcessingAgents.Add(Agent);
                }
            }
            CurrentNode->QueuedAgents.Empty();
        }

        // Check agents is they are complete
        // send them to copmpleted set if so
        if (!CurrentNode->ProcessingAgents.IsEmpty()) {
            TSet<AXYZActor*> AgentsToBeCompleted;
            for (AXYZActor* Agent : CurrentNode->ProcessingAgents) {
                if (Agent) {
                    if (CurrentAction) {
                        if (CurrentAction->HasAgentComplete(Agent)) {
                            AgentsToBeCompleted.Add(Agent);
                        }
                    }
                }
                //if (Agent && CurrentAction && CurrentAction->HasAgentComplete(Agent)) {
                //    AgentsToBeCompleted.Add(Agent);
                //}
            }
            for (AXYZActor* Agent : AgentsToBeCompleted) {
                CurrentNode->ProcessingAgents.Remove(Agent);
                CurrentNode->CompletedAgents.Add(Agent);
            }
        }

        // Move copleted agents to the next node
        // Update agent-node cache
        if (!CurrentNode->CompletedAgents.IsEmpty()) {
            if (CurrentNode->Next) {
                for (AXYZActor* Agent : CurrentNode->CompletedAgents) {
                    if (Agent) {
                        CurrentNode->Next.Get()->QueuedAgents.Add(Agent);
                        AgentToNodeCache.Add(Agent, CurrentNode->Next);
                    }
                }
                CurrentNode->CompletedAgents.Empty();
            }
        }
        CurrentNodePtr = CurrentNodePtr.Get()->Next;
    }
    CurrentNodePtr = Head->Next;
    while (CurrentNodePtr != Tail) {
        if (CurrentNodePtr->QueuedAgents.IsEmpty() &&
            CurrentNodePtr->ProcessingAgents.IsEmpty() &&
            CurrentNodePtr->CompletedAgents.IsEmpty()) {
            CurrentNodePtr->Previous->Next = CurrentNodePtr->Next;
            CurrentNodePtr->Next->Previous = CurrentNodePtr->Previous;
            CurrentNodePtr->Action = nullptr;
            ActionListSize--;
        }
        else {
            break;
        }
        CurrentNodePtr = CurrentNodePtr.Get()->Next;
    }

}

In short we are moving units from three states Queued -> Processing -> Complete We go through all the actions in the list and check what actors are in which of the buckets and move them along until they reach the tail which they will just sit and wait at. Each action has a HasAgentComplete(Agent) which will check if that agent has completed their action and will move them along if so.

BlobManager

Now what creates/removes/processes the blobs is the BlobManager class The client sends Inputs to the Server if an input contains a group of units and some sort of Action it will feed it into the BlobManager.

The BlobManager has some basic duties

Check to see if the units given an action are already in a blob
Remove units in a current blob to create a new blob
Create blobs
Enqueue new actions to blobs

void Process(float DeltaSeconds)
{
    for (; ActionIndex < Actions.Num(); ActionIndex++) {
        QueueAction(Actions[ActionIndex]);
    }
    for (UXYZBlob* Blob : ActiveBlobs)
    {
        if (Blob) {
            Blob->Process(DeltaSeconds);
        }
    }
    RemoveInactiveBlobs();
}

void AddBlob(UXYZBlob* NewBlob)
{
    if (NewBlob->AgentsInBlob.Num() == 0) return;

    if (ActiveBlobs.Num() > 0) {
        TMap<UXYZBlob*, TArray<AXYZActor*>> AgentsToRemove;
        for (UXYZBlob* Blob : ActiveBlobs) {
            if (!Blob || Blob == NewBlob) continue;
            AgentsToRemove.Add(Blob, {});
            for (AXYZActor* Agent : NewBlob->AgentsInBlob) {
                if (Blob->AgentsInBlob.Contains(Agent)) {
                    AgentsToRemove[Blob].Add(Agent);
                }
            }
        }


        for (auto& Entry : AgentsToRemove)
        {
            UXYZBlob* Blob = Entry.Key;
            for (AXYZActor* Actor : Entry.Value) {
                Blob->AgentsInBlob.Remove(Actor);
                Blob->RemoveAgent(Actor);
            }
        }
    }
    
    ActiveBlobs.Add(NewBlob);
}

void RemoveInactiveBlobs()
{
    TArray<UXYZBlob*> BlobsToRemove;
    for (UXYZBlob* Blob : ActiveBlobs) {
        if (Blob->AgentsInBlob.Num() == 0 || Blob->Tail->QueuedAgents.Num() == Blob->AgentsInBlob.Num()) {
            BlobsToRemove.Add(Blob);
            Blob->InitializeBlob();
            Blob->AgentsInBlob.Empty();
        }
    }
    for (UXYZBlob* Blob : BlobsToRemove) {
        ActiveBlobs.Remove(Blob);
        UE_LOG(LogTemp, Warning, TEXT("Removed Blob"));
    }
}

void QueueAction(UXYZAction* Action) {

    bool bIsBlobEqual = true;
    UXYZBlob* NewBlob = UXYZBlobFactory::CreateBlobFromAction(Action, NextBlobId);
    if (!NewBlob) return;
    UXYZBlob* ExistingBlob = nullptr;

    if (ActiveBlobs.Num() > 0) {
        for (UXYZBlob* Blob : ActiveBlobs) {
            bIsBlobEqual = true;
            if (Blob->AgentsInBlob.Num() != Action->ActorSet.Num()) {
                bIsBlobEqual = false;
                continue;
            }
            for (AXYZActor* Agent : Blob->AgentsInBlob) {
                bIsBlobEqual = bIsBlobEqual && Action->ActorSet.Contains(Agent);
            }
            if (bIsBlobEqual) {
                ExistingBlob = Blob;
            }
        }
    }

    if (ExistingBlob && ExistingBlob->GetClass() == NewBlob->GetClass()) {
        if (!Action->bQueueInput) {
            ExistingBlob->InitializeBlob();
        }
        ExistingBlob->AddAction(Action);
        UE_LOG(LogTemp, Warning, TEXT("Existing Blob Enqueued Action"));
    }
    else {
        NewBlob->AgentsInBlob = Action->ActorSet;
        NewBlob->AddAction(Action);
        UE_LOG(LogTemp, Warning, TEXT("New Blob Enqueued Action"));
        NewBlob->BlobId = NextBlobId;
        NextBlobId++;
        AddBlob(NewBlob);
    }
}

And here are the results!

Single Move Commands

XYZ

Queued Moved Commands

XYZ

Queued Moved Commands While Creating New Blobs

XYZ

Since our move action is just a derived class of UXYZAction it was quite simple to create different actions and have the blobs process them in the same way!

Challenges

Since having that doubly linked list structure was a little complex to sort out there were quite a lot of bugs to fix in the structure itself ( not adding agents, not removing, not moving up, action not completing, etc). I'm sure there is simpler solution, but I did have a great feeling of accomplishment building a semi complex structure, and it leveled up my debugging skills by a lot :)

Thank you for reading and if you have any questions feel free to email me at jandro@xyzrts.com

View original