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 algorithms