Implementing A Procedural Movement System Inspired By WFC In Unity

For a game, a friend and I are working on (which at the current time I can't show because it is not released yet), we decided to swap out our existing "simulation" based movement system, or rather agent-based movement system with one that is evaluated once, and the npcs then follow like a train track. The goal is to create a predictable pattern and to have a generated component to increase replayability.

When making a generative system I put a lot of focus on the ability to art-direct it and have as much "manual" input as possible, while abstracting away tedious or repetitive tasks. I want the movement to be in a closed loop, so that the agent stops where it started and having a seemless transition. I also want to make sure to have an evenly distributed and spaced out organization.

The concept and architecture

So to implement this, I first need to think about the interacting components. I want the system to be modular and easy to edit. This will be achieved with something that I call a movement ingredient. Which looks like this

This is achieved with the help of the existing line renderer which is made up of a list of points which can be edited. I also added a custom AnimationCurve field, so that we can adjust the relative position on the segment based on time or the speed based on position.

This Animation curve means that the agent accelerates until reaching the middle, slows down, or even goes backwards slightly, in the middle before accelerating until it reaches the end.

The movement ingredient is in normalized space, meaning it does not represent absolute positions and can be adjusted and fitted. Only the points to themselves define the shape proportions. Also the movement needs to be open, as opposed to closed, so that we can use it as a puzzle piece.

The reason it is called a movement ingredient and not a piece or segment is due to its semantics. An ingredient is just an editor editable template. My system will then create variations of it, by creating flipped variants on the Z (left right) and X axis (forward/backwards). The collection of these variant will become the actual pieces.

Next we have what I call the movement assembler. It takes a list of ingredients, gathers them in a pool of variants as movement segments and starts joining them. To ensure an even distribution it will be centered around a central neutral point. Around that point I will build a three-dimensional grid as cells, that will then be populated by the movement segments. To avoid backtracking and excessive looping, I will need to find an efficient algorithm to do this.

What system can take components with local similarities and place them into a grid like structure by eliminating options progressively?

That's right, wave function collapse! Luckily I have been fidgetting around with my own unity implementation (post about that will follow soon), and even more so, it is an abstract implementation based on interfaces which can just be implemented in terms of the needs of the application's specification. The core algorithm just deals with indices and numbers and can do the entropy based design-space traversal independent of the components that implement it.

This is a very good example which showcases a concept I have talked about before, where Abstraction is the bridge between algorithms and architecture. Also it shows a corner stone of development strategy, of building up concepts as vague and abstract as possible bottom up, so that we can then later use them to model different applications. Moving up layers of abstraction, and having most of the problem solved thanks to movable parts and flexible definitions.

My movement ingredient and movement assembler will be implementing the WFC interface that I have developed, and so the main problem has been solved. What remains now is the specific implementation that gives informations about the involved local depencies for movement segments. And of course assigning and following those segments by turning them into real movement on the agents.

This brings us to the last component. The Procedural Movement component which defines a simple interpolation based position while keeping track of the segment it is on and querying from it the speed curve. Also we want to keep track of the same pattern for each instance of an agent from the same kind, or rather created from the same prefab. But game object lose their reference to their prefab at runtime.

To solve this I also implemented a small editor script that OnValidate assigns the Prefab to the gameobject, so I don't have to do that manually.

Adapting Wave function collapse to Movement Segments

So the main development activity now is to refactor my loose architecture with the template provided by my existing abstraction and fill the gaps for the needs of the movement system.

To give you a brief overview and also to review it my self here is a summary of the involved components.

public WaveFunctionCollapse(IWaveCollapseOutput context, int number_of_entries, float[] weightedOptions, bool useEntropy = true)

Wave function collapse is a normal C# Object (class), so that it can be moved and passed around without being tied to any asset specifically. I also have a Wave function collapse controller class, which provides its connection to the Unity Engine as a possible editor tool, should we need to manually adjust things. (Not in this case)

Wave function collapse is passed a IWaveCollapseOutput which contains the information about the environment to be collapsed. In our case the movement grid with the neutral center. It then is initialized with the number of available options and optional weights for that options. It then creates an abstract array of indeces and uses the entropy algorithm to determine the next best option and likelihood of a solution.

This is where I feel the design is very elegant, the decision what this iteration in the design space is, is implemented in the IWaveCollapseOutput which is my MovementAssembler, in this case. Also my algorithm is not aware about the movement segments, a reference to them is stored in the Movement Assembler.

Which brings us to the last component of the abstract WFC System (which is also not used in this case). A ICollapsibleSamplePattern. This idea again follows the principle of manual art direction. For when we want to give a base case or template to follow or want to manually place some elements and interpolate the remaining pattern later.

So if I am correct, I would just need to initialize a Wave Function Collapse object in my Movement Assembler pass the object a reference to it with the number of segments, and let it do its work.

// -- Begin WFC Interface

public bool SkipNode(int nodeIndex){
    return false;
}

public void Propagate(int nodeIndex, int collapsedOption, System.Action<int, int> banFunction){
}

public void Collapse(int nodeIndex, int selectedOption, System.Action<int, int> banFunction){
}

public float[] AdjustWeights(int nodeIndex, float[] weights){
    return weights;
}

public bool ForceManualPickAndCollapse(int i){
    return false;
}
  
// end WFC Interface

This is the functions my MovementAssembler has to implement. Which we will leave blank for now. So let's break it down. A node is an abstract term for one position in my WaveCollapseOutput, in this case a cell of the grid. We can decide to skip it.

Propagate is a function that gets the chosen Option (collapsed) for a node and then based on the internal implementation allows to ban other options by calling the ban callback Function. Collapse is the very act of collapsing. Some systems I found work more efficiently by using the propagate option, some the collapse, based on their internal semantics.

We also have an AdjustWeights option which we can at any time call to adjust the chances of an option to be picked on a certain node. As I said, I built in all sorts of use cases for maximum flexibility. We will probably not use all of it in this implementation.

And ForceManualPickAndCollapse is a very clumsy function that given a node returns true, and we pick an option ourselves and then communicate that decision to the internal Wave Function Collapse data structure directly. Just to have as much control as possible. I also don't anticipate needing this.

So what we need now is to create the "output", our grid, assign each cell an integer index. Ask our movement recipes to be so kind and provide us with different variants to store and pass the indices of their array.

We have our grid, which is shown in the editor. And now we construct our wave function collapse.

// Keep the interface abstract if the implementation should change in the future

    private void InitializePG(){

        wfc = new WaveFunctionCollapse(this, cellCenters.Count, new float[0]);

        int seed = 21231244;

        int limit = 2000;

        wfc.Init(21231244, 2000, new (int, int)[0]);

    }

Little Intermission for Quality of Life in Editor

Before we assemble the movement patterns, I would like to do the same with the MovementPart (remember those are the final variants that come out of the MovementIngredient). I would like some form of visual feedback in the editor to confirm that my implementation works. This is not about the generation, but the playback. A proof of concept if the idea works as intended on a smaller scope and to give my less technical partner a preview so that he knows, how the patterns he designs works, and more importantly, feels.

Also this would right away focus my attention of solving the abstraction of the segment based position playback. Given a value between 0 and 1 as ratio it should give back the interpolated position on the track. Also this abstraction should work for a single MovementPart, aswell as for a compound track made of multiple instances of it.

First Attempt

As we can see we have a jump starting from the index+1, which means I am doing something wrong between the ratio estimation from full distance to local distance (per segment)

I made another adjustment, getting the remainder between curveTime and ratio then dividing that by ratio. But this seems to upset it even more. Hm, I think I have to draw this out.

Well turns out I had one missing step in my thought process

I was dividing the curveTime by the main ratio (here 0.6f and 0.7f respectively), which caused the jump. I projected the relative position to the full length on the segment. Turns out I need to substract the last ratio from it and also from the next ratio, which will get me 0.1 and 0.2 respectively, which would then be the middle (0.5) on the segment.

for(int i = 0; i < lengths.Length; i++){

            float ratio = lengths[i] / totalLength;
            if(curveTime <= ratio){
                segmentIndex = i;
                segmentPosition = (curveTime - lastRatio) / (ratio - lastRatio);
                break;
            }
            lastRatio = ratio;
            
        }

Works perfectly and is seamless between segments. Awesome!
Also with AnimationCurve:

Back to Wave Function Collapse

Thanks to this short proof of concept, I now have a full picture of all the interacting components and what the system needs. I find starting with the final algorithm in mind and complimenting data-structures and classes on a per-need basis the most effective and efficient. It helps me to reason in terms of the process, which I then can refactor once it works for reusability, interfacing and clarity. I will follow the same approach with my Wave function collapse implementations.

Collapse

This is very simple, when the WFC Object decides to collapse an Option on a cell, I will create a Dictionary entry that maps position on Grid to Object. Remember this is all just "virtual" for now.

Propagate

To check for adjency I will need to get an understanding of my data structure and if there is any pattern I can use to get neigboring rules.

"(-100.00, -100.00, -100.00)"
"(-100.00, -100.00, 100.00)"
"(-100.00, 100.00, -100.00)"
"(-100.00, 100.00, 100.00)"
"(100.00, -100.00, -100.00)"
"(100.00, -100.00, 100.00)"
"(100.00, 100.00, -100.00)"
"(100.00, 100.00, 100.00)"

So it seems that the negative X is at the half point, the negative -Y alternates every second value and the negative Z every other value. I have to check how this pattern changes when I increase the size. While I think I could get the right index, doing the calculation for it this way would be incredibly complex.

I also realized when thinking about the Data Structure, that I should separate my Prefab to Movement manager from the actual Movement assembler (Single Responsibility Principle). So I had to refactor a bit.

public void Collapse(int nodeIndex, int selectedOption, System.Action<int, int> banFunction){

        Vector3 cell = cells[nodeIndex];

        MovementPart selectedPart = part_options[selectedOption].CopyIntoSpace(cell, cellSize);

        partToGridMap.Add(cell, selectedPart);

    }

The propagate step is the essential one. It is a recursive elimination of options, based on the picked choice and all the consequent cells. However the more I think about, the less it reflects my algorithm's semantics. By eliminating one option we can't exclude other options.
Only when we know for sure what option has been selected we know, what other options are unavailable to us. So I have to focus on that for now.

public void Collapse(int nodeIndex, int selectedOption, System.Action<int, int> banFunction){

        Vector3 current_cell = cells[nodeIndex];

        MovementPart selectedPart = part_options[selectedOption].CopyIntoSpace(current_cell, cellSize);

        partToGridMap.Add(current_cell, selectedPart);

        foreach(Vector3 other_cell in GetNeighboringCells(nodeIndex)){

            for(int i = 0; i < part_options.Count; i++){

                Vector3 offset = other_cell-current_cell;

                int otherCellIndex = cells.IndexOf(other_cell);

                if(wfc.wave[cells.IndexOf(other_cell)][i]){

                    if(!selectedPart.IsPartCompatible(part_options[i], offset.normalized)){

                        banFunction(otherCellIndex, i);

                    }

                }

            }

        }

    }

And the more important Method is IsPartCompatible

public bool IsCompatible(MovementPart other, Vector3 direction){

        Vector3 thisEndPoint = points[points.Length - 1];

        Vector3 thisStartPoint = points[0];

        Vector3 otherEndPoint = other.points[points.Length - 1];

        Vector3 otherStartPoint = other.points[0];

        return (Vector3.Dot(thisEndPoint, direction) > 0 || Vector3.Dot(thisStartPoint, direction) > 0)

            && (Vector3.Dot(otherEndPoint, direction) < 0 || Vector3.Dot(otherStartPoint, direction) < 0)

    }

With that now it is time to check the result, by visualizing it in the Editor.

Filling in the Gaps

I also just realized that the selection of options is not just dependent on the neighbors, but also on the position of the cell. I can't have a movement connecting to the outside of the grid. This would reverberate through the entire grid and result in an incompatible structure. So back to the drawing board.

I think I need another Interface function which is called IsOptionAvailable.

bool IsOptionAvailable(int nodeIndex, int option){

        Vector3 thisCell = cells[nodeIndex];

        (Vector3 start, Vector3 end) = part_options[option].GetTipDirection();

        bool isStartCompatible = false;

        bool isEndCompatible = false;

        foreach(Vector3 neighborCell in GetNeighboringCells(nodeIndex)){

            if(cells.IndexOf(neighborCell) > -1){

                if(Vector3.Dot(neighborCell - thisCell, start) > 0.9f){

                    isStartCompatible = true;

                }

                if(Vector3.Dot(neighborCell - thisCell, end) > 0.9f){

                    isEndCompatible = true;

                }

                if (isStartCompatible && isEndCompatible){

                    return true;

                }

            }

        }

        return false;

    }
   

This might seem correct at first glance, but I could notice some misalignment around the connecting cell faces, due to a more complex segment anatomy. So let's try to find a base case by using very simple segments.

As we can see, it sort of works. One problem there is, the algorithm will run out of options if there are no fitting pieces, leaving a blank spot. As of now I have no piece that can connect a -X / +X facing cell. But I think this is not as relevant in my specific use case. So let's ignore it for now and instead focus on the next step, which is the key part: Joining the segments to a full movement loop.

That looks promising! So now I have to try again with more unique segment designs.

And it works like a charm!

So turns out that WFC was not the sole component to make this system work. My MovementPart sorting and merging is way more relevant for this particular system. I am a bit resentful having spent a lot of time trying to fit my system into its framework. However it is still a good abstraction to randomly select, superpose and select options on a grid (or other form of input), not having to keep track of it in the object implementing it. It is a very flexible shell, allowing for neighbor based exclusion, but by no mean a full WFC and also by no mean a "one fits all" solution.

I am very happy for this solution as a first implementation. At least now I have components in place that I can modify and improve to a later stage.

Takeaway

When working on a complex system it is very important to get visual (or other forms of output) feedback as soon as possible to check the behavior of components. Eventhough one part of the algorithm does not perform as it should straight away, don't get too hung up on it and try to get the bigger picture working as soon as possible. In my case it turned out that the key algorithm was the glue, that fit everything together. Implement algorithms first as they come to your mind, and refactor later. Don't overengineer right from the start, to avoid solving two problems at once. You waste your cognitive resources on two fronts, while both require your undivided attention. In this algorithm the WFC component played a minor role, more crucial was the ordering and joining of the movement path pieces. However many ideas from WFC where still essential for the result: the entropy based randomness, the exclusion of pieces based on the surrounding neighbors (in this case the grid cells themselves) as well as the grid based approach. Even with an incomplete grid, they worked and created interesting results. I have to look into WFC again, especially in the propagation step. As it stands, it is incomplete in my abstract implementation. This implementation also taught me a valuable lesson about resource tradeoff, what should be computed, and what stored and to what amount. The original WFC stores everything, even the compatible tiles for each other tile option. This allows for quick iteration. However by hardcoding the data into the algorithm you deprive it of flexibility and make it application specific. The performance of mine was sufficient for my application, but I can definitely see it struggle for bigger output formats with more options per node. This is something that needs to be improved upon.