编程知识 cdmana.com

Using JavaScript to realize path finding algorithm -- Programming Training

{"type":"doc","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Hello, students , I'm from 《","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Technology Galaxy ","attrs":{}},{"type":"text","text":"》 Of ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Three drills ","attrs":{}},{"type":"text","text":" .","attrs":{}}]},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Pathfinding algorithm practice ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" What are the benefits of learning pathfinding algorithms ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Pathfinding is a breadth first search algorithm ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" All of the search algorithms are very similar ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So in the process of speaking breadth first algorithm, we can also tell the depth first search class again ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Search is very important in algorithms , The general algorithm is also a very good one ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Here can help you to improve the algorithm ","attrs":{}}]}],"attrs":{}}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Understanding algorithms through visualization ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The algorithm also has UI The relevant part of ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" And there are some JavaScript The unique part ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Learning this part can help you understand JavaScript Get familiar with the language ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" It's a way to get a deeper understanding of the language ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" And most importantly, through the features of asynchronous programming , Let's talk about visualization ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" By visualizing the steps of the algorithm , We can see the operation of the algorithm very intuitively ","attrs":{}}]}],"attrs":{}}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" The definition of pathfinding problem ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" The problem of finding a way ","attrs":{}},{"type":"text","text":" —— It is to specify a starting point and an end point on a map , From the starting point, find a path to the end through all directions .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In our exercise, we will make a 100 x 100 A grid map , And draw our path from the beginning to the end on it .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" At the beginning, we will use simple vertical and horizontal directions to find our destination , Because there will be some differences in the oblique path , Especially when the map is empty . Later, we will gradually add various functions , Until we've solved all the problems .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Map editor ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In such a large-scale routing problem , We need to make a map editor first . Its functions are as follows :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" You can click with the left mouse button , Or click and drag to draw a map ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" You can right-click , Or click and drag to clear the map ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" You can save map data , After refreshing the map , It can also be redrawn ","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" First we need to map the chassis of our map , Before drawing, we need to give us HTML Join in CSS.","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Our chassis is a 100 x 100 Lattice , So we need to give each grid a pattern . We just need to use ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"flex","attrs":{}}],"attrs":{}},{"type":"text","text":" To lay out . Let's assume that every grid ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"6px","attrs":{}}],"attrs":{}},{"type":"text","text":" Wide and high , And then arrange each row in turn 100 individual . So our HTML The layout code is as follows :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"
\n
\n
\n
\n
\n ...\n
","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"container","attrs":{}}],"attrs":{}},{"type":"text","text":" It's the outsourcing box ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"cell","attrs":{}}],"attrs":{}},{"type":"text","text":" It's the grid inside ","attrs":{}}]}],"attrs":{}}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Layout CSS It's like this :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" That's the layout CSS, But the whole chassis needs to be built with data , So that we can use it later to do our pathfinding . So we need to join here JavaScript To do the whole rendering process .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"HTML We just need to add one part of ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"div","attrs":{}}],"attrs":{}},{"type":"text","text":", And have a ID by ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"container","attrs":{}}],"attrs":{}},{"type":"text","text":" that will do :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"
","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","marks":[{"type":"italic","attrs":{}}],"text":" Realize the idea ","attrs":{}},{"type":"text","text":":","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" Create a 10000 An array of data , And put it all in ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"0","attrs":{}}],"attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" From left to right , From top to bottom , Loop through all the chassis grids ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" Create... While traversing ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"div","attrs":{}}],"attrs":{}},{"type":"text","text":" Elements ,","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"class","attrs":{}}],"attrs":{}},{"type":"text","text":" by ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"cell","attrs":{}}],"attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" In the process of traversal, we encountered the value of ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":" I'll give you the background color ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"#7ceefc","attrs":{}}],"attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":5,"align":null,"origin":null},"content":[{"type":"text","text":" add to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"mousemove","attrs":{}}],"attrs":{}},{"type":"text","text":" ( Mouse movement ) monitor ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":6,"align":null,"origin":null},"content":[{"type":"text","text":" There are two situations in mouse movement monitoring , If it is the left mouse button click state to add the background color , If it is right-click, it is clear that the current background color ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":7,"align":null,"origin":null},"content":[{"type":"text","text":" Finally, use ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"appendChild","attrs":{}}],"attrs":{}},{"type":"text","text":" hold ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"cell","attrs":{}}],"attrs":{}},{"type":"text","text":" Add to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"container","attrs":{}}],"attrs":{}},{"type":"text","text":" In ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":8,"align":null,"origin":null},"content":[{"type":"text","text":" Use localStorage Record our chassis data ","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","marks":[{"type":"italic","attrs":{}}],"text":" Code implementation ","attrs":{}},{"type":"text","text":":","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"// Definition 100 x 100 The chassis data of \n// Use localStorage obtain , If not, create a new one \nlet map = localStorage['map'] ? JSON.parse(localStorage['map']) : Array(10000).fill(0);\n\n// obtain container Element object \nlet container = document.getElementById('container');\n\n// Traversing all the lattices \nfor (let y = 0; y < 100; y++) {\n for (let x = 0; x < 100; x++) {\n // Create a map grid \n let cell = document.createElement('div');\n cell.classList.add('cell');\n // The state of the grid is 1 Of , Just give the background color \n if (map[100 * y + x] == 1) cell.style.backgroundColor = 'aqua';\n // Listen for mouse movement events \n cell.addEventListener('mousemove', () => {\n // Only in the mouse click state \n if (mousedown) {\n if (clear) {\n // 1. When you right-click , It's about knowing the state of the grid \n cell.style.backgroundColor = '';\n map[100 * y + x] = 0;\n } else {\n // 2. Left click , It's the state of drawing into the grid \n cell.style.backgroundColor = 'aqua';\n map[100 * y + x] = 1;\n }\n }\n });\n\t// Add to container In \n container.appendChild(cell);\n }\n}\n\nlet mousedown = false;\nlet clear = false;\n\n// When you click the mouse button , Change the mouse click status to true\ndocument.addEventListener('mousedown', e => {\n mousedown = true;\n clear = e.which === 3;\n});\n// Leave after clicking the mouse button , Make it more like false\ndocument.addEventListener('mouseup', () => (mousedown = false));\n// Because we need to right-click , So you should disable the right-click open menu by default \ndocument.addEventListener('contextmenu', e => e.preventDefault());","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Finally, we add a save button here , When we refresh the page, we will also save the map we edited :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"
\n\n ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" This is the end result :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/87/8757228fcd808efcf5d60de3b97d4b19.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"http://tridiamond.tech/frontend-tutorials/exercises/path-finder/1-map-editor.html","title":""},"content":[{"type":"text","text":" See the effect ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"link","attrs":{"href":"https://github.com/TriDiamond/frontend-tutorials/blob/master/exercises/path-finder/1-map-editor.html","title":""},"content":[{"type":"text","text":" Look at the code ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Favorite students star Thank you !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Achieve breadth first search ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Now let's go deep into the problem of road finding , We have defined the pathfinding problem above , Namely “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Find a start and end , And then we need to find a path , You can go from the beginning to the end , And can't cross our borders and walls ","attrs":{}}],"attrs":{}},{"type":"text","text":"”.","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's take a look at this 100 x 100 The grid of , I really feel that this problem is not particularly easy to solve . In the process of calculating this path , There's a lot of data in the middle that we need to calculate . But we can make it a little simpler .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" We'll get to the starting point , From the starting point to carry out our thinking . Let's ask ourselves a question :” Where can we go from here ?“","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The problem is not simple , There are so many places to go . Because there may be no obstacles at the starting point , It's no longer on any edge . That is to say, you can go anywhere ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/11/1193bc583f261339d6205170541d3c11.gif","alt":null,"title":"","style":[{"key":"width","value":"25%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" ok , So let's narrow down the scope of the problem a little bit ,“ Let's start from the beginning ,","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" First step ","attrs":{}}],"attrs":{}},{"type":"text","text":" Where can we go ?”. Well, the key to this problem is ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" First step ","attrs":{}}],"attrs":{}},{"type":"text","text":".","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Suppose we ignore the oblique walk ( We'll consider this later , The end point here is to simplify the problem ), We can walk to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" On ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Next ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Left ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Right ","attrs":{}}],"attrs":{}},{"type":"text","text":" 4 Lattice . If we mark these positions anticlockwise, we will get a path mark .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/3c/3c146da50d8937ed5732d6ca3d18a764.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" this is it , We have completed the first step of finding the way . Now let's see where we can go next . If it's marked ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"3","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"4","attrs":{}}],"attrs":{}},{"type":"text","text":" It's all walkable , According to what we just thought , Let's look at ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":" Where can I go ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/bd/bd3cb170561b2bb956cc4639cbc98c94.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" No mistake. , In a counter clockwise fashion , The grids we can walk are ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"5","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"6","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"7","attrs":{}}],"attrs":{}},{"type":"text","text":" Three squares . So we can go this way , hold ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"3","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"4","attrs":{}}],"attrs":{}},{"type":"text","text":" All over again . Finally, we will find the following path :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/a3/a3dadfa9cff63dc8c7f8d996cb7ba5db.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Finally, let's take a look at the animation below , Look at the whole process .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/02/0215f598bfeac2c41a59df21f7f952a3.gif","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So that's how we are , Keep looking out for the grid we can go to , Until we find our destination . This will help us find the route from the beginning to the end . Of course, when searching, if we encounter a boundary or obstacle, we will skip , Because these are things that can't go through .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The question of this idea , It's easy to think of recursion , But this method is not suitable for recursive expression . If we use recursive expression , We must have found ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":" After this grid , Will start looking for ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":" All around the grid . that 5,6,7 Will be in 2,3,4 It was executed before ( Because it's recursion , We're going to do it layer by layer ).","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So , If we default to recursion , This way of finding the way will become “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Depth-first search ","attrs":{}}],"attrs":{}},{"type":"text","text":"”, But depth first search is not good for pathfinding ,“","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Breadth first search ","attrs":{}}],"attrs":{}},{"type":"text","text":"” That's what's good .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","marks":[{"type":"italic","attrs":{}}],"text":" Why is breadth first search better than depth first search ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's give you an example , It's better to understand !","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/a9/a919a6f8f37b0acd29894aa82f2f13b8.gif","alt":null,"title":"","style":[{"key":"width","value":"25%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Suppose we are now in a maze , There are thousands of forks ahead , At this time, we have two ways to search for a way out ","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Scheme 1 ","attrs":{}},{"type":"text","text":":","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" be on one's own , Choose left or right and go straight to each branch over there , And walk all the way to the end , Then go back to the other branch . Just keep going, keep switching branches , Until we find the branch of the exit . With luck , Soon we found the exit , Bad luck , All branches have to walk around to find the exit .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Option two ","attrs":{}},{"type":"text","text":":","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" We are alone , But we have “ Separation ”, When we encounter a fork, we can try every fork . such as A,B,C Three forks , We can A One step along the way , then B The route also goes one step , Last C The route also goes one step , Here we are in step , It's a bit like the dynamic diagram above , Go all the way out to all the forks to find the route . So that we can N One fork, one step at a time , Until we find the exit . This is the same way that we are looking for each fork in turn , This kind of search is obviously better than the first one .(","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" I don't know about you , But with the skill of separation, I feel that I have won in the problem of finding the way !","attrs":{}},{"type":"text","text":")","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/db/dbc5f72ec5ef682ce8c4fc7e823faddf.gif","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Back to the algorithm ,","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Scheme 1 ","attrs":{}},{"type":"text","text":" In fact, that is “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Depth-first search ","attrs":{}}],"attrs":{}},{"type":"text","text":"”, and ** Option two ** Namely \"","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Breadth first search ","attrs":{}}],"attrs":{}},{"type":"text","text":"\"! Obviously in pathfinding, the problem is that breadth first search is more efficient !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":2},"content":[{"type":"text","text":" Implement breadth first search code ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Students who have played maze will surely think of , In the maze , We all mark the path we have taken , So we know where we've been , Finally, we can find the path to the destination through these records . Our problem of finding our way is no exception , According to our analysis above , We start from the starting point and expand to find the grid that we can walk , Whenever we find a walkable grid , We all need to record it .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In the algorithm, we all add data to a “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" aggregate ","attrs":{}}],"attrs":{}},{"type":"text","text":"” Inside , And this set is all the search algorithms “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" soul ","attrs":{}}],"attrs":{}},{"type":"text","text":"”. The difference between all search algorithms , It's all about this “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" aggregate (queue)","attrs":{}}],"attrs":{}},{"type":"text","text":"” Inside .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":" It's a data structure , We also call it “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" queue ","attrs":{}}],"attrs":{}},{"type":"text","text":"”, Its characteristic is ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" fifo ","attrs":{}}],"attrs":{}},{"type":"text","text":" ,","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" One way in and the other way out ","attrs":{}}],"attrs":{}},{"type":"text","text":". The actual effect is similar to the figure below :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/84/843eb20499f13be573965d347d8ff062.gif","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" that JavaScript Is there such a data structure as queue in the database ? Yes !","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"JavaScript An array in is a natural queue (Queue)","attrs":{}}],"attrs":{}},{"type":"text","text":", meanwhile ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"JavaScript Arrays in are also natural stacks (Stack)","attrs":{}}],"attrs":{}},{"type":"text","text":".","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/11/1193bc583f261339d6205170541d3c11.gif","alt":null,"title":"","style":[{"key":"width","value":"25%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"JavaScript The array of is 2 Group common processing methods ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"shif","attrs":{}}],"attrs":{}},{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"unshift","attrs":{}}],"attrs":{}},{"type":"text","text":", as well as ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"push","attrs":{}}],"attrs":{}},{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"pop","attrs":{}}],"attrs":{}},{"type":"text","text":". But if we mix them up to use them , It will make our array into a different data structure .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"bulletedlist","content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"push","attrs":{}}],"attrs":{}},{"type":"text","text":" And ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"shift","attrs":{}}],"attrs":{}},{"type":"text","text":" perhaps ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"pop","attrs":{}}],"attrs":{}},{"type":"text","text":" And ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"unshift","attrs":{}}],"attrs":{}},{"type":"text","text":" Use a combination of , So an array is a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" queue (Queue)","attrs":{}}],"attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"codeinline","content":[{"type":"text","text":"push","attrs":{}}],"attrs":{}},{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"pop","attrs":{}}],"attrs":{}},{"type":"text","text":" In combination, then , An array is a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Stack (Stack)","attrs":{}}],"attrs":{}},{"type":"text","text":" ( Of course shif and unshif It's OK, too , But we don't usually use this combination to make stacks , Because we think about JavaScript The implementation of the array of , In this way, the performance will be lower .)","attrs":{}}]}],"attrs":{}}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" All these theoretical knowledge have been understood , We can start to sort out the idea of writing code :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" We need to declare a queue , That is to say a statement ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":", And put our starting point in the queue by default .(JavaScript We can use arrays in )","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" Write a “ The team ” Methods , The condition is to jump out of the method if you encounter an edge or obstacle , These are not walkable grids, so they won't join our queue .","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" If you don't meet the above situation , We can put the walkable grid in our ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"map","attrs":{}}],"attrs":{}},{"type":"text","text":"( An array declared when implementing our map data ) Record a state in , Here we can use ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":", This is the grid we've been through , Here we add a marker .","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" Loop the grid we can walk in the queue , The main goal here is to find all the grids that can be walked ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" On ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Next ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Left ","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Right ","attrs":{}}],"attrs":{}},{"type":"text","text":", And put all these walkable cells in the queue , Then, when we enter the next cycle, we will find out where these newly queued cells can go , Then put the lattices found in the back into the queue again , And so on .","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":5,"align":null,"origin":null},"content":[{"type":"text","text":" This cycle has a cut-off condition , That's if we loop through each grid , Found the end of the grid , We can go straight back to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"true","attrs":{}}],"attrs":{}},{"type":"text","text":", We have found the end .","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Good idea again , Let's take a look at the code implementation right now :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"// The code from the previous part , It's ignored here ...\n// Just modify this part after the code in the upper part \n\n// Leave after clicking the mouse button , Make it more like false\ndocument.addEventListener('mouseup', () => (mousedown = false));\n// Because we need to right-click , So you should disable the right-click open menu by default \ndocument.addEventListener('contextmenu', e => e.preventDefault());\n\n/**\n * The way to find the way \n * @param {Array} map Map data \n * @param {Array} start The starting point for example :[0, 0]\n * @param {Array} end End for example :[50, 50]\n * @return Boolean\n */\nfunction path(map, start, end) {\n var queue = [start];\n \n function insert(x, y) {\n // To the edge of the chassis , Direct stop \n if (x < 0 || x >= 100 || y < 0 || y >= 100) return;\n // Meet the wall of the map , And stop \n if (map[y * 100 + x]) return;\n // The status of the grid marking the possible path is 2\n map[y * 100 + x] = 2;\n // Push the road into line \n queue.push([x, y]);\n }\n\n // Circular lattice 4 Side grid \n while (queue.length) {\n let [x, y] = queue.shift();\n console.log(x, y);\n\n // You can return to the destination position \n if (x === end[0] && y === end[1]) return true;\n\n // Push up, down, left and right into the queue \n insert(x - 1, y);\n insert(x, y - 1);\n insert(x + 1, y);\n insert(x, y + 1);\n }\n\n return false;\n}","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In order to debug it , Is our code correct , Let's add a button , And let it perform our pathfinding method ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"path","attrs":{}}],"attrs":{}},{"type":"text","text":".","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"
\n\n
\n \n \n
","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Here our button will perform a pathfinding method , The starting point is x = 0,y = 0 The location of , The end is x = 50,y = 50 The location of . After you click this button , We can use it in the browser's debugging tool ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"console","attrs":{}}],"attrs":{}},{"type":"text","text":" In the process of finding the way x and y. If we're right about the code , In the end, we'll see 50, 50 It'll stop working when it's time .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"http://tridiamond.tech/frontend-tutorials/exercises/path-finder/2-map-path.html","title":""},"content":[{"type":"text","text":" See the effect ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"link","attrs":{"href":"https://github.com/TriDiamond/frontend-tutorials/blob/master/exercises/path-finder/2-map-path.html","title":""},"content":[{"type":"text","text":" Look at the code ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Favorite students star Thank you !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Join in Async and Await To facilitate debugging and display ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In the last code , In fact, the main part of the routing algorithm has been realized . But there are still some problems :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" Although the algorithm finally returns to our destination , And back to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"true","attrs":{}}],"attrs":{}},{"type":"text","text":", It seems to be in line with our expectations . But we can't guarantee its correctness .","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" So we want to have a visual effect to observe the process of the pathfinding algorithm ","attrs":{}},{"type":"text","text":".","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" We're finding a path ,","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" We haven't found the final path yet ","attrs":{}},{"type":"text","text":".","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" We will solve these problems step by step in the next few steps .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" How to have a look at our 《TicTacToe Sanzi 》 The programming and algorithm practice of the article , We talked about the use of ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"async","attrs":{}}],"attrs":{}},{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"await","attrs":{}}],"attrs":{}},{"type":"text","text":" , To insert some asynchronous operations in the middle of the function .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In this part of the code, we have made some code changes :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" hold ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"path()","attrs":{}}],"attrs":{}},{"type":"text","text":" The function is changed to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"async","attrs":{}}],"attrs":{}},{"type":"text","text":" function ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" hold ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"insert()","attrs":{}}],"attrs":{}},{"type":"text","text":" The function is changed to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"async","attrs":{}}],"attrs":{}},{"type":"text","text":" function ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" because ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"insert()","attrs":{}}],"attrs":{}},{"type":"text","text":" Programmed asynchronous functions , So we ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while()","attrs":{}}],"attrs":{}},{"type":"text","text":" In the loop insert All calls need to be preceded by ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"await","attrs":{}}],"attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" At the same time, we need to add a wait function ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"sleep()","attrs":{}}],"attrs":{}},{"type":"text","text":", It has to return a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"promise","attrs":{}}],"attrs":{}},{"type":"text","text":" ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":5,"align":null,"origin":null},"content":[{"type":"text","text":" After we were in line , Change the current grid state to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":" Before , We will be right. DOM Change the background color of the grid in the element , So we can see the path finding process ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":6,"align":null,"origin":null},"content":[{"type":"text","text":" Because we need to see the process , So every time we enter the queue, we need to give a 1 Second waiting time , This is the use of ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"async","attrs":{}}],"attrs":{}},{"type":"text","text":" and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"await","attrs":{}}],"attrs":{}},{"type":"text","text":" The benefits of . Before adding this background color , We can join a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"await sleep(1)","attrs":{}}],"attrs":{}},{"type":"text","text":", In this way, before entering the queue and changing the background color of the grid, there will be 1 Second delay .","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Good. Cut the crap , Let's see what the code has changed :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"// The code from the previous part , It's ignored here ...\n// Just modify this part after the code in the upper part \n\n// Leave after clicking the mouse button , Make it more like false\ndocument.addEventListener('mouseup', () => (mousedown = false));\n// Because we need to right-click , So you should disable the right-click open menu by default \ndocument.addEventListener('contextmenu', e => e.preventDefault());\n\n/**\n * Wait function \n * @param {Integer} t Time ( second )\n * @return Promise\n */\nfunction sleep(t) {\n return new Promise(function (resolve) {\n setTimeout(resolve, t);\n });\n}\n\n/**\n * The way to find the way ( asynchronous )\n * @param {Array} map Map data \n * @param {Array} start The starting point for example :[0, 0]\n * @param {Array} end End for example :[50, 50]\n * @return Boolean\n */\nasync function path(map, start, end) {\n var queue = [start];\n\n /**\n * The method of entrance ( asynchronous )\n * @param {Integer} x\n * @param {Integer} y\n */\n async function insert(x, y) {\n // To the edge of the chassis , Direct stop \n if (x < 0 || x >= 100 || y < 0 || y >= 100) return;\n // Meet the wall of the map , And stop \n if (map[y * 100 + x]) return;\n // Join in 30 A millisecond pause , Let's see UI The changes above \n await sleep(1);\n // Add the background color to the grid of the searched path \n container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';\n // The status of the grid marking the possible path is 2\n map[y * 100 + x] = 2;\n // Push the road into line \n queue.push([x, y]);\n }\n\n // Circular lattice 4 Side grid \n while (queue.length) {\n let [x, y] = queue.shift();\n // console.log(x, y);\n\n // You can return to the destination position \n if (x === end[0] && y === end[1]) return true;\n\n // Push up, down, left and right into the queue \n await insert(x - 1, y);\n await insert(x, y - 1);\n await insert(x + 1, y);\n await insert(x, y + 1);\n }\n\n return false;\n}","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Finally, the result of our implementation :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/5a/5aab27190ac1ab42e994009159e7bf37.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"http://tridiamond.tech/frontend-tutorials/exercises/path-finder/3-map-search-async.html","title":""},"content":[{"type":"text","text":" See the effect ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"link","attrs":{"href":"https://github.com/TriDiamond/frontend-tutorials/blob/master/exercises/path-finder/3-map-search-async.html","title":""},"content":[{"type":"text","text":" Look at the code ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Favorite students star Thank you !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Deal with the path problem ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Last time we used an animation , Let's have a clear understanding of the whole process of path finding algorithm . But the second problem mentioned in the previous step , We haven't solved it yet . So here we are trying to find out what the final path is , After we finally passed the pathfinding algorithm , How can we get a path from the beginning to the end ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In fact, it's very simple to deal with this path , Let's take a look at the idea of finding the way we talked about before :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/a3/a3dadfa9cff63dc8c7f8d996cb7ba5db.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Through the picture above , We all remember , When we visit every grid , We're all expanding out to find the walkable grids . In the process , We all know that each extended lattice is self extended by the previous one . let me put it another way , Every grid knows that we are self expanding from that grid .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" for instance ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"5","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"6","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"7","attrs":{}}],"attrs":{}},{"type":"text","text":" These three lattices are all from ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"1","attrs":{}}],"attrs":{}},{"type":"text","text":" This lattice is expanded . Now that we know each source from the previous step , Can we put a source grid on every self record ? So in the code, can we join the team , Just record one for myself x,y What about the shaft ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So we have an idea , Through this record , How do we find the final path ?","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Let's assume that the destination is ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"8","attrs":{}}],"attrs":{}},{"type":"text","text":" This position , Let's come here ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"8","attrs":{}}],"attrs":{}},{"type":"text","text":" This point is expanded step by step from our starting point , Then we record the precursor lattice of each lattice in turn , You can shrink step by step and go back to the starting point ?","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" That is to say , from ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"8","attrs":{}}],"attrs":{}},{"type":"text","text":" Start to collect ,","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"8","attrs":{}}],"attrs":{}},{"type":"text","text":" It's from ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":" Come here , and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"2","attrs":{}}],"attrs":{}},{"type":"text","text":" It's from ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" The starting point ","attrs":{}}],"attrs":{}},{"type":"text","text":" Extended , In the end, we have a starting point . If we record the lattice we visit during the contraction , In the end, these grids are the whole path from the beginning to the end ! Isn't that amazing ?!","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" In fact, it can also be understood as a “ Please Return by the Way You Came ” The effect of !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/bd/bd95a0f527518180b8a254451db42abe.gif","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" No chicken jelly for now , steady ! Let's take a look at how the code handles :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" In fact, our code hasn't changed much ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" The first is in the ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while","attrs":{}}],"attrs":{}},{"type":"text","text":" In the loop ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"insert()","attrs":{}}],"attrs":{}},{"type":"text","text":" When calling, the parameter of the previous coordinate is added ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" Here we also add horizontal and walkable grids to the queue ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" Here, because we need to record the precursor coordinates of all the lattices , So we need to declare a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"table","attrs":{}}],"attrs":{}},{"type":"text","text":" The variable that holds this data ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":5,"align":null,"origin":null},"content":[{"type":"text","text":" Before we get into the queue , We save the value of the current grid in the queue as the coordinates of the previous grid ( This is for our convenience. The contraction is to find the whole path )","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":6,"align":null,"origin":null},"content":[{"type":"text","text":" Last in ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while","attrs":{}}],"attrs":{}},{"type":"text","text":" In circulation , When we meet the end of x and y When , Let's add a paragraph ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while","attrs":{}}],"attrs":{}},{"type":"text","text":" loop ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":7,"align":null,"origin":null},"content":[{"type":"text","text":" This ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while","attrs":{}}],"attrs":{}},{"type":"text","text":" Just go back and keep going , Until we find the starting point , While going back , Change the background of each passing grid to another background color , So we can draw a path on our map !","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Good, clear thinking , Let's take a look at the code !","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"// The code from the previous part , It's ignored here ...\n// Just modify this part after the code in the upper part \n\n/**\n * The way to find the way ( asynchronous )\n * @param {Array} map Map data \n * @param {Array} start The starting point for example :[0, 0]\n * @param {Array} end End for example :[50, 50]\n * @return Boolean\n */\nfunction sleep(t) {\n return new Promise(function (resolve) {\n setTimeout(resolve, t);\n });\n}\n\n/**\n * The method of entrance ( asynchronous )\n * @param {Integer} x\n * @param {Integer} y\n */\nasync function findPath(map, start, end) {\n // Create a record form \n let table = Object.create(map);\n let queue = [start];\n\n /**\n * The method of entrance ( asynchronous )\n * @param {Integer} x\n * @param {Integer} y\n * @param {Array} pre The coordinates of the last grid :[x,y]\n */\n async function insert(x, y, pre) {\n // To the edge of the chassis , Direct stop \n if (x < 0 || x >= 100 || y < 0 || y >= 100) return;\n // Meet the wall of the map , And stop \n if (table[y * 100 + x]) return;\n // Join in 30 A millisecond pause , Let's see UI The changes above \n // await sleep(1);\n // Add the background color to the grid of the searched path \n container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';\n // Mark the value of the grid passed by , A mark on the grid x,y Location \n table[y * 100 + x] = pre;\n // Push the road into line \n queue.push([x, y]);\n }\n\n // Circular lattice 4 Side grid \n while (queue.length) {\n let [x, y] = queue.shift();\n // console.log(x, y);\n\n // You can return to the destination position \n if (x === end[0] && y === end[1]) {\n let path = [];\n\n // Go back , Until we get to the starting point \n // So you can draw the best path \n while (x != start[0] || y != start[1]) {\n path.push(map[y * 100 + x]);\n [x, y] = table[y * 100 + x];\n await sleep(1);\n container.children[y * 100 + x].style.backgroundColor = 'fuchsia';\n }\n\n return path;\n }\n\n // Push up, down, left and right into the queue \n await insert(x - 1, y, [x, y]);\n await insert(x, y - 1, [x, y]);\n await insert(x + 1, y, [x, y]);\n await insert(x, y + 1, [x, y]);\n\n // hold 4 individual The beveled edge pushes into the queue \n await insert(x - 1, y - 1, [x, y]);\n await insert(x + 1, y - 1, [x, y]);\n await insert(x - 1, y + 1, [x, y]);\n await insert(x + 1, y + 1, [x, y]);\n }\n\n return null;\n}","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Be careful : Here we put the original ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"path","attrs":{}}],"attrs":{}},{"type":"text","text":" Change the function name to ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"findPath","attrs":{}}],"attrs":{}},{"type":"text","text":", Because looking for a path ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"while","attrs":{}}],"attrs":{}},{"type":"text","text":" In the loop we use ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"path","attrs":{}}],"attrs":{}},{"type":"text","text":" As a variable to record the path . What we need to pay attention to here is , our ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"find","attrs":{}}],"attrs":{}},{"type":"text","text":" The function calls in the button also need to be modified .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"html"},"content":[{"type":"text","text":"\n
\n \n \n
","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" ","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The final results are as follows :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/eb/eb81f224a7a560665193edbe218d5829.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"http://tridiamond.tech/frontend-tutorials/exercises/path-finder/4-map-find-path.html","title":""},"content":[{"type":"text","text":" See the effect ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"link","attrs":{"href":"https://github.com/TriDiamond/frontend-tutorials/blob/master/exercises/path-finder/4-map-find-path.html","title":""},"content":[{"type":"text","text":" Look at the code ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Favorite students star Thank you !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"heading","attrs":{"align":null,"level":1},"content":[{"type":"text","text":" Heuristic pathfinding (A*)","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So far, we have completed the whole breadth first routing algorithm . But is it the best way to find a way ?","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" It's not ","attrs":{}}],"attrs":{}},{"type":"text","text":"!","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/bc/bc8b68ef9eb75f70203c94c48089c90b.gif","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Through the efforts of mathematical scientists , They proved one thing . We can have a way to speed up the path finding , In this way, we don't have to use a very silly way to go one by one .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" This way of finding your way is called “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Heuristic pathfinding ","attrs":{}}],"attrs":{}},{"type":"text","text":"”","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Heuristic pathfinding is to use a function to determine the priority of these point extensions . As long as we judge the priority , We can go to the direction of the grid purposefully to find the way first .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":"“ But is this the best path ? It's amazing .“ Tell the truth , This idea of our ordinary people is useless . But mathematicians have proved one thing , As long as we use heuristic functions to estimate values , And these values can be less than the length of the path from the current point to the end point , In this way, we can find the best path .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" This heuristic method can find the best path , In the computer, we call it to do “","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"A*","attrs":{}}],"attrs":{}},{"type":"text","text":"”. Inside ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"A","attrs":{}}],"attrs":{}},{"type":"text","text":" It represents a heuristic route finding that does not necessarily find the optimal path . therefore ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"A*","attrs":{}}],"attrs":{}},{"type":"text","text":" Namely A A special case of pathfinding , It's an algorithm that can find the best path .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" To implement this heuristic pathfinding , In fact, we don't need to change too much ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"findPath()","attrs":{}}],"attrs":{}},{"type":"text","text":" Function inside the code of . We need to change the data structure , That's our ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":" queue .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" We are going to put ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":" The first in, first out becomes a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Priority queue (Prioritized Queue)","attrs":{}}],"attrs":{}},{"type":"text","text":".","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" So we need to build a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"Sorted","attrs":{}}],"attrs":{}},{"type":"text","text":" class , This class has several jobs :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" This class can store our previous ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":" Data in the queue ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" Can support incoming sort functions ( That is, with us ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"array sort","attrs":{}}],"attrs":{}},{"type":"text","text":" Function like function , You can pass in a collation function , Also called ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"compare","attrs":{}}],"attrs":{}},{"type":"text","text":" function )","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" When we get the value through this class, give us the minimum value in the data ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" We don't need to sort when we insert data , It's just simple preservation ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":5,"align":null,"origin":null},"content":[{"type":"text","text":" Every time the data is removed , You can delete the output data from the class data ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":6,"align":null,"origin":null},"content":[{"type":"text","text":" So we can always get data in it , Until we know there's no data ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":7,"align":null,"origin":null},"content":[{"type":"text","text":" Finally, add a length to get the current data ( This is used in our routing algorithm )","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Here we use a very “ Woodlouse ” To implement this Sorted class , But in computers , There are many other ways we can achieve this kind of . for instance ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"winner tree","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Pile up (heap)","attrs":{}}],"attrs":{}},{"type":"text","text":",","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":" Sort binary trees ","attrs":{}}],"attrs":{}},{"type":"text","text":" And so on many different ideas to achieve an orderly data structure .","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Good. Cut the crap , Let's see how to implement this data structure :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"/** Sort data classes */\nclass Sorted {\n constructor(data, compare) {\n this.data = data.slice();\n this.compare = compare || ((a, b) => a - b);\n }\n take() {\n // in consideration of null We can also participate in the comparison , So back here null It's not appropriate \n if (!this.data.length) return;\n // Record the minimum value \n // By default, the first position is the minimum value \n let min = this.data[0];\n // Record the location of the minimum \n let minIndex = 0;\n\n // Start comparing all the values in the array , Find a smaller value , It's recorded as min\n // Record the minimum value at the same time , And the location of the minimum \n for (let i = 1; i < this.data.length; i++) {\n if (this.compare(this.data[i], min) < 0) {\n min = this.data[i];\n minIndex = i;\n }\n }\n\n // Now we're going to take out the minimum , So we need to remove it from our current data \n // Here we don't consider using splice, because splice Removal involves moving the elements in the array forward \n // such splice There will be one O(N) Time complexity of \n // Here's a little trick , Move the value of the last bit in the array to the position where the minimum value is found \n // Finally using pop Remove the last bit of data \n this.data[minIndex] = this.data[this.data.length - 1];\n this.data.pop();\n // Finally, output the minimum value \n return min;\n }\n give(value) {\n this.data.push(value);\n }\n get length() {\n return this.data.length;\n }\n}","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" With this ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"Sorted","attrs":{}}],"attrs":{}},{"type":"text","text":" After the data structure , We can use it to solve our pathfinding problem , So we can find the best path .","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Add the logic of the best path , We need to change to a few points :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"numberedlist","attrs":{"start":"1","normalizeStart":1},"content":[{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":1,"align":null,"origin":null},"content":[{"type":"text","text":" First of all, rewrite our stored data ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"queue","attrs":{}}],"attrs":{}},{"type":"text","text":", Use us ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"Sorted","attrs":{}}],"attrs":{}},{"type":"text","text":" Sort data structure of ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":2,"align":null,"origin":null},"content":[{"type":"text","text":" Write a ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"distance()","attrs":{}}],"attrs":{}},{"type":"text","text":" Function to calculate the linear distance between any lattice and the end grid ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":3,"align":null,"origin":null},"content":[{"type":"text","text":" Change all incoming and outgoing calls to use ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"Sorted","attrs":{}}],"attrs":{}},{"type":"text","text":" The inside of the class ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"take","attrs":{}}],"attrs":{}},{"type":"text","text":" Value and ","attrs":{}},{"type":"codeinline","content":[{"type":"text","text":"give","attrs":{}}],"attrs":{}},{"type":"text","text":" Insert value function ","attrs":{}}]}],"attrs":{}},{"type":"listitem","content":[{"type":"paragraph","attrs":{"indent":0,"number":4,"align":null,"origin":null},"content":[{"type":"text","text":" Basically nothing else has changed ","attrs":{}}]}],"attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" Next, let's see how the code is implemented :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"codeblock","attrs":{"lang":"javascript"},"content":[{"type":"text","text":"// The code from the previous part , It's ignored here ...\n// Just modify this part after the code in the upper part \n\n/**\n * The way to find the way ( asynchronous )\n * @param {Array} map Map data \n * @param {Array} start The starting point for example :[0, 0]\n * @param {Array} end End for example :[50, 50]\n * @return Boolean\n */\nasync function findPath(map, start, end) {\n // Create a record form \n let table = Object.create(map);\n let queue = new Sorted([start], (a, b) => distance(a) - distance(b));\n\n async function insert(x, y, pre) {\n // To the edge of the chassis , Direct stop \n if (x < 0 || x >= 100 || y < 0 || y >= 100) return;\n // Meet the wall of the map , And stop \n if (table[y * 100 + x]) return;\n // Join in 30 A millisecond pause , Let's see UI The changes above \n await sleep(1);\n // Add the background color to the grid of the searched path \n container.children[y * 100 + x].style.backgroundColor = 'DARKSLATEBLUE';\n // Mark the value of the grid passed by , A mark on the grid x,y Location \n table[y * 100 + x] = pre;\n // Push the road into line \n queue.give([x, y]);\n }\n\n /**\n * Get the distance between the lattice and the lattice \n * @param {Array} point The coordinates of the current grid :[x,y]\n */\n function distance(point) {\n // Use triangles x^2 + y^2 = z^2 How to calculate the distance \n return (point[0] - end[0]) ** 2 + (point[1] - end[1]) ** 2;\n }\n\n // Circular lattice 4 Side grid \n while (queue.length) {\n let [x, y] = queue.take();\n // console.log(x, y);\n\n // You can return to the destination position \n if (x === end[0] && y === end[1]) {\n let path = [];\n\n // Go back , Until we get to the starting point \n // So you can draw the best path \n while (x != start[0] || y != start[1]) {\n path.push(map[y * 100 + x]);\n [x, y] = table[y * 100 + x];\n container.children[y * 100 + x].style.backgroundColor = 'fuchsia';\n }\n\n return path;\n }\n\n // Push up, down, left and right into the queue \n await insert(x - 1, y, [x, y]);\n await insert(x, y - 1, [x, y]);\n await insert(x + 1, y, [x, y]);\n await insert(x, y + 1, [x, y]);\n\n // hold 4 individual The beveled edge pushes into the queue \n await insert(x - 1, y - 1, [x, y]);\n await insert(x + 1, y - 1, [x, y]);\n await insert(x - 1, y + 1, [x, y]);\n await insert(x + 1, y + 1, [x, y]);\n }\n\n return null;\n}","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" The final operation effect is as follows :","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/cd/cd7dfa17b40260f1210e225cfb5b1c5c.png","alt":null,"title":null,"style":[{"key":"width","value":"75%"},{"key":"bordertype","value":"none"}],"href":null,"fromPaste":true,"pastePass":true}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"blockquote","content":[{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"link","attrs":{"href":"http://tridiamond.tech/frontend-tutorials/exercises/path-finder/6-map-best-path.html","title":""},"content":[{"type":"text","text":" See the effect ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"link","attrs":{"href":"https://github.com/TriDiamond/frontend-tutorials/blob/master/exercises/path-finder/6-map-best-path.html","title":""},"content":[{"type":"text","text":" Look at the code ","attrs":{}}]},{"type":"text","text":" | ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Favorite students star Thank you !","attrs":{}}]}],"attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"horizontalrule","attrs":{}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null},"content":[{"type":"text","text":" I'm from 《","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Technology Galaxy ","attrs":{}},{"type":"text","text":"》 Of ","attrs":{}},{"type":"text","marks":[{"type":"strong","attrs":{}}],"text":" Three drills ","attrs":{}},{"type":"text","text":":\" Learning is for growth , Growth is to keep going . Persistence leads to success , Failure is just because there is no persistence . Come on, students ! See you next time !\"","attrs":{}}]},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"image","attrs":{"src":"https://static001.geekbang.org/infoq/f7/f7db8645b6fdfa85351bc5f5aeb79aeb.gif","alt":null,"title":"","style":[{"key":"width","value":"25%"},{"key":"bordertype","value":"none"}],"href":"","fromPaste":false,"pastePass":false}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}},{"type":"horizontalrule","attrs":{}},{"type":"heading","attrs":{"align":null,"level":1}},{"type":"paragraph","attrs":{"indent":0,"number":0,"align":null,"origin":null}}]}

版权声明
本文为[InfoQ]所创,转载请带上原文链接,感谢
https://cdmana.com/2020/12/20201225134431193k.html

Scroll to Top