Development

Using the previous bot from the first assessment as base, I began to expand on it by developing a separate navigation class that handled the path-finding. The bot provides a start and end position consisting of the bot position as well as the bot found via the sensor data and the navigation class calculates this class, providing an array of nodes to travel to which form the final path that the bot takes. The navigation system performs three steps to initialise the node network.

The Path-Finding

Upon initialisation, the first step to creating the path is performed by the navigation component creates a network of nodes at every edge of all walls provided by the bot’s init data, and adds a 32-pixel offset to allow the bot to have sufficient room to navigate. Before the node is added to the final list of nodes, it is checked if it is outside the level as well as within a 32-pixel vicinity of any other walls. I chose to produce nodes via this method as it is more efficient than simply creating in every open location. Only a minimal amount of nodes is required as the nodes are not used when an enemy bot is in plain sight of the player’s bot.

The second step in creating the path system is performed by a series of ray-traces that check every node against other nodes, and checks whether or not there are walls between nodes, once more with a 32-pixel offset. Upon initial testing, lines were drawn to the point that a ray-trace failed. This resulted in a very interesting visual representation that, in a level with a lot of nodes created what appears similar to a navigation mesh. This gave a basic idea of where the bot is able to navigate, but it was not used as actual data within the path-finding system.

 

Figure 1 – Nodes connect to each other in various ways over open areas.

Once the nodes are connected they are stored within the navigation class. The bot itself only receives a list of the node positions themselves while the navigation system calculates the actual path that connects these nodes. The third step involves the actual path finding, where the path is found by filling node information and then determining the shortest path. Path-finding is not performed if there is less than one node between the start and end node which indicates that the target is in plain sight of the player’s bot where movement style switches to twitch-techniques.

For performance purposes the calculated path is determined by finding the nearest available node around both the player bot and the target bot. This is found by a narrow-first search where a small radius around both bots determines if there are nodes, and ray-traces towards them to determine if there are any walls. This process continues by widening the radius in each update until a valid combination of start and end nodes are found that the both can travel to in a straight line. This allows me to use a minimal number of nodes while keeping performance up by only doing path calculations when the nearest node for either bot has changed, rather than recalculating the path each update.

As the player bot traverses the calculated path, a ray trace is performed from the next target node to the current nearest node. If the player intersects the trace line, the node has been reached and the player travels to the next one. If not, nothing is changed and we can determine the bot has not yet reached its destination. This is more reliable than distance checking the next target node as it prevents issues such as walls or other obstacles that may incorrectly trigger around corners causing the path finding to ultimately fail.

Debugging

During initial development the first debugging information used was the node positions, represented using the provided ‘line drawing’ class. Nodes were represented as yellow boxes and gave me an understanding of the first task of the navigation system – the ability to place the nodes, which resulted in fixing small issues resulting from ray-tracing wall offsets and such.

The most interesting debugging information was not actually the calculated paths themselves, but the traces between nodes which formed complex networks if I chose to display failed paths as well as the succeeded paths to other nodes.

 

Figure 2 – Failed paths being rendered resemble the possible areas the bot can travel to.

The final visual debug information that was provided was the paths themselves, which are updated when the nearest target or start node has changed.

Combat

Combat is handled almost identically to that of the original bot design. A ray trace is performed between both bots to determine if the bot is in clear sight with no walls obstructing the view and the movement style is changed to a twitch style until this clear line of sight is broken. The bot fires in a 3-round burst and changes direction if hit, assuming it has not changed direction very recently to prevent stuck positions. The combat and path-finding techniques are switched between flawlessly.

Alternative Algorithm

I also looked into some alternative path-finding algorithms to use for this scenario. The most likely alternative path-finding algorithm that could be used in place of A* is Dijkstra, which A* is based upon, requiring very little modification to reach a functional state.

Personally I found that the most interesting alternative to A* path-finding are navigational meshes. Rather than paths being determined by individual nodes and connecting by what are essentially thin lines, navigation meshes differ as they represent volumes of reachable areas rather than specific points.

Navigation meshes provide various advantages over traditional node-based systems and is able to perform the same operations as a node system. Navigational meshes are now beginning to become more common in games such as the Unreal Engine 3 as well as updates to the Source engine in 2011.

Some of the advantages to a navigational mesh include the ability to predict faster paths, ensuring entity accessibility to an area as well as various surfaces such as the instruction to jump, climb or crouch in a particular nav-mesh.