A* Pathfinding in React JS Web Development

Introduction to search algorithms (A*, Dijkstra)

Welcome to the world of pathfinding algorithms! In this article, I want to introduce you to one of the most widely-used and powerful algorithms in the IT sector: the A* algorithm. A* combines aspects of pathfinding algorithm Dijkstra's algorithm and heuristic search to efficiently find the shortest path between nodes. As one of the common pathfinding algorithms, A* is favored for its balance between speed and accuracy in calculating distances. We’ll explore the core concepts behind the A* grid pathfinding graph algorithm and finish with a simple implementation using JavaScript and pure React. Admittedly, React isn't the most intuitive tool for visualizing exploration processes due to the complexity of managing renders and passing information via props. A more straightforward approach using HTML, CSS, JS, and canvas—or even C++—might have been better for demonstrating logistics challenges and heuristic functions. 😄 In A*, priority queues are essential for efficiently selecting the next node to explore based on cost, making it a powerful tool for solving logistics and routing problems. Nonetheless, this example serves as a stepping stone to inspire you to dive deeper into algorithms like binary search, linear search, or recursion. For a more in-depth understanding of A* and its relationship to Dijkstra’s algorithm, check out these resources:

There you will find explained A* in more detail.

About pathfinding algorithms

Pathfinding is a fundamental concept in computer science. We encounter it every day—whether navigating with Google Maps or intuitively determining a path between two points. Our ability to find an optimal path seems effortless, but mathematically, it involves complex considerations to choose good direction like edges, cost paths, priority queue, and the potential outcomes of each step eq. neighboring nodes. In software development, various algorithms support graph traversal and help identify possible paths. Examples include Dijkstra's algorithm, breadth-first search, and greedy best-first search. One of the most popular is the A* algorithm, which efficiently balances heuristics and admissible heuristics. A* was developed by researchers like Bertram Raphael and is widely regarded for its practical effectiveness. To illustrate its popularity, I conducted quick research using Google Trends. As shown in below image, A* clearly outperforms other pathfinding algorithms in terms of search interest.

The applications of pathfinding algorithms like A* extend beyond simple navigation. They are used in robotics, games development, and even NLP. Pathfinding challenges often involve abstract obstacles beyond physical barriers, making a solid understanding of nodes, trees, and steps crucial. A properly implemented A* algorithm can address many of these challenges efficiently. While machine learning and artificial intelligence continue to advance, traditional pathfinding techniques often remain more effective for specific graph traversal and pathfinding tasks. If you have insights into why A* remains dominant, feel free to leave a comment! 😊.

Basics fundaments

OK! Let’s dive into the fundamentals of A*. According to Wikipedia - A* is an informed search algorithm, or a best-first search, meaning 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 with the smallest cost (least distance, shortest time, etc.). This process is essential in the world of path finding. The key elements here are node, starting node, goal, and the node with the smallest cost. As I mentioned earlier, understanding data is crucial in pathfinding. These nodes are connected through a tree, where each decision leads to possible optimal paths. To find the best path, A* relies on calculating costs effectively. After understanding the data structure, we can move from the current node to the next node with the lowest cost. The A* algorithm achieves this by using a heuristic function to estimate the cost and determine the shortest path to the goal node. The calculation follows this formula:

This formula consists of two primary components: g(n) and h(n).

g(n) calculates the cost from the starting node to the current node, plus the cost of moving to the nearest neighbor.
h(n) is the heuristic function, estimating the cost from the current node to the goal node.

The heuristic function plays a critical role in guiding the search. A good heuristic can make A* an efficient pathfinder. In my example, g(n) will use a Pythagorean equation (square root calculation) to measure the distance between square tiles. Similarly, h(n) can vary depending on your needs. For my approach, I used the same Pythagorean calculation for h(n). While this method may not be perfect, it effectively demonstrates the concept. More advanced heuristics include:

Manhattan Distance
Diagonal Distance
Euclidean Distance
Euclidean Distance (Squared)

The choice of heuristic depends on your project and the type of path finding you’re performing. Selecting an admissible heuristic ensures the search algorithm remains efficient and accurate. For a better understanding, here’s a step-by-step animation of A*:

Legend:

The black square represents our player.
The pink square represents our goal.
Green squares are the neighbors currently being considered.
Yellow squares form the chosen path.
Gray squares represent nodes excluded during the current selection.
The numbers inside the squares represent the F(n) value, calculated using g(n) and h(n).

The algorithm always selects the node with the lowest F(n) value, dynamically updating the cost as neighbors are evaluated. This ensures the most efficient path is chosen, illustrating the power of A* as a versatile and reliable pathfinder.

Further explanation of algorithm

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 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 first glance, you might be surprised by the use of useMemo. React is not inherently designed for motion planning or game engines. In this case, a Tile is the smallest element of the map, and during graph search operations, each calculation in the map analysis phase can trigger the Tile to rerender. As you can imagine, if a large number of elements continuously rerender, it can lead to significant performance issues. To mitigate this, React.memo and useMemo are utilized to optimize rendering and maintain completeness in the pathfinding process. These tools help ensure that only the necessary components are updated, preventing unnecessary rerenders. Additionally, simple classes are used to provide a visual understanding of what’s happening during the search process. For instance, as the algorithm progresses, tiles may be added to a queue, reflecting the traversal of nodes in the search graph. This approach allows for a clearer visualization of how the motion planning algorithm processes each step efficiently. Quick legend:

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 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 .mapor .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) => {
    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.

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 [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 within useEffect. As dependencies and the initial state, I used the player’s position (player.x and player.y), representing the starting node. If these values change, recalculations are triggered. Working within the useEffect scope wasn’t particularly comfortable, but it was necessary to ensure everything stayed in sync — including the player’s movement, neighbor updates, and cost recalculations.

Here’s a brief explanation of the process:

doCalculations generates all tiles with their associated costs.
removeUndefined filters out unwanted tiles.
parseData excludes tiles like Player, Road, or Blockers.

Due to the nature of mazes and pathfinding, the duplication of newUniques and newNeighbours is intentional. In subsequent functions, only the current neighbors are evaluated to select the lowest cost path (a brute-force approach). The Uniques set, representing open tiles, is used for standard decision-making processes based on estimated cost.

For efficient navigation in complex environments, techniques like flow field pathfinding help guide the player to the destination node while maintaining manageable space complexity. This ensures that even with dynamic changes in the maze, the algorithm continues to perform reliably.

Finally, the decision-making logic is encapsulated in the useRoad.js file.

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. findLowestCostTilebjust finds the minimum of all costs and returns it. There is a with NeighboursEvaluationthat is simple boolean. If truethen we carry out brute-force mentioned earlier. Ok, so this function returns the best choice. The movetakes place in another useEffectwhere 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 moveByOneTilewe 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 intervalin 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 ReactJS 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/

Frontend Development Insights: Mastering ReactJS and VueJS

Are you fascinated by the evolving landscape of frontend development, particularly in ReactJS and VueJS? At Mobile Reality, we are eager to share our rich expertise and insights in these cutting-edge technologies. Uncover the challenges we navigate, the innovative strategies we employ, and the groundbreaking solutions we deliver in ReactJS and VueJS development. Immerse yourself in our curated selection of articles, each a deep dive into aspects of these powerful frontend frameworks:

Delve into these comprehensive resources to enhance your understanding of ReactJS and VueJS. For any inquiries or if you’re considering a career with us, don't hesitate to contact us or visit our careers page to submit your CV. Join us in shaping the future of front-end development!