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.