The traditional approach to solving routing problems is to model the road network as a weighted graph and apply algorithms to determine the shortest path (Miller, Shaw 2001). While effective for finding optimal routes within road networks, this approach is not suitable for calculating the shortest paths across continuous surfaces, such as geographic terrain. In geographic information systems (GIS), an alternative approach uses a raster to represent the cost surface in the form of a regular grid. Each cell in the raster is assigned a cost value, reflecting the difficulty of traversing that cell. These costs can be expressed in terms of money, time, or other units, taking into account factors such as travel time, distance, and safety. See also comparative algorithmic reviews in [Ashish 2021; Susanto 2021]

Finding a route with the minimum accumulated cost from the start cell to the target cell is known as the least-cost path (LCP) method. The cost raster is treated as a planar graph, with each cell center representing a vertex, and each node is connected to neighboring cells according to a predefined neighborhood pattern (Kourtz and O’Regan 1971; Tomlin 1990; ESRI 1991). The most common neighborhood patterns are the “knight”, “rook”, and “queen” patterns, with the “queen” and “rook” patterns being the most frequently used. Some studies suggest that the knight pattern is optimal for pathfinding (Choi 2013; Yu et al. 2010).

The LCP method is often affected by distortions caused by the raster structure. Paths may appear zigzagged due to turn-angle restrictions, particularly close to the starting point, which can introduce significant errors. These distortions are independent of raster resolution because the path in a regular model always proceeds from one vertex to an adjacent one in discrete increments, rather than traversing continuous space (Tomlin 1990). This type of deviation and elongation error was first formalized by Goodchild (1977). Post-processing can reduce these distortions; for example, the zigzag segments of the path can be simplified using the Douglas–Peucker algorithm (Choi et al. 2009).

Several studies have attempted to reduce the geometric distortions inherent in raster-based least-cost path modeling. Antikainen (2013) demonstrated that placement of nodes either at cell centers (CC) or along cell boundaries (BC), as well as the choice of neighborhood structure, significantly influences path accuracy and computational performance. Subsequently, Seegmiller et al. (2020) built upon this approach by formulating an extended raster model in which nodes are positioned on cell boundaries. This improves topological consistency and mitigates the impact of raster-induced artifacts. Nevertheless, these approaches still operate strictly within the raster domain and do not fully resolve the limitations associated with integrating vector networks into continuous cost surfaces.

To address the issue of zigzagging, one option is to increase neighborhood connectivity, which minimizes the possible turning angles. However, this approach violates the theoretical principle of the shortest path, since a straight line passing through cells with varying costs is not necessarily the shortest. The optimal path should therefore follow the boundaries between cells with different values, in a manner similar to the laws of refraction in optics (Warntz 1957) and to later refinements of cost-surface refraction modeling (Tomlin 2010). The raster representation only approximates real-world landscapes, whose boundaries are difficult to define precisely. Consequently, cell boundaries may be disregarded.

Large neighborhoods create additional issues. Minimal turning angles may be blocked if an edge intersects a high-cost cell or an obstacle. Paths with a shared endpoint may also intersect incorrectly. Errors associated with traversing cells with varying costs and with intersecting paths can be addressed using a method proposed by Bemmelen et al. (1993). This method involves constructing a graph in which nodes are located along cell boundaries (boundary-connected, BC), rather than at cell centers (center-connected, CC). This extended raster configuration enables connections between nodes within the same homogeneous cell, thereby facilitating calculations and improving flexibility in route planning. However, this approach does not entirely eliminate distortions associated with raster structures.

The least-cost path method, which is based on conventional raster representation, is widely used and effective. The search for an optimal path is crucial not only for off-road route planning, as shown by Balstrøm (2002) and Rees (2004), but also in the design and construction of infrastructure, such as highways (Yu et al. 2010), railways, pipelines (Rylsky 2009), power lines (Novakovsky et al. 2017; Bagli et al. 2011), channels (Collischonn & Pilar 2000), and other transportation systems.

However, a separate issue arises when linear features, such as roads and waterways, are included in a raster model. While these features can be converted to a raster format and incorporated into a cost surface using overlay operations, this approach has limitations. Notably, integrating vector objects into a regular model can make it challenging to distinguish between different types of intersection (e.g., bridges, overpasses, and road crossings). Consequently, topological relationships cannot be preserved correctly (Choi et al. 2013). Accurately representing vector networks and their properties in a raster-based model is important because the optimal path often depends on the location of existing linear network features. For instance, waterways can restrict movement, whereas road networks usually provide low-cost travel routes. Anisotropic costs must also be considered, as these account for changes in edge costs based on movement direction, which is often influenced by slope orientation and steepness.

