Computer Game AI - Revision history

Lena.kamenzin at 11:52, 18 January 2021

2021-01-18T11:52:05Z

← Older revision		Revision as of 13:52, 18 January 2021
Line 1:		Line 1:
	Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" /> The first Computer Game AI ever to beat a human player in a specific game is the chess computer [[~~Deep Blue~~]].		Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" /> The first Computer Game AI ever to beat a human player in a specific game is the chess computer [[deep blue]].

	==Introduction==		==Introduction==

Lena.kamenzin: Added a phrase with link to Deep Blue.

2021-01-18T11:50:47Z

Added a phrase with link to Deep Blue.

← Older revision		Revision as of 13:50, 18 January 2021
Line 1:		Line 1:
	Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" />		Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" /> The first Computer Game AI ever to beat a human player in a specific game is the chess computer [[Deep Blue]].

	==Introduction==		==Introduction==

Jacob.hoeferlin at 08:10, 15 April 2020

2020-04-15T08:10:46Z

← Older revision		Revision as of 10:10, 15 April 2020
Line 10:		Line 10:
	===Algorithms===		===Algorithms===
	The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>		The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>
			[[File:Pathfinding and Steering.png\|thumb]]

	====Pathfinding with A*====		====Pathfinding with A*====
	A* is the most used algorithm to compute a long distance route for NPCs. It requires the definition of waypoints and their connection to a network that spans the entire map to enable the evaluation of a route from A to B. Given a starting point and an end point, the A* algorithm gradually tries to find the shortest route along the waypoints. Step by step the algorithm explores the waypoints in increasing distance to the starting point until the end point is reached. Thereby A* uses an evaluation component which generates an estimate of the distance between a point and the destination to concentrate the spread on the most promising waypoints.<ref name=":2" />		A* is the most used algorithm to compute a long distance route for NPCs. It requires the definition of waypoints and their connection to a network that spans the entire map to enable the evaluation of a route from A to B. Given a starting point and an end point, the A* algorithm gradually tries to find the shortest route along the waypoints. Step by step the algorithm explores the waypoints in increasing distance to the starting point until the end point is reached. Thereby A* uses an evaluation component which generates an estimate of the distance between a point and the destination to concentrate the spread on the most promising waypoints.<ref name=":2" /> (Shown in Fig.1)

	"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />		"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />

Jacob.hoeferlin at 07:18, 15 April 2020

2020-04-15T07:18:20Z

← Older revision		Revision as of 09:18, 15 April 2020
Line 30:		Line 30:
	While the Turing test provides a universally acclaimed method to measure the intelligence of machines, by letting a human interact with a machine. If that human is unable to distinguish the interaction with that with another human the test is passed. This test however proves to be a wrong frame of reference for AI in video games specifically, as the goal of AI in video games is not necessarily to emulate human-like behavior, but to provide the player with a fun gaming experience.<ref name=":0">Dill, Kevin: What Is Game AI?. In: CRC Press (Hrsg.): ''Game AI Pro. Collected Wisdom of Game AI Professionals'', 2014.</ref>		While the Turing test provides a universally acclaimed method to measure the intelligence of machines, by letting a human interact with a machine. If that human is unable to distinguish the interaction with that with another human the test is passed. This test however proves to be a wrong frame of reference for AI in video games specifically, as the goal of AI in video games is not necessarily to emulate human-like behavior, but to provide the player with a fun gaming experience.<ref name=":0">Dill, Kevin: What Is Game AI?. In: CRC Press (Hrsg.): ''Game AI Pro. Collected Wisdom of Game AI Professionals'', 2014.</ref>
	==Conclusion==		==Conclusion==
			The constantly increasing processor power inspires the hope for an increasing performance of AI in general and Game AI in particular. With more available power for calculating AI, there is the possibility for an increased use of Expert Systems in games and therefore new possibilities.

	==Related Links/Research==		==Related Links/Research==

Jacob.hoeferlin at 23:10, 14 April 2020

2020-04-14T23:10:42Z

← Older revision		Revision as of 01:10, 15 April 2020
Line 1:		Line 1:
	~~In progress~~

	Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" />		Computer Game AI is the use of Artificial Intelligence in computer games in a broader sense, that is, "to create a compelling experience for the player."<ref name=":0" />

Line 10:		Line 8:
	===How to be intelligent for the player===		===How to be intelligent for the player===
	Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />		Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />
	~~<br />~~
	===Algorithms===		===Algorithms===
	The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>		The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>

	~~<br />~~

	====Pathfinding with A*====		====Pathfinding with A*====
