Multithreaded Tower Defense
Real-Time Development
Multithreaded Tower Defense is a research project commenced under the advisement and supervision of Edward Keenan (Senior Professional Lecturer, DePaul University & former Executive Technology Director, Midway Games). The project was developed concurrently within the custom Azul game engine, which required building all necessary systems from scratch. Furthermore, Multithreaded Tower Defense utilizes various software engineering design patterns in an effort to optimize performance and maintain an architecturally-sound real-time environment. Various engine tools were developed and refined to support development of the application including:
-
2D Graphics system supporting alpha-blended, opaque, and box sprites
-
Collision system utilizing Composite Pattern to process unique object interactions
-
Various managers promoting effective re-use and recycling of real-time assets
-
Engine-integrated event system utilizing timed priority manager to execute commands
-
User input functionality for visual detection and placement of game objects
-
Fully integrated custom-built multithreaded audio engine including streaming functionality
The following videos and accompanying descriptions highlight several key aspects of the application, with certain statistics generated and displayed in real-time. This demonstrates the technical refinement of the systems developed to support the game; namely, object collisions and real-time asset recycling. All videos include various gameplay elements captured entirely in Debug mode, thereby better demonstrating the performance optimizations.
Collision System
The above video provides an overview of the basic interactions present within the game. To achieve this, a collision system was built utilizing a custom scene-graph-like data structure known as a PCSTree (Parent-Child-Sibling Tree). The PCSTree permits the simplified organization of game assets for fast modification in real-time. Regarding the interactions, the PCSNodes contained within the tree are arranged in a Composite/Component relationship, allowing for early-out collision detection. Furthermore, a fully integrated Iterator pattern was employed to perform quick O(N) traversals on the collections.
In order to maintain object-specific behavior, a Visitor Pattern was also employed to permit the optimal real-time processing of unique interactions. Since all objects present within the game inherit from the TDVisitor class, behavior can be defined for each unique collision. This subsequently eliminates the need for expensive conditional expressions to be checked each frame. An Observer/Listener Pattern is also employed in conjunction to efficiently process desired actions as a result of the collision. This proves useful in scenarios like processing explosion animations upon removal of an enemy object. The following is a UML-style diagram showing part of the architectural design for the collision system:
In this model, two objects within the game are attached to a unique CollisionPair instance, which in turn references (and is referenced back) by a CollisionSubject. Observers are then attached to the CollisionSubject which will be notified whenever an interaction, or collision, occurs between the CollisionPair. This encompasses the essence of an Observer Pattern, which provides both a significant optimization and organized layer of abstraction.
Object Recycling
When developing within any real-time environment, proper management of resources is paramount. An Object Pooling design pattern was utilized to manage many of the objects present within Multithreaded Tower Defense. This is most evident when pertaining to enemy objects, which are repeatedly spawned and killed in real-time. To mitigate the performance overhead of dynamically allocating enemies on-demand, an object-pooled manager was developed to reserve enemy objects during initialization of the game. By employing this pattern, the application can simply request an enemy object whenever necessary, and the manager is guaranteed to have one available. If more enemy objects are required in real-time, the manager will automatically grow its reserve to account for the unanticipated inflation.
A similar manager is used when performing the pathfinding required of each individual enemy. In any Breadth-First approach, a large number of search nodes is often required to mark potential paths. These search nodes must remain resonant in memory and easily modifiable when dealing with constant pathfinding in a real-time environment. Employing object pooling to manage the search nodes permits the enemies to re-use these assets. Furthermore, whereas many traditional implementations of search algorithms denote recursive characteristics, the searches performed in Multithreaded Tower Defense are entirely iterative, thereby decreasing stack consumption. The following video shows a stress test of the application, displaying object pooling characteristics of the enemy objects. The bottom left corner of the screen displays statistics from the EnemyManager class in real-time, including the current active and reserve node count:
While the pre-loading of enemies and re-use of search nodes remain critical, the most important aspect of the enemy manager pertains to the recycling of enemy objects. Whenever an enemy is killed or reaches its destination, the associated object is recycled and placed on the reserve list within the manager. This allows the application to re-use enemy objects repeatedly, and thus, reduce dynamic allocations in real-time. While this introduces an unbelievable amount of complexity into the system, the resulting optimizations yield significantly greater possibilities regarding potential enemy quantity. A general outline of the system can be seen in the following diagram:
EnemyManager contains the essential logic required to support the interactions of enemies throughout the running of the application. As can be seen in the diagram, the manager holds a reference to the EnemyGroup, which is a collection of all currently active enemy objects. Because of this, the appropriate enemy objects can be uniformly updated or modified each frame. In addition to managing the associated objects and collections, the manager also determines enemy path viability, in order to permit tower placement. If the user attempts to place a tower inhibiting an enemy from reaching its destination, the manager will detect and prevent the action from occuring. Numerous other managers exist to similarly support the various systems within the application, but the enemy manager presently encompasses the greatest degree of complexity.
Projectile Targeting System
The handling of projectile interactions within Multithreaded Tower Defense proved one of the most challenging aspects of development. As is required in any real-time application, the primary goal was initially to prevent unnecessary dynamic memory allocation. In order to achieve this, each tower owns and manages a single projectile, which is re-used throughout the entire application. The projectile interaction begins when an enemy intersects the radius of a tower object. Once this occurs, the collision is processed, and the projectile is updated depending on one of several scenarios:
Projectile is inactive: Projectile will be activated and move toward target
Projectile already engaging enemy target: Projectile will continue on the path to its current target
Projectile’s previous target still alive and in-range: Projectile will fire on previous target
Projectile’s reset timer has not expired: Projectile will remain dormant until reset timer expires
While in an active state, a collision of the projectile and enemy is guaranteed by use of linear interpolation between the objects each frame. This is just one of many functions performed by the custom math library created to support development of the Azul Engine. In the case of linear interpolation, vectorization is utilized by way of intrinsic operations(SIMD) in an effort to perform faster calculations.
The following video highlights the functionality of the projectile system, with an increased tower collision radius for better visual demonstration:
The optimization benefits of re-using the projectile objects come at the cost of having to manage their behavioral states. As can be seen above, there are numerous scenarios to account for regarding the various projectile interactions. To account for this, a State design pattern was employed to avoid the use of costly conditional expressions to determine which course of action to take. This is achieved by swapping the state object each projectile references in real-time, thereby modifying its behavior according to its present state. The following is a code snippet from the ProjectileState_Ready class used in the game; specifically its overridden Fire() method, which will send commands to the Azul event manager, and thus, change the projectile’s state to “active”:
Furthermore, the active projectile state does not have an overridden Fire() method, and will simply default to the base class implementation, which essentially does nothing when called:
There are currently three unique states employed by the projectile, including ready, active, and reset. The tower object updates its projectile each frame, which in turn updates its current state. An added benefit to employing the State Pattern arrives in the need to instantiate each state only a single time. This is possible because state objects are unchanging, simply providing uniform modification for passed in objects (in this case, a projectile). The following is a UML-style diagram showing the relationships present among the objects in the projectile system:
Multithreaded Tower Defense is a work in progress, and constantly changing. Check back for updates…