Multithreading Continues

With the deadline to push for a polished beta build of our game closing in fast, I really want to bring my focus back to fixing the MT-D*-Lite issue. But of course, things rarely go my way. With the multithreading system in, I managed to integrate A* with ACO into our game without any major performance hits. However, upon further testing, multiple issues arise.

The first being the game would lock up on occasion when there are many enemies alive and turrets are placed which then causes all the enemies to try and re-path (an unfortunate drawback for A*). While this seems relatively harmless, since I have moved the A* calculations onto threads so it does not hold-up update calls, I have forgotten that I had also multithreaded physics collision. With the previous threading system setup, I have a job queue that threads pull jobs from. I start threads at the start of our engine and the thread waits until there are available jobs in the queue or shutdown is called. But therein lies the problem. I push both A* calculation jobs and physics jobs into the same queue. There is a limited amount of threads that can be running simultaneously. Thus, if the queue is first flooded with A* calculation jobs, it has to first process all those jobs before it gets to the physics jobs that are pushed in later on in the queue, and therefore, causing updates the wait and hangs the game.

To resolve this issue, I have decided to create two separate queues. One for critical game stopping jobs and one for other jobs that are not essential for the game to run smoothly. Additionally, I set aside a percentage of threads to dedicate only to process critical jobs to avoid the chance that all threads be occupied by non-critical jobs which we also cause the game to hang.

Another major issue this week is our game freezing during restart while there are still enemies alive. This poses a similar issue as the previous where the game hangs because it needed to first complete all the running jobs. More precisely, on restarting, all active enemies call a function that destroys themselves. However, this logic does not execute and resolve until our game goes through a late update, which gave enemies the time to continue adding jobs to the queue for pathing. By the time the enemies are actually destroyed, the job queue is flooded with these pathing requests which the threads continue to process until the queue is empty, thus, causing a performance spike with the game. To address this issue, I implemented a mechanism so that the queue will stop accepting jobs as soon as the restart is called and additionally, it also clears all jobs in the queue as they are no longer valid. While further testing is required, our game runs quite smoothly now.

Multithreading Begins

With the current state of the enemies, there is no possible way to make the game working, let alone “fun.” While A* algorithm is usable in terms of functionality, it does not bode well during runtime when turrets are being placed and the enemies needed to recalculate their paths entirely. However, since I have not been able to work out a suitable solution to the MT-D*-Lite with ACO issue, I have to, at a minimum, get A* enemies to a point of functioning in terms of our game; thus, brings me to the focus of the week, multithreading.

Attempting to incorporate multithreading into our game presents a few challenges. While we had set up a thread pool in the beginning makings of our game engine, it has never actually been used or testing thoroughly for functionality. And as I have found, the threading system we had in place does not function properly. After solving the initial hurdle, I am now able to properly generate jobs and insert to a queue waiting to be executed by available threads. But of course, things never work as smoothly as intended.

The second challenge comes with the fact that while we had the foresight to include a threading system in our engine, we most certainly have not utilized it, and therefore, everything thus far is not thread-safe. And finally, the main challenge, what and where to thread. While I have a pretty good idea of where the performance hold-up is located, we profiled our game to be sure. The results confirmed my suspicion that the main culprit is the A* calculations, additionally, physics system is also taking a considerable amount of time. Upon discovering the results, I was able to the multithread the collision testing on the physics and allowed the A* calculations to happen within threads, which was the main issue that caused the game to hang due to is blocking updates while waiting for the calculations to finish.

Ant Colony Optimization

After some struggle over the weekend, I was finally able to integrate MT-D*-Lite into the game. And while the enemies are able to find their proper paths, due to the nature of algorithms and given the same environment, enemies will always pick the same path. This is expected behavior, but we needed the enemies to at the very least spread out and not line up in single file for easy picking. Thus, we begin additional research on grouping and swarming behaviors. We stumble upon another type of pathfinding method, Ant Colony Optimization, that is beneficial in a hive-like situation where you have multiple agents attempting to find the better path toward a common goal. This sounds perfect for our game, so I decided to implement it.

