Autonomous A* Pathfinding
C#, Unity

Summary:

I wrote a Unity project to practice what I learned in Game AI and demonstrate A* pathfinding with steering behaviors.

I enjoyed working on both A* pathfinding and creating autonomous movement through steering because they are relatively simple yet powerful when combined.

I've embedded 2 videos & described the implementations below.

Scope:

Personal Project | C#, Unity


A* Pathfinding

I implemented A* pathfinding using a grid setup in Unity. In the video scene, ten zombies are simultaenously using A* to constantly calculate their paths to the player as the player runs around.

My Contributions:

To reduce lag and improve runtime, I:

  1. Spread the processing of each zombie into separate frames to avoid lag from computing all paths on 1 frame
  2. Utilized my own Priority Queue class to better handle the retrieving of the Node with the lowest F-cost
  3. Used HashMaps to reduce the cost of checking if a node was contained in open or closed sets
  4. Only recalculated paths if the target moved to a new node or location

Results:

I found it exciting to be able to see the paths of each zombie change as the player moved around various obstacles!

Implementation is @ my Github Pathfinding Folder.

Look at Pathfinding.cs for the A* Algorithm.


Autonomous movement

I implemented autonomous behaviors through calculation of steering forces. Steering is done by calculating the force required to achieve a desired movement behavior for any AI character.

All movement was handled through calculations of acceleration, velocity and position. Unity’s collision detection was also turned off to prove the AI is calculating obstacle avoidance vs. relying on the physics engine.

My Contributions:

I implemented many behaviors such as:

  1. Crowd flocking to form a triangle, circle, square or V shape
  2. Seeking towards a target
  3. Fleeing from a target
  4. Wandering randomly
  5. Avoiding obstacles

Results:

Implementing autonomous movement allowed me to create zombies with much more realistic movements.

By "pushing" zombies, their movement is more fluid than if they were being programmed to directly go to XYZ point.

This can be seen in the A* Pathfinding video which combines autonomous movement with A* pathfinding guidance.

Implementation is @ my Github BasicMovement Script.

Look at the MoveController.cs for the behaviors mentioned.

Look at the Flocking Anchor.cs to see algorithms for shape-based flocking.