The scientific literature offers few approaches to solving the problem of combining irregular and regular network models. While Choi et al. (2013) propose a method that integrates these two classical models, their algorithm only permits access to or exit from a vector network at graph vertices and not at any point along the edges. Overcoming this limitation could make the integrated methodology more widely applicable.

Many geospatial studies have successfully applied algorithms to determine optimal paths based on both regular and irregular network models. However, the challenge of developing an efficient method for integrating these models while preserving their respective advantages remains unresolved. Existing routing approaches demonstrate that modeling walking routes in sparsely connected areas requires a method that integrates the two models and allows flexible parameterization based on user needs. This study aims to develop and test a methodology that integrates raster-based cost surfaces with vector road network data in order to simulate realistic walking routes in sparsely connected areas while accounting for varying environmental conditions and user-defined priorities.

The initial data for creating the network model include the road network, field track-data, and remote sensing imagery used for surface segmentation. The continuous terrain surface was first segmented into land cover units with different passability conditions based on image interpretation. These units were subsequently assigned walking speeds derived from field observations, forming a passability map representing terrain suitability for transportation or walking (Pokonieczny 2020). The passability map based on satellite imagery can be created in two ways: (1) through automated classification or (2) through expert interpretation. To identify different land types in our case, we used a mosaic of ultra-high-resolution satellite scanner images available through the ESRI map viewer online service for expert interpretation.

Table 1 was used as the basis for identifying potential land cover types. The classification follows a functional approach to passability mapping, where surface categories are distinguished according to vegetation structure, obstacle presence, and expected pedestrian mobility conditions. The selected classes reflect both established approaches to terrain suitability assessment and local field knowledge of movement conditions within the study area, which, together, justify their use for routing impedance modeling. Initially, the entire area was divided into large and homogeneous groups based on the surface or the prevailing type of vegetation: open ground areas characterized by the presence of a predominantly grassy layer; forests; sparsely populated land; bodies of water; and settlement areas.

The next stage involved dividing the main groups into more specific categories, as some areas had significant variations in the dominant type of flora and its density. For instance, logging has been carried out in the study area for several years, resulting in a significant number of old and relatively recent cuttings with various structures and at different stages of restoration. Therefore, additional land cover categories were required. The mapped objects vary widely in terms of vegetation type, density, and succession stage, all of which affect passability. This is determined by the type of vegetation cover, the presence and nature of secondary vegetation tiers, and the degree of density of the stand.

An average travel speed is assigned to each identified land cover type and road. This determines the weight for travel along edges associated with that area or network segment. These speeds can be calculated analytically, based on territorial knowledge, or empirically, using field data obtained from satellite navigation receivers. In our case, we used the second approach – the resulting table of speeds can be found in the Results section. The resulting network model combines a regular grid-based surface model with a road network model. The spatial resolution of this model is determined by the regular point grid step.

According to the chosen neighborhood pattern (e.g. queen or knight), each vertex is connected to neighboring cells. These edges form a non-planar graph, with geometrically identical duplicates excluded. The impedance of each edge is calculated based on its length and the time difference in seconds between the connected vertices. Additionally, a hierarchy of edges is established to reduce computation time and limit the search for paths by prioritizing higher-level edges. This approach makes it easier to determine more convenient routes, including transitions between roads and unpaved surfaces when necessary. The hierarchy is algorithmically implemented by assigning each edge a priority class and multiplying its base impedance by a hierarchy coefficient. During pathfinding, higher-priority edges have lower effective costs, forcing the search algorithm to explore them first unless there is a substantially shorter alternative outside the hierarchy.

Route planning also accounts for terrain irregularities by incorporating elevation and movement direction using a digital elevation model (DEM). We used a DEM from the Satino local educational geoinformation system with 5-meter resolution. We used the hiking exponential Tobler function (Tobler 1993), which models speed based on slope angle, to calculate a terrain-based coefficient.

(1)

According to this formula, the maximum speed is achieved at an angle of inclination of α=-2.860, while an increase or decrease in this angle results in an exponential decrease in speed.

Obstacles such as water bodies, fenced areas, and buildings are marked as inaccessible, and edges crossing them are removed from the graph. Weather conditions are factored in by adjusting edge weights with additional coefficients.

This methodology was tested at the Satino educational field station in the Borovsky district of the Kaluga region. A set of field data was collected using a satellite navigation receiver. Three network models were initialized based on the passability surface to represent different regular lattice configurations and connectivity schemes commonly used in raster-based path modeling. The square grid with queen adjacency (8 neighbors) was used as a conventional baseline configuration; the knight adjacency (16 neighbors, including queen adjacency and L-shaped neighbors) (Yu et al. 2010) was included to increase directional flexibility and angular resolution of movement, while the hexagonal grid represents an alternative lattice geometry often considered to reduce directional bias. Together, these models enable comparison of routing behavior under varying structural properties of the regular network (Fig. 1).

