Assignment 1 Pathfinding concepts and Algorithms


Path-finding concepts

The first thing I will be talking about in this section of the assignment, under the topic of AI in games, is the concepts of path-finding. This aspect is all to do with AI which in very simple terms is the route that the AI takes to get from point A to B. It will consider all of the options that are at hand. Also it considers things such as time, cost and effectiveness to find the best path. The classic example of path-finding is sat nav as it finds the best route for you to get to your destinations. The points are called nodes and there are many different types of path-finding algorithms such as A*, Dijkstra Algorithm and Cost Driven.          




A* Algorithm 

The second thing I will be talking about in this section of the assignment under the topic of AI in games is A*, which is a path finding algorithm. It is one of the most popular and widely used path-finding algorithms as it is considered simpler to use than some of the other algorithms. So it is mainly used by people who use it because they are more comfortable with it but this doesn't mean it is the best, it's just the easiest to use. Also it can be found in the basic game engine game maker and is the considered the simplest which is an advantage for beginners to make a game. It uses a heuristic function to find the best possible path, which is an advantage for players travelling down a path so they can keep away from any dangerous obstacles in a game. That's the best path solution for A* Algorithm, but if you wanted the quickest path or the most cost effective path A* isn't the best algorithm for this (Rooij, 2017).


(California Institute of Technology, 2011)


Dijkstra Algorithm and Cost Driven

The second algorithm I will be talking about in this section of the assignment under the topic of AI in games is the Dijkstra algorithm. Then I will be talking about another algorithm called Cost Driven. Dijkstra is a path-finding algorithm that is considered the shortest path-finding concept. This means it tries the shortest path out of all of the options, although this doesn't means it is the quickest path-finding algorithm. Then there is the Cost Driven path-finding algorithm that, instead of just finding the shortest route, goes for the route that costs the least,  even if that turns out to be the longest and slowest route. So first thing to talk about is the Dijkstra Algorithms advantage which is that by looking for the shortest routes it is good for a timed game but bad if you are trying to find the best path. With the Cost Driven Algorithm the advantage is that it finds the cheapest path and is therefore the most cost effective, however one disadvantage is that the most cost effective path is not always the best path (Rooij, 2017).


(Computer Science Dept. University of Mayland, 2017)
   

Comments

Post a Comment

Popular posts from this blog

Assignment 1 Hardware constraints AI Engines and Boids flocking

Image
    Hardware Constraints AI Engines  The first point on this second section of this assignment that I will talk about is hardware constraints about the developers and what they have to think about, such as the time it will take to create the game and player experience.  I will also be talking about the player and looking at this from a developer’s point of view. They keep in mind the player experience and try to push this to the limits to make the game as much fun as possible, but they also have to keep in mind the time aspect. They can delay the release of a games if they think it is necessary to get the best level of player experience. An example of pushing player experience to the limit is AC Black Flag when developers tried to get the best player experience on PS3, but certain things didn't work out as it had limitations. They, therefore, decided to make a version of it on the new console the PS4, as it could cope much better with the lighting, realistic shadows and reali
Read more

Assignment 1 Decision making concepts,State machines and Fuzzy logic

Image
          Decision making concepts The first thing that I will talk about in this section of the assignment, under the topic of AI in games, is decision making concepts i.e. the decision tree or the classification tree.  Every AI character makes a decision to do something such as the decision to attack the player character if they are seen (Artificial Intelligence, 2010) . Each decision is put in to a tree like graph which is called the decision tree and the decision itself is made up of child and parent nodes. To make sure that the tree works properly the child nodes are under the parent nodes and have to represent all the possible decisions that are in play. These may be yes, no, maybe or an action like pick up, store or drop (Gallear, 2017) . So with a decision tree it starts off at the root where the decision is made such as yes to take cover, then another decision is made and another until it get to the leaf which is the end node for that section of decisions  ( Artificial I
Read more

Reference Page

Website/ PowerPoint: References: Birch, C., 2010. Understanding Pac-Man Ghost Behavior. [Online] Available at: http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior [Accessed 2 October 2017]. Sikder, F., 2010. Difference Between Algorithm and Heuristic. [Online] Available at: https://faisalsikder.wordpress.com/2010/02/15/difference-between-algorithm-and-heuristic/ [Accessed 2 October 2017]. Wikipedia, 2016. Boids Flocking. [Online] Available at: https://en.wikipedia.org/wiki/Boids [Accessed 2 October 2017]. Artificial Intelligence, 2010. Learning Decision Trees. [Online] Available at: http://artint.info/html/ArtInt_177.html [Accessed 9 October 2017]. Gallear, W., 2017. Bsc Creative Computing. [Online] Available at: https://prezi.com/view/GsEiZBJDMchJZzfCNaHx/ [Accessed 9 October 2017]. tutorialspoint.com, 2017. Artificial Intelligence - Neural Networks. [Online] Available at: https://www.tutorialspoint.
Read more