Line 20:		Line 15:

	"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />		"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />

	~~<br />~~
	====Finite state Machines and Decision Trees====		====Finite state Machines and Decision Trees====
	Both finite state machines (FSM) and decision trees can be realized by using simple if-then statements and are both used to control the behavior of an NPC in specific situation based on environmental events. "FSM describe under which events/conditions a current state is to be replaced by another—for example, switching from an attack mode to an escape mode if the NPC is hit."<ref name=":2" />		Both finite state machines (FSM) and decision trees can be realized by using simple if-then statements and are both used to control the behavior of an NPC in specific situation based on environmental events. "FSM describe under which events/conditions a current state is to be replaced by another—for example, switching from an attack mode to an escape mode if the NPC is hit."<ref name=":2" />

	Decision trees use a branch and leaf structure, which, starting from one point, is always divided into two further branches and thus enables decision making. "This type is often used to make high-level strategic decisions–for example, if a computer guided opponent in a strategy game should prepare an attack or concentrate on resource gathering."<ref name=":2" />		Decision trees use a branch and leaf structure, which, starting from one point, is always divided into two further branches and thus enables decision making. "This type is often used to make high-level strategic decisions–for example, if a computer guided opponent in a strategy game should prepare an attack or concentrate on resource gathering."<ref name=":2" />

	~~<br />~~

	====Expert systems====		====Expert systems====
	One way to create high-level behavior in games, more in the style of academic AI, is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world. This expert system suffers at the beginning from the enormous amount of situations that may occur, which inevitably leads to many of the possibilities being overlooked. This in turn causes the NPC to behave inappropriately if one of the unexpected cases occurs, causing the controlled NPC to behave stupidly. If one of these errors is found before the game is released, it can be easily fixed by adding new information about the unexpected event to the controller. For this reason it is very difficult to establish such an AI system in a complex game world and without much time effort this approach is only possible in "toy problems". One advantage is that AI does not have to be perfect in games. The game can already be launched when the process of adding new knowledge does not result in any significant changes.<ref name=":1" />		One way to create high-level behavior in games, more in the style of academic AI, is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world. This expert system suffers at the beginning from the enormous amount of situations that may occur, which inevitably leads to many of the possibilities being overlooked. This in turn causes the NPC to behave inappropriately if one of the unexpected cases occurs, causing the controlled NPC to behave stupidly. If one of these errors is found before the game is released, it can be easily fixed by adding new information about the unexpected event to the controller. For this reason it is very difficult to establish such an AI system in a complex game world and without much time effort this approach is only possible in "toy problems". One advantage is that AI does not have to be perfect in games. The game can already be launched when the process of adding new knowledge does not result in any significant changes.<ref name=":1" />

	~~<br />~~

	===The problem with the term (artificial) intelligence===		===The problem with the term (artificial) intelligence===

Jacob.hoeferlin: /* Expert systems */

2020-04-14T23:09:50Z

Expert systems

← Older revision		Revision as of 01:09, 15 April 2020
Line 30:		Line 30:

	====Expert systems====		====Expert systems====
	One way to create high-level behavior in games, more in the style of academic AI, is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world. This expert system suffers at the beginning from the enormous amount of situations that may occur, which inevitably leads to many of the possibilities being overlooked. This in turn causes the NPC to behave inappropriately if one of the unexpected cases occurs, causing the controlled NPC to behave stupidly.		One way to create high-level behavior in games, more in the style of academic AI, is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world. This expert system suffers at the beginning from the enormous amount of situations that may occur, which inevitably leads to many of the possibilities being overlooked. This in turn causes the NPC to behave inappropriately if one of the unexpected cases occurs, causing the controlled NPC to behave stupidly. If one of these errors is found before the game is released, it can be easily fixed by adding new information about the unexpected event to the controller. For this reason it is very difficult to establish such an AI system in a complex game world and without much time effort this approach is only possible in "toy problems". One advantage is that AI does not have to be perfect in games. The game can already be launched when the process of adding new knowledge does not result in any significant changes.<ref name=":1" />

	<br />		<br />

Jacob.hoeferlin at 22:55, 14 April 2020

2020-04-14T22:55:14Z

← Older revision		Revision as of 00:55, 15 April 2020
Line 10:		Line 10:
	===How to be intelligent for the player===		===How to be intelligent for the player===
	Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />		Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />
			<br />
	===Algorithms===		===Algorithms===
	The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>		The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>

			<br />

	====Pathfinding with A*====		====Pathfinding with A*====
Line 17:		Line 20:

	"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />		"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />

			<br />
	====Finite state Machines and Decision Trees====		====Finite state Machines and Decision Trees====
	Both finite state machines (FSM) and decision trees can be realized by using simple if-then statements and are both used to control the behavior of an NPC in specific situation based on environmental events. "FSM describe under which events/conditions a current state is to be replaced by another—for example, switching from an attack mode to an escape mode if the NPC is hit."<ref name=":2" />		Both finite state machines (FSM) and decision trees can be realized by using simple if-then statements and are both used to control the behavior of an NPC in specific situation based on environmental events. "FSM describe under which events/conditions a current state is to be replaced by another—for example, switching from an attack mode to an escape mode if the NPC is hit."<ref name=":2" />

	Decision trees use a branch and leaf structure, which, starting from one point, is always divided into two further branches and thus enables decision making. "This type is often used to make high-level strategic decisions–for example, if a computer guided opponent in a strategy game should prepare an attack or concentrate on resource gathering."<ref name=":2" />		Decision trees use a branch and leaf structure, which, starting from one point, is always divided into two further branches and thus enables decision making. "This type is often used to make high-level strategic decisions–for example, if a computer guided opponent in a strategy game should prepare an attack or concentrate on resource gathering."<ref name=":2" />

			<br />

	====Expert systems====		====Expert systems====
	One way to create high-level behavior in games more in the style of academic AI is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world.		One way to create high-level behavior in games, more in the style of academic AI, is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world. This expert system suffers at the beginning from the enormous amount of situations that may occur, which inevitably leads to many of the possibilities being overlooked. This in turn causes the NPC to behave inappropriately if one of the unexpected cases occurs, causing the controlled NPC to behave stupidly.

			<br />

	===The problem with the term (artificial) intelligence===		===The problem with the term (artificial) intelligence===

