This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Since the invention of the first programmable digital computer in the nineteen forties computer based artificial intelligence has been on the forefront of development. During this time a great number of advances have been made in creating artificial intelligences that are getting ever closer to replicating human behaviour over a number of settings. In this report a number of different artificial intelligence methods in relation to the movement and states of NPC characters will be examined and implemented in a deliverable which will show the differences between how these methods behave in different states.
Background and Context
Evidence of the existence of artificial intelligence concepts can be found even before the invention of the first digital computer, however the development of modern AI didn't come around until the invention of the programmable digital computer. This computer allowed mathematicians to start thinking seriously about the development of an electronic brain using manipulation of mathematical symbols to create basic reasoning. Development funded began on attempting to create artificial intelligence entities that could serve and complete tasks that would otherwise need to be completed by humans. However the amount of time and money required to get to a stage where the AI could even come close to a human brain was grossly underestimated.
A cycle began over the years from the nineteen fifties until the present day where projects to create such entities would be started and consequently would have their funding withdrawn. During this time the advancement of the field has been massive and many problems that scientists at first thought impossible have been solved with the advancement of both the AI techniques and the technology. To this day however no system or entity has been created with a human level of intelligence, or that can successfully pass the a test developed in the 1950s by Alan Turing, whereby a human participant must not be able to decipher the difference between a two entities, one being human and one being an AI.
In the early nineteen fifties the first instance of the use of artificial intelligence was used in games. A simple checkers and chess program were created on one of the early computers. Eventually the checkers program gained enough skill to take on ameteur players. Ever since this time the standard of AI in games has been used to measure the advancements in AI and the level of skill that AI has in modern games has increased dramatically as hardware has improved.
A Star Algorithm
The A Star algorithm is a widely used in pathfinding where an entity is required to traverse a path between two points. It does this by assigning each tile of the map as a node, it is these nodes that are used to calculate the path. The A Star algorithm has been highlighted for its efficiency and impressive performance and it is because of this that it is used in most modern games.The A Star algorithm is an adaptation of the Edsger Dijkstra algorithm, the main addition to the Dijkstra algorithm is the addition of a heuristic. The heuristic is used to get an estimate of the distance between the two points being traversed.
Although there are a number of heuristics that can be used to get the distance cost for the A Star algorithm there are two that are used in the majority of cases and these will be discussed now. The most commonly used heuristics for games are the Manhattan distance and the Euclidian distance equation. There are some advantages and disadvantages to using each of the differing equations. The main advantage to manhattan distance is that the calculation does not include a square root function but still returns a distance that can be used in the A Star algorithm. The Euclidian distance calculation does include the use of a Square root function to return a usable distance. The Square root function is extremely computationally expensive but gives a result which is more accurate and should produce better results when used in A Star. For this reason Euclidian distance is more accurate however much more computationally expensive whereas Manhattan distance is computationally less expensive however produces less accurate results.
The A Star algorithm uses a best-first search to find the path of the least cost to get from the start node, to the end node. A best-first search searches a graph by exploring the most likely node according to a given rule. As the algorithm moves through the graph it finds the path of lowest known heuristic cost and, it keeps a sorted priority queue of other path segments along the way. The algorithm adds the distance and the cost for each node to determine the order that the search visits the nodes in the tree. The distance to the goal must not be overestimated so a function is used to get the smallest distance between any two nodes.
Finite State Machines
A finite state machine is a method of defining and implementing a finite number of behaviours for a given object, known as states, it also defines the transitions between these states and the actions taken by the entities controlled by it while in a given state. There are two types of state machine that are used commonly, the Mealy state machine and the Moore state machine each of which has its own advantages and disadvantages.
The main difference between the Moore and the Mealy finite state machines is that with the Moore FSM the output only depends on the conditions of the state that the machine is in, additionally the entry conditions of the state are the only input to the state. In contrast the Mealy FSM can have varying outputs dependant on both the entry conditions of the state and some input to the state. The advantages of the Moore FSM is that it is much simpler to develop, the development process is much more straightforward but the main disadvantage is that it is limited by the amount of states that the machine contains. The main advantage of the Mealy machine is that there are generally less states as one state can handle multiple situations, however the disadvantage of the Mealy machine is that the complexity of implementation is much greater.
Finite state machines are used in a wide array of situations with applications both for general software are in the games artificial intelligence fields. FSMâ€™s can be used in any situation where a defined number of behaviours is required, the application for AI allows for an entities behaviour to be defined in each of the states. Some example of states that could be defined for an AI in a game world include; dead, patrol, respawn, attack, defend and so on. In each of these given states the AI will behave differently depending on the inputs it is receiving from the world and the transition requirements and actions will also be defined within the FSM.
Examine the differences between AI movement methods
Examine AI state driven behaviour.
Examine background of AI in games
Objectives and Outcomes
A demonstrable system will be created which will show the implementation of:
NPC movement through various example â€œworldsâ€Â.
Control of NPC behaviour using a finite state machine
Implementation of different AI methods to control movement
The implementation of this program will have a will have a number of player elements, some of which are controlled by the player and some are controlled by the computer using the AI methods discussed later. The player is able to control a sprite which can move freely around the game world both in the vertical, horizontal and diagonal directs while being constrained the game grid. There could be a number of other AI controlled players on the map which can demonstrate different behaviours using different AI methods.
Platform and Operating System
This system will be developed to be compatible with the windows operating system running on Windows XP, Windows Vista or Windows 7 operating systems. The hardware requirements in order to run this software will be minimal as it uses basic textures and graphics.
The deliverable will be developed using the Microsoft XNA Game Studio 4.0 with C# as the base language. XNA game studio sets up the basic systems that allows the game to run and also has built in code which allows for easier creation of the elements which do not relate to the function of the artificial intelligence.
In this deliverable, when the system initial the program class will call the Game1 class. This is the default name for this class This class controls the main loop for the program, which in turn controls the update methods for all other classes in the system. Game1 also contains the managements of the player entities in the system and the drawing of these entities. The final element of the system that Game1 controls is the size and display type of the window in which the system is displayed.
Object Class Diagrams
UML Class Diagram
In this deliverable there are two differing types of artificial intelligence, each using its own AI method to control the movement of the entity through the map. The map will have a number of obstacles through which the AI cannot pass, these AI controlled entities are able to navigate around these obstacles. The first entity uses the A* algorithm to allow for navigation around the map, and the second uses a breadcrumb trail based algorithm to navigate the map.
Finite State Machine
A finite state machine class is used to control the various behaviours of each of the AI classes, the AI entity is passed into the finite state machine and depending on entry conditions, in the case a key press, the behaviour specified is then carried out. In the case of this project the following states are described.
A chase state during which the AI will chase the player around the map.
There is a patrol state where the AI will patrol a set of predefined points around the map.
A dead state where the AI will cease all activity
A respawn state where the AI will return to the spawn point.
There is also an evade state where the AI will attempt to flee from the player
In this deliverable the A Star algorithm was implemented as a solution to the problem of player navigation around a dynamic map, although the deliverable does not allow for the map to be changed during runtime the way in which the A Star algorithm is implemented will allow for the AI to successfully navigate around new obstacles on the map. The A Star class implemented takes in two points into the class , the return function returns a path of walkable tiles to the goal tile on the map. On the map some tiles are not walkable by the AI and such it has to find a path which successfully navigates around these obstacles. As the player and the AI element move around the map their new positions are fed into the algorithm and the path is recalculated ensuring that the shortest distance to the target is always maintained.
Another feature implemented in this deliverable is a basic breadcrumb based AI. As the player moves around the game world a breadcrumb trail is stored of the tiles visited in an array of positions. When the breadcrumb AI is in the chase state in its FSM its behavior is such that it follows the trail left by the player. This type of AI is not able to deal with the addition of new obstacles being added to the map dynamically and as such will stop working.
The system was designed using a fully object orientated approach, this meant that all of the separate components of the system are able to be kept separate. This allowed for a more efficient development process. This has positive implications for any future expansion of the project later, using an object orientated approach means that more entities and features can be added easily to expand the solution.
There are some limitations to the solution produced, the ability for the user to be able to dynamically change the layout of the walkable and non walkable tiles on the world would better show the features of the A Star algorithm compared to a breadcrumb trail. Additionally some further work on the breadcrumb to improve the accuracy of the trail left by the player to exclude situations where to player crosses its own path. This would improve the comparison between the AI methods shown in the deliverable.
Discussion and Conclusions
From the implementation of both A Star Algorithm and the breadcrumb trails it is clear to see that the nature of the paths generated by the A Star algorithm in the majority of conditions are more efficient and get to the target faster than the breadcrumb trails. In any condition where the player moves around a small area repetitively the breadcrumb trail will mimic the actions of the player, meaning that the breadcrumb entity will go around in circles following the player if that is the actions the player has taken. The A Star algorithm has no such issues as the path from the entity to the player is generated each frame meaning the most efficient route based on current conditions is generated rather than a path based on past or old positions. However the downside to this improved accuracy on the part of the A star algorithm is that the computational cost to the system is greatly increased. In comparison to the breadcrumb trail which has relatively low computational costs and very little calculations involved.
If this project were to be expanded or completed again then more time would be spend on the research aspects of the project. Investigation into other movement algorithms and their implementation would be included in the project and implementation to compare their performance and accuracy to the ones already implemented in the current project. Additionally the ability of the user to be able dynamically change the layout of the non-walkable tiles on the map would show the different algorithms ability to react to this type of map and the performance costs associated with these sorts of changes.