Research Assignment: Data Structures and “Space Quest”
“Space Quest” is a game about a lone traveller, flying through the cosmos. The journey is not a quite one, however, as there are alien Bounty Hunters trying to take down the traveller. The player takes the role of the traveller, and their aim is to avoid an AI controlled alien ship, destined to crash into the player. Unfortunately for the player, it isn’t exactly over once the first ship has been outmanoeuvred: there are still other alien spaceships waiting. Luckily for the traveller, the Bounty Hunter’s identity is published throughout the galaxy, so devising a strategy will be easy work. For the implementation of ‘Space Quest’, two ...view middle of the document...
Figure 1: A Visual Representation of a Binary Tree (1998)
For Space Quest, however, the tree will be used for AI, thus, a general binary tree data structure, such as the one illustrated above, cannot be used. The enemy AI needs to make decisions based on where the player is located, and attempt to move towards the player. This can only be accomplished through a series of ‘Yes and No’, or ‘True and False’, trials. The AI will ask questions such as, “Is the player above me? Is the player below me?” and so forth, therefore, the tree will need to generate and decide on finding the best path to take to approach the player. In order to achieve this, a data structure known as a Decision Tree is required.
According to de Ville & Neville (2013), a decision tree can be defined as “a simple, but powerful form of multiple variable analysis.” Decision Trees were first introduced over fifty years ago, and are still being refined today to provide new functionality for dealing with the newer code-development related issues we might encounter (de Ville & Neville, 2013). Since decisions trees are essentially binary trees, they also operate in O(log(n)) time complexities for best and worst case scenarios, and O(n) for space. Decision trees are generated by algorithms which determine possible ways to branch-off data depending on the end result of a set question. From this, the aim of the tree would be to predict the probability of a specific outcome. In terms of Space Quest: where will the player be next, and how can they be reached? For each node in the implementation, the AI will ask itself if the defined condition mentioned earlier yielded either a true or false result, and it will generate either a ‘Yes’ branch, or a ‘No’ branch depending on the result. This is the most effective method due to the fact that, in essence, a logical “map” will be created which will help easily guide the AI controlled alien antagonist towards the player. Its movement instructions will be greatly simplified to just consist of ‘up,’ ‘down,’ ‘left,’ and ‘right’ commands based on four questions it will ask itself. In order to get obtain the required questions, the AI will react based on the player movements.
Figure 2: An Example of a Decision Tree (nd)