{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T22:16:01Z","timestamp":1769552161408,"version":"3.49.0"},"reference-count":46,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T00:00:00Z","timestamp":1381968000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>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. 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. One of the problems with this method is computational expense, which may be very high with large rasters. 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. 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. The method is implemented in GIS and tested with actual data. 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.<\/jats:p>","DOI":"10.3390\/ijgi2040996","type":"journal-article","created":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T13:39:40Z","timestamp":1382017180000},"page":"996-1014","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Using the Hierarchical Pathfinding A* Algorithm in GIS to Find Paths through Rasters with Nonuniform Traversal Cost"],"prefix":"10.3390","volume":"2","author":[{"given":"Harri","family":"Antikainen","sequence":"first","affiliation":[{"name":"Department of Geography, University of Oulu, P.O. Box 3000, 90014 Oulu, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2013,10,17]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1080\/00167223.2002.10649465","article-title":"On identifying the most time-saving walking route in a trackless mountainous terrain","volume":"102","year":"2002","journal-title":"Geogr. Tidsskr."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/j.cageo.2003.11.001","article-title":"Least-cost paths in mountainous terrain","volume":"30","author":"Rees","year":"2004","journal-title":"Comput. Geosci."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.compenvurbsys.2009.12.003","article-title":"Using GIS-based multicriteria evaluation and path optimization for effective forest field inventory","volume":"34","author":"Store","year":"2010","journal-title":"Comput. Environ. Urban"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0034-4257(95)00047-5","article-title":"A prototype for pipeline routing using remotely sensed data and geographic information system analysis","volume":"53","author":"Feldman","year":"1995","journal-title":"Remote Sens. Environ."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0169-2046(96)00303-9","article-title":"A GIS based method for trail alignment planning","volume":"35","author":"Xiang","year":"1996","journal-title":"Landsc. Urban Plan."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1080\/13658810050024304","article-title":"A direction dependent least-cost-path algorithm for roads and canals","volume":"14","author":"Collischonn","year":"2000","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1080\/1365881031000072645","article-title":"Extensions to least-cost path algorithms for roadway planning","volume":"17","author":"Yu","year":"2003","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"234","DOI":"10.1016\/j.eiar.2010.10.003","article-title":"Routeing of power lines through least-cost path analysis and multicriteria evaluation to minimise environmental impacts","volume":"31","author":"Bagli","year":"2011","journal-title":"Environ. Impact Asses."},{"key":"ref_9","unstructured":"Diestel, R. (2000). Graph Theory, Springer-Verlag. [2nd ed.]."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Miller, H.J., and Shaw, S.-L. (2001). Geographic Information Systems for Transportation, Oxford University Press.","DOI":"10.1093\/oso\/9780195123944.001.0001"},{"key":"ref_11","first-page":"37","article-title":"Least-cost path in GIS using an accumulated cost surface and slopelines","volume":"31","author":"Douglas","year":"1994","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_12","first-page":"19","article-title":"Geographic information systems and disaggregate transportation modeling","volume":"5","author":"Goodchild","year":"1998","journal-title":"Geogr. Syst."},{"key":"ref_13","unstructured":"De Smith, M.J., Goodchild, M.F., and Longley, P.A. (2007). Geospatial Analysis, Winchelsea Press. [2nd ed.]."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1080\/02693799508902031","article-title":"Improving simulation accuracy of spread phenomena in a raster-based geographic information system","volume":"9","author":"Xu","year":"1995","journal-title":"Int. J. Geogr. Inf. Syst."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1068\/a090727","article-title":"An evaluation of lattice solutions to the problem of corridor location","volume":"9","author":"Goodchild","year":"1977","journal-title":"Environ. Plan. A"},{"key":"ref_16","unstructured":"Van Bemmelen, J., Quak, W., van Hekken, M., and van Oosterom, P. (November, January 31). Vector vs. Raster-Based Algorithms for Cross Country Movement Planning. Proceedings of the 11th International Symposium on Computer-Assisted Cartography, Minneapolis, MN, USA."},{"key":"ref_17","unstructured":"Bolstad, B. (2002). GIS Fundamentals, Eider Press."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connexion with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"ref_19","unstructured":"Cormen, T.H., Leiserson, C.E., and Rivest, R.L. (1990). Introduction to Algorithms, MIT Press."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1111\/j.1467-9671.2012.01355.x","article-title":"Comparison of different strategies for determining raster-based least-cost paths with a minimum amount of distortion","volume":"17","author":"Antikainen","year":"2013","journal-title":"Trans. GIS"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1391","DOI":"10.1080\/13658811003779152","article-title":"Propagating radial waves of travel cost in a grid","volume":"24","author":"Tomlin","year":"2010","journal-title":"Int. J. Geogr. Inf. Sci."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3324","DOI":"10.1016\/j.cor.2005.03.027","article-title":"Heuristic shortest path algorithms for transportation applications: State of the art","volume":"33","author":"Fu","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Trans. Syst. Sci. Cybern."},{"key":"ref_24","unstructured":"Russell, S., and Norvig, P. (2003). Artificial Intelligence, Prentice Hall. [2nd ed.]."},{"key":"ref_25","unstructured":"Pearl, J. (1984). Heuristics, Addison-Wesley."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/S1474-0346(03)00018-1","article-title":"Path planning in construction sites: Performance evaluation of the Dijkstra, A*, and GA search algorithms","volume":"16","author":"Soltani","year":"2002","journal-title":"Adv. Eng. Inform."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Glover, F., and Kochenberger, G.A. (2002). Handbook of Metaheuristics, Kluwer Academic Publishers.","DOI":"10.1007\/b101874"},{"key":"ref_28","first-page":"1793","article-title":"Finding optimal paths on terrain maps using ant colony algorithm","volume":"2","author":"Rishiwal","year":"2010","journal-title":"Int. J. Comput. Theory Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.asoc.2009.11.002","article-title":"Digitals ants as the best cicerones for museum visitors","volume":"11","author":"Navarro","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_30","unstructured":"Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1109\/TEVC.2002.804323","article-title":"A genetic algorithm for shortest path routing problem and the sizing of populations","volume":"6","author":"Ahn","year":"2002","journal-title":"IEEE Trans. Evol. Comput."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1068\/b32167","article-title":"Genetic algorithms and the corridor location problem: Multiple objectives and alternative solutions","volume":"35","author":"Zhang","year":"2008","journal-title":"Environ. Plan. B"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"482","DOI":"10.15837\/ijccc.2012.3.1389","article-title":"DGA: A fast and scalable re-routing algorithm based on shortest path and genetic algorithms","volume":"7","author":"Lee","year":"2012","journal-title":"Int. J. Comput. Commun."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Pohl, I. (1969). Bi-Directional and Heuristic Search in Path Problems, Stanford Linear Accelerator Center.","DOI":"10.2172\/1453875"},{"key":"ref_35","unstructured":"Nilsson, N.J. (1980). Principles of Artificial Intelligence, Tioga Publishing."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1613\/jair.460","article-title":"Bidirectional heuristic search reconsidered","volume":"7","author":"Kaindl","year":"1997","journal-title":"J. Artif. Intell. Res."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1145\/322003.322004","article-title":"An improved bidirectional heuristic search algorithm","volume":"24","author":"Sint","year":"1977","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0004-3702(89)90069-6","article-title":"BS*: An admissible bidirectional staged heuristic search algorithm","volume":"38","author":"Kwa","year":"1989","journal-title":"Artif. Intell."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Samet, H. (1990). Applications of Spatial Data Structures, Addison-Wesley.","DOI":"10.1007\/3-540-52208-5_28"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/JRA.1986.1087051","article-title":"Multiresolution path planning for mobile robots","volume":"2","author":"Kambhampati","year":"1986","journal-title":"IEEE J. Robot. Autom."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1109\/70.631228","article-title":"A framed-quadtree approach for determining Euclidean shortest paths in a 2-D environment","volume":"13","author":"Chen","year":"1997","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_42","unstructured":"Sturtevant, N., and Jansen, R. (2007, January 18\u201321). An Analysis of Map-Based Abstraction and Refinement. Proceedings of the 7th International Symposium on AbstractionReformulation and Approximation, Whistler, Canada."},{"key":"ref_43","first-page":"7","article-title":"Near optimal hierarchical path-finding","volume":"1","author":"Botea","year":"2004","journal-title":"J. Game Dev."},{"key":"ref_44","unstructured":"Jansen, M.R., and Buro, M. (2007, January 6\u20138). HPA* Enhancements. Proceedings of the 3rd Artificial Intelligence and Interactive Digital Entertainment ConferenceStanford, Stanford, CA, USA."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Harabor, D., and Botea, A. (2008, January 15\u201318). Hierarchical Path Planning for Multi-Size Agents in Heterogeneous Environments. Proceedings of the IEEE Symposium on Computational Intelligence and Games, Perth, Australia.","DOI":"10.1109\/CIG.2008.5035648"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Li, Y., Su, L.-M., and Li, W.L. (2012, January 17\u201320). Hierarchical Path-Finding Based on Decision Tree. Proceedings of the 7th International Conference on Rough Sets and Knowledge Technology, Chengdu, China.","DOI":"10.1007\/978-3-642-31900-6_32"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/2\/4\/996\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:49:57Z","timestamp":1760219397000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/2\/4\/996"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10,17]]},"references-count":46,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2013,12]]}},"alternative-id":["ijgi2040996"],"URL":"https:\/\/doi.org\/10.3390\/ijgi2040996","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,10,17]]}}}