The elongation error is due to the raster-based path unavoidably proceeding from one cell center to the center of one of the adjacent cells. The distortion, provoked by the neighborhood pattern used to create the raster graph, manifests itself as elongation and deviation error. There are two major drawbacks of raster-based pathfinding: one is the distortion inherently present in raster-based paths, and the other is the high computational effort needed to calculate the paths, especially when large rasters are concerned. The path between the two nodes can be determined simply by backtracking the sequence of moves from d to s, which only requires that a pointer to the previous node be assigned to each node by the algorithm. The process is repeated until all nodes reachable from s have been visited, or if a path needs to be found between s and the destination node d only (rather than from s to all other nodes), it is sufficient to terminate the search as soon as d is reached. Once all the neighbors of i have been processed, i is marked “closed” and thus never visited again by the algorithm. If this is the case, c j is updated with the new, smaller value. This means that the algorithm scans all unvisited neighbors of i, and checks if the combined value of c i and the cost of the edge connecting i and its neighbor j is smaller than the previously recorded tentative value c j. The algorithm then repeatedly selects and “expands” the node with the smallest c among the “open” nodes. At the initial stage all nodes are also marked “open”, denoting that they have not yet been visited by the algorithm. The algorithm is initialized by assigning a tentative cost value c to all nodes: zero for s, and infinity for all other nodes. The results indicate that by taking into account the information embedded in the cost raster, paths of relatively good quality can be calculated while effecting significant savings in computational effort compared to the traditional, nonhierarchical approach.ĭijkstra’s algorithm essentially solves the single-source least-cost paths problem on a weighted graph G in other words, it produces a tree of least-cost paths from a start node s to all other nodes of G. The method is implemented in GIS and tested with actual data. The aim of this study is to enhance the method to make it more suitable for calculating paths over cost rasters with nonuniform traversal cost. In this study, a pathfinding method called Hierarchical Pathfinding A* (HPA*), based on an abstraction strategy, is investigated as an alternative to the traditional approach. One of the problems with this method is computational expense, which may be very high with large rasters. In geographic information systems (GIS), the latter is usually associated with the cost surface method, which allows optimum paths to be calculated through rasters in which the value of each cell depicts the cost of traversal through that cell. A fair amount of research has been carried out on pathfinding problems in the context of transportation networks, whereas pathfinding in off-network space has received far less interest.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |