What is pathfinding in informatics?

Pathfinding algorithms are among the best known and most used algorithms. We show how pathfinding works and what it is used for.

What is pathfinding?

Pathfinding, also known as wayfinding, is a fundamental problem in computer science. It’s about finding the shortest or most efficient path between two points. Pathfinding algorithms are critical in numerous application scenarios, and there are many different algorithms available to tackle this problem.

How pathfinding works and what it is used for

To start a pathfinding algorithm, the problem is typically represented as a graph or grid. A graph consists of nodes connected by edges, like a flowchart. Alternatively, a grid can be used, which is a two-dimensional array of cells like a chessboard. The nodes or cells represent locations in the problem space, and the edges or adjacent cells represent the possible paths between them. Pathfinding algorithms utilise a range of techniques to discover the path between two points once the problem is represented as a graph or grid. Typically, these algorithms aim to identify the shortest or least costly path while also being as efficient as possible.

Pathfinding algorithms have many applications in computer science, including:

• Robotics: Pathfinding algorithms are used to help autonomous robots navigate complex environments. Think of self-driving cars or smart hoovers that navigate the home by themselves.
• Video games: In video games, pathfinding algorithms are used to control the movements of non-player characters (NPCs). In a real-time strategy game, if you click to send units to the enemy base, pathfinding algorithms are also used.
• Logistics: Pathfinding algorithms are used in logistics to find the most efficient way to transport goods or people.
• Traffic planning: Pathfinding algorithms are used to plan the best routes for a city’s traffic while avoiding congestion.
• Network routing: In computer networks, pathfinding algorithms are used to find the fastest path for data transmission between different network nodes. Let’s look at some possible applications of pathfinding in detail.

Pathfinding in logistics

Pathfinding in logistics is about finding the best route for transporting goods. An optimal route minimises costs and travel time while ensuring the safety of the transported products. Thus, pathfinding in logistics is a crucial tool for optimising the movement of goods and reducing costs.

Let us illustrate with a handful of examples how pathfinding is used in logistics:

• Vehicle routing: In freight transportation, pathfinding algorithms optimise the route of delivery vehicles. The algorithm considers factors such as distance, traffic conditions, and delivery time constraints to create the most efficient route.
• Inventory management: Pathfinding is used in inventory management or warehouse management to optimise the placement of goods. This ensures that goods are stored in optimal positions. This reduces the effort and time required for the retrieval and delivery of goods.
• Supply chain management: Pathfinding algorithms are used to optimise the entire supply chain from its origin to delivery. This ensures that products are transported as efficiently and cost-effectively as possible.

Pathfinding in video games

Pathfinding is a crucial technique for creating immersive and realistic game worlds in video games. It enables non-player characters (NPCs) and units to move around the game world efficiently and realistically. Pathfinding algorithms are used to identify the optimal path for NPC movements while avoiding obstacles and other hazards to ensure seamless and enjoyable gameplay.

In video games, pathfinding is used for the following tasks, among others:

• Enemy NPCs: Pathfinding is used to control the behaviour of enemy NPCs. This allows NPCs to follow the player while avoiding obstacles and other dangers.
• Unit control: Pathfinding controls the movement of friendly units in the game world. This can include guiding NPCs to their destination or following the player character.
• Obstacle prevention: Pathfinding algorithms ensure that units avoid obstacles such as walls, cliffs or other hazards.
• Map / level generation: Pathfinding algorithms are also used for procedural generation of maps or levels. This allows for the creation of realistic and varied game worlds.

Pathfinding in network routing

Pathfinding is used in network routing to find optimal paths for data packets through a network. Pathfinding algorithms enable network administrators to enhance network performance based on the specific circumstances. It is utilised in various network routing applications, including:

• Traffic engineering: Pathfinding algorithms optimise network traffic and minimise congestion. By analysing the network topology and traffic patterns, pathfinding algorithms can identify the most efficient paths for data packets through the network.
• Quality of Service (QoS): Pathfinding algorithms are also employed to prioritise network traffic based on Quality of Service (QoS) requirements. For instance, time-critical data, such as voice-over-IP (VoIP) or video streams, are given priority routing through the network. Prioritisation is integrated into the cost function as part of pathfinding algorithms.
• Load balancing: Specially adapted pathfinding algorithms are used to distribute network traffic across multiple paths. Through load balancing, pathfinding algorithms help improve network performance and reduce the risk of congestion.
• Reliability: Pathfinding algorithms are used to find alternative paths for the data flow in the event of network failures. This ensures that data packets are reliably delivered if a network component fails.

Pathfinding in traffic planning

Pathfinding is used in transportation to optimise traffic flow and reduce congestion. Pathfinding algorithms help traffic engineers design efficient traffic networks and develop strategies to improve traffic flow. Some of the most important applications of pathfinding in transportation include:

• Route planning: Pathfinding algorithms are used to plan optimal routes for vehicles, avoiding congested areas. This improves the flow of traffic and reduces delays.
• Traffic light optimisation: Pathfinding algorithms can be used to optimise traffic signal switching based on traffic patterns and traffic demand. Synchronising traffic lights and adjusting schedules can improve traffic flow.
• Event management: Pathfinding algorithms are used to identify alternative routes for vehicles in case of accidents or road closures. In this way, pathfinding helps to reduce congestion and improve traffic flow in affected areas.
• Public transport: Pathfinding algorithms can be used to optimise public transport routes and timetables. This can help improve the efficiency of public transport systems and reduce traffic congestion.

What pathfinding algorithms are there?

The complexity of pathfinding arises due to the constraints of the specific problem space. This means that pathfinding algorithms must consider any obstacles that block the direct path and the costs associated with navigating the space. Costs can be multidimensional, such as the trade-off between energetically favourable paths that require longer travel time versus quicker routes that demand more energy. In certain cases, defined points must be included in the path, and pathfinding algorithms ensure that the user doesn’t end up walking in circles when navigating through the space. Typically, the goal of pathfinding algorithms is to identify an optimal path as efficiently as possible, particularly when real-time pathfinding is required.

Some common pathfinding algorithms are:

• Breadth-first search (BFS): This algorithm explores all neighbouring nodes of the starting point before moving to the next level of nodes until the goal is reached.
• Dijkstra algorithm: This algorithm explores the graph by first visiting an unexplored node closest to the starting point and then repeatedly updating the distance of all nodes from the starting point until the goal is reached.
• A* search: This algorithm combines the ideas of BFS and Dijkstra’s algorithm by using a heuristic function to guide the search to the target node.
• Greedy best-first search: This algorithm selects the next node to explore based on a heuristic estimate of the distance to the target node.
• Bidirectional search: This algorithm simultaneously searches from both the start and destination nodes towards the centre of the graph to determine the shortest path between them.