ACO works by sending its agents out to the environment in a random direction and have them discover and venture around the world until the agent has discover its goal or something beneficial; at which point, the agent will retrace its steps leading to the goal and leave behind a pheromone that attracts other agents to more likely to follow its path. Unfortunately, waiting for an enemy to free roam the world until it finds the goal is not the type of behavior we envisioned for our game. However, not all is lost in this research. The concept of leaving pheromones can be adapted to get the separating behavior that I was looking for. When an enemy travel over a tile, I would increase the weight of the tile to discourage our enemies to traverse to that tile.

Implementing this adoption of ACO was fairly simple. However, the integration with MT-D*-Lite has produced a challenge. Pheromones are left behind and dissipate over time. This results in a constantly changing weights of tiles. By itself, it is perfectly fine, but because MT-D*-Lite reevaluates its path every time it detects a cost change for traversal, this caused a major performance hit on our game. So much so, that I can only have about 5 enemies before the game is unplayable. Obviously, this is not ideal; therefore, I have reverted to using A* for the time being until we can solve this issue.

MT-D*-Lite Integration Issues

This week, the team’s focus was to push for a playable Alpha build. We have most of the milestone features implemented. However, one important feature that I am still working on was the MT-D-* Lite pathfinding system. As mentioned previously, there was an issue with the system where the agent would not be able path find correctly. I have spent countless hours trying to locate the cause of the issue and ultimately decided to recode it with fresh eyes. While most of its functionality and structure remained the same, there was one major adjustment to the system this time around. The system maintains its own set of data representing its perception of the world. Previously, it was set to initialize the data for every tile currently existing in the world, such an approach has the potential to waste memory. Therefore, I have adapted the system to only initialize the data when necessary, such as when the information becomes relative to find the path.

To my surprise, because of the change in structure, it appears to have resolved the prior issues with the system. Under multiple testing, the agent was able to correctly find the path to goal regardless of the test conditions. With the system in place, the next major step is to have an enemy apply the system and utilize it in the game in real-time. Unfortunately, a few problems arise upon integration. First, the enemy would occasionally exit the playable area, thus preventing the game to continue. Second, at times, the enemy would path in a circle, not moving towards its target. Because of these concerns, I was not able to include the system in this recent build. While I am currently working to resolve these bugs, I suspect that the first problem is caused by the fact that the agent moves based on its velocity. When the agent is close to the map boundaries and happens to have a target towards that direction, there is a communication gap in which the velocity did not get updated in time to divert the agent towards a different path. Further investigation is needed to narrow down the cause.

Reinforcement Learning (A2C)

With MT-D*-Lite yet to be fully functional, I have decided to take a pause from the pathing algorithm and focus on helping a teammate with creating a neural network. The intention was to ultimately have the AI decide what action it should perform creating less predictable behavior. In order to have an AI that does such a behavior, it is impossible to program it the traditional way where the AI’s actions are deterministic and therefore predictable. There are other options that would potentially produce the desired result such as fuzzy logic, GOAP, and even genetic algorithm; however, we have decided on taking the challenge to create a neural network that would produce the behavior we imagined.

Neural network and machine learning is a vast subject. There are many different implementations and models that suit different needs. We started by understanding the basics of a neural network; the inputs, the neurons, the activation functions, and the layers. The basic concepts behind the neural network are not too difficult to understand. The struggling part comes when determining what activation function to use and the mathematics that goes behind these formulas. While understanding the basics of a neural network is important, it will not produce the desired outcome that we want. For that, we needed to search deeper into more complex neural network models, thus, stumbling across the actor-critic model.

For an AI to decide its actions, it first needs to be trained. One way to train the AI is through reinforcement learning, of which the actor-critic model falls under. The basic principle of the model is to have a multi-network system that influences one another. The actor-network focuses on maximizing the immediate reward of its actions while the critic-network focuses on the quality of the action in relation to the overall outcome. Both these network work in complement to improve one another to ultimately produce an optimal policy for solving the problem at hand.

Understanding the concept is completely different than understanding the underlying math. We researched the algorithm and implementations of the model in hopes to be able to produce our own implementation, unfortunately, most of our search ends in a Python implementation that streamlines the math and underlying calculations that we seek. We spend most of the week trying to implement the network and programmed as far as we can. The remaining issue is how to perform the necessary calculations that we needed, which we would have to research deeper on.

 

MT-D*-Lite Implementation

