-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy patha-pathfinding.html
More file actions
89 lines (80 loc) · 37.5 KB
/
a-pathfinding.html
File metadata and controls
89 lines (80 loc) · 37.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - A* Pathfinding</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Introduction to A*, A* Pathfinding through a maze with no obstacles, Solving 8-puzzle problem using A* algorithm">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - A* Pathfinding">
<meta property="og:description" content="Introduction to A*, A* Pathfinding through a maze with no obstacles, Solving 8-puzzle problem using A* algorithm">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/a-pathfinding.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - A* Pathfinding">
<meta name="twitter:description" content="Introduction to A*, A* Pathfinding through a maze with no obstacles, Solving 8-puzzle problem using A* algorithm">
<meta name="twitter:url" content="/algorithm/a-pathfinding.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/12.5444bb42.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" aria-current="page" class="active sidebar-link">A* Pathfinding</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/a-pathfinding.html#introduction-to-a" class="sidebar-link">Introduction to A*</a></li><li class="sidebar-sub-header"><a href="/algorithm/a-pathfinding.html#a-pathfinding-through-a-maze-with-no-obstacles" class="sidebar-link">A* Pathfinding through a maze with no obstacles</a></li><li class="sidebar-sub-header"><a href="/algorithm/a-pathfinding.html#solving-8-puzzle-problem-using-a-algorithm" class="sidebar-link">Solving 8-puzzle problem using A* algorithm</a></li></ul></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" class="sidebar-link">Bubble Sort</a></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="a-pathfinding"><a href="#a-pathfinding" class="header-anchor">#</a> A* Pathfinding</h1> <h2 id="introduction-to-a"><a href="#introduction-to-a" class="header-anchor">#</a> Introduction to A*</h2> <p>A* (A star) is a search algorithm that is used for finding path from one node to another. So it can be compared with <a href="http://stackoverflow.com/documentation/algorithm/7215/breadth-first-search" target="_blank" rel="noopener noreferrer">Breadth First Search<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>, or <a href="http://stackoverflow.com/documentation/algorithm/7151/dijkstra-s-algorithm" target="_blank" rel="noopener noreferrer">Dijkstra’s algorithm<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>, or <a href="http://stackoverflow.com/documentation/algorithm/7247/depth-first-search" target="_blank" rel="noopener noreferrer">Depth First Search<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>, or Best First Search. A* algorithm is widely used in graph search for being better in efficiency and accuracy, where graph pre-processing is not an option.</p> <p>A* is a an specialization of Best First Search , in which the function of evaluation <strong>f</strong> is define in a particular way.</p> <p><strong>f(n) = g(n) + h(n)</strong> is the minimum cost since the initial node to the objectives conditioned to go thought node <strong>n</strong>.</p> <p><strong>g(n)</strong> is the minimum cost from the initial node to <strong>n</strong>.</p> <p><strong>h(n)</strong> is the minimum cost from <strong>n</strong> to the closest objective to <strong>n</strong></p> <p>A* is an informed search algorithm and it always guarantees to find the smallest path (path with minimum cost) in the least possible time (if uses <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" target="_blank" rel="noopener noreferrer">admissible heuristic<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>). So it is both <strong>complete</strong> and <strong>optimal</strong>. The following animation demonstrates A* search-</p> <p><a href="https://i.stack.imgur.com/TGfc9.gif" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/TGfc9.gif" alt="a* search"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h2 id="a-pathfinding-through-a-maze-with-no-obstacles"><a href="#a-pathfinding-through-a-maze-with-no-obstacles" class="header-anchor">#</a> A* Pathfinding through a maze with no obstacles</h2> <p>Let's say we have the following 4 by 4 grid:</p> <p><a href="https://i.stack.imgur.com/9pe82.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/9pe82.png" alt="Beginning 4x4 grid"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Let's assume that this is a <strong>maze</strong>. There are no walls/obstacles, though. We only have a starting point (the green square), and an ending point (the red square).
Let's also assume that in order to get from green to red, we cannot move diagonally.
So, starting from the green square, let's see which squares we can move to, and highlight them in blue:</p> <p><a href="https://i.stack.imgur.com/vDqkY.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/vDqkY.png" alt="Grid #2"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>In order to choose which square to move to next, we need to take into account 2 heuristics:</p> <ol><li>The "g" value - This is how far away this node is from the green square.</li> <li>The "h" value - This is how far away this node is from the red square.</li> <li>The "f" value - This is the sum of the "g" value and the "h" value. This is the final number which tells us which node to move to.</li></ol> <p>In order to calculate these heuristics, this is the formula we will use: <code>distance = abs(from.x - to.x) + abs(from.y - to.y)</code></p> <p>This is known as the <a href="https://xlinux.nist.gov/dads/HTML/manhattanDistance.html" target="_blank" rel="noopener noreferrer">"Manhattan Distance"<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a> formula.</p> <p>Let's calculate the "g" value for the blue square immediately to the left of the green square:
<code>abs(3 - 2) + abs(2 - 2) = 1</code></p> <p>Great! We've got the value: 1.
Now, let's try calculating the "h" value:
<code>abs(2 - 0) + abs(2 - 0) = 4</code></p> <p>Perfect. Now, let's get the "f" value:
<code>1 + 4 = 5</code></p> <p>So, the final value for this node is "5".</p> <p>Let's do the same for all the other blue squares. The big number in the center of each square is the "f" value, while the number on the top left is the "g" value, and the number on the top right is the "h" value:</p> <p><a href="https://i.stack.imgur.com/RoGbr.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/RoGbr.png" alt="Grid #3"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>We've calculated the g, h, and f values for all of the blue nodes. Now, which do we pick?</p> <p>Whichever one has the lowest f value.</p> <p>However, in this case, we have 2 nodes with the same f value, 5. How do we pick between them?</p> <p>Simply, either choose one at random, or have a priority set. I usually prefer to have a priority like so:
"Right > Up > Down > Left"</p> <p>One of the nodes with the f value of 5 takes us in the "Down" direction, and the other takes us "Left". Since Down is at a higher priority than Left, we choose the square which takes us "Down".</p> <p>I now mark the nodes which we calculated the heuristics for, but did not move to, as orange, and the node which we chose as cyan:</p> <p><a href="https://i.stack.imgur.com/Dunrn.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/Dunrn.png" alt="Grid #4"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Alright, now let's calculate the same heuristics for the nodes around the cyan node:</p> <p><a href="https://i.stack.imgur.com/WuCwv.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/WuCwv.png" alt="Grid #5"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Again, we choose the node going down from the cyan node, as all the options have the same f value:</p> <p><a href="https://i.stack.imgur.com/nlywy.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/nlywy.png" alt="Grid #6"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Let's calculate the heuristics for the only neighbour that the cyan node has:</p> <p><a href="https://i.stack.imgur.com/2rf8P.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/2rf8P.png" alt="Grid #7"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Alright, since we will follow the same pattern we have been following:</p> <p><a href="https://i.stack.imgur.com/8UBoB.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/8UBoB.png" alt="Grid #8"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Once more, let's calculate the heuristics for the node's neighbour:</p> <p><a href="https://i.stack.imgur.com/TuXrO.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/TuXrO.png" alt="Grid #9"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Let's move there:</p> <p><a href="https://i.stack.imgur.com/r8MJd.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/r8MJd.png" alt="Grid #10"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Finally, we can see that we have a <strong>winning square</strong> beside us, so we move there, and we are done.</p> <h2 id="solving-8-puzzle-problem-using-a-algorithm"><a href="#solving-8-puzzle-problem-using-a-algorithm" class="header-anchor">#</a> Solving 8-puzzle problem using A* algorithm</h2> <blockquote></blockquote> <p><strong>Problem definition</strong>:</p> <p>An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The object is to move to squares around into different positions and having the numbers displayed in the "goal state".</p> <p><a href="https://i.stack.imgur.com/M2n1h.png" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/M2n1h.png" alt="8-puzzle"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p>Given an initial state of 8-puzzle game and a final state of to be reached, find the most cost-effective path to reach the final state from initial state.</p> <blockquote></blockquote> <p><strong>Initial state</strong>:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code>_ <span class="token number">1</span> <span class="token number">3</span>
<span class="token number">4</span> <span class="token number">2</span> <span class="token number">5</span>
<span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span>
</code></pre></div><blockquote></blockquote> <p><strong>Final state</strong>:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span>
<span class="token number">4</span> <span class="token number">5</span> <span class="token number">6</span>
<span class="token number">7</span> <span class="token number">8</span> _
</code></pre></div><blockquote></blockquote> <p><strong>Heuristic to be assumed</strong>:</p> <p>Let us consider the Manhattan distance between the current and final state as the heuristic for this problem statement.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">h</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token operator">|</span> x <span class="token operator">-</span> p <span class="token operator">|</span> <span class="token operator">+</span> <span class="token operator">|</span> y <span class="token operator">-</span> q <span class="token operator">|</span>
where x <span class="token operator">and</span> y are cell co<span class="token operator">-</span>ordinates in the current state
p <span class="token operator">and</span> q are cell co<span class="token operator">-</span>ordinates in the <span class="token keyword">final</span> state
</code></pre></div><blockquote></blockquote> <p><strong>Total cost function</strong>:</p> <p>So the total cost function <code>f(n)</code> is given by,</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">f</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token function">g</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">+</span> <span class="token function">h</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span><span class="token punctuation">,</span> where <span class="token function">g</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> is the cost required to reach the current state from given initial state
</code></pre></div><blockquote></blockquote> <p><strong>Solution to example problem</strong>:</p> <p>First we find the heuristic value required to reach the final state from initial state. The cost function, g(n) = 0, as we are in the initial state</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">h</span><span class="token punctuation">(</span>n<span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token number">8</span>
</code></pre></div><p>The above value is obtained, as <code>1</code> in the current state is 1 horizontal distance away than the <code>1</code> in final state. Same goes for <code>2</code>, <code>5</code>, <code>6</code>. <code>_</code> is 2 horizontal distance away and 2 vertical distance away. So total value for <code>h(n)</code> is 1 + 1 + 1 + 1 + 2 + 2 = 8. Total cost function <code>f(n)</code> is equal to 8 + 0 = 8.</p> <p>Now, the possible states that can be reached from initial state are found and it happens that we can either move <code>_</code> to right or downwards.</p> <p>So states obtained after moving those moves are:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token number">1</span> _ <span class="token number">3</span> <span class="token number">4</span> <span class="token number">1</span> <span class="token number">3</span>
<span class="token number">4</span> <span class="token number">2</span> <span class="token number">5</span> _ <span class="token number">2</span> <span class="token number">5</span>
<span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span> <span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span>
<span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">)</span>
</code></pre></div><p>Again the total cost function is computed for these states using the method described above and it turns out to be 6 and 7 respectively. We chose the state with minimum cost which is state (1). The next possible moves can be Left, Right or Down. We won't move Left as we were previously in that state. So, we can move Right or Down.</p> <p>Again we find the states obtained from (1).</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token number">1</span> <span class="token number">3</span> _ <span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span>
<span class="token number">4</span> <span class="token number">2</span> <span class="token number">5</span> <span class="token number">4</span> _ <span class="token number">5</span>
<span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span> <span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span>
<span class="token punctuation">(</span><span class="token number">3</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">)</span>
</code></pre></div><p>(3) leads to cost function equal to 6 and (4) leads to 4. Also, we will consider (2) obtained before which has cost function equal to 7. Choosing minimum from them leads to (4). Next possible moves can be Left or Right or Down. We get states:</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span> <span class="token number">1</span> <span class="token number">2</span> <span class="token number">3</span>
_ <span class="token number">4</span> <span class="token number">5</span> <span class="token number">4</span> <span class="token number">5</span> _ <span class="token number">4</span> <span class="token number">8</span> <span class="token number">5</span>
<span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span> <span class="token number">7</span> <span class="token number">8</span> <span class="token number">6</span> <span class="token number">7</span> _ <span class="token number">6</span>
<span class="token punctuation">(</span><span class="token number">5</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span> <span class="token punctuation">(</span><span class="token number">7</span><span class="token punctuation">)</span>
</code></pre></div><p>We get costs equal to 5, 2 and 4 for (5), (6) and (7) respectively. Also, we have previous states (3) and (2) with 6 and 7 respectively. We chose minimum cost state which is (6). Next possible moves are Up, and Down and clearly Down will lead us to final state leading to heuristic function value equal to 0.</p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/a-pathfinding.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/dijkstras-algorithm.html" class="prev">
Dijkstra’s Algorithm
</a></span> <span class="next"><a href="/algorithm/a-pathfinding-algorithm.html">
A* Pathfinding Algorithm
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/12.5444bb42.js" defer></script>
</body>
</html>