For each network model, three experimental routes were created using different parameters, based on the modified Dijkstra’s algorithm, including edge hierarchy (ESRI 2005). Similar start and end points were also used for routing, which was performed using the least-cost path (LCP) method on a raster cost surface. Weather influence modeling was tested by applying additional coefficients to edge weights. The start and end points were located on opposite sides of a river, enabling the analysis of various crossing options under different conditions.

Three routes were created based on the assumption of comfortable weather conditions: cloudy weather without precipitation and a temperature of +17°C. To compare the results, similar routes were generated using the traditional least-cost path (LCP) method. In this method, the cost surface is a rasterized representation of different terrain types, including a rasterized road network. The cost of each raster cell represents the time it takes to traverse that area. The resolution of the raster surface is 10 meters, similar to the modeled one (Fig. 2).

An analysis of the generated routes revealed significant differences in the modeling results, depending on the initial conditions. One key factor influencing these differences is the parameter related to the hierarchy of network elements. Routes generated based on the hierarchical model prioritize the road network when searching for paths. The algorithm selects the shortest route from the starting point to the nearest road and follows it for as long as possible. This results in a more convenient path, as people generally prefer to travel on roads and avoid natural obstacles. In contrast, routes generated using a non-hierarchical model focus more on minimizing total path length or optimizing movement time, which may not always prioritize the road network.

Routes generated by the LCP method are conceptually similar to those produced by the non-hierarchical model. However, LCP results depend strongly on raster resolution, as seen in our experiments. For example, the LCP-generated path suggests crossing a river directly instead of using a nearby bridge, because the river is too narrow to be represented in the raster at its given scale, leading to a misinterpretation by the model. Furthermore, the LCP method lacks the ability to assign hierarchical importance to individual raster pixels, which highlights the advantage of the proposed non-hierarchical approach over LCP.

Various weather conditions were modeled using hierarchical network models. Edge weights were adjusted using coefficients to simulate different scenarios (see Table 2). Two scenarios were tested: rainy weather at +7°C and extremely hot weather at +32°C. In the extreme heat scenario, the use of a ford at a designated location was permitted. The edge weight coefficients were defined analytically for each scenario, based on the assumption that movement speed generally decreases on most surface types and roads, as the energy required to move increases under these conditions (Fig. 3).

Route modeling under these scenarios shows that, in rainy conditions, both the hexagonal and square grids with queen adjacency patterns produce shorter routes through forested areas and the road network. Meanwhile, the square grid model with knight adjacency produced a longer route around forested areas initially, prioritizing use of the road network wherever possible.

Rainy weather produced the most significant variation in route options. In contrast, the routes were almost identical in hot weather because users tended to choose the ford, which is closer than the bridge. To evaluate the practicality of the proposed routes, we conducted a survey of individuals familiar with the area. They were asked to design their preferred routes based on the same start and end points used in the modeling. Analyzing the results, we found that the preferred routes were similar to the modeled ones: in hot weather, people tended to take a shorter route by using the ford, which is closer to the starting point than the bridge (Fig. 4).

When we compared different network models based on a regular grid structure, we found that the square configuration had certain advantages over the hexagonal one. This is because significant geometric distortions are absent from the resulting routes, which are often seen in the hexagonal model. These distortions arise from the grid’s connectivity type, resulting in a zigzag effect, similar to that seen in the least-cost path (LCP) method, where raster structure causes artificial elongation and increased path costs. In terms of adjacency patterns, the knight pattern offers 16 possible movement directions compared to 8 for the queen pattern. In most weather scenarios, except rainy conditions, the knight pattern produced routes that were slightly more advantageous in terms of travel time. This advantage is due to its connectivity structure, with longer edges, as the knight pattern extends into a 5×5 neighborhood, whereas the queen pattern extends into a 3×3 neighborhood. This allows for more diverse path options.

To complement the qualitative assessment, we performed a quantitative comparison of route similarity across all modeling configurations. Fig. 5 shows pairwise percentages of spatial identity between routes generated using different grid structures, adjacency patterns, and hierarchical settings. Models with edge hierarchy demonstrate very high internal consistency (97–100%) across all three test routes, while agreement between hierarchical and non-hierarchical models drops to 13–36%, reflecting their different movement priorities. The LCP paths exhibit only 11–35% spatial overlap with hierarchical models, confirming that raster-based routing deviates substantially from more realistic on-road/off-road transitions.

