Analysis of selected pathfinding algorithms in 2D porous media with binary representation
FIlip Klimek
a:1:{s:5:"en_US";s:43:"Uniwersytet Warmińsko-Mazurski w Olsztynie";}Wojciech Sobieski
Abstract
The article presents an analysis of the influence of geometric parameters of a porous medium represented in a binary form – grid size, obstacle width, and porosity – on the tortuosity of transport paths and the efficiency of pathfinding algorithms. Numerical simulations were carried out for grids of 100–200 nodes, obstacle widths of 1–13 nodes, and porosity values ranging from 0.9 to 0.5, using the Dijkstra, A*, BFS, and Greedy BFS algorithms. The results confirmed the existence of a percolation threshold at ϕ ≈ 0.6 and showed that decreasing porosity increases path tortuosity. For high porosity (ϕ = 0.9), paths were nearly straight (τ ≈ 1.03), while for low porosity (ϕ = 0.5–0.6) they became highly tortuous (τ > 1.3). Among the tested methods, the A* and Greedy BFS algorithms proved to be the most computationally efficient, confirming the effectiveness of heuristic approaches in modeling transport phenomena in porous structures.
Keywords:
porous media, tortuosity, porosity, path searching algorithmsReferences
CARMAN P.C. 1937. Fluid flow through a granular bed. Transactions of the Institute of Chemical Engineers, Jubilee Supplement, 75: 32-48. Google Scholar
FU J., THOMAS H.R., LI C. 2021. Tortuosity of porous media: Image analysis and physical simulation. Earth-Science Reviews, 212, 103439: 1-30. Google Scholar
KOPONEN A., KATAJA M., TIMONEN J. 1996. Tortuous flow in porous media. Physical Review E, 54: 406-410. Google Scholar
KOPONEN, A., KATAJA, M., TIMONEN, J. 1997. Permeability and effective porosity of porous media. Physical Review E, 56, 3319-3325. Google Scholar
KOZENY J. 1927. Über kapillare Leitung des Wassers im Boden. Akademie der Wissenschaften in Wien, Sitzungsberichte, 136(2a): 271-306. Google Scholar
MATYKA M., KHALILI A., KOZA Z. 2008. Tortuosity-porosity relation in porous media flow. Physical Review E, 78: 026306. Google Scholar
NEWMAN M.E.J., ZIFF R.M. 2000. Efficient Monte Carlo algorithm and high-precision results for percolation. Physical Review Letters, 85(19): 4104-4107. Google Scholar
SOBIESKI W. 2019. Numerical investigations of tortuosity in randomly generated pore structures. Mathematics and Computers in Simulation, 166: 1-20. Google Scholar
SOBIESKI W. 2020. Calculating the binary tortuosity in DEM-generated granular beds. Processes, 8(9): 1-19. Google Scholar
WANG J., ZHOU Z. 2013. Site percolation thresholds in two dimensions. Physical Review E, 87(5): 052107. Google Scholar
a:1:{s:5:"en_US";s:43:"Uniwersytet Warmińsko-Mazurski w Olsztynie";}
