# A Topology Map Generation Algorithm for Optimal Path Finding for Image-Based Maps
## 5 Experimental Results  
The map data used in the experiment and building floor plan are shown in Table 2. The map data were used to evaluate complexity with respect to the resolution, number of rooms, number of wall data, and preprocessing time, and were divided into very simple, simple, intermediate, complicated, and very complicated. Figure 11: Visualisation of the generated path over the real world and mini-map. Figure 10: Visualisation of the pathfinding process after the user selects the destination point with Microsoft HoloLens2. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Complexity** & **Map Image** & **Width** & **Height** & **Number of Walls** \\ \hline Very Simple & & & 600 & 400 & 7942 \\ \hline Simple & & & 800 & 800 & 22,151 \\ \hline Intermediate & & & 1000 & 1000 & 23,550 \\ \hline Complicated & & & 1500 & 1200 & 86,743 \\ \hline Very Complicated & & & 2000 & 2000 & 137,931 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Floorplan data. To demonstrate the map generation results of CNAs, we used maze data generated with mazegenerator.net of Alice AB. The experimental environment is the same as that shown in Table 1.  
Table 3 summarises five examples from among the results of applying the methodology described above to the virtual map data. Map Image is an image of the virtual maze map data created on mazegenerator.net. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Index** & **Map Image** & **Topology Map** & **Maze Solution** & **CNA + A\({}^{*}\) algorithm** \\ \hline
1 & & & \\
2 & & & \\
3 & & & \\
4 & & & \\
5 & & & \\
6 & & & \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Experimental results. Topology Map is a topology map image created based on map data. Maze Solution is included to prove that the path can be successfully explored when the pathfinding algorithm (here A*) is applied to the topology map (produced by the CNA). CNA + A* is the result of applying the A* algorithm to the generated topology map. As shown above, CNA + A* obtained the same results in a comparison of the correct solutions. We also tested 100 virtual maze data points, from which a topology map was successfully created. Pathfinding was successfully carried out based on the generated topology map. To verify that generating a topology map through preprocessing aids path discovery, 10 scenarios per map data were created, and the performance was compared and analysed according to the time required to search for a path, number of nodes visited and the specified starting and ending points. For the same scenario, A* used the straight-line distance between the starting point and arrival point as a heuristic. The experiment in which A* applied the same heuristic to the topology map generated by the CNA was repeated. In this case, the starting and ending points of the scenario were arbitrary points, in which the linear distance differed by \(\geq\)100; scenarios in which a route could not be searched were excluded. Table 4 shows the results of reducing the number of nodes through preprocessing. Complexity refers to the complexity of each map. We used the number of image pixels and the number of corners when evaluating map complexity. The information on the image used for each complexity is shown in Table 2.  
Table 5 shows the results of analysing the time difference when A* is used alone versus when A* is applied to the topology map generated with the CNA. Complexity refers to the complexity of each map. Single A* time is the average time taken to search for a route using only A* in the map data. Preprocessing Time is the average time taken to generate the topology map by performing the CNA. Topology Map + A* Time is the average time taken when the A* algorithm is applied to the topology map generated by applying the CNA.