Jacob.hoeferlin: /* Expert systems */

2020-04-14T22:45:23Z

Expert systems

← Older revision		Revision as of 00:45, 15 April 2020
Line 23:		Line 23:

	====Expert systems====		====Expert systems====
			One way to create high-level behavior in games more in the style of academic AI is to use brute force to create a controller that has a lot of knowledge about behavior in a specific game world.

	===The problem with the term (artificial) intelligence===		===The problem with the term (artificial) intelligence===

Jacob.hoeferlin: /* Finite state Machines and Decision Trees */

2020-04-14T22:36:24Z

Finite state Machines and Decision Trees

← Older revision		Revision as of 00:36, 15 April 2020
Line 18:		Line 18:
	"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />		"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />
	====Finite state Machines and Decision Trees====		====Finite state Machines and Decision Trees====
			Both finite state machines (FSM) and decision trees can be realized by using simple if-then statements and are both used to control the behavior of an NPC in specific situation based on environmental events. "FSM describe under which events/conditions a current state is to be replaced by another—for example, switching from an attack mode to an escape mode if the NPC is hit."<ref name=":2" />

			Decision trees use a branch and leaf structure, which, starting from one point, is always divided into two further branches and thus enables decision making. "This type is often used to make high-level strategic decisions–for example, if a computer guided opponent in a strategy game should prepare an attack or concentrate on resource gathering."<ref name=":2" />

	====Expert systems====		====Expert systems====

Jacob.hoeferlin: Pathfinding with A*

2020-04-14T22:02:12Z

Pathfinding with A*

← Older revision		Revision as of 00:02, 15 April 2020
Line 11:		Line 11:
	Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />		Although AI does not need to be personalized, most referrals to AI in video games are made to computer-controlled NPCs. But how does the player perceive the intelligence of an AI? They consider several aspects like goal-related behavior, physical characteristics, language cues and social skills. "A good looking and sympathetic NPC is likely to be considered more intelligent"<ref name=":2">Nareyek, Alexander: AI in Computer Games. In: ACM (Hrsg.): ACM Queue, Game Development. Vol. 1, No. 10, 02.2004, S.59-65.</ref> John David Funge puts it this way: <blockquote>"In terms of the player's perception of a game's AI, appropriate animations can also make an enonnous difference. For example, consider an NPC who is surrounded by hostile monsters and cannot think of anything intelligent to do. The NPC could simply stand there looking dumb, or the animation system can be triggered to play an animation of the NPC running around screaming. It is surprising how an appropriate animation can make all the difference in the player's perception of the AI."<ref name=":1" /></blockquote>Apart from an appropriate behavior of the NPC in complex situations, the aim of the AI is basically not to be better than the player, but to be as credible and entertaining as possible for them. This goal is mostly implicit. Instead, the NPC follows the lower level task of stopping the player at all costs.<ref name=":2" /> "Measures such as cheating are a lutely acceptable as long as the “suspension of disbelief” is retained."<ref name=":2" />
	===Algorithms===		===Algorithms===
	The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/</ref>		The basics of seemingly intelligent movement for game AI are not getting stuck in anything on their way and taking a possibly short route to the destination. To archive this goal, a couple of tools are available for development. The functionality of some popular pathfinding algorithms, including A*, can be tested on "PathFinding.js"<ref>PathFinding.js: https://qiao.github.io/PathFinding.js/visual/ (last checked on 14.04.2020)</ref>

	====Pathfinding with A*====		====Pathfinding with A*====
	<br />		A* is the most used algorithm to compute a long distance route for NPCs. It requires the definition of waypoints and their connection to a network that spans the entire map to enable the evaluation of a route from A to B. Given a starting point and an end point, the A* algorithm gradually tries to find the shortest route along the waypoints. Step by step the algorithm explores the waypoints in increasing distance to the starting point until the end point is reached. Thereby A* uses an evaluation component which generates an estimate of the distance between a point and the destination to concentrate the spread on the most promising waypoints.<ref name=":2" />

			"In many cases, a game applies pathfinding techniques at multiple granularity levels. For example, for long distances, a path of high granularity is computed first, and then the paths between the selected waypoints are computed with finer granularity."<ref name=":2" />
	====Finite state Machines and Decision Trees====		====Finite state Machines and Decision Trees====