Continuing on with last week’s issue, were not able to make any headway on the issue with range detection. We, therefore, decided to search for alternatives. As we continue to explore options on potential pathfinding algorithms, we came across a more dynamic version of the D*-Lite. While D*Lite allows for dynamic changes occurring in the map, MT-D*-Lite offers an additional benefit; it allows targets to also be dynamic, which can be crucial to our game when we allow enemies to target the player.

The underlying concept of MT-D*-Lite, as you may have guessed, is similar to that of D*-Lite. It retains information on the nodes it has visited thus far to avoid recalculation of the node. However, in order to accommodate a dynamic target, MT-D*-Lite also employs concepts from G-FRA*. In full action, MT-D*–Lite maintain a list of visited nodes with their calculations, however, when changes are made to the environment, it recalculates its path and basically erase/delete nodes in the visited list that are no longer useful in searching for the current path.

The basic implementation was quick, as it was very similar to D*-Lite. Unfortunately, we ran into multiple issues. First, we have a bug where somewhere along the calculations, nodes are pointing at each other as parents, causing an infinite loop to occur when determining a path. Second, on occasion, the enemy was ignoring obstacles and walks straight through them. Third, an issue with path calculation when the target suddenly becomes far from its position in the last frame of the update. I was able to locate most of the issues to be caused by the way we are handling the recalibration of nodes when the cost of a node changes. Unfortunately, I have yet to be able to uncover the reason why strange things happen when trying to path to a target that is suddenly far away.

D*-Lite Implementation

This month’s focus will be on enemy AI and pathfinding. With basic A* algorithm implemented for pathfinding, we needed to explore other pathing algorithms that are more optimized than A*. A* gives us an optimized path from point A to point B provided that the environment maintains its properties after the path is calculated. The issue comes when the environment changes where the weight to traverse a section of the path increases or even becomes blocked. In the case of A*, it would basically have to recalculate the path with the new changes accounted for. This is not ideal for our game since we plan on allowing defense towers to be created and destroyed dynamically throughout the game. Each enemy using A* would have to react to the change by recalculating the entire path, which can hinder the smoothness of the gameplay.

As such, we researched other algorithms and came across D*-Lite. D*-Lite is essentially the same as A* except it maintains its search data to allow quicker calculation when environmental properties change. While The underlying concept seems relatively simple, the lack of information and implementation currently available has made the research process a bit difficult. All information on D*-Lite converges back to a singular source and thus caused some delays for us when implementing the algorithm. On the first implementation, we were not optimistic about a successful outcome, however, to our surprise, the algorithm appears to be working fairly well.

We then decided to incorporate range detection to simulate the enemy seeing changes to its surroundings. To do so, we kept track of all changes made in the environment and only act on them we the enemy is within range of the change. Unfortunately, it did not go as smoothly as the first implementation. It seems that regardless of range the enemy only detects its immediate neighboring changes. Increasing its perception range had seemingly no effect on rerouting the enemy’s path. We are currently investigating the issue.

Static Physics Objects

Physics system consists of a few flaws. The biggest on which is how to properly collide with terrain. There are a few issues with the terrain. Our system from the beginning of the week does contain the terrain object, but the spatial partition does not recognize objects that are larger than the partition space and thus the terrain, regardless of size, gets its corners partitioned into the space but the center/insides of the terrain are ignored. This causes objects to not collide with the terrain’s center because the terrain does not exist in those partitioned space and thus collision is not checked.

I begin to implement a way for larger objects to be inputted into the spatial partition. If any dimension of the object is larger than partitioned unit size, it divides the object into sections that are partition sized and puts them into the spatial partition. This raises another issue. When this was implemented and tested, our game performance drops significantly to the point where it is almost non-functional. This problem comes from the way collision is being handled. As it was, the collision check function requests all objects inside each partitioned space. This becomes an issue with extremely large objects such as the terrain. The terrain occupies over a thousand partitioned units and therefore, each frame it iterates these thousand buckets for collision check.

Things like terrain are not moving, there is no reason to test collision between two static objects. To account for this and to fix the performance crash, I separated static and dynamic objects into their own pools. Static objects like terrain are no longer put inside the partition and instead all objects when checking against the static objects for collision. While it is not currently implemented, a further optimization is to own check the dynamic object against the static object if it is within a range.