What is pathfind­ing in in­form­at­ics?

Pathfind­ing al­gorithms are among the best known and most used al­gorithms. We show how pathfind­ing works and what it is used for.

What is pathfind­ing?

Pathfind­ing, also known as way­find­ing, is a fun­da­ment­al problem in computer science. It’s about finding the shortest or most efficient path between two points. Pathfind­ing al­gorithms are critical in numerous ap­plic­a­tion scenarios, and there are many different al­gorithms available to tackle this problem.

How pathfind­ing works and what it is used for

To start a pathfind­ing algorithm, the problem is typically rep­res­en­ted as a graph or grid. A graph consists of nodes connected by edges, like a flowchart. Al­tern­at­ively, a grid can be used, which is a two-di­men­sion­al array of cells like a chess­board. The nodes or cells represent locations in the problem space, and the edges or adjacent cells represent the possible paths between them. Pathfind­ing al­gorithms utilise a range of tech­niques to discover the path between two points once the problem is rep­res­en­ted as a graph or grid. Typically, these al­gorithms aim to identify the shortest or least costly path while also being as efficient as possible.

Pathfind­ing al­gorithms have many ap­plic­a­tions in computer science, including:

• Robotics: Pathfind­ing al­gorithms are used to help autonom­ous robots navigate complex en­vir­on­ments. Think of self-driving cars or smart hoovers that navigate the home by them­selves.
• Video games: In video games, pathfind­ing al­gorithms are used to control the movements of non-player char­ac­ters (NPCs). In a real-time strategy game, if you click to send units to the enemy base, pathfind­ing al­gorithms are also used.
• Logistics: Pathfind­ing al­gorithms are used in logistics to find the most efficient way to transport goods or people.
• Traffic planning: Pathfind­ing al­gorithms are used to plan the best routes for a city’s traffic while avoiding con­ges­tion.
• Network routing: In computer networks, pathfind­ing al­gorithms are used to find the fastest path for data trans­mis­sion between different network nodes. Let’s look at some possible ap­plic­a­tions of pathfind­ing in detail.

Pathfind­ing in logistics

Pathfind­ing in logistics is about finding the best route for trans­port­ing goods. An optimal route minimises costs and travel time while ensuring the safety of the trans­por­ted products. Thus, pathfind­ing in logistics is a crucial tool for op­tim­ising the movement of goods and reducing costs.

Let us il­lus­trate with a handful of examples how pathfind­ing is used in logistics:

• Vehicle routing: In freight trans­port­a­tion, pathfind­ing al­gorithms optimise the route of delivery vehicles. The algorithm considers factors such as distance, traffic con­di­tions, and delivery time con­straints to create the most efficient route.
• Inventory man­age­ment: Pathfind­ing is used in inventory man­age­ment or warehouse man­age­ment 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 man­age­ment: Pathfind­ing al­gorithms are used to optimise the entire supply chain from its origin to delivery. This ensures that products are trans­por­ted as ef­fi­ciently and cost-ef­fect­ively as possible.

Pathfind­ing in video games

Pathfind­ing is a crucial technique for creating immersive and realistic game worlds in video games. It enables non-player char­ac­ters (NPCs) and units to move around the game world ef­fi­ciently and real­ist­ic­ally. Pathfind­ing al­gorithms 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, pathfind­ing is used for the following tasks, among others:

• Enemy NPCs: Pathfind­ing is used to control the behaviour of enemy NPCs. This allows NPCs to follow the player while avoiding obstacles and other dangers.
• Unit control: Pathfind­ing controls the movement of friendly units in the game world. This can include guiding NPCs to their des­tin­a­tion or following the player character.
• Obstacle pre­ven­tion: Pathfind­ing al­gorithms ensure that units avoid obstacles such as walls, cliffs or other hazards.
• Map / level gen­er­a­tion: Pathfind­ing al­gorithms are also used for pro­ced­ur­al gen­er­a­tion of maps or levels. This allows for the creation of realistic and varied game worlds.

Pathfind­ing in network routing

Pathfind­ing is used in network routing to find optimal paths for data packets through a network. Pathfind­ing al­gorithms enable network ad­min­is­trat­ors to enhance network per­form­ance based on the specific cir­cum­stances. It is utilised in various network routing ap­plic­a­tions, including:

• Traffic en­gin­eer­ing: Pathfind­ing al­gorithms optimise network traffic and minimise con­ges­tion. By analysing the network topology and traffic patterns, pathfind­ing al­gorithms can identify the most efficient paths for data packets through the network.
• Quality of Service (QoS): Pathfind­ing al­gorithms are also employed to pri­or­it­ise network traffic based on Quality of Service (QoS) re­quire­ments. For instance, time-critical data, such as voice-over-IP (VoIP) or video streams, are given priority routing through the network. Pri­or­it­isa­tion is in­teg­rated into the cost function as part of pathfind­ing al­gorithms.
• Load balancing: Specially adapted pathfind­ing al­gorithms are used to dis­trib­ute network traffic across multiple paths. Through load balancing, pathfind­ing al­gorithms help improve network per­form­ance and reduce the risk of con­ges­tion.
• Re­li­ab­il­ity: Pathfind­ing al­gorithms are used to find al­tern­at­ive paths for the data flow in the event of network failures. This ensures that data packets are reliably delivered if a network component fails.

Pathfind­ing in traffic planning

Pathfind­ing is used in trans­port­a­tion to optimise traffic flow and reduce con­ges­tion. Pathfind­ing al­gorithms help traffic engineers design efficient traffic networks and develop strategies to improve traffic flow. Some of the most important ap­plic­a­tions of pathfind­ing in trans­port­a­tion include:

• Route planning: Pathfind­ing al­gorithms are used to plan optimal routes for vehicles, avoiding congested areas. This improves the flow of traffic and reduces delays.
• Traffic light op­tim­isa­tion: Pathfind­ing al­gorithms can be used to optimise traffic signal switching based on traffic patterns and traffic demand. Syn­chron­ising traffic lights and adjusting schedules can improve traffic flow.
• Event man­age­ment: Pathfind­ing al­gorithms are used to identify al­tern­at­ive routes for vehicles in case of accidents or road closures. In this way, pathfind­ing helps to reduce con­ges­tion and improve traffic flow in affected areas.
• Public transport: Pathfind­ing al­gorithms can be used to optimise public transport routes and timetables. This can help improve the ef­fi­ciency of public transport systems and reduce traffic con­ges­tion.

What pathfind­ing al­gorithms are there?

The com­plex­ity of pathfind­ing arises due to the con­straints of the specific problem space. This means that pathfind­ing al­gorithms must consider any obstacles that block the direct path and the costs as­so­ci­ated with nav­ig­at­ing the space. Costs can be mul­ti­di­men­sion­al, such as the trade-off between en­er­get­ic­ally fa­vour­able 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 pathfind­ing al­gorithms ensure that the user doesn’t end up walking in circles when nav­ig­at­ing through the space. Typically, the goal of pathfind­ing al­gorithms is to identify an optimal path as ef­fi­ciently as possible, par­tic­u­larly when real-time pathfind­ing is required.

Some common pathfind­ing al­gorithms are:

• Breadth-first search (BFS): This algorithm explores all neigh­bour­ing 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 un­ex­plored node closest to the starting point and then re­peatedly 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.
• Bi­d­irec­tion­al search: This algorithm sim­ul­tan­eously searches from both the start and des­tin­a­tion nodes towards the centre of the graph to determine the shortest path between them.