The goal of pathfinding algorithms is to find a path between the desired points. An optimal path is more complex and time consuming to find, which is why some industries, such as the video game industry, can sacrifice optimality for reduced run-time. A grid map can be represented as an image, so techniques used in image processing, such as filtering, may be applied to pathfinding. In this paper we propose a convolution inspired hierarchical pathfinding algorithm that achieved 4% longer paths and 97% shorter runtime than A* on average.
2023 Copyright for this paper by its authors. CEUR
ceur-ws.org
One of the biggest problems with grid maps is path symmetry, where there are multiple equally optimal paths for two given points, as shown in Figure 1. Path symmetry is often a property of uniformcost grid maps, where the order of steps can often be rearranged to form another equally optimal path.
The number of symmetric paths increases with path length, and a pathfinding algorithm, such as A*,
must evaluate all the redundant symmetric paths to find an optimal path. JPS is a pathfinding algorithm
based on elimination of symmetric paths and can run up to 3.5 times faster than A* [
A*
One of the most popular and effective pathfinding algorithms is A* [
Each iteration A* adds a node to current paths, which is determined by current cost of the path and the estimated cost from this node to goal by a heuristic function. The nodes keep track of which node they were reached from, and once the algorithm reaches the goal, it traces back to the start to form a path and terminates.
One of the ways to reduce search time for A* is to have a better heuristic. Standard online heuristics,
such as Manhattan distance, do not consider obstacles and can only estimate an optimistic scenario
without obstacles, which leads to the pathfinding algorithm having to expand many nodes when
encountering obstacles. A heuristic function that can accurately evaluate distance between nodes may
result in the pathfinding algorithm expanding only nodes on the optimal path [
HPA*
Hierarchical Pathfinding A* (HPA*) is a pathfinding algorithm that was developed in 2004, with
the aim of reducing the pathfinding time by sacrificing path optimality [
HPA* algorithm creates an abstraction layer by dividing the map into rectangular parts called
clusters, as marked by the red rectangles in Figure 2. Next, the passage points, shown in green, are
searched between the clusters and added to the graph of the abstraction layer. This algorithm has been
applied to 4-way connected graphs and experimental results have shown up to a 10-fold speedup in
pathfinding and a 1% degradation in path quality compared to the optimal [
( , ) = ∑| − | ( , ) = √∑( − )2 =1 =1
To speed up the computation, square root can be removed from the equation (2). This makes the
heuristic function overestimate the distance to the destination, which results in the pathfinding
algorithm finding paths faster at the cost of no longer guaranteeing optimality [
Convolutional Hierarchical Pathfinding A* is a pathfinding algorithm that utilizes offline preprocessing to construct an abstraction layer, which is used to perform an online search. The abstraction layer is smaller than the original search space, which results in reduced search time. As the name suggests, the process for creating the abstraction layer is based on 2D image convolution, where a sliding window is used to generalize information inside the window.
During preprocessing, a non-square sliding window is used to partition the map into square segments, as shown in Figure 3. If necessary, a map is padded to the required length by copying the nearest pixel of the original image. The shape of the sliding window is derived from the square segment shape and should be one tile longer to allow overlap with neighboring segments.
Within each window, a search is performed to find any valid path along the window, and the purpose of the overlap with neighboring segment is to guarantee, that the neighboring segment can be entered. A clockwise rotated window is also used to perform the same operations and store vertical traversal information. The abstraction layer graph is created by using the segments as nodes, and the traversal information from sliding windows to connect the nodes.
Increasing the segment size will result in a smaller abstraction layer and faster search time, however more information will be lost during preprocessing, which can reduce path optimality. For this paper a segment size of 3x3 was chosen to introduce some data loss and evaluate the effect of it on pathfinding performance.
During phase 1 of online search, an initial path is found in the abstraction layer using A*, which is presented in Figure 4. In phase 2, the nodes of this path are then used as checkpoints and guide the A* algorithm in the real grid. For this to work, a coordinate translation must be performed between abstraction layer path nodes and real grid nodes. The translation method first determines the direction of movement and shifts the translated center point of the target segment towards the origin segment. A valid unoccupied tile is then needed as a goal, which is searched in a predetermined order along the wall of the origin segment.
This method of coordinate translation may reduce path optimality. To reduce errors caused by the coordinate translation, a Pstep parameter is introduced, which defines the interval of checkpoints to be used for pathfinding in the real grid. An example of Pstep effect on final path can be seen in Figure 5, where the resulting final path using Pstep=2 is more optimal than Pstep=1. Increasing Pstep value reduces the checkpoint, and the associated coordinate translation count, which results in fewer opportunities for sub-optimal translations and should on average increase path optimality.
The proposed algorithm was tested against the A* algorithm using various heuristic functions. The same A* implementation was also used for CHPA*, which will make for a fair comparison as there will not be an implementation optimization difference.
The benchmark set of maps and scenarios used for testing were created by Sturtevant [
The effects of CHPA* parameter Pstep were tested and can be seen in Figure 6. As the value of Pstep increases, the path length approaches optimal, however that also causes more nodes to be explored in the real grid, which will increase search time.
We can also see that on average, with Pstep=2 the path length was reduced by 8%, and explored node count by 0.5%. Increasing Pstep further has diminishing returns on path length reduction of 1.5% and 0.5% for Pstep value of 3 and 4 respectively, and increases explored node count by 1.5%. Pstep=2 resulted in the best balance of path quality and search area, so further experiments will be carried out only using this value.
Next, A* and CHPA* algorithms were tested using various heuristic functions, and the results can be seen in Table 1.
A* algorithm with ED and MD heuristics achieved the expected optimal average path length, however MD heuristic explored 33% less tiles and was less computationally expensive, so it led to significantly shorter search times. Using SED heuristic results in 19% longer paths on average, but it explores 80% less nodes than MD, which can be valuable in situations where computation time is strict.
Shifting focus to CHPA*, phase 1 and phase 2 ED heuristic on average explored only 8% more nodes than A* with SED, while having only 4% longer path than optimal. Other CHPA* configurations explored even less nodes, while preserving average path length within 0.2% of other configurations, so choosing a heuristic for CHPA* largely comes down to minimizing explored nodes. Out of the tested configurations with CHPA*, MD heuristic resulted in longest average path, which is still 14% better than A* with SED, and 20% less explored nodes.
A* + ED A* + SED A* + MD
CHPA* + F1-MD F2-MD CHPA* + F1-MD F2-ED
Surprisingly, ED heuristic outperforms MD heuristic on CHPA* average path length by 0.2%, but explored 34% more nodes. MD and ED heuristics both find optimal paths, however those paths may differ and cause different errors in CHPA* coordinate translation, which results in paths of different length in the real map.
The last test was performed to compare average search time between the algorithms, and the results are shown in Table 2.
During this testing, CHPA* achieved only 2% longer path, however on average it took 97% less time to find them, which is the result of heavily reducing search space.
The implemented system includes capability to visualize the pathfinding process, which was used to observe general pathfinding algorithm behavior. In Figure 7 a comparison between A* and CHPA* is shown for a short path, where CHPA* has a smaller exploration footprint than A*. Unfortunately, this system does not visualize the abstraction layer, and the total explored nodes count is very similar to A* in this instance.
a) b) Figure 7 Pathfinding result visualization on 12x12 map. a) A* b) CHPA*. Heuristic – MD, Pstep=1, green – start, blue – goal, orange – path, yellow – checkpoint, red – closed list tile, green – open list tile
Figure 8, Figure 9, and Figure 10 present pathfinding algorithm behavior over a longer distance, and here the benefits of CHPA* can be seen. A* explored most of the map due to the walls obstructing the optimal path, whereas CHPA* performs pathfinding in the compressed abstraction layer, which greatly reduces node expansion.
Main problems of current CHPA* implementation: 1. Only works with 4-way connected graphs. 2. Simplistic coordinate translation logic reduces path quality. 3. Preprocessing edge cases lead to obstacles not being recognized and producing extremely long paths.
In the future, an analysis on the effect of different window sizes for path quality and search times can be performed.
The proposed algorithm finds paths between multiple checkpoints, which could be done in any order, so parallel processing may be applied to speed up the search even further.
In this paper a new pathfinding algorithm is proposed for fast approximate pathfinding called CHPA*. The algorithm utilizes preprocessing, inspired by 2D image convolution, to create an abstraction layer, reduce search space and improve path search times.
Results in worst case show 4% path length degradation on average, more than 80% less explored nodes, and takes 97% less time to find a path compared to A* with an optimal MD heuristic. During our testing, the heuristic function for CHPA* had very low impact on path length (only 0.2% difference), but significantly changed explored node count, so the heuristic choice in most cases will come down to minimizing search space.
The drawbacks of the algorithm are preprocessing edge cases that can lead to not recognizing obstacles in abstraction layer, creating extremely long paths during online search, or even not being able to find a path.