{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:14:22Z","timestamp":1760177662057,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T00:00:00Z","timestamp":1594944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Pathfinding is the problem of finding the shortest path between a pair of nodes in a graph. In the context of uniform-cost undirected grid maps, heuristic search algorithms, such as     A \u2605     and weighted     A \u2605     (    W  A \u2605     ), have been dominantly used for pathfinding. However, the lack of knowledge about obstacle shapes in a gird map often leads heuristic search algorithms to unnecessarily explore areas where a viable path is not available. We refer to such areas in a grid map as blocked areas (BAs). This paper introduces a preprocessing algorithm that analyzes the geometry of obstacles in a grid map and stores knowledge about blocked areas in a memory-efficient balanced binary search tree data structure. During actual pathfinding, a search algorithm accesses the binary search tree to identify blocked areas in a grid map and therefore avoid exploring them. As a result, the search time is significantly reduced. The scope of the paper covers maps in which obstacles are represented as horizontal and vertical line-segments. The impact of using the blocked area knowledge during pathfinding in     A \u2605     and     W  A \u2605      is evaluated using publicly available benchmark set, consisting of sixty grid maps of mazes and rooms. In mazes, the search time for both     A \u2605     and     W  A \u2605      is reduced by     28 %    , on average. In rooms, the search time for both     A \u2605     and     W  A \u2605      is reduced by     30 %    , on average. This is achieved while preserving the search optimality of     A \u2605     and the search sub-optimality of     W  A \u2605     .<\/jats:p>","DOI":"10.3390\/sym12071186","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T05:10:30Z","timestamp":1595394630000},"page":"1186","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Exploiting Obstacle Geometry to Reduce Search Time in Grid-Based Pathfinding"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9311-807X","authenticated-orcid":false,"given":"Fahed","family":"Jubair","sequence":"first","affiliation":[{"name":"Computer Engineering Department, The University of Jordan, Amman 11942, Jordan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0322-4865","authenticated-orcid":false,"given":"Mohammed","family":"Hawa","sequence":"additional","affiliation":[{"name":"Electrical Engineering Department, The University of Jordan, Amman 11942, Jordan"}]}],"member":"1968","published-online":{"date-parts":[[2020,7,17]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1145\/3828.3830","article-title":"Generalized Best-First Search Strategies and The Optimality of A\u2605","volume":"32","author":"Dechter","year":"1985","journal-title":"J. ACM"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0004-3702(70)90007-X","article-title":"Heuristic Search Viewed as Path Finding in a Graph","volume":"1","author":"Pohl","year":"1970","journal-title":"Artif. Intell."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1016\/j.engappai.2012.08.010","article-title":"Light-Assisted A\u2605 Path Planning","volume":"26","author":"Hawa","year":"2013","journal-title":"Eng. Appl. Artif. Intell."},{"key":"ref_5","unstructured":"Thayer, J., and Ruml, W. (2008, January 24\u201329). Faster than Weighted A\u2605: An Optimistic Approach to Bounded Suboptimal Search. Proceedings of the 18th International Conference on Automated Planning and Scheduling, Delft, The Netherlands."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1109\/TCIAIG.2012.2197681","article-title":"Benchmarks for Grid-Based Pathfinding","volume":"4","author":"Sturtevant","year":"2012","journal-title":"Trans. Comput. Intell. AI Games"},{"key":"ref_7","unstructured":"Sturtevant, N., Felner, A., Barrer, M., Schaeffer, J., and Burch, N. (2009, January 11\u201317). Memory-Based Heuristics for Explicit State Spaces. Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, CA, USA."},{"key":"ref_8","unstructured":"Botea, A. (2010, January 11\u201313). Ultra-Fast Optimal Pathfinding Without Runtime Search. Proceedings of the 6th Conference on Artificial Intelligence and Interactive Digital Entertainment, Stanford, CA, USA."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1613\/jair.4931","article-title":"Compressing Optimal Paths with Run Length Encoding","volume":"54","author":"Strasser","year":"2015","journal-title":"J. Artif. Intell. Res."},{"key":"ref_10","unstructured":"Xie, F., Botea, A., and Kishimoto, A. (2015, January 25\u201330). Heuristic-Aided Compressed Distance Databases. Proceedings of the Workshops at the 29th AAAI Conference on Artificial Intelligence, Austin Texas, TX, USA."},{"key":"ref_11","first-page":"7","article-title":"Near Optimal Hierarchical Path-Finding","volume":"1","author":"Botea","year":"2004","journal-title":"J. Game Dev."},{"key":"ref_12","unstructured":"Demyen, D., and Buro, M. (2006, January 16\u201320). Efficient Triangulation-Based Pathfinding. Proceedings of the 21st Conference on Artificial Intelligence, Boston, MA, USA."},{"key":"ref_13","unstructured":"Sturtevant, N. (2007, January 6\u20138). Memory-efficient Abstractions for Pathfinding. Proceedings of the 3rd Conference on Artificial Intelligence and Interactive Digital Entertainment, Stanford, CA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Uras, T., Koenig, S., and Hern\u00e1ndez, C. (2013, January 10\u201314). Subgoal Graphs for Optimal Pathfinding in Eight-Neighbor Grids. Proceedings of the 23rd International Conference on Automated Planning and Scheduling, Rome, Italy.","DOI":"10.1609\/icaps.v23i1.13568"},{"key":"ref_15","unstructured":"Bj\u00f6rnsson, Y., and Halld\u00f3rsson, K. (2006, January 20\u201323). Improved heuristics for optimal pathfinding on game maps. Proceedings of the 2nd Conference on Artificial Intelligence and Interactive Digital Entertainment, Marina del Rey, CA, USA."},{"key":"ref_16","unstructured":"Pochter, N., Zohar, A., and Rosenschein, J. (2009, January 10\u201315). Using Swamps to Improve Optimal Pathfinding. Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems, Budapest, Hungary."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Thayer, J., and Ruml, W. (2011, January 16\u201322). Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates. Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Spain.","DOI":"10.1609\/icaps.v22i1.13514"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Harabor, D., and Grastien, A. (2011, January 7\u201311). Online Graph Pruning for Pathfinding on Grid Maps. Proceedings of the 25th Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v25i1.7994"},{"key":"ref_19","first-page":"66","article-title":"The Grid-Based Path Planning Competition","volume":"35","author":"Sturtevant","year":"2014","journal-title":"AI Mag."},{"key":"ref_20","unstructured":"Sturtevant, N., Traish, J., Tulip, J., Uras, T., Koenig, S., Strasser, B., Botea, A., Harabor, D., and Rabin, S. (2015, January 11\u201313). The grid-based path planning competition: 2014 entries and results. Proceedings of the Annual Symposium on Combinatorial Search, Ein Gedi, Israel."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/978-3-319-49487-6_2","article-title":"Route Planning in Transportation Networks","volume":"Volume 9220","author":"Kliemann","year":"2016","journal-title":"Algorithm Engineering, Lecture Notes in Computer Science Book Series"},{"key":"ref_22","first-page":"319","article-title":"Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks","volume":"Volume 5038","author":"McGeoch","year":"2012","journal-title":"Experimental Algorithms. WEA 2008 30 May-1 June, Provincetown, MA, USA. Lecture Notes in Computer Science Book Series"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","article-title":"Algorithms for Reporting and Counting Geometric Intersections","volume":"c\u201328","author":"Bentley","year":"1979","journal-title":"IEEE Trans. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/147508.147511","article-title":"An Optimal Algorithm for Intersecting Line Segments in the Plane","volume":"39","author":"Chazelle","year":"1992","journal-title":"J. ACM"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Guttman, A. (1984, January 8\u201321). R-Trees: A Dynamic Index Structure for Spatial Searching. Proceedings of the ACM SIGMOD International Conference on Management of Data, Boston, MA, USA.","DOI":"10.1145\/602264.602266"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Manolopoulos, Y., Nanopoulos, A., Papadopoulos, A.N., and Theodoridis, Y. (2006). R-Trees: Theory and Applications, Springer.","DOI":"10.1007\/978-1-84628-293-5"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0925-7721(01)00012-8","article-title":"The point in polygon problem for arbitrary polygons","volume":"20","author":"Hormann","year":"2001","journal-title":"Comput. Geom."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"De Berg, M., Cheong, O., van Kreveld, M., and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer. [3rd ed.].","DOI":"10.1007\/978-3-540-77974-2"},{"key":"ref_29","unstructured":"Burns, E., Hatem, M., Leighton, M.J., and Ruml, W. (2012, January 19\u201321). Implementing Fast Heuristic Search Code. Proceedings of the Annual Symposium on Combinatorial Search, Niagara Falls, ON, Canada."},{"key":"ref_30","unstructured":"Holte, R.C. (2012, January 19\u201321). Common Misconceptions Concerning Heuristic Search. Proceedings of the Annual Symposium on Combinatorial Search, Niagara Falls, ON, Canada."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/7\/1186\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:49:21Z","timestamp":1760176161000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/12\/7\/1186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,17]]},"references-count":30,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2020,7]]}},"alternative-id":["sym12071186"],"URL":"https:\/\/doi.org\/10.3390\/sym12071186","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2020,7,17]]}}}