Home || About/Contact || Resume || Articles || LinkedIn
Ever since I started to learn how to program and implement gameplay, I’ve been excited to learn about AI. It’s an interesting problem to me: it’s easy to write code to make an enemy undefeatable by m, but for the purposes of player enjoyment, an enemy has to be able to be bested, to be perfectly imperfect. How can rigid code translate into abstract behaviors?
Needless to say, the AI programming course I took in college was one of my favorites, giving me some glimpses into the basic pieces that make enemies operate the way they do. The earlier projects we did were made in C++ using a codebase that our professor provided us, and the first projects we were assigned dealt with steering and flocking.
A video showing my flocking algorithm written in C++. I wrote an input manager to allow the user to adjust various steering values at runtime and save them to a .txt file.
We were first told to implement individual steering behaviors for units to use, but were then introduced to combined steering. This eventually lead to implementing a flocking behavior, which is comprised of three steering behaviors: cohesion steering keeps units together; separation steering gives units some space between each other and prevents them from all stacking at the same point; and alignment steering moves them forward. These are all combined in a flocking steering file, which gives each steering behavior a weight, then averages the direction of all of them.
Steering* AlignSteering::getSteering()
{
mAngular = 0; //Initializes values that will be returned
mLinear = 0;
float rotation = 0;
//Sets all other units within a given range as targets
setTargets(UnitManager::getInstance()->
getUnitsInRange(mpMover->getPosition(), mTargetRadius));
//Adds up the differences between this unit's rotation and targets' rotations
for (KinematicUnit* unitPtr : mpTargets)
mLinear += unitPtr->getOrientationAsVector();
//Averages rotations
mLinear /= mpTargets.size();
rotation = atan2(mLinear.getX(), mLinear.getY());
rotation = convertToRadians(rotation);
//Clamps rotation of unit to match a certain rotate speed
float targetRotation;
if (rotation > mSlowRadius)
targetRotation = mMaxRotation;
else
targetRotation = mMaxRotation * (rotationSize / mSlowRadius);
targetRotation *= (rotation / rotationSize);
mAngular = targetRotation - mpMover->getOrientation();
mAngular /= mTimeToTarget;
float angularAcceleration = abs(mAngular);
if (angularAcceleration > mMaxAngularAcceleration)
{
mAngular /= angularAcceleration;
mAngular *= mMaxAngularAcceleration;
}
return this;
}
The getSteering function for the align steering, which is called from the flocking steering every frame.
Steering* CohesionSteering::getSteering()
{
mLinear = 0;
//gets all units within a range
setTargets(UnitManager::getInstance()->getUnitsInRange(mpMover->getPosition(), mThreshold));
for (KinematicUnit* unitPtr : mpTargets)
{
//Gets the distance between the unit and the current target
Vector2D direction = unitPtr->getPosition() - mpMover->getPosition();
float distance = direction.getLength();
if (distance < mThreshold)
{
float strength;
//Clamps the strength of the target's influence
if (distance < mMaxAcceleration)
strength = distance;
else strength = mMaxAcceleration;
//Normalizes the direction, then multiplies it by strength
//and adds it to linear velocity
direction.normalize();
mLinear += direction * strength;
}
}
return this;
}
The getSteering function for the cohesion steering, which is called from the flocking steering every frame.
Steering* SeparationSteering::getSteering()
{
mLinear = 0;
//gets all units within a range
setTargets(UnitManager::getInstance()->getUnitsInRange(mpMover->getPosition(), mThreshold));
for (KinematicUnit* unitPtr : mpTargets)
{
//gets the negative distance between the unit and the current target
Vector2D direction = mpMover->getPosition() - unitPtr->getPosition();
float distance = direction.getLength();
if (distance < mThreshold)
{
float strength;
//Clamps the strength of the target's influence
if (distance < mMaxAcceleration)
strength = distance;
else strength = mMaxAcceleration;
//Normalizes the direction, then multiplies it by strength and adds it to linear velocity
direction.normalize();
mLinear += direction * strength;
}
}
return this;
}
The getSteering function for the separation steering, which is called from the flocking steering every frame.
Steering* FlockingSteering::getSteering()
{
mLinear = 0;
mAngular = 0;
//Gets the align steering result
mAlign->getSteering();
//Gets the separate steering result
mSeparate->getSteering();
//Gets the cohesion steering result
mCohesion->getSteering();
//Combines the three results using a weighted average
//Weights can be tweaked at runtime
mLinear = (mAlign->getLinear() * mAlignWeight) + (mSeparate->getLinear() * mSeparationWeight)
+ (mCohesion->getLinear() * mCohesionWeight);
mLinear /= mWeightTotal;
return this;
}
The getSteering function for the flocking steering, which calls the three steering functions above.
The next unit dealt with pathfinding. Our professor talked with us about several different common algorithms for this purpose. It was interesting to note that, as a newcomer to AI, the Dijkstra algorithm was most in line with how I assumed pathfinding would work: from the start point, the algorithm would search through all adjacent nodes, then search through the nodes adjacent to those, and so on until it hit the destination. What we were assigned to do, though, was to implement A*, which turned out to be much simpler:
A video demonstrating my A* algorithm written in C++. The program finds the path to the point clicked from the point previously clicked.
A* offers a simple tweak on Dijkstra: instead of searching through every single possibility, A* looks through all adjacent nodes and finds the one that is the shortest distance from the destination. It then searches through the nodes adjacent to that one, and so on until it reaches the destination node. Using these distance checks, this methods cuts off a lot of possible paths that Dijkstra has to search through.
const Path& AStar::findPath(Node* pFrom, Node* pTo)
{
//defines the open and closed node lists
std::vector<Node*>open;
std::vector<Node*>closed;
//Sets pFrom node as start of open list and initializes values
pFrom->setCost(0);
pFrom->setHeuristic(0);
pFrom->setPrevNode(NULL);
open.push_back(pFrom);
mPath.clear();
//Creates coordinates from pTo node to use in heuristic checks
int destX = pTo->getId() % mGridWidth;
int destY = pTo->getId() / mGridWidth;
//Sets pFrom as current node
//Creates vector for connections and pointer to other node on connection
Node* pCurrentNode = pFrom;
std::vector<Connection*> connections;
Node* endNode;
//While the current node isn't the pTo node
while (pCurrentNode->getId() != pTo->getId() && open.size() > 0)
{
//Finds the node with the smallest heuristic, then gets its connections
pCurrentNode = FindSmallestHeuristic(open);
connections = mpGraph->getConnections(pCurrentNode->getId());
//For all of this node's connections
for (Connection* connectionPtr : connections)
{
endNode = connectionPtr->getToNode();
//if already visited, ignore
if (SearchForNode(endNode, closed))
continue;
else if (SearchForNode(endNode, open)) //if in the open list
{
//if the node is further back on the path
if (endNode->getCost() <= (pCurrentNode->getCost() + connectionPtr->getCost()))
continue; //ignore
}
else //if not on the open or closed lists, add to open list
{
endNode->setCost(pCurrentNode->getCost() + connectionPtr->getCost());
endNode->setPrevNode(pCurrentNode);
endNode->setHeuristic(CalcDistance(endNode, destX, destY));
open.push_back(endNode);
}
}
//when done with this node, add it to closed list
closed.push_back(pCurrentNode);
open.erase(open.begin() + FindNodeIndex(pCurrentNode, open));
}
//if no solution, just return current path
if (pCurrentNode->getId() != pTo->getId())
return mPath;
else
{ //If there is a solution, construct path to return
mPath.addNode(pTo);
while (pCurrentNode->getId() != pFrom->getId())
{
mPath.addNode(pCurrentNode->getPrevNode());
pCurrentNode = pCurrentNode->getPrevNode();
}
}
//reverses path, since construction above started with destination
return ReturnReversedPath(mPath);
}
The main function of the implementation of A* I wrote. Navigation is based on a grid graph.
The most advanced project we ended up doing involved making state machines. We were tasked with making a game where there were state machine-driven enemies, and where the player could press a button to toggle state machine AI for the player character as well. I suggested to my teammates that Pac-Man would be an ideal game for this project, which they agreed with. They also suggested that we use Unity for this project, since they just discovered that it had navmesh available.
A video of our state machine project in Unity. I was responsible for implementing the player state machine, while Paul Webster-Pact implemented the ghost state machines. Chris Johnson handled the state machine architecture, as well as XML parsing that allowed our state machines to be created at the start of the game.
We first needed to figure out what states defined both the player behavior and the ghost behavior in Pac-Man. We also needed to figure out what conditions in each states would cause a transition to another state, and what it would transition to. Having used something similar to universal markup language (UML) for some systems design documents, I offered to create diagrams for the state machines in order to alleviate confusion.
Two UML diagrams I made to define how the state machines operated.
As for implementation of the states themselves, Unity’s navmesh capabilities were a great help, since we wouldn’t need to port one of our pathfinding projects from C++. Because of that, all we had to worry about was the logic handling transitions between states, and the steering that would send the ghosts or the player in a certain direction.
public override StateTransition UpdateState()
{
StateTransition toTransition = new InvalidTranstion(TransitionType.INVALID_TRANSITION_TYPE, -1);
//Only runs if the player has toggled the AI to run
if(!manager.getIsPlayerControlled())
{
Vector3 targ = Vector3.zero;
//Gets the average direction between the player and each ghost
foreach (GameObject ghost in ghosts)
{
targ += (ghost.transform.position - gameObject.transform.position);
}
targ /= ghosts.Length;
//Sets that point as the destination
agent.SetDestination(targ + gameObject.transform.position);
}
if(!manager.getPowerPelletActive()) //if time runs out
{
bool inRange = false;
//Checks to see if any ghosts are in range of the player
foreach(GameObject ghost in ghosts)
{
if ((ghost.transform.position - gameObject.transform.position).magnitude < fleeRadius)
inRange = true;
}
//If ghosts are in range, transition to flee enemy state
if(inRange)
{
return GetTransitionOfType(TransitionType.P_FLEE_ENEMIES_TRANSITION);
}
else //If not in range, transition to seek dots state
{
return GetTransitionOfType(TransitionType.P_SEEK_DOTS_TRANSITION);
}
}
return null;
}
The update function for the chase enemy state, which is activated when the player eats a power pellet.
public override StateTransition UpdateState()
{
StateTransition toTransition = new InvalidTranstion(TransitionType.INVALID_TRANSITION_TYPE, -1);
//Only runs if the player has toggled the AI to run
if(!manager.getIsPlayerControlled())
{
Vector3 targ = Vector3.zero;
//If ghosts are within flee radius, add their negative distance
foreach (GameObject ghost in ghosts)
{
if ((ghost.transform.position - gameObject.transform.position).magnitude < stopFleeRadius)
targ += (gameObject.transform.position - ghost.transform.position);
}
targ /= ghosts.Length;
//If the player is within 10 units of a power pellet,
//ignore ghosts and go straight to that
foreach (GameObject pellet in powerPellets)
{
if (pellet != null && (pellet.transform.position - gameObject.transform.position).magnitude < 10.0f)
{
targ = (pellet.transform.position - gameObject.transform.position);
}
}
agent.SetDestination(targ + gameObject.transform.position);
}
//If no ghosts are in range, switch to seek dots state
foreach (GameObject ghost in ghosts)
{
bool inRange = false;
if ((ghost.transform.position - gameObject.transform.position).magnitude < stopFleeRadius)
{
inRange = true;
}
if(!inRange)
{
return GetTransitionOfType(TransitionType.P_SEEK_DOTS_TRANSITION);
}
}
//If a power pellet is activated, switch to seek enemy state
if (manager.getPowerPelletActive())
{
return GetTransitionOfType(TransitionType.P_SEEK_ENEMIES_TRANSITION);
}
//If a ghost hits the player, transition to death state
if(manager.getIsDead())
{
return GetTransitionOfType(TransitionType.P_DEAD_TRANSITION);
}
return null;
}
The update function for the flee enemy state, which is activated when ghosts are in range of the player and no power pellet is active.
public override StateTransition UpdateState()
{
StateTransition toTransition = new InvalidTranstion(TransitionType.INVALID_TRANSITION_TYPE, -1);
//Only runs if the player has toggled the AI to run
if(!manager.getIsPlayerControlled())
{
Vector3 targ = Vector3.zero;
int dotCount = 0;
//Gets the average distance between the player and all pellets
foreach (GameObject dot in dots)
{
if (dot != null)
{
++dotCount;
targ += (dot.transform.position - gameObject.transform.position);
}
}
targ /= dotCount;
//Sets destination to average position
agent.SetDestination(targ + gameObject.transform.position);
}
//If a ghost is within the range of the player, switch to flee enemy state
foreach (GameObject ghost in ghosts)
{
if((ghost.transform.position - gameObject.transform.position).magnitude < fleeRadius)
{
return GetTransitionOfType(TransitionType.P_FLEE_ENEMIES_TRANSITION);
}
}
//If a power pellet is active, switch to seek enemy state
if(manager.getPowerPelletActive())
{
return GetTransitionOfType(TransitionType.P_SEEK_ENEMIES_TRANSITION);
}
return null;
}
The update function for the seek dots, which is activated when ghosts are not in range of the player and no power pellet is active.
Jared Mitchell 