# Web DevelopmentA* Pathfinding in React.js   ###### Stanislav Naborshchikov

Channel Marketing Manager

Share the article

## Introduction

Welcome to the algorithm world. I would like to introduce you, in my opinion, to one of the most popular pathfinding algorithms in the IT sector which is A*. In this article, we will go through the concept of it and we will end up with a simple implementation in JS and pure React.js. Before we start I must admit that wasn’t a clever choice for showing this implementation because making a rendering engine in React.js for presentation purposes and passing every information via props isn’t the most comfortable thing to do, however, that was my foundation so I couldn't skip it 🤷‍♂. With the next implementation, I would go with simple HTML, CSS, JS and canvas (or maybe C++, it’s still a better choice for presentation stuff than React.js 😄) One more thing, treat this article as something that may motivate you to dive into algorithms like binary search, linear search or recursive algorithm. If you are looking for a solid chunk of knowledge, here are some:

There you will find explained A* in more detail.

Pathfinding is a great thing in computer science. We are close to it every day (Or you might not if you don’t go outside) for instance in google maps. Thanks to our intuition we do not notice it. Eventually, we will find a way how to move from place A to place B by enough walking in circles 🏃. From a mathematical point of view, this is not that simple. We just can’t tell the program to move around because it will just move around and nothing more. We need to tell it about the consequences of its movement (great explanation of the idea of algorithms).

In software development, we have a bunch of different pathfinding algorithms (I might be wrong. Maybe there are only a few 🤷‍♂) which will help us to find the optimal path. For instance, we have Dijkstras algorithm or breadth first search or simple greedy best first search. One of them is A* which is, in my opinion, the most popular because if you type https://www.google.com/search?q=pathfinding then you will notice that most of the results are connected to A*. One of the creators is Bertram Raphael from Stanford Research Institute. To prove my wisdom 🤔 I have done quick research in google trends and these are my results: As you can see A* overcomes other algorithms without any sweat. If you are interested why is that, I won’t answer it because I don’t know, however, if you have this kind of knowledge you can leave a comment. I will appreciate it 🙂 .

Usage of pathfinding algorithms like A* is pretty wide. Starting from obvious searching shortest path issues and ending on NLP programs. Pathfinding issues are just an abstraction that can be found in various areas. Obstacles might have different nature than simple lying stones on the road. Understanding data here is a key and right implementation of simple eq. A* algorithm can solve a lot. Of course, now we live in an era of machine learning algorithms, however, in most cases, artificial intelligence models are not as efficient in terms of path search algorithm as algorithms mentioned earlier.

## Basics fundaments

OK! Let’s dive into the fundaments of A*. Basically from Wikipedia:

A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.).

The keywords here are node, starting node, goal, and node having the smallest cost. As I have mentioned understanding data is vital so node, starting node, and goal are related to this point. Part of the smallest cost is strictly connected with A* but we will get to that.

I don’t want to extend this article if I can link you to something for an explanation so a good example of understanding data is here (I have linked it earlier). Apart from what’s written there, I can only add data that should represent a graph through which we can move by choosing the node with the smallest cost. It doesn’t have to be a visual representation like a labyrinth. It can be anything. “Paths” in 2D/3D labyrinths are easy and most sufficient for explanation pathfinding algorithms.

After understanding the data we can move from current node to the smallest actual cost node. A* algorithm makes its movement based on this value and makes it the shortest path to destination node. This value is calculated with this formula: As you can see everything here depends on 2 things g(n) and h(n)

• g(n) is a function that calculates a cost from the current point to the nearest neighbor plus the g cost of the current position

• h(n) is our heuristic function that calculates a cost from the current point to the end.

G(n) can vary depends on what you want to achieve. In my example, I will be a simple Pythagorean equation (square root value) plus g(n) cost value of the current tile. My example will be based on tiles that are squares, that’s why the Pythagorean theorem is good for me.

H(n) is a heuristic value an also varies on your needs. My approach was the same as in g(n) function. I have used the Pythagorean theorem for getting this value. It will work. Maybe not perfectly but it will. On the other hand, in the related articles, we can listen to more clever guys and proceed here with:

• Manhattan distance

• Diagonal distance

• Euclidean distance

• Euclidean distance, squared

• Come up with something else like multiple goals or breaking ties

It really depends on your project and what you would like to achieve in your search algorithm.

For better understanding step by step here is the simple animation of A*: Legend:

1. The black square is our player

2. The pink square is our goal

3. Green squares are our neighbours