However, these advantages are offset by the data and processing time required for the knight pattern. It requires more than twice the data and computational resources of the queen pattern, rendering it less efficient. Therefore, we conclude that a network model based on a square grid with queen connectivity offers greater efficiency in terms of processing time and routing.

Compared to previous attempts at integrating vector networks with raster cost surfaces, such as the extended raster approach (Antikainen 2013; Seegmiller et al. 2020) and the method proposed by Choi et al. (2013), the methodology presented in this study introduces several significant improvements. While the extended raster and boundary-connected (BC) models do overcome some of the distortions inherent in regular raster structures, they still rely on cell-based geometry and do not allow for flexible transitions between road networks and continuous terrain.

While Choi et al. (2013) take an essential step towards integrating regular and irregular models, their method restricts entry to and exit from the vector network to predefined graph vertices. Consequently, transitions can only occur at road intersections or endpoints, which restricts the realism of simulated routes, particularly in sparsely connected areas where pedestrians often join a road at various positions along its length.

The approach developed in this paper builds on this research by enabling transitions between roads and off-road terrain at any point along an edge, rather than just at vertices. This significantly increases the flexibility of the integrated model and better reflects real pedestrian movement. Additionally, the incorporation of edge hierarchy – with prioritization of high-quality or more passable segments – is a methodological advancement lacking in previous raster- or vector-based approaches. This hierarchy enables the model to approximate realistic walking preferences rather than merely identifying the shortest possible route.

Undoubtedly, the framework combines these improvements with anisotropic movement costs, weather-dependent coefficients, and a consistent treatment of slopes using Tobler’s function. Together, these features offer a more comprehensive and adaptable routing methodology. These contributions distinguish the proposed approach from previous work, providing a more robust tool for simulating walking behavior in heterogeneous environments.

Despite the demonstrated advantages of the proposed methodology, several limitations must be acknowledged. Firstly, the model is inherently dependent on the spatial resolution of the regular grid used to generate the network. While finer grids improve the representation of terrain heterogeneity and reduce geometric distortions, they significantly increase data volume and computational requirements. Conversely, coarser grids simplify calculations but may overlook important landscape features that influence walking behavior.

Secondly, assigning walking speeds to land cover types and calibrating weather-related coefficients involves a degree of subjectivity. Although these coefficients were based on analytical estimates and expert knowledge, they may not fully capture the variability of real-world movement conditions. Their accuracy can vary between regions and user groups, and additional empirical field measurements would help to refine these parameters.

Thirdly, the computational cost of the method increases substantially when it is applied to large regions or when complex adjacency schemes are used. The number of edges increases rapidly with grid density and connectivity, which affects processing time and potentially limits the approach’s applicability in extensive territories without additional optimization.

Finally, the model assumes simplified walking behavior, focusing primarily on minimizing travel time or distance and prioritizing roads through hierarchical edge weighting. However, human route choices are influenced by many additional factors, such as comfort, safety, visibility, fatigue, and terrain preferences – that are not fully represented in the current implementation. This may result in simulated routes lacking realism in certain contexts.

Given the need for routing methods capable of integrating road networks with continuous terrain representation while overcoming the limitations of conventional raster-based approaches, the experiments we conducted have allowed us to determine the advantages of the developed technique compared to the current pathfinding method using the LCP algorithm.

In particular, the LCP approach is similar to the resulting non-hierarchical network model. However, the LCP output is accompanied by a significant number of distortions due to the raster structure, and its accuracy depends heavily on its resolution. Furthermore, the LCP technique does not permit the formation of a hierarchy among individual pixels, preventing the prioritization of movement along the road network.

Following analysis, we identified the square regular grid network model with a “queen” adjacency pattern as the optimal option in terms of both computational complexity and route efficiency. This model has the shortest implementation time and is virtually free from geometric errors that could distort routes. Overall, the proposed methodology represents terrain more accurately than a raster-based approach. It is also more flexible and can be adapted to different movement conditions.

Depending on user priorities, the model can either emphasize more convenient routes through hierarchy or focus solely on the shortest (or fastest) path by removing hierarchy. The decision on which approach to use depends on the goals of the proposed model.

The developed methodology can be applied in several real-world contexts. In tourism route planning, for example, the model can generate comfortable walking routes that take into account weather conditions, terrain complexity, and user preferences regarding road versus off-road movement. In environmental and field research, it supports assessment of site accessibility, the planning of field campaigns, and the evaluation of how land cover changes affect mobility. In search and rescue operations, the hierarchical network structure enables the quick identification of feasible routes, optimal access points, and alternative paths under adverse conditions, providing a practical advantage over raster-based LCP approaches. Together, these use cases demonstrate the broader applicability and flexibility of the proposed routing framework.