hero image of blog post - A* Pathfinding in React.js

Authors

Marcin Sadowski

Head Of Team

Stanislav Naborshchikov

Channel Marketing Manager

10.09.2021

A* Pathfinding in React.js

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 or pathfinding problems. If you are looking for a solid chunk of knowledge, here are some:

There you will find explained A* in more detail.

* * *

The introduction

Pathfinding is a great thing. We are close to it every day (Or you might not if you don’t go outside). 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 🤷‍♂). 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*. 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.

Basics

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 to the smallest cost node. A* makes its movement basing on this value. 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) 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, 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.

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

Legend:

The black square is our player
The pink square is our goal
Green squares are our neighbours
Yellow squares are our road
Gray square is excluded square during current choosing
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.

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. 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 isRoadClass = isRoad ? 'is_road' : '';
    const isGoalClass = isGoal ? 'is_goal' : '';
    const isUserPositionClass = isUserPosition ? 'is_user' : '';
    const isPathClass = isPath ? 'is_path' : '';
    const memoIsRoadClass = useMemo(() => isRoadClass, [isRoadClass]);
    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) => {
        return road.length > 0 && road.find((roadTile) => roadTile.y === 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 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 tiles.

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

export const doCalculations = (player, open, goal) => {
    const check = (tile) => checkIfAlreadyAddedToOpen(tile, open)
    const leftTile = addCosts(
        checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: player.y }),
        goal,
        player
    )
    const rightTile = addCosts(
        checkIfCanReturn({ x: letCalculateHigherPosition(player.x), y: player.y }),
        goal,
        player
    );
    const topTile = addCosts(
        checkIfCanReturn({ x: player.x, y: letCalculateHigherPosition(player.y) }),
        goal,
        player
    );
    const bottomTile = addCosts(
        checkIfCanReturn({ x: player.x, y: letCalculateLowerPosition(player.y) }),
        goal,
        player
    );
    const topLeftTile = addCosts(
        checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: letCalculateHigherPosition(player.y) }),
        goal,
        player
    );
    const topRightTile = addCosts(
        checkIfCanReturn({ x: letCalculateHigherPosition(player.x), y: letCalculateHigherPosition(player.y) }),
        goal,
        player
    );
    const bottomLeftTile = addCosts(
        checkIfCanReturn({ x: letCalculateLowerPosition(player.x), y: letCalculateLowerPosition(player.y) }),
        goal,
        player
    );
    const bottomRightTile = addCosts(
        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.

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 [road, setRoad] = useState([player]);
    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 uniquesWithoutRoadTiles = evaluateTilesFromOpen(uniques, road.concat(player));
            const withoutBlocker = removeBlockerTilesFromOpen(uniquesWithoutRoadTiles, blockers);
            const withoutCurrentPlace = removeCurrentPositionFromOpen(prevState.concat(withoutBlocker), player);
            return withoutCurrentPlace
        }
        setCurrentNeighbours(parseData(newNeighbours));
        setOpen((prevState) => parseData(newUniques, prevState))
    }, [player.x, player.y])


    ...

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

Everything takes place in useEffect . As dependencies I have used the player’s position ( player.x and player.y ) . 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. 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(() => {
    if(count > 0 && !isGoalReached(road[road.length - 1])) {
        const nextTile = findLowestCostTile();
        move(nextTile)

        setRoad((prevState) => prevState.concat(nextTile))
    }
}, [count])

And that’s how it looks like.

findLowestCostTile

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 path from the starting point to ending point. That’s why we need an

interval

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 in React.js!

Below I’m pasting links to code and demo:

https://github.com/MobileReality/astar

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

Summary

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 would give me more flexibility and more elastic control over all dependencies such as the user’s position, calculations, or frames. Anyway, the goal 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/

Matt Sadowski / CEO of Mobile Reality

Has this article been helpful? Are you interested in consulting your business initiative with us? We would be thrilled to support your tech and business efforts in order to create profitable digital products with you! Just contact us through the contact form or chat on our website our experts are always ready to advise you and help you create an effective mobile or/and web platform for business.