DEV BLOG
CROWD PATHFINDING SIMULATION
This summer, I decided to work on furthering my knowledge of AI algorithms by working on creating a Crowd Simulation that was capable of modeling individual behaviors amongst a larger group. Taking heavy inspiration from the multiplayer in Assassin’s Creed: Brotherhood I wanted to create an AI that incorporated many systems including Pathfinding, Steering, Immediate Collision Avoidance, Predictive Collision Avoidance, and Flocking.
The goal was to create a Crowd Simulation so realistic that not only did it look like an actual crowd in a busy area, but that a player could blend right in.
UPDATES
7/28
This week, I prepared for my final presentation of my project. This involved some project changes such as cleaning up parameters to better optimize movement. However, I also added other changes purely for presentation purposes.
One such change I made was adding a toggle for a lot of the drawn elements in the game. This proved more complex than I would have imagined, and is something I wish I had considered from the start. That being said, I decided to implement a manager that could take input and handle setting other objects accordingly. It would handle all the different cases for what variable to flip on different actors (Nodes, Civilians, Player).
The other major feature I added in engine for presentation purposes was a top-down camera. This could give a viewport of the scene agnostic of which Civilian the player was controlling. My purpose in doing this was to address the original goal of the project of creating a Crowd AI that would allow a normal player to move within itself while blending in and appearing natural. I could now control a player character amongst Civilians with no indicator as to which I was controlling. I could then analyze footage to see if the player character was identifiable.
To aid in this test, I added colors to a set amount of Civilians in the level, as well as the player. These were used as an indicator so that whoever was watching could guess which color the player was. I then added a button to remove colors from Civilians to narrow down options as the person got incorrect answers.
Overall, the movement appeared reasonably natural for a crowd, and almost no one was ever able to tell which character the player was. Don’t believe me? Here is a sample below, see if you can figure it out.
I also prepared a PowerPoint presentation similar to my initial pitch and mid-way status update. I went over some of the things I had implemented before the half way mark, as well as what I did since then. My presentation concluded with the demo you see above.
Conclusion: Overall, I feel as though I was able to achieve the goal I originally set out to achieve of a player-realistic crowd path finding simulation. The crowds move in natural ways that a player is easily able to disguise amongst without having to move abnormally. Given more time I would add more collision avoidance checks as well as focus on more gameplay elements to test the system even more in context.
7/21
This week, I decided to focus more on some of the Microscopic models I researched in my previous week’s work.
To fix this, I set the AI so that it would disable Predictive Collision Detection towards Civilians that it considers to be a part of its group while it is Sprinting. Since the Civilians determine those in their group based on their current movement, this means that they do not consider stationary Civilians to be apart of their group, so they will still be avoided.
Here we can see the grouping in action. The result is less of hard-set groups and more of a tendency of Civilians to walk together along the same routes. The benefit to this looser grouping is that Civilians are no way impeded from reaching their goal by trying to follow others.
Although it was a bit intimidating to open the door to allowing Civilians to change their speed, the planned designs used previously made it safe to do. Since Civilians grouping does not affect their Steering at all, but only their Speed, this means that Civilians will never fail to reach their goal because of trying to follow others. I find this method to enhance the functionality of my source material, Assassin’s Creed, and provide further functionality from what was originally in that game.
In my last week I researched Microscopic and Macroscopic models of AI behavior. Upon further review, based on the Microscopic focus of my model thus-far, trying to add Macroscopic functionality onto the model at this point is not a reasonable course of action with the amount of time remaining. Instead, I decided to use further Microscopic methods to utilize a feature I have thus-far been avoided changing: speed.
I originally avoided changing the Civilians’ speeds as I wanted to keep their movement within that of a player. Most player inputs do not allow a range-based movespeed, and those that do (controller) are mostly not utilized by players (they tend to hold the stick at max or not at all). So instead, I restricted my model’s speed controls to only allow for 3 different move speeds. Idle (x0), Walking (x1), and Running (x2).
I then used these properties to achieve a grouping behavior, which I had so far not been focused on. I used a similar technique as was used in Assassin’s Creed: Brotherhood in which the ai would speed up if they got too far away from their group. This way the ai in the front could path normally, and the ones in the back could increase speed to not get left behind as obstructions got in the way.
However, there was one main problem. The ai in Assassin’s Creed relies on predefined groups and ai having the sole purpose of staying in that group. Each individual ai has no individual goal or target; while mine do. This made defining clear cut groups not feasible whilst still fitting with my current system.
So to account for this, I instead had the groups be specific to each Civilian. Each Civilian can determine for itself what groups it believes itself to be a part of, even if no real group exists. To do this, each Civilian finds all other Civilians that are in front of it and moving in the same direction as it, and assumes that is its group. If the Civilian finds it is too far away from its closest group member, it sprints to catch up.
However, this lead to an unintentional problem. Last week I had implemented a predictive collision system. Civilians can see future collisions before they happen and attempt to avoid them. Because of this though, when a Civilian is Sprinting to catch up to another Civilian in front of it, it foresees a collision and steers to avoid.
Next Week: Polishing parameters and limit testing. Testing original goal of disguising a player amongst Civilians. Preparing final presentation and associated demos.
7/14
This week, I decided to take a second chance to go in depth researching all types of crowd simulations currently being used. I will go through and summarize some of my research here as well as how it relates to my model.
One type of Microscopic model is a Rule-Based model. In this design, each actor has a set of conditions and results that then either dictate or influence its behavior.
One simple implementation of this is Boid’s algorithm. This takes in 3 different influences on each actor to dictate its desired movement direction. Separation ensures actors are not too close to each other, cohesion keeps actors in groups, and alignment influences actors to keep moving in the same direction as those around them.
The drawback to this algorithm is that the actors have no destination, but instead move wherever they see fit that follows the above rules. There is no pathing in this algorithm, but rather, only steering.
Although I use a separation component in my algorithm, I achieve the effects of cohesion and alignment through other methods.
The alternative to Microscopic models are Macroscopic models. While Microscopic models function based on individual actors and their movements, Macroscopic models create crowd simulations by controlling all actors as part of a wholistic system. This means that functions such as collision avoidance and clustering are handled from a central problem solver.
One such Macroscopic model is the Continuum model. What this model does is it takes the desired movement of each agent in a given area, and uses it to calculate the average flow within that area. All actors within that area then have their movements adjusted to better align with the flow in the area. The flow is also projected to determine what the flow in the area will be for those actors in the future as they move through the area. This results in traffic common crowd behaviors such as traffic lanes and clustering. Although this doesn’t handle low-level movement such as collisions avoidance, it is great for creating a natural flow of traffic. I could see something like this adding well to give a more flow-like feel to my simulation.
Another common way of controlling the flow of traffic in a Macroscopic model is using Guidance fields. Stemming form fluid dynamics, a Guidance Field is essentially a flow field that helps to encourage high and low traffic routes. The different influences on the grid of a guidance field influence the steering choices of the actors as they move across them. These Guidance Fields can either be calculated dynamically based on environmental conditions, or manually created to encourage specific behavior.
A third type of crowd movement simulation is Mesoscopic crowd simulations. In these models, actors share a common goal and attempt to communicate with each other individually to achieve this goal without relying on a high-level organizer. This is often used to cause actors to attempt to create specific patterns or formations, such as geese flying in a V.
Source: Yang, Shanwen, et al. “A Review on Crowd Simulation and Modeling.” Graphical Models, 27 July 2020, www.sciencedirect.com/science/article/pii/S1524070320300242#sec3.
The first type of simulation algorithm is a Microscopic model. These types of models work at the individual actor level providing rules for each individual to follow. Using multiple actors in conjunction with these rules results in crowd-based behaviors. The model I have developed thus far is a Microscopic model.
Another type of Microscopic model is a Force-Based model. In this model, many different factors add forces to an actor to determine its movement. Objects such as walls or other actors add a force in the direction opposite of their position, scaling inversely based on the distance to that actor. These forces are then added and normalized and the actor then has its new desired movement direction to avoid obstacles.
In itself, this is only an avoidance algorithm. However, adding other factors to this such as a force in the direction of desired movement results in pathing and avoidance.
This is the most similar algorithm to the one I have implemented. I add many forces for different factors such as other actors, but also for other factors such as moving in the direction of the path as well as moving closer to the path if the actor is too far away.
One other type of Microscopic model is the Velocity-Based model. In these models, the velocity of obstacles are considered in order to avoid future collisions. This considers factors such as a VO space which is the parts of a velocity that will lead to a collision and uses this to cause new velocities to be chosen that will avoid future collisions.
Some common implementations of this are a VO (Velocity Obstacle) model as well as the RVO (Reciprocal Velocity Obstacle) model.
My model uses a similar technique, but instead of calculating a VO space based on the cone of projected collision, I instead move in the opposite direction of the closest point of collision.
However, there are other applications to this type of algorithm that could still be useful to my project. One such application is having actors attempt to path around each other as they are moving towards each other. Although it may not seem clear at first, essentially the two actors need to move into the formation in which one or both actors move around the other.
I currently have a similar behavior to this, but achieved through collision avoidance as opposed to coordinated movement. If the collision avoidance does not appear to be sufficient with further testing, a simulation such as this may be beneficial.
In conclusion, there are tons of different ways that crowd pathing can be influenced from a high and low level implementation. However, all good crowd simulations develop as a combination of many different influences and algorithms. Finding the right combination and balance of these different algorithms and influences is what leads to a truly efficient and accurate simulation.
Next Week: Implementing some of the algorithms researched this week. Seeing which fit well with the current implementation and tweaking parameters from there to gain the most value possible from them.
7/7
This week, I designed and implemented a Predictive Collision Avoidance system to calculate collisions long before they happen and subtly avoid them.
I couldn’t find many great resources on how this had been done in the past, so I decided to work from scratch.
My first consideration was what information I have available to calculate at a given time. I can’t know for certain the exact path of each AI, so I must project their path using their current Position and Vector. This is, of course, not always accurate, but is a great guess that is easy to calculate
From here, I can calculate the distance between each Civilian at any time (in the rough prediction) by multiplying each of their Velocities by a time t and adding it to their current positions.
A few hours of parameter tweaks later, and the results were astonishing. The Civilians were pathing to avoid each other in intelligent, seamless manners. Civilians would comprehend not only future collisions with a single other Civilian, but all other relevant Civilians, often weaving between multiple others to move in the optimal route.
This showcases the immense power of combining different, simple steering forces in a way that can efficiently, effectively, and naturally calculate intelligent pathing routes around dynamic obstacles.
Last week, I made it so that the Civilians would avoid each other if there current positions were too close to each other, trying to avoid a collision. And this worked great for stopping them from colliding, however it wasn’t really natural.
Imagine you are walking down the middle of a long hallway, and you see someone walking towards you from the other end of the hallway. The average person does not wait for the other to be right next to them before deciding how the two will navigate. Instead, a subconscious exchange occurs in which each party tries to estimate which direction the other is going and then tries to slowly move in the other direction, also then indicating to the other party their desired path. This is the behavior I wanted to implement.
Now to find the point where they may collide, we needed to find the value of t such that the distance between the two Civilians, D, is minimized. Since both of the Civilians are predicted to be moving at a linear rate, and the distance between the two is a factor of that squared, the graph of their movement is essentially a parabola. This means that there is exactly one Minimum in the entire graph.
To find this minimum, I calculate the derivative of my position equation and set it equal to 0. This finds the point at which the change in distance is 0 and at the minimum. From here I solved for t and plugged that in to the original equation to find the position of each Civilian when they are closest to colliding.
From here, I can take the vector between each of the two Civilians and add it to the current Civilian performing the calculation such that they are influenced to move in the opposite direction of the other Civilian at the point they would have been closest to colliding.
The last step was to scale this vector. The first multiplier was to invert its magnitude, as we want to add more of a force away from the other vector the closer the two Civilians are to each other in the predicted movement. Secondly, we also want to scale by the inverse of t, as we want to have more of an effect on collisions that are predicted to happen sooner.
Next Week: Civilians need to also avoid walls as they sometimes get forced into (and currently through) them. Fine tuning Parameters both linearly and exponentially can lead to even better results.
6/30
This week, I implemented the Collision Avoidance System to allow Civilians to path around obstacles.
Last week, I had adjusted my system so that Civilians movement was based on steering, and that a set of vectors would be weighted and added based on a set of parameters to determine movement direction.
This week, I added to that system by adding influence to move away from any other actors in the scene marked as Avoid. This allowed Civilians to move along their path, while avoiding obstacles.
The first step in this process was making sure that each Civilian knew about the Avoid actors in an efficient manner.
To do this, I created an Actor Component called Avoid that could be attached to any other actor. When the game begins, this component registers the Actor it is attached to in an Avoid list.
To store this list, I needed some sort of static or singleton pattern. However, since Unreal allows Editor level code, I needed to make sure any static variables I was creating were local to each run of the game. I decided to create a custom GameInstance child, with the only difference from its parent being 2 lists and functions to handle adding and removing elements from those lists. The two lists in the GameInstance were the Avoid list and the list of all Civilians in the world. Civilians were then set to add themselves to this list upon the game starting. This means that the GameInstance could send the updated list of Avoid obstacles to the Civilians whenever it was changed.
This was a simple implementation of the Observer pattern, as Civilians would subscribe themselves to the GameInstace and would be notified whenever the Avoid list changed.
Civilians could then check the elements in Avoid each tick to determine which Actors were close enough to start avoiding.
If an Actor was close enough to the Civilian, a Vector would be added to the Civilians AvoidVector that was inversely exponentially proportional to the length of the vector from the Avoid to the Civilian. In other words, the Force added to tell the Civilian to turn away from the Actor increases the closer the Actor is to the Civilian.
This lead to some pretty good behavior, however there were a few more polish steps I wanted to take this week.
One change I made was to make it so that an Avoids influence on a Civilians movement was scaled based on how close the Avoid was to being directly in front of the Civilian. This meant that the farther an Avoid got from the immediate direction of the Civilian, the less the Civilian would try to avoid it.
The other major change I made was to consider the direction of the Avoid in relation to that of the Civilian. If the Civilian is moving in the same direction as the Avoid, collision is impossible given no external collisions and the same speed of each. This means that I add influence to those Avoid that are moving as opposite to that of the Civilians motion. This is my first step into Predictive Collision Avoidance.
Next Week: Begin Predictive Collision Avoidance as well as Scale Test using full map size.
6/23
This week, I focused on redesigning some of the work to instead support a Spline system of movement.
My plan for this week had been to begin implementing the avoidance system to allow Civilians to avoid obstacles in their path. However, as I began planning out the system for how this work work, I realized that the smoothing system I had implemented in my previous week did not fit well with this design.
The nested LERP functions used in the smoothing system did not lend themselves very well to any sorts of deviation, as they calculate based on a fixed path.
The solution I found to this problem, was to calculate the entire path of the AI and smooth along one continuous route. In other words, a Spline.
By using a Spline, I could determine the entire spline as soon as the route is calculated, and then steer the entity by having it prioritize 3 factors: staying close to the spline, and moving in the same direction as the spline, and continuing moving in the same direction.
Taking a look at what made this system so static, I found the main issue to be that I was trying to directly calculate the entities position. This leads to fixed, non-natural movement that is neither smooth, nor realistic.
Instead I wanted to limit the AI to (initially) only be able to turn. To do this, I needed a route that I could map out for the AI and have it steer to try and stay on, allowing deviation as necessary to avoid obstacles.
These three forces were represented as Vectors, and by combining these forces together in different ratios, I could achieve varying AI behavior. Setting these up with simple parameters allowed manual tweaking, and will continue to be fine tuned through out the rest of the project.
Next Week: With the new system in place, expect the Collision Avoidance System to be up and running.
6/16
This week focused on implementing animations, and then smoothing out the routes that the characters were following.
The first thing I worked on was hooking up the animations I had already made the blend states for. This just involved adjusting the variables between the Blueprint Animation and the C++ of my character. Added a specific variable on the Blueprint called Speed that would then be updated based on the Civilians own value of Speed.
Since both the player and the Civilian use the same Blueprint Animation, they are able to line up perfectly in their movement.
To accomplish this, I used 3 different Linear Interpolations (LERP) in conjunction with each other to create an Arc.
To do this, I started by using a LERP on the Vector the player had currently been on towards the center of the circle. At the same time, I would use another LERP to find the point from the Center of the circle towards the edge the player wanted to exit on.
By then finding the Vector that connected those two points at any given time, I could then LERP on this new Vector to calculate the desired player position. All I had to do now was move the player along that arc.
From here, the main connection between the two Arcs is that they share the same Cord (C). This Cord can be calculated using the Radius of the Circle and the Angle of the Arc.
This means that Since we know the Radius and Angle of the first circle, and the Angle of the second circle, we can then find the last piece of information: the Radius of the second circle (R2).
Now knowing R2 and a2, we can then use these to calculate the length of A2: the arc the player will be traveling on. From here we can use this distance to determine how fast the player should be moving through out this section.
The next thing I tackled was the fact that the Civilian movement was way to strict; in that Civilians had to previously walk node to node in straight lines with no deviation.
To help ease this problem before diving head-on into steering, I made it so that each Node had a radius that designated an area around that Node that civilians were free to path within. From there, I made it so that Civilians would calculate where they would enter the Node’s Radius, where they wanted to exit, and move in an arc in between those two points.
This already resulted in much more natural pathing.
However, there was one slight problem: I had no idea how fast to move the player along this arc.
Player movement was being handled via a series of LERP, which operated on a range of 0.0 - 1.0. The problem was that I had no idea what that translated to in Player Speed since I didn’t know the length of the Arc the player would move on.
To calculate the Arc (A2) I began by projecting out the circle represented by A2 for a given angle a1. The angle of the arc of A2 (a2) could be then easily found since you can form a square between P1, P2, P3, and P4 since all angles in a square add to 2Pi Radians.
This week was a great exercise in my Vector Math and using the information available to calculate the information needed. Sometimes complex equations are required to create behaviors that seem so simple when seen naturally.
Next Week: Expect some work with Steering and allowing the player to step off of the Path to avoid obstacles.
6/9
For this week, I focused on implementing the A* algorithm with the current node system. Although I had implemented this algorithm before, integrating it well with the my new node system was interesting.
The first step was to implement basic A* pathing. A Civilian character would start at a random node and pick another node to path to. The Civilian would then before the A* algorithm calculation to efficiently find the shortest path from the Start Node to the Target Node through any other nodes in the graph. Once the Civilian reaches the Target Node, it then goes Idle for a random amount of time. Afterwards, it then uses its Target Node as its new Start Node and chooses a new Target Node and begins calculating again. This simple State Machine can later be modified for more dynamic behaviours.
Speaking of multiple Civilians, the last thing that was implemented this week wasn’t even much of an implementation; it was just testing the behavior with more than one Civilian.
Due to each Civilian containing their own internal Path that they calculate when they run A* they each path autonomously as desired. By marking when they are targeting a Node, it ensures that there are never too many Civilians targeting a given node based on that Node’s Capacity.
The next aspect I wanted to implement was adding a specific Capacity to each Node which represented how many Civilians could be at, or pathing towards, that Node at a given time.
One great benefit of this is that Civilians would no longer be going idle in high-traffic zones, and instead can be designated to only go idle in areas that will not impede traffic.
Since this system allows me to designate how many Civilians can be at a given Node, this gives the potential for some Nodes to allow interactions between Civilians that are Idle at them.
Although I have implemented an A* algorithm many times before, this was by far my most efficient an modular design so far. The most rewarding point was testing with a single Civilian for much of the development, and then getting immediate success when adding more Civilians purely due to the design of the system.
6/2
This week, I began production on my proposed project. My main focuses were on setting up the map, as well as implementing the node system to be used in the A* implementation.
The first thing I chose to implement was the map layout. Although I probably spent more time on this than I should have, I focused heavily on population flow and creating both high and low traffic areas. This would allow for wide ranges of context-specific AI behavior.
Lastly, I began implementation of the A* algorithm and creating the nodes necessary for implementation. I added a C++ class for the node actor as well as implementing connections to other nodes. For ease of editing nodes in the editor, I added a spline component that was only drawn in the editor and would dynamically update based on which nodes were connected to a given node. This allowed paths to be easily created and visualized.
Next, I took a look at the Player Model provided by Unreal as well as the default character controller for NPCs. I decided to create my own animation transitions controller to use between each of these two actors to ensure consistency. I did not want to run into the problem later down the line of the player not blending in with the AI at all solely due to animation consistency.
Overall there was much more setup than I originally anticipated, but taking these steps early on should hopefully prevent extra work later on.
5/26
Recently, I pitched my plan for a complex crowd AI simulation. By combining a pathing algorithm such as A* with multiple steering algorithms such as Boid and RVO, I plan to achieve natural crowd movement in such a way that a player can become indistinguishable from AI. The project was quickly approved to begin production.
Below I have attached some of the slides used in my presentation pitch.
