A Comparsion of Pathfinding Algorithms

in this video we'll be exploring pathfinding we'll be dissecting through some classic path finding algorithms before going through simulating them and comparing them in the end an arm a simulation will have the black tells us passages and the White House has passable cells in addition for each maze and we'll have one start out and one end tile and red and green respectively the objective of the maze is to find a path from the red tile to the green tile and for the purpose of this video there will always be a path between the red start and the green finish and importantly why our path finding algorithm is running we'll be highlighting what noted searching expanding and what the path is when it finally does find one briefly speaking the pathfinding algorithms that we'll be examining in this video all fold the same simple structure our first step is to add our initial read cell to the list of cells to be searched we would then pick a cell from the list of cells to be searched and expanded during expansion we would add all the adjacent cells that are actually not walls into our list of search ones the orders that we add them in our top right bottom and left and we will repeat this action until either the expanded cell is the destination or there are no cells left in our search here's an example of an a-star run on a very small maze today we'll be exploring four simple types of path finding algorithms BFS DFS Dijkstra and a start let's start off by exploring the simplest of the four DFS in DFS a roof expansion is to expand a node that was most recently added in particular because we add the nodes from top right down and left in that order we will always be expanding the left most node if possible when no longer Punk when it no longer becomes possible to expand the left node we then go to the bottom note the right note and the top note in that order in fraternity one downside with DFS is that even if the answer is right above it because the prioritizes nodes in a certain order it can tend to take the long route and then miss the short path moving on to our second pathfinding algorithm BFS is very similar to DFS except however instead of expanding our most recently added node we expand our least recently at a node in this example you can see the expansion of BFS as a wide net that covers every single node that is closest in order BFS in conscious DFS will always find an optimal route and is much more suited to finding those that are very close however as you can see for the roots that are medium range it can take a long time because it has to expand every single node nearby moving on to our third path finding algorithm one explored i-strip DFS and BFS tend to be very primitive because the way they choose which cell to expand has no criteria making it very loose and easy to pick a wrong path for Dijkstra we assign each cell that we are brought to search with a value this value will be the distance from their parent to the current cell plus whatever the parent value is and as you might have guessed because we can only move in four directions the value that we always add is one while idea to make a criteria for which cell to expand is great in theory it doesn't work very well as Dijkstra tends to turn out to search very similar to BFS lastly we want to talk about a star a star uses the criteria model from Dijkstra were also implementing its own heuristic value in order to make search more accurate we'll talk more about a star in depth in another video but in the gist of it a star tends to take the parent value plus the Manhattan distance away to the target you think of Manhattan distance as an amount of notes from one node to another assuming that all tiles are walkable so now that we have a brief overview of all the path finding algorithms will be competing in let's simulate them so in the simulation will be petting DFS DFS Dykstra and a star in a head-to-head match so we'll have the same randomly generated maze for each of the four algorithms to run on and we'll be calculating the distance no it's expanded and place that they came so we'll be running the simulation 20 times to see who on average gives the best performance you as we can see from the results and it's clear that DFS as we can see the results it is clear that a star on average is the best algorithm out of these four and in particular it seems that there is very little difference between Dykstra and BFS despite the computational differences with these simulations in mind there are some additional things we want to keep in mind in terms of path finding first if we're looking to simulate how a human or an agent can realistically paths find through something like a maze this certainly isn't a path this is especially true if you were to take into consideration a path finding algorithm such as BFS or a star for a human is simply just isn't realistic to go through each of the added nodes in order combined with the fact that humans can memorise the amount of nose as well we need a different algorithm in order to simulate humans for most problems a star is to prefer path finding algorithm and if at the maze problem our heuristic is the Manhattan distance however depending on the problem a different heuristic is required in order to get the optimal path using the same example below we can show that by using Euclidean distance instead of Manhattan distances heuristic we also get the same path but just in a different manner and in a future video we'll explain the different types of heuristics that come with much more complicated problems lastly with these classical path finding algorithms we find that the performance does not increase or get any better to progressive friends this is particularly a problem in algorithms such as a star or Dijkstra where we have a heuristic or set value that's actually stored and computed thanks for watching you

Channel: John Song

Views: 216,308

Keywords: education, computer science, johnsongnow, programming, computer, john song, pathfinding, BFS, DFS, Dijkstra, A*, A Star, algorithm

Id: GC-nBgi9r0U

Length: 7min 54sec (474 seconds)

Published: Sun Sep 15 2019