Game AI
[Game Development] | [Software Development]
Description
I studied AI techniques used in game development, beginning with foundational algorithms, data structures, and representation strategies. From there, we explored practical applications, including arrival, alignment, wandering, flocking, path-finding, and decision/behavior trees.
I implemented each of these sophisticated AI behaviors and algorithms, gaining hands-on experience in designing agents and opponents that enhance player engagement and overall gameplay quality. My implementation was written in C++ with the Simple and Fast Multimedia Library (SFML).
Wandering
Flocking
Steering Behaviors
My initial implementation of steering behaviors centered on four major systems: arrival, alignment, wander, and flocking, each building on a shared kinematic framework.
Arrival enables a boid to decelerate smoothly as it approaches a target, using distance thresholds to control slowing and stopping behavior. Alignment rotates the boid toward its target orientation using angular acceleration and a deceleration radius, allowing movement to feel fluid and natural.
For more organic motion, I developed a wander behavior that projects a circle ahead of the boid and selects new target points along its edge using a binomial-distributed random offset. This creates continuous but non-erratic directional changes, producing lifelike drifting motion.
Finally, flocking combines separation, cohesion, and (local) alignment to let boids form dynamic groups. By averaging neighbor velocities, applying repulsion when boids get too close, and steering toward the group center, the flock maintains structure while still responding to wander forces. Together, these behaviors produce agents capable of smooth arrivals, intentional facing, natural roaming, and emergent group dynamics.
Path-finding
I explored two path-finding algorithms: Dijkstra and A*. My Dijkstra’s implementation relied on a priority queue for its open list and initially used a list for the closed set, but switching that to a dictionary cut runtime by more than half. A* began with a similar structure but required major fixes to avoid infinite loops, ultimately borrowing improvements from my Dijkstra work, especially using dictionaries for faster lookups. Adding a cluster-based heuristic further improved A*’s performance, particularly on large graphs where grouping nodes sharply reduced the search space.
Although the two algorithms share structural similarities, their performance diverges as problem size grows: when the goal is nearby, they behave comparably, but heuristics allow A* to explore far fewer nodes, reducing fill, fringe size, and overall runtime dramatically compared to Dijkstra’s exhaustive search.
[1]
[2]
[3]
[4]
Trees
My project implements three complementary AI systems: decision trees [1], behavior trees [2], and decision-tree learning [3]. The decision tree governs two boids whose behaviors change based on sight and distance, using chained decision nodes to choose between wandering, approaching, or idling, with visual breadcrumb colors signaling internal state.
In contrast, the behavior tree drives a monster sprite [4] using composite nodes such as sequences, selectors, decorators, and parallels, enabling more flexible and reactive behavior; the tree coordinates searching, size-based state changes, controlled growth, animation, and chasing a wandering boid.
Finally, the decision-tree learning system attempts to reconstruct this behavior automatically by parsing logged examples and using attributes such as scale, visibility, max-size state, and action labels to build a learned classifier.