4. Yellow squares are our road

5. Gray square is excluded square during current choosing

6. The number inside squares represents the F(n) value

Numbers are taken randomly but the main purpose is to take a square with the lowest F(n). Also, as you can see the numbers inside squares are updated. It’s because all current neighbours are taken into account. Value is changing mainly because of G(n) because the result depends on the position of the black square.

## Further explanation

A* can be faster or slower. Depends on the number of neighbours. Even in our example above we can make it a little bit faster by excluding previously appeared neighbours. We wouldn't have those changing numbers inside tiles. We would end up with a kind of brute force logic. I would be faster in choosing neighbour, however, might not be faster in finding the whole road. Again, it depends.

BTW For the purpsose of this article I have this animation above in remotion . Nice tool and simple in use 🤓

`````` A_Star(start, goal, currentPos) {
gScore = func which calculate g score
hScore = func which calculate h score
fScore = hScore(start) + gScore(start)

playerPosition = start

open = []

getNeighbours = (position) = {
for each neighbour of position {
gScore = gScore(neighbour) + currentPos.gScore
hScore = hScore(neighbour)
fScore = gScore + hScore
}
return neighbours
}

while open is not empty {

if player == goal
break

neighbours = getNeighbours(currentPos)
open = [...open, ...neighbours] // update list of available tiles to check

tileToMove = getMinFScore(open) // get min fScore from available tiles

open.remove(tileToMove) // remove chosen tile from available tiles

player = tileToMove // move player
}

return false
}``````

Example and further explanation. Ok, we have gone through the basics.Ok, we have gone through the basics. Now I can share how I have done it in React.js . We need a Map on which our Player can move and reach the ending point from starting point with proper obstacle avoidance. Let’s begin with hooks. Here is our player:

``````import { useState, useEffect } from 'react';import { letCalculateLowerPosition, letCalculateHigherPosition } from '../utils/evaluateCalculations';
export const usePlayer = (startingPoint) => {
const extendUserData = {
gCost: 0,
parent: null,
}
const [player, setPosition] = useState({
...startingPoint,
...extendUserData,
});
useEffect(() => {
setPosition((prevValue) => ({
...prevValue,
x: startingPoint.x,
y: startingPoint.y,
}))
}, [startingPoint.x, startingPoint.y])

const move = (position) => {
setPosition(position);
}
return {
player,
setPosition,
move,
extendUserData,
}
}``````

We have here the initial setup for player’s position and utility function which is move. Other data is being passed for easier management.

Let’s move on to blockers:

``````import { useState } from 'react'
import { maps } from '../constants/maps';

export const useBlockers = ({ dimension }) => {
const [blockers, setBlockers] = useState([]);
// blockers set randomly
const calculateBlockers = () => {
const calculate = () => {
const coordinate = Math.round(Math.random() * dimension)
if (coordinate !== 0)
return coordinate - 1;
return coordinate
}
return new Array(dimension * 8).fill(0).map(() => ({
x: calculate(),
y: calculate(),
}))
.filter(({ x, y }) => (x !== 0 && y !== 0))
.filter(({ x, y }) => (x !== dimension - 1 && y !== dimension - 1))
}

const setBlockersBasedOnGeneratedMap = (mapName) => {
const blockersInMap = [];
maps[mapName].reverse().forEach((row, yIndex) => {
row.forEach((tile, xIndex) => {
if(tile === '-') return;
blockersInMap.push({ x: yIndex, y: xIndex })
})
})
setBlockers(blockersInMap)
}

const setBlockersOnMap = () => {
setBlockers(calculateBlockers());
}

const setTileAsBlocker = (tile) => {
setBlockers((prevState) => prevState.concat(tile));
}

return {
setBlockersOnMap, // setting blockers randomly
blockers, // list of set blockers
setTileAsBlocker, // utility function for setting blocker in place of tile (eq. with mouse, not particulary vital)
setBlockersBasedOnGeneratedMap // setting blockers based on prepared schemes, I will show them later
}
}``````

I don’t want to go into details in this file because the main responsibility is just setting blockers on the Map and that’s all.

Simple start and goal hook:

``````import { useState } from 'react';
import { START, GOAL } from '../constants';

export const useGoalAndStart = () => {
const [start, setStart] = useState(START);
const [isStartSetting, setIsStartSetting] = useState(false);
const [goal, setGoal] = useState(GOAL);
const [isGoalSetting, setIsGoalSetting] = useState(false);

return {
start,
setStart,
goal,
setGoal,
isStartSetting,
isGoalSetting,
setIsStartSetting, // function for enabling setting START point
setIsGoalSetting // function for enabling setting GOAL point
}
}``````

I guess this file is self-explanatory 🤓

Ok! Before showing you the rest of the hooks let me present my Map elements:

Simple Tile.js:

``````import React, { useMemo } from 'react'
import './Tile.css'

export const MemoTile = ({ item, isBlocker, isOpen, isRoad, isGoal, isPath, isUserPosition, setTileAsBlocker, isSetting, isGoalSetting, isStartSetting, onSetStart, onSetGoal }) => {
const classes = isBlocker ? 'block_tile' : 'tile';
const isOpenClass = isOpen ? 'is_open' : '';
const isGoalClass = isGoal ? 'is_goal' : '';
const isUserPositionClass = isUserPosition ? 'is_user' : '';
const isPathClass = isPath ? 'is_path' : '';
const memoIsGoalClass = useMemo(() => isGoalClass, [isGoalClass]);
const memoIsOpenClass = useMemo(() => isOpenClass, [isOpenClass]);

const resolveClickBehaviour = () => {
if(isStartSetting) {
onSetStart({ x: item.x, y: item.y })
}
if(isGoalSetting) {
onSetGoal({ x: item.x, y: item.y })
}
if(isSetting) {
setTileAsBlocker({ x: item.x, y: item.y })
}
return false
}

return <div
onClick={resolveClickBehaviour}
className={`size \${classes} \${memoIsOpenClass} \${memoIsRoadClass} \${memoIsGoalClass} \${isUserPositionClass} \${isPathClass}`}
/>
};

export const Tile = React.memo(MemoTile);``````

At the first glance, you might be surprised because of useMemo. React is not designed for game engines. Tile is the smallest element of the map and every calculation made during pathfinding can push Tile to rerender. As you might imagine, when a lot of elements rerender a lot constantly and it can cause performance issues. That’s why React.memo and useMemo are being used to prevent that. The next things here are simple classes to determine visually what’s going on. I will explain some of them:

• isOpenClass: class to visual open tile — neighbours (or omitted neighbors in the previous choosing) which can be picked.

• isGoalClass: class for goal representation

• isRoadClass: class for road visualization — when the user hasn’t reached the goal we show the road on the map

• isPathClass: class for the finished road — after reaching the end we can construct a final road from start to end

• isUserPositionClass: class for determining where our user is 🌝

Row.js

``````import React from 'react';
import { Tile } from './Tile';
import './Row.css'

const MemoRow = ({ x, columns, blockers, open, road, goal, path, userPosition, setTileAsBlocker, isSetting, isGoalSetting, isStartSetting, onSetGoal, onSetStart }) => {
const columnsToRender = new Array(columns).fill(x);

const isOpen = (y) => {
return open.length > 0 && open.find((openTile) => openTile.y === y);
}
const isBlocker = (y) => {
return blockers.length > 0 && blockers.find((blocker) => blocker.y === y);
}
const isRoad = (y) => {
}
const isGoal = (y) => {
return goal && goal.y === y;
}

const isPath = (y) => {
return path.length > 0 && path.find((pathTile) => pathTile.y === y);
}

const isUserPosition = (x, y) => {
return userPosition.x === x && userPosition.y === y;
}

return(
<div className="row">
{columnsToRender
.map((item, index) => ({ x: item, y: index, ...item }))
.map((item, index) => {
return <Tile
...passing all props and func to tile
/>
})}
</div>
)
}

export const Row = React.memo(MemoRow);``````

I have simplified this file by removing passing props and functions declarations in `<Tile />`. All necessary actions take place in Tile. I was thinking about context to omit props passing, however, it’s the only place where such props passing occurs. Row, in general, just render Tiles in a row.

And finally Map.js:

``````import React from 'react';
import {Row} from "./Row";
import './Map.css';

export const Map = ({ columns, rows, blockers, open, road, goal, path, userPosition, setTileAsBlocker, isSetting, isGoalSetting, isStartSetting, onSetGoal, onSetStart }) => {
const rowsToRender = new Array(rows).fill(0);

const getRowValue = (tiles, index) => {
return tiles.filter((tile) => tile.x === index)
}

return(
<div className="map">
{rowsToRender.map(
(_, index) => {
return(
<Row
...props passing
/>
)
}
).reverse()
}
</div>
)
}``````

Map.js is responsible for Row rendering and that’s all.

Right. We have our Map, User, Blockers, Start and Goal. We can move on to the core which is calculations.

``````const gCost = (tilePosition, playerPosition) => {
const width = tilePosition.x - playerPosition.x;
const height = tilePosition.y - playerPosition.y;
return Math.sqrt(width*width + height*height);
}

const hCost = (tilePosition, goal) => {
const width = goal.x - tilePosition.x;
const height = goal.y - tilePosition.y;
return Math.sqrt(width*width + height*height);
}

export const addCosts = (item, goal, player) => {
if(!item) return undefined;
const g_cost = gCost(item, player) + player.gCost;
const h_cost = hCost(item, goal);
const cost = g_cost + h_cost;
return {
x: item.x,
y: item.y,
gCost: g_cost,
hCost: h_cost,
cost: cost,
parent: player,
}
}``````

Here we have some straightforward things. As I have said earlier, my foundation was to use sole React.js. Because of that:

• All structures are based on an array because it was simpler for me to manage that with React data communication based on props

• Most of the results in calculations are updated in Tiles via `.map`or `.concat`. In some places, I’m using `.filter`.

• Every change is constructed by returning a new value instead of mutating the existing one.

Here addCosts is the most vital. The usage of it I will show you in a minute, but the purpose is clear. This adds costs to chosen source node and its neighboring node.

Having this, now we need to have function which add those costs to proper tiles:

``````export const doCalculations = (player, open, goal) => {
checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: player.y }),
goal,
player
)
checkIfCanReturn({ x: letCalculateHigherPosition(player.x), y: player.y }),
goal,
player
);
checkIfCanReturn({ x: player.x, y: letCalculateHigherPosition(player.y) }),
goal,
player
);
checkIfCanReturn({ x: player.x, y: letCalculateLowerPosition(player.y) }),
goal,
player
);
checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: letCalculateHigherPosition(player.y) }),
goal,
player
);
checkIfCanReturn({ x: letCalculateHigherPosition(player.x), y: letCalculateHigherPosition(player.y) }),
goal,
player
);
checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: letCalculateLowerPosition(player.y) }),
goal,
player
);
checkIfCanReturn({ x: letCalculateHigherPosition(player.x), y: letCalculateLowerPosition(player.y) }),
goal,
player
);
return {
leftTile: leftTile && check(leftTile),
rightTile: rightTile && check(rightTile),
topTile: topTile && check(topTile),
bottomTile: bottomTile && check(bottomTile),
topLeftTile: topLeftTile && check(topLeftTile),
topRightTile: topRightTile && check(topRightTile),
bottomLeftTile: bottomLeftTile && check(bottomLeftTile),
bottomRightTile: bottomRightTile && check(bottomRightTile),
neighbours: {
leftTile,
rightTile,
topTile,
bottomTile,
topLeftTile,
topRightTile,
bottomLeftTile,
bottomRightTile,
}
}
}``````

It can look massive but is relatively simple. This function just takes the position of the user and adds costs to its neighbours. One detail here is that sometimes our neighbor does not exist. This situation appears when:

• tile is outside the map

• tile is a blocker

That’s why `addCosts` can return `undefined` and this is a check condition for later operations.

## Last step

Ok, we have almost done, the last step is to aggregate all logic in one place. For this purpose, I have created a hook called `useRoad.js` . I do not want to paste all code written in this file. I will be focused on the main one. If you want to look at the whole project, at the very bottom of this article I have posted link to the repository 🙂 .

Here is our code:

``````import { useState, useEffect } from 'react';
...

export const useRoad = (goal, player, blockers, count, move, withSkipping, withNeighbourEvaluation) => {
const [path, setPath] = useState([]);

// Initialization - initial tiles
const {
leftTile,
rightTile,
topTile,
bottomTile,
topLeftTile,
topRightTile,
bottomLeftTile,
bottomRightTile,
} = doCalculations(player, [], goal)
const uniques = removeUndefined([
leftTile,
rightTile,
topTile,
bottomTile,
topLeftTile,
topRightTile,
bottomLeftTile,
bottomRightTile,
]);

const [neighbours, setCurrentNeighbours] = useState(evaluateTilesFromOpen(uniques, road));
const [open, setOpen] = useState(evaluateTilesFromOpen(uniques, road));
const isGoalReached = (position) => position && position.x === goal.x && position.y === goal.y
// update neighbours` calculations
useEffect(() => {
const {
leftTile,
rightTile,
topTile,
bottomTile,
topLeftTile,
topRightTile,
bottomLeftTile,
bottomRightTile,
neighbours,
} = doCalculations(player, open, goal)
const newUniques = removeUndefined([
leftTile,
rightTile,
topTile,
bottomTile,
topLeftTile,
topRightTile,
bottomLeftTile,
bottomRightTile,
])
const newNeighbours = removeUndefined([
neighbours.leftTile,
neighbours.rightTile,
neighbours.bottomTile,
neighbours.topTile,
neighbours.topLeftTile,
neighbours.topRightTile,
neighbours.bottomLeftTile,
neighbours.bottomRightTile,
])
const parseData = (uniques, prevState = []) => {
const withoutCurrentPlace = removeCurrentPositionFromOpen(prevState.concat(withoutBlocker), player);
return withoutCurrentPlace
}
setCurrentNeighbours(parseData(newNeighbours));
setOpen((prevState) => parseData(newUniques, prevState))
}, [player.x, player.y])

...

return {
open,
path,
setFinalPath,
isGoalReached,
clearAll,
}
}``````

Everything takes place in useEffect . As dependencies and start state I have used the player’s position ( player.x and player.y ) which is a start node. If these values are changed then calculations occur again. Working in the `useEffect` scope wasn’t comfortable, however, that was the only way to have everything in sync (players movement, neighbours changes, and cost calculations and recalculations). A short explanation of what’s going on here: `doCalculations`gives us all tiles with all costs `removeUndefined`removes unwanted tiles `parseData`removes tiles like Player, Road or Blockers reason of duplication of `newUniques`and `newNeigbours`is that in the later function I’m using only current neigbours for choosing the lowest cost (brute force). Uniques (open tiles)are used in the normal decision-making process based on estimated cost. Let’s go to the end of it so decision-making (it’s still): `useRoad.js`

• ``````const findLowestCostTile = () => {

if(withNeighbourEvaluation) { // evaluating only neighbour tiles
const neighboursCosts = getMinCostTiles(neighbours);

if(neighboursCosts.min < min) {
if(neighboursCosts.minArray.length > 1) {
return getMinHCostTile(neighboursCosts.minArray);
}
return getMinCostTile(neighbours, neighboursCosts.min);
}
}
// evaluating all open tiles
const { minArray, min } = getMinCostTiles(open);
if(minArray.length > 1) {
return getMinHCostTile(minArray);
}
return getMinCostTile(open, min);
}

useEffect(() => {
const nextTile = findLowestCostTile();
move(nextTile)

}
}, [count])``````

And that’s how it looks like. `findLowestCostTileb`just finds the minimum of all costs and returns it. There is a with `NeighboursEvaluation`that is simple boolean. If `true`then we carry out brute-force mentioned earlier. Ok, so this function returns the best choice. The `move`takes place in another `useEffect`where our dependency is

(I should call it a frame) and this is our changing frames mechanism (great engine 😅). This has been declared at the very top of the structure, in `App.js`:

``````const [count, setCount] = useState(0); // frames
...
const positionRef = useRef(player)

// updating position based on frame (count)
useEffect(() => {
positionRef.current = player;
...
}, [count])
...
const moveByOneTile = () => setCount((prevState) => prevState + 1);
...``````

These lines were enough to force React to rerender and change the User position which is a dependency in the calculation. With `moveByOneTile`we can execute rerender on eq. button click but our goal was to show an animation of reaching the shortest path from the starting point to the destination. That’s why we need an `interval`in `App.js`:

``````const moveToLowestCost = () => {
const handler = setInterval(() => {
if (isGoalReached(positionRef.current)) {
clearInterval(handler);
return
}
moveByOneTile()
}, 5);
}``````

And this is how we reach our A* pathfinding algorithm in React.js and find the shortest route!

Below I’m pasting links to code and demo:

https://github.com/MobileReality/astar

https://mobilereality.github.io/astar/

## Conclusion

In the introduction, I have written that it wasn’t a good idea to make this in React and I guess now you understand why 😅 . Vanilla JS or other programming languages, or some additional library for React or maybe a different data structure would give me more flexibility and more elastic control over all dependencies such as the user’s position, calculations, or frames. Anyway, the target node is reached! Thanks for reading.

Other sources:

https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2

https://qiao.github.io/PathFinding.js/visual/

https://qiao.github.io/PathFinding.js/visual/

## Did you like the article?Find out how we can help you.

CEO of Mobile Reality

## Mobile Reality sp. z o.o.

• Grzybowska 62
• 00-844 Warsaw, Poland
• VAT ID: PL7010559296
• REGON: 363981117