4. Using AI in Computer Games (Pathfinding Concepts)
NWC603COM – Using AI in Computer Games Rachel Osho ID: 309740
Assignment 1 – Theory One
The concept of path-finding also known as pathing is merely the method of the planning via the use of a computer application in terms of what is the more condensed route between two points. (Wikipedia, n.d) Path-finding is used in gaming so that the players so that motion is allowed, so that the characters are able to move around within a game e.g. a zombie wandering round aimlessly. A* Algorithm and Dijkstra algorithm are both examples path finding algorithms even though there are several.
In comparison to the *A algorithm, the Dijkstra algorithm it is a much more straightforward. The Dijkstra algorithm is more used in strategical decision making as opposed to being used in path-finding. Another comparison that can be made between the two path-finding methods is that A* algorithm aids you to locate the paths to just one location. However this is not the same with Dijkstra algorithm as it is able to find paths to near enough every location. Dijkstra algorithm was designed by Edsger Dijkstra and it was created to establish the shortest routes/path from the initial mark. The problem in regards to the Dijkstra algorithm is that even though it may help you derive at the shortest route, it might not be the best possible route given and is also proven to be wasteful for point to point path-finding. (Millington and Funge, 2016)
This diagram displays all the differents routes using the A* algorithm, Hueristics and the most cost driven route. The A* route tells us to go a certain route as it is the quickest and best way we’re as the hueristics driven path tells you to go the route that has been derived through trail and error, so what they have learnt over time, should you do it several times this is the path your going to take. The heuristics algorithm isn’t always the best route. Lastly we have cost driven which derives at the path that uses the least cost from getting to A to B,. These are all different routes a NPC can take to get from one point to another.
(NEED TO REF)
Path-finding
Path-finding Concepts:
Path-finding Concepts:
The concept of path-finding also known as pathing is merely the method of the planning via the use of a computer application in terms of what is the more condensed route between two points. (Wikipedia, n.d) Path-finding is used in gaming so that the players so that motion is allowed, so that the characters are able to move around within a game e.g. a zombie wandering round aimlessly. A* Algorithm and Dijkstra algorithm are both examples path finding algorithms even though there are several.
A* Algorithm
The A* algorithm is the most common path finding algorithm that is used as it is very useful. A* Algorithm can be applied in order to give you an estimated costs to derive at a goal. A* algorithm was created for point to point path finding, as it locates a path from a given initial node and then to a given goal node. A* algorithm t is supposed to be faster in comparison to Dijkstra even should
The A* algorithm is the most common path finding algorithm that is used as it is very useful. A* Algorithm can be applied in order to give you an estimated costs to derive at a goal. A* algorithm was created for point to point path finding, as it locates a path from a given initial node and then to a given goal node. A* algorithm t is supposed to be faster in comparison to Dijkstra even should
it requires more memory and more operations per node since it discovers a lot less nodes and the gain is good in any case. The algorithms purpose is to help you find the path route with the best cost, by minimising costs (time, energy, distance,fuel etc)
Dijkstra
Algorithm
In comparison to the *A algorithm, the Dijkstra algorithm it is a much more straightforward. The Dijkstra algorithm is more used in strategical decision making as opposed to being used in path-finding. Another comparison that can be made between the two path-finding methods is that A* algorithm aids you to locate the paths to just one location. However this is not the same with Dijkstra algorithm as it is able to find paths to near enough every location. Dijkstra algorithm was designed by Edsger Dijkstra and it was created to establish the shortest routes/path from the initial mark. The problem in regards to the Dijkstra algorithm is that even though it may help you derive at the shortest route, it might not be the best possible route given and is also proven to be wasteful for point to point path-finding. (Millington and Funge, 2016)
Path-finding Example:
-A* and
other methods ( routes cost and paths)
This diagram displays all the differents routes using the A* algorithm, Hueristics and the most cost driven route. The A* route tells us to go a certain route as it is the quickest and best way we’re as the hueristics driven path tells you to go the route that has been derived through trail and error, so what they have learnt over time, should you do it several times this is the path your going to take. The heuristics algorithm isn’t always the best route. Lastly we have cost driven which derives at the path that uses the least cost from getting to A to B,. These are all different routes a NPC can take to get from one point to another.
(NEED TO REF)
Comments
Post a Comment