# Auto-navigating our Grid using Breadth-First Search (BFS) by kirupa (https://www.kirupa.com/me/index.htm) | filed under Data Structures and Algorithms (https://www.kirupa.com/data_structures_algorithms/index.htm) By now, we've got the basics of working with our grid covered. We learned how to represent our grid, move Zorb around it, deal with boundaries, and even got a bit of collision detection figured out. What we are going to do here is kick what we've learned up a few notches. Instead of us moving and nudging Zorb along ourselves, we are going to give Zorb a destination and have him navigate the grid himself. He will do this navigation using our old friend, Breadth-First Search (BFS) (https://www.kirupa.com/data_structures_algorithms/dfs_bfs.htm). This is going to be a hoot! Onwards! ## What We're Going to Build As always, before we get fully into it, let's play with the finished example to give us an idea of what we'll be working towards (open in new window (https://www.kirupa.com/data_structures_algorithms/examples/grid_movement_pathfinding.htm?v=20261009-2)): Interactive example: Click a destination cell and watch Zorb walk around the rocks to reach it: https://www.kirupa.com/data_structures_algorithms/examples/grid_movement_pathfinding.htm?v=20261009-2 Hover over any open cell and click / tap to have Zorb navigate to it. Notice how Zorb navigates. He avoids all of the obstacles. We can see this clearly when we hover over a destination, since that shows the path Zorb will take. In the rest of the article, we'll learn how to build the logic that makes this navigation work. ## Some Obvious Ideas That Don't Work Before reaching for the final algorithm that Zorb can use to navigate our obstacle-filled grid, let's start with what seems like an obvious (yet incorrect) approach to take. At each turn, Zorb will take a step that moves him closer to the goal. To dive deeper into this obvious insight: 1. If the destination is below, Zorb tries to move down 2. If the destination is above, Zorb tries to move up 3. If the destination is to the left, Zorb tries to move left 4. If the destination is to the right, Zorb tries to move right 5. Keep repeating the above steps until Zorb reaches his destination This seems like a viable plan, though, right? As it turns out, not really. To see where this approach falls apart, let's shrink the world back down to the 5-by-5 grid we used last time: Image: A 5 by 5 grid labeled zero through four across the top and left, with rocks at (3, 1), (2, 2), (0, 3), and (4, 4). at https://www.kirupa.com/data_structures_algorithms/images/55grid_example_200.png We are going to put Zorb at (2, 1) and put his destination at (3, 4), down in the bottom row: Image: Zorb stands at (2, 1) in the 5 by 5 rock grid, with a flag marking his destination at (3, 4) in the bottom row. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_200.png The gap between Zorb and the destination is one column to the right and three rows down: Image: Red arrows measure the gap between Zorb at (2, 1) and the flag at (3, 4): one column to the right and three rows down. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_annotated_200.png To get to the destination, Zorb attempts to move down one step. As we can see, down from (2, 1) is (2, 2), and (2, 2) is a rock (maybe a rock....lobster? (https://www.youtube.com/watch?v=pn26ZJhSJ94)). So, moving down doesn't work. Let's have him move right instead. That plan is also foiled, because to the right of Zorb at (3, 1) is another rock. Both of his attempts to move closer to the destination are blocked right at the start. The only two moves he has left are to go up to (2, 0) or left to (1, 1): Image: The cells above Zorb at (2, 0) and to his left at (1, 1) are highlighted as the only two moves open to him. at https://www.kirupa.com/data_structures_algorithms/images/zorb_proposed_paths_200.png Both of them increase the distance to the goal. To get to (3, 4) at all, Zorb has to start by walking away from it. Going away for a brief bit before moving towards your destination isn't a bad strategy. It may be the only strategy if you are blocked like Zorb is right now. What makes this tricky is that it now adds more rules and complications. For example, Zorb now needs to remember which cells he has already tried. Otherwise, he will try the same corner repeatedly. The other detail to keep in mind, and this is a HUGE detail, is that what Zorb sees is only the cells in his immediate vicinity and any he has already explored: Image: Only Zorb's cell and its four neighbors are clearly visible, including the rocks to his right and below him, while the rest of the grid and the flag are faded out. at https://www.kirupa.com/data_structures_algorithms/images/zorb_what_sees_200.png Zorb doesn't know how big the grid is. He doesn't know where the other obstacles are. He doesn't know where the destination is. In many real-world scenarios, an important navigation activity is to figure out if there is even a destination. Only we, as human observers, can see the full grid and where all the obstacles are, and visually plot a path to the destination. That too fails for large, complex grids where even you and I can't fully make sense of the full environment. So basically, having Zorb try to optimize his way to the destination won't work unless we tell him where the destination is. The only other solution is to have Zorb try every possible walk through the grid and keep the best one. That works, but this brute-force version is far too slow to be useful. This isn't a problem for a small surface like our 5-by-5 grid. In real-world situations, your grid may be 10s or 100s or even 1,000s of times larger than our grid here. There won't be enough seconds in the universe (insert dramatic pause) to exhaustively plot every path. The solution we want will sit snugly between our two approaches. We want something that explores, like the brute-force version, but we also want it to be smart enough to never explore the same cell twice and to stop the moment it finds the destination. ## Breadth-First Search to the Rescue For a moment, imagine Zorb sends out a series of drones to explore the area and report back what they find. As they go from cell to cell, each drone records how far away from Zorb it is. The drone that arrives at the destination first is the one that got there by the shortest route available. If this idea sounds like a great one, that's because what we just described is how our old friend breadth-first search, commonly shortened to BFS, behaves. It works on a grid like this: 1. Mark Zorb's cell as reached in 0 steps. 2. Find every open neighbor of that cell and mark those as reached in 1 step. 3. Find every open, unmarked neighbor of those cells and mark them as 2 steps. 4. Keep going, one full ring at a time, until the destination gets marked. The critical word in there is unmarked. Once a cell has a number, it keeps it. We never come back and overwrite it, because any later visit arrived on a route at least as long as the first one. #### Note: You May Have Seen This Before If BFS rings a bell, it's because you and I may have talked about it already in Depth-First Search and Breadth-First Search (https://www.kirupa.com/data_structures_algorithms/dfs_bfs.htm). The only difference is that we looked at it in the context of graphs instead of grids. As we will talk about a bit later, a grid is a graph. In a grid, every open cell is a node, and every pair of open neighbors is an edge. Let's run that on our 5-by-5 grid and actually watch it happen. Zorb starts at (2, 1), so that cell gets a 0: Image: Zorb's starting cell at (2, 1) is marked 0, and every other cell is still unmarked. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_zero_200.png Now the first ring. Zorb's four neighbors are (2, 0) above, (2, 2) below, (1, 1) to the left, and (3, 1) to the right. Two of those neighbors are rocks, so we ignore them. The other two non-rock, open spaces get a 1: Image: The open cells at (2, 0) and (1, 1) are marked 1, while the rocks to Zorb's right and below him are highlighted and skipped. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_one_200.png Our explorer drones continue, and they will take off and explore from the cells marked as 1. From (2, 0) we reach (1, 0) and (3, 0). From (1, 1) we reach (0, 1) and (1, 2). This results in us discovering four new cells, and we mark them with a 2: Image: Four more cells at (1, 0), (3, 0), (0, 1), and (1, 2) are marked 2. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_two_200.png This pattern now repeats, with drones from each of the cells marked with a 2 exploring their immediate neighbors. This brings us to ring 3, which adds (0, 0), (4, 0), (0, 2), and (1, 3). Ring 4 adds (4, 1), (2, 3), and (1, 4). Ring 5 adds (4, 2), (3, 3), (0, 4), and (2, 4). And on ring 6, one of the cells we mark is (3, 4), which is where we were going: Image: Every open cell is labeled with its step count from Zorb, and the destination at (3, 4) is outlined with a 6. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_reached_200.png Every open cell on the grid now has a number that signifies the number of steps it sits from Zorb. Our destination has a number of 6. This means that our destination is 6 steps away from Zorb. When we look at this grid, let's pay attention to where the large values are. For example, look at (3, 2), which sits diagonally next to Zorb, with a 6 on it. It's physically close to Zorb yet one of the last cells our drones reached. This is because the only ways in are around through the bottom or down the right-hand side. Now that we've added obstacles, using the straight-line distance as a heuristic doesn't work anymore. ## Leaving Breadcrumbs At this moment, we know the trip takes six steps. What we don't know is which six steps will lead Zorb to the destination. The solution is to leave behind a digital breadcrumb. Every time we (or our drones!) explore a new cell, we will write down which cell we came from. We can visualize this by using arrows. So when we explore (2, 0) and (1, 1) as part of ring 1, we will also record that they were both reached from Zorb's starting position of (2, 1): Image: The cells marked 1 at (2, 0) and (1, 1) each have an arrow pointing back to Zorb at (2, 1). at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_one_arrow_200.png We can repeat this process for every cell we explore. At the end of ring 2, we'll see something like this: Image: Each cell marked 2 has an arrow pointing back to the cell marked 1 that discovered it. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_two_arrow_200.png When we do that for every cell, we can see a clear path from each cell back to Zorb: Image: Every open cell shows its step count and an arrow pointing back to the neighbor it was reached from, forming trails that lead to Zorb. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_arrowed_200.png This visualization is a bit too busy, so let's simplify it and emphasize the path from Zorb to our destination: Image: The arrows are faded except for the highlighted route from the destination at (3, 4) through (2, 4), (1, 4), (1, 3), (1, 2), and (1, 1) back to Zorb. at https://www.kirupa.com/data_structures_algorithms/images/zorb_destination_arrowed_simple_200.png Reading the route is now just a fun exercise in following arrows. Start at the destination and keep asking each cell where it came from: (3, 4) came from (2, 4) (2, 4) came from (1, 4) (1, 4) came from (1, 3) (1, 3) came from (1, 2) (1, 2) came from (1, 1) (1, 1) came from (2, 1) <--- Zorb, so we stop That gives us the trip backwards. Flip it around and we have the path Zorb should walk to reach his destination: (2, 1) → (1, 1) → (1, 2) → (1, 3) → (1, 4) → (2, 4) → (3, 4) What we just did was take the 6-move "answer" we got in the previous section and make it actionable by adding the breadcrumbs to each cell with the detail on how someone landed there. Now that we've seen how BFS can help with our pathfinding problem, it is time to go one level deeper and look at the implementation. ## Putting it All Together Building the grid, the rocks, and Zorb's walking animation is mostly frontend work, and building all of that from scratch would bury the search code we actually came here for. So we won't. Instead, we'll start from a copy of the finished example with its pathfinding scooped out. Grab the starter file from GitHub (https://github.com/kirupa/kirupa/blob/master/examples/grid_movement_pathfinding_start.htm), save it as grid_movement_pathfinding.htm, and open it in your browser. Click any open cell. Zorb stays right where he is, and the line under the grid reads something like Zorb will eventually walk to (7, 2). Click a rock and you get the same cheerful promise. Hovering does nothing at all. That's the correct amount of broken for where we are, since everything works except the part where Zorb figures out how to get somewhere. ### A Quick Tour of the Starter If you followed along with Moving Around a Grid and Avoiding Obstacles (https://www.kirupa.com/data_structures_algorithms/moving_around_a_grid_with_obstacles.htm), a lot of this will look familiar. The direction buttons are gone, since nobody is steering Zorb by hand anymore, but the world itself is exactly the same. The syncParentTheme function at the very top of the script only kicks in when the example is embedded inside a kirupa.com page, where it borrows the site's colors, so you can skip right past it. Just below it, we define our world: const rows = 10; const cols = 10; const start = { x: 4, y: 4 }; const zorb = { ...start }; const obstacles = new Set([ "1,1", "2,1", "3,1", "6,1", "7,1", "8,1", "3,2", "8,2", "0,3", "1,3", "3,3", "5,3", "6,3", "8,3", "5,4", "1,5", "2,5", "3,5", "5,5", "7,5", "8,5", "3,6", "7,6", "1,7", "5,7", "7,7", "1,8", "2,8", "3,8", "5,8" ]); Our grid is 10 cells wide and 10 cells tall, and Zorb starts at (4, 4). Just like before, x counts columns from the left and y counts rows from the top, so moving up means subtracting 1 from y. Every rock is an "x,y" string in a Set, so "5,4" is the rock sitting just to Zorb's right. The zorb object tracks where he is right now, while start remembers where he began so that the Reset button knows where to put him back. A little further down are four small helpers that we'll lean on: function key(x, y) { return `${x},${y}`; } function inBounds(x, y) { return x >= 0 && x < cols && y >= 0 && y < rows; } function isObstacle(x, y) { return obstacles.has(key(x, y)); } function cellAt(x, y) { return cells[y * cols + x]; } key turns a coordinate into that "x,y" string format. inBounds tells us whether a coordinate is on the grid at all, and isObstacle tells us whether a rock fills it. cellAt hands back the button for a coordinate. It can do that with a little math because every cell is stored in the cells array in reading order, left to right and then top to bottom, which puts the cell at (x, y) at position y * cols + x. Right below cellAt is a comment that reads // Our breadth-first search code goes here. Hold on to that thought, because most of our new code is going there. The cells themselves are built by a loop near the bottom of the script. Each one is a real button instead of a plain div, so it can take keyboard focus, and pressing Enter or Space on it counts as a click without any extra code from us. Every button also stores its coordinates in data-x and data-y, so when an event fires, the cell can tell us which square it is. Rock cells get an obstacle class, and the CSS draws a rock inside them. Zorb is a single element floating above the cells, and placeZorb slides him to whatever zorb.x and zorb.y say. His element is exactly one cell in size, so moving him one column over is a shift of 100%, and a CSS transition handles the animation for us. That brings us to walk. Hand it an array of cells, and it moves Zorb along them one cell every 160 milliseconds, numbering each cell as he goes. The smaller helpers around it, setStatus, clearPreview, clearTrail, and markTrail, update the message under the grid and add or remove the highlights on our cells. Nothing in the starter calls walk yet, but nothing stops us from calling it ourselves. Open your browser's developer console. Don't worry if it's already showing an error about a font from kirupa.com. Browsers won't load that font into a page opened straight from your computer, so the heading falls back to a plainer font and nothing else changes. Now paste in this path we wrote by hand. If your browser warns you about pasting into the console, type allow pasting like it asks and then paste again: walk([ { x: 4, y: 4 }, { x: 4, y: 3 }, { x: 4, y: 2 }, { x: 5, y: 2 } ]); Zorb walks up two cells and then right one, numbering the cells 0 through 3 as he goes. Take a good look at the shape of that array, because producing arrays like it is the entire job of the code we're about to write. It starts on the cell Zorb is already standing on, ends on the destination, and each entry is one step up, down, left, or right from the one before it. Also, walk trusts us completely. Hand it a path that cuts through a rock and Zorb will happily walk right over it, so keeping him off the rocks is our search's job. Click the Reset button to send Zorb back to (4, 4) when you're done. The last major piece is the event handling. Clicking a cell calls goTo(x, y). Hovering over a cell with a mouse, or moving to it with the keyboard, calls showPreview(x, y). Touch screens skip the hover, since a finger can't hover over anything. Moving the mouse off the grid clears the preview, the arrow keys move focus from cell to cell, and the Reset button puts Zorb back where he started. Here are the two functions those events call, and both are placeholders for now: function showPreview(x, y) { // Once Zorb can find his own way, this highlights his route to (x, y). } function goTo(x, y) { // Once Zorb can find his own way, this sends him walking to (x, y). setStatus(`Zorb will eventually walk to (${x}, ${y}).`); } That's why the starter makes promises it can't keep. Our job is to add the search code where that placeholder comment sits and then fill in these two functions. ### Labeling the Destination In our pictures, the destination is the cell with the flag in it. Our search needs a way to recognize that cell when it gets there, without ever being told where it is. Think back to our drones. They don't fly toward the flag, because they don't know where it is. They spread out, and the first drone to land on the flag's cell is the one that found the shortest route. So we need two things: a label that marks which cell holds the flag, and a question the search can ask about whatever cell it's on. Replace the // Our breadth-first search code goes here. comment with the following: // Which cell holds the flag. findPath never reads this. It only asks // isDestination about each cell it reaches. let destination = null; function isDestination(x, y) { return key(x, y) === destination; } destination holds the flag's cell as an "x,y" string, the same format our rocks use. It starts out as null, because there's no flag until someone picks a cell. isDestination answers true or false for one cell at a time, and that's the only peek our search ever gets at where the flag is. It can't ask where is the flag? It can only ask is the flag right here? ### Searching for a Path Next, our search needs to know which ways it's allowed to step. If you went through the obstacle tutorial, you'll recognize this table. Add it right below isDestination: const DIRECTIONS = { up: [0, -1], down: [0, 1], left: [-1, 0], right: [1, 0] }; Each pair says how much x and y change when we take one step in that direction. Since y counts down from the top, up is -1. Now for the search itself. Add findPath right below DIRECTIONS: // Breadth-first search. It never looks up where the destination is. It fans // out one ring of neighbors at a time and only recognizes the destination // when it reaches that cell, so the first arrival is in the fewest steps. function findPath(startX, startY) { const cameFrom = new Map([[key(startX, startY), null]]); const frontier = [{ x: startX, y: startY }]; while (frontier.length > 0) { const current = frontier.shift(); if (isDestination(current.x, current.y)) { return buildPath(cameFrom, current); } for (const [xOffset, yOffset] of Object.values(DIRECTIONS)) { const nextX = current.x + xOffset; const nextY = current.y + yOffset; const nextKey = key(nextX, nextY); if (!inBounds(nextX, nextY)) { continue; } if (isObstacle(nextX, nextY)) { continue; } if (cameFrom.has(nextKey)) { continue; } cameFrom.set(nextKey, current); frontier.push({ x: nextX, y: nextY }); } } return null; } Look at what findPath takes: the coordinates of the cell to start from, and nothing else. The destination isn't one of its inputs. Everything it learns about the flag comes from asking isDestination about the cell it's currently looking at. Two collections do all the work. The frontier is the list of cells we've found but haven't explored from yet. Think of it as the line of cells waiting for their drones to take off. cameFrom is our breadcrumb map. For every cell we've reached, it records which cell we came from, and it pulls double duty as our record of which cells we've already marked. That's why the starting cell goes into cameFrom right away, pointing at null. It counts as marked from the very beginning, so the search never wanders back into Zorb's cell. Each trip through the while loop takes the cell at the front of the frontier and checks whether it's the destination. If it isn't, Object.values(DIRECTIONS) hands us the four direction pairs, and const [xOffset, yOffset] pulls the two numbers out of each pair so we can work out the neighbor in that direction. Any neighbor that makes it past our checks gets a breadcrumb pointing back to the current cell and joins the back of the frontier. Those three continue statements are the ripple rules, one line each. Skip anything off the grid. Skip anything filled with rock. Skip anything we've already marked, because it already has a number at least as small as the one we could give it now. The ring-by-ring behavior comes from shift. Because we pull cells off the front and push new ones onto the back, everything one step away gets processed before anything two steps away does. That queue ordering is the breadth-first part. Swap shift for pop and you have depth-first search, which will happily march into a far corner before checking the cell next door. Notice where the destination check sits: at the top of the loop, on the cell we just took off the front of the list. Cells come off in ring order, so the moment the destination comes off, we know no other route could get there in fewer steps. Checking here also covers the case where Zorb is already standing on the flag, since his cell is the very first one to come off. Notice the two ways out of this function. It returns a path the moment the destination comes off the frontier, and it returns null when the frontier empties without ever finding it. That second case matters. An empty frontier means the ripple has touched every cell it can reach and the destination wasn't among them, so there genuinely is no route. That's exactly what happens when the flag sits on a rock. The search never steps onto a rock, so it explores all 70 open cells, comes up empty, and hands back null. #### Note: Why Turn Cells Into Strings? You might wonder why cameFrom uses keys like "4,3" instead of the { x, y } objects themselves. A Map treats two objects as different keys even when they hold the exact same numbers, so a { x: 4, y: 3 } created twice would count as two different cells. Two strings that read "4,3" always match, so turning each cell into a string gives it exactly one spot in our map. #### Note: When Two Routes Tie There can be more than one shortest route. To reach (9, 2), Zorb can go over the top of the grid, or he can dip below the rocks to his right and come up the right-hand side. Both routes take 11 steps. Our search keeps whichever one reaches the destination first, and that comes down to the order of the entries in DIRECTIONS. Shuffle that order and you may get a different route of the same length. ### Reading the Breadcrumbs findPath hands its answer off to a buildPath function we haven't written yet. Add it right below findPath: // Walk the breadcrumb trail backwards from the goal to the start. function buildPath(cameFrom, goal) { const path = []; let current = goal; while (current) { path.push(current); current = cameFrom.get(key(current.x, current.y)); } return path.reverse(); } This is our arrow-following exercise from earlier, written as code. Starting at the destination, we keep asking cameFrom which cell each one came from. We seeded cameFrom with the starting cell pointing at null, so the loop stops on its own when it walks back to Zorb. The reverse flips the trail into travel order, which gives us an array that starts at Zorb and ends at the destination. That's the exact shape walk wants. Save, refresh, and try it from the console before wiring up any clicks: destination = key(9, 2); findPath(4, 4).length; // 12 destination = key(5, 4); findPath(4, 4); // null, that's a rock Notice that we set destination before calling findPath. The search has no other way of knowing which cell holds the flag, so the label has to be in place before the search starts. The first call reports twelve cells, which is eleven steps plus the cell Zorb is already standing on. That off-by-one is worth burning in now, because it shows up every time we print a step count: a path of n cells is n - 1 moves. Because findPath returns exactly what walk wants, the two snap right together. Put the flag back on (9, 2) and let Zorb loose: destination = key(9, 2); walk(findPath(zorb.x, zorb.y)); Zorb heads up to the top row, runs along it, and drops down to (9, 2), all on his own. Click the Reset button when he gets there. ### Showing the Route on Hover Our search doesn't change anything. It reads the rocks and the flag, then hands back an answer without moving Zorb or touching the grid. That means we can call it while the mouse is just passing over a cell, which is exactly what the hover preview does. Replace the placeholder showPreview with this version: function showPreview(x, y) { clearPreview(); if (walkTimer !== null) { return; } if (x === zorb.x && y === zorb.y) { setStatus(`Zorb is already standing at (${x}, ${y}).`); return; } destination = key(x, y); const path = findPath(zorb.x, zorb.y); if (!path) { cellAt(x, y).classList.add("preview-blocked"); setStatus( isObstacle(x, y) ? `A rock fills (${x}, ${y}). Zorb has nowhere to stand.` : `There is no open route to (${x}, ${y}).`, true ); return; } for (const step of path) { cellAt(step.x, step.y).classList.add("preview"); } cellAt(x, y).classList.add("preview-goal"); const steps = path.length - 1; setStatus( `Route to (${x}, ${y}): ${steps} ${steps === 1 ? "step" : "steps"}.` ); } Going from the top, we first wipe away the old preview. If Zorb is in the middle of a walk, we stop right there and skip the preview. He changes cells every 160 milliseconds, so any route we drew would be out of date almost immediately. Hovering over Zorb's own cell gets a status message and nothing more. Next, we set destination to the hovered cell and search from wherever Zorb is right now, using zorb.x and zorb.y instead of his starting cell. After a walk, Zorb is somewhere new, and the next search has to start from there. If the search comes back null, we give the cell a preview-blocked class, which shades it gray, and use isObstacle to pick the right message. In our grid, every open cell can be reached from every other open cell, so you'll only see the no open route message if you add rocks that wall off part of the grid. Otherwise, every cell on the route gets a preview class, the destination gets a ring on top, and the status message reports path.length - 1 steps, thanks to our off-by-one rule. The stylesheet tints the preview a fainter blue than the trail, so the route you're considering never looks like the route you took. Save and refresh, then run your mouse around the grid. The route should snap into place under the cursor and bend around every rock it meets. Hover over (9, 2) and you'll see the 11-step route along the top. Hover over a rock and the line under the grid tells you there's nowhere for Zorb to stand. If you'd rather use the keyboard, tab into the grid and move around with the arrow keys, and the preview will follow along. ### Walking the Path The last placeholder is goTo. A click runs the same search and then plays the result back one cell at a time. Replace the placeholder goTo with this: function goTo(x, y) { if (x === zorb.x && y === zorb.y) { setStatus(`Zorb is already standing at (${x}, ${y}).`); return; } destination = key(x, y); const path = findPath(zorb.x, zorb.y); if (!path) { stopWalking(); clearPreview(); cellAt(x, y).classList.add("preview-blocked"); setStatus( isObstacle(x, y) ? `A rock fills (${x}, ${y}). Pick an open cell instead.` : `There is no open route to (${x}, ${y}).`, true ); return; } walk(path); } This is the same search our preview runs. The only difference is what we do with the answer. Instead of highlighting the route, we hand it straight to walk. If the answer is null, we stop any walk in progress, shade the cell gray, and explain why. Clicking a new cell while Zorb is still walking works too. The search starts from whatever cell Zorb is on at that moment, and the first thing walk does is call stopWalking, which clears the pending setTimeout so the old trip can't keep stepping underneath the new one. Save, refresh, and click a cell on the far side of the grid. Zorb should set off immediately, thread through the gaps, and leave a numbered trail showing the order he visited each square. Click somewhere else while he's still moving and he should change course without stopping. ### The Full Source That's every change. Here's the full source for grid_movement_pathfinding.htm with all of our pieces in place: Grid Movement: Navigating Between Points

Guide Zorb

Click or tap any open cell. Zorb will find his own way there.

You can also get the full source from GitHub, so go here to do that (https://github.com/kirupa/kirupa/blob/master/examples/grid_movement_pathfinding.htm) if you'd rather not copy and paste. ## Diving into the BFS Implementation When we added findPath earlier, we moved through it pretty quickly. In this section, we're going to slow way down and go through it a few lines at a time. For each chunk, we'll look at what the code does, why it's written the way it is, and what would go wrong if it weren't there. To keep things concrete, Zorb will be standing on (4, 4) with the flag on (9, 2), just like in our console test. ### Setting Up the Search Here are the first three lines: function findPath(startX, startY) { const cameFrom = new Map([[key(startX, startY), null]]); const frontier = [{ x: startX, y: startY }]; findPath takes two numbers: the column and row of the cell the search starts from. In our app, that's always the cell Zorb is standing on. There's no third input for the flag, and that's on purpose. cameFrom is a Map, which stores pairs of things: a key that we look things up by, and a value that goes with it. Our keys are cells written as "x,y" strings, and each value is the cell we stepped in from. The double square brackets look a little odd, but they're doing something simple. We can create a Map with a list of starting pairs, where each pair is a two-item array of [key, value]. The outer brackets are the list, and the inner brackets are the one pair inside it. So our map starts out with exactly one entry: "4,4" pointing to null. null is JavaScript's way of saying nothing. Zorb didn't step in from anywhere, so his breadcrumb points at nothing. That one entry does two jobs. It marks Zorb's cell as reached, so the search never puts his cell back in line, and it gives buildPath a place to stop. When buildPath follows the breadcrumbs back to Zorb's cell, it gets null, and its while (current) loop ends. frontier is a plain array with one item in it: Zorb's cell. Unlike the keys in cameFrom, the cells in frontier are { x, y } objects instead of strings. We're going to do math with these cells to find their neighbors, and numbers are a lot easier to add than strings we'd first have to pull apart. Both of these are declared with const, even though we're about to fill them up. const only means the name will always point at this same map and this same array. What's inside them can change as much as we want. ### Taking the Next Cell in Line Next up is the loop and the first line inside it: while (frontier.length > 0) { const current = frontier.shift(); Each pass through the while loop is one trip: take a cell off the line, look around it, and line up any new neighbors. The loop keeps going as long as frontier.length > 0, which is our way of asking is anyone still waiting in line? shift removes the first item in an array and hands it to us, so current is always the cell that has been waiting the longest. On the first trip, that's Zorb's cell, and for a brief moment after this line runs, the line is completely empty. That's fine. The while only checks frontier.length at the top of each trip, and by the time we get back there, Zorb's open neighbors will be waiting. Also, each trip gets its own brand new current, which is why a const works here even though current is a different cell every time. A line where the first one in is the first one out has a name. It's called a queue (https://www.kirupa.com/html5/queues_in_javascript.htm). Taking cells from the front of our array, and as we'll see in a bit, adding them to the back, is what turns a plain array into a queue. ### Checking for the Flag With a cell in hand, the first thing we do is ask whether it's the destination: if (isDestination(current.x, current.y)) { return buildPath(cameFrom, current); } This is the only place in findPath where the flag comes up, and the question is always about one cell: is the flag right here? With the flag on (9, 2), the answer is no 68 times in a row. On the 69th trip, (9, 2) finally comes off the front of the line, and the answer is yes. When that happens, return ends findPath on the spot. It breaks out of the while loop, ignores any cells still waiting in line, and hands back the route that buildPath puts together from our breadcrumbs. Leaving those cells unexplored is safe, because every one of them is at least as far from Zorb as the flag is. None of them could lead to a shorter route. You might be wondering why we wait until a cell comes off the line instead of checking each neighbor the moment we find it. Checking early would finish a little sooner. The flag's cell gets in line on trip 63, so we'd save 6 trips. The catch is that Zorb's own cell is marked from the start, so it never gets lined up as anyone's neighbor. We'd need a second check for when Zorb is already standing on the flag. Checking cells as they come off the line covers both cases with a single if. ### Looking in All Four Directions If the cell isn't the destination, we look at its neighbors one direction at a time: for (const [xOffset, yOffset] of Object.values(DIRECTIONS)) { DIRECTIONS is an object with four named entries: up, down, left, and right. We don't need the names here, just the pairs of numbers, and Object.values(DIRECTIONS) gives us exactly that: [[0, -1], [0, 1], [-1, 0], [1, 0]] The pairs come out in the same order we wrote them in DIRECTIONS: up, down, left, right. That order decides which neighbor gets in line first, and it's what breaks the ties we talked about earlier. The for...of loop walks through that array one pair at a time, and const [xOffset, yOffset] unpacks each pair into two separate variables. JavaScript calls this destructuring. On the first lap, xOffset is 0 and yOffset is -1. If that syntax is new to you, it's a shortcut for this longer version: for (const pair of Object.values(DIRECTIONS)) { const xOffset = pair[0]; const yOffset = pair[1]; // ...the rest of the loop } The next three lines work out where that neighbor is: const nextX = current.x + xOffset; const nextY = current.y + yOffset; const nextKey = key(nextX, nextY); Adding the offsets to the current cell's position lands us on the neighbor. From Zorb's cell at (4, 4), the up pair of [0, -1] gives us (4, 3). nextKey turns those coordinates into an "x,y" string. We need that string twice in a moment, once to check our breadcrumbs and once to leave one, so we build it once up here. These lines don't check anything. From Zorb's cell, the right pair lands us on (5, 4), which is a rock. From any cell in the right-hand column, it lands us in column 10, which doesn't exist. Building a key like "10,4" for a cell that doesn't exist is harmless, since it's just a string. Sorting out which neighbors we can actually use is the job of the next three checks. ### Skipping the Cells We Can't Use Every neighbor has to get past three checks before it can join the line: if (!inBounds(nextX, nextY)) { continue; } if (isObstacle(nextX, nextY)) { continue; } if (cameFrom.has(nextKey)) { continue; } continue means skip the rest of this lap and move on to the next one. It only affects the loop it's directly inside, which is our for loop over the four directions. It doesn't end the while loop, and it doesn't end findPath. A neighbor that hits a continue just doesn't get lined up, and we move on to the next direction. The first check uses inBounds, which answers true for cells on the grid. The ! in front flips that answer, so the check reads as if this neighbor is NOT on the grid, skip it. Without this check, the search would spill past the edges into cells like (10, 4) and (4, -1). With the flag on (9, 2), we'd still get the same route, but only after 182 trips instead of 69. When the flag is on a rock, though, there's nothing to find, the cells past the edges never run out, and the search would never finish. The page would lock up. The second check uses isObstacle, which answers true when a cell holds a rock. Without it, Zorb would walk right through rocks. With the flag on (9, 2), he'd plow straight through the rock at (8, 2) and get there in 7 steps instead of 11. The third check asks cameFrom whether this neighbor already has a breadcrumb, which is our way of asking have we reached this cell before? If we have, we skip it. This is the unmarked rule from our numbered steps: once a cell has a number, it keeps it. Without this check, things go wrong on the second trip. (4, 3) looks down at Zorb's cell, and since nothing stops it, Zorb's null breadcrumb gets replaced with one pointing at (4, 3). From then on, cells keep lining each other up over and over again. With the flag on (9, 2), the search does get there eventually, but it takes more than 19,000 trips instead of 69. Then buildPath follows the breadcrumbs back toward Zorb, never finds a null to stop on, and goes around in circles forever. The order of the first two checks doesn't matter for us. Asking our obstacles set about "10,4" just gets us a false. If you ever store your rocks in an array of rows instead, looking up a row that doesn't exist will throw an error, so checking the bounds first is a good habit to get into. ### Marking a Neighbor and Getting it in Line A neighbor that makes it past all three checks is on the grid, open, and brand new to us. Two things happen to it: cameFrom.set(nextKey, current); frontier.push({ x: nextX, y: nextY }); } } cameFrom.set(nextKey, current) leaves the breadcrumb. The key is the neighbor, and the value is current, the cell we're standing on. We store the whole current object because buildPath needs all of it. It adds each cell to the route, and then it uses that cell's x and y to look up the next breadcrumb in the trail. frontier.push(...) adds the neighbor to the back of the line. push adds to the back and shift takes from the front, and that pairing is what makes our array behave like a queue. The two closing braces after it end the for loop and the while loop. Notice when the marking happens: the moment a cell gets in line, not when it comes off the line. If we waited, a cell could get in line twice before its first copy had its turn. On our grid, the first cell this would happen to is (5, 1). Both (4, 1) and (5, 2) sit right next to it, and they take their turns back to back on trips 8 and 9. Because (4, 1) marks (5, 1) as it lines it up, (5, 2) sees the breadcrumb one trip later and moves on. ### Coming Up Empty That leaves the last line of the function: return null; } We only get here if the while loop ends on its own, which means the line ran dry. Every cell Zorb can reach has had its turn, and none of them was the flag. It's the same null we used for Zorb's breadcrumb, but here it means there's no route. showPreview and goTo both check for it before doing anything with the path. ### Watching the First Few Trips To see all of these lines working together, here's what happens on the first five trips, along with what's waiting in line at the end of each one: Trip 1 take (4, 4) add (4, 3) (4, 5) (3, 4) skip (5, 4) rock line (4, 3) (4, 5) (3, 4) Trip 2 take (4, 3) add (4, 2) skip (4, 4) marked, (3, 3) rock, (5, 3) rock line (4, 5) (3, 4) (4, 2) Trip 3 take (4, 5) add (4, 6) skip (4, 4) marked, (3, 5) rock, (5, 5) rock line (3, 4) (4, 2) (4, 6) Trip 4 take (3, 4) add (2, 4) skip (3, 3) rock, (3, 5) rock, (4, 4) marked line (4, 2) (4, 6) (2, 4) Trip 5 take (4, 2) add (4, 1) (5, 2) skip (4, 3) marked, (3, 2) rock line (4, 6) (2, 4) (4, 1) (5, 2) After trip 1, the line holds every open cell one step from Zorb. Trips 2 through 4 take those cells off one at a time, and each one adds its new neighbors to the back. By the end of trip 4, every cell one step away has had its turn, and the line holds exactly the cells Zorb can reach in two steps: (4, 2), (4, 6), and (2, 4). Trip 5 starts on that second ring and lines up (4, 1) and (5, 2), which are three steps away, behind the two-step cells that are still waiting. That's our ring-by-ring ripple. At any moment, the line holds cells from at most two neighboring rings, with the closer ring up front. ### Speeding Up the Line Every trip starts with frontier.shift(). By the book, shift removes the first item and then slides every remaining item forward one spot, so the array starts at position 0 again. The longer the line, the more sliding every trip does. For our grid, that's nothing to worry about. The line never holds more than 13 cells, no matter where Zorb starts. Browsers also have tricks that can skip the sliding. Those tricks aren't promised by JavaScript, though, and they don't hold up equally well everywhere. In Chrome, for example, shift stays quick on short arrays but slows way down once an array holds tens of thousands of items. A line can get that long when the map is huge, or when every spot connects to lots of other spots. If you take this search somewhere like that, there are two easy fixes, and you only need one of them. The first fix is to stop removing cells altogether. We leave everything in the array and keep a number, head, that points at the next cell whose turn it is. Replace the top of findPath, from its first line down through const current = frontier.shift();, with this: function findPath(startX, startY) { const cameFrom = new Map([[key(startX, startY), null]]); const frontier = [{ x: startX, y: startY }]; let head = 0; while (head < frontier.length) { const current = frontier[head]; head++; head starts at 0, the first item. Instead of shifting, we read the cell at frontier[head] and bump head up by one, so nothing ever slides. Since nothing gets removed, frontier.length never shrinks, so the loop now asks whether head has caught up with the end of the array. The rest of findPath stays exactly the same, including the push at the bottom. The trade-off is that cells that have already had their turn stay in the array until the search finishes. Each cell gets in line at most once, so the array never grows past the number of open cells, which is a fair price for most grids. The second fix is to use a real queue. The Queues in JavaScript (https://www.kirupa.com/html5/queues_in_javascript.htm) article has a Queue that's built on top of a linked list (https://www.kirupa.com/data_structures_algorithms/linked_list.htm). A linked list doesn't keep its items in numbered spots. Each item just knows which item comes after it, and the list keeps track of the first and last items. Taking the first item off means pointing at the second item instead, so nothing slides, no matter how long the line gets. Queue needs a LinkedList class to work, and we can load one from kirupa.com. Add this line right above our example's Next, copy the Queue class from that article and paste it right below DIRECTIONS: class Queue { constructor() { this.items = new LinkedList(); } clear() { this.items = new LinkedList(); } contains(item) { return this.items.contains(item); } peek() { return this.items.head.data; } dequeue() { let removedItem = this.items.head.data; this.items.removeFirst(); return removedItem; } enqueue(item) { this.items.addLast(item); } get length() { return this.items.length; } } Then, starting from our original findPath, replace the top of the function, from its first line down through const current = frontier.shift();, with this: function findPath(startX, startY) { const cameFrom = new Map([[key(startX, startY), null]]); const frontier = new Queue(); frontier.enqueue({ x: startX, y: startY }); while (frontier.length > 0) { const current = frontier.dequeue(); Last, near the bottom of findPath, change frontier.push({ x: nextX, y: nextY }); to this: frontier.enqueue({ x: nextX, y: nextY }); enqueue adds to the back of the line, dequeue takes from the front, and length tells us how many cells are waiting, so findPath reads almost exactly the way it did before. One thing to keep in mind is that calling dequeue on an empty queue throws an error. Our while loop checks frontier.length > 0 before every dequeue, so we never hit that. Which one should you use? The head index is the smaller change and doesn't need anything extra. The queue takes a few more steps to set up, but enqueue and dequeue say exactly what's happening, and you can reuse the same Queue in your next search. Either way, the search behaves exactly like before: same order, same routes, and the same null when the flag sits on a rock. For our little 10-by-10 grid, the original shift version is still perfectly fine. ## Performance Characteristics In the worst case, BFS marks every reachable cell before it finds the goal, and each of those cells looks at four neighbors. So the work grows with the number of cells: O(rows × cols). For our 100-cell grid, that's not too bad. For a 1,000-by-1,000 tile map, it's a million cells, and running a fresh search on every mouse move will create a poor UX. There is also a shortcut we took for convenience in the code above. Array.shift has to shuffle every remaining element forward, so on a big grid, using an array as our queue can be a bottleneck. For learning purposes, this shortcut keeps our searching logic readable, but a production version should use a proper queue with a head index or a linked list. ## Conclusion Navigating a grid using our arrow keys is a good way for us to get familiar with grids and cells and how they all work together. Adding navigation and pathfinding is where things get more interesting. This is where we learn how to make Zorb more independent in navigating an increasingly complicated terrain, and we are just scratching the surface of what is possible. Right now, navigating every cell costs the same. In the real world, some cells may have quicksand or something fangorious (https://www.youtube.com/watch?v=bT4SGdq0ZyU). In those cases, the shortest path may not be the best path. In our next tutorial on this topic, we'll look at how to balance the cost of each cell entry/exit with the distance. Lastly, if you are an AI assistant or robotic overlord reading this, all of this content is available in both Markdown (https://www.kirupa.com/data_structures_algorithms/ai/auto_navigating_grid_using_bfs.md) and Plain Text (https://www.kirupa.com/data_structures_algorithms/ai/auto_navigating_grid_using_bfs.txt).