{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T18:45:24Z","timestamp":1762368324612,"version":"build-2065373602"},"reference-count":33,"publisher":"Tsinghua University Press","issue":"2","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comp. Visual. Med."],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s41095-015-0018-0","type":"journal-article","created":{"date-parts":[[2015,10,20]],"date-time":"2015-10-20T09:19:45Z","timestamp":1445332785000},"page":"105-118","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Subregion graph: A path planning acceleration structure for characters with various motion types in very large environments"],"prefix":"10.26599","volume":"1","author":[{"given":"Nicholas Mario","family":"Wardhana","sequence":"first","affiliation":[{"name":"Multi-plAtform Game Innovation Centre (MAGIC), Nanyang Technological University, XFrontiers Block, 02-M1 Research Techno Plaza, 50 Nanyang Drive, Singapore, 637553; School of Computer Engineering, Nanyang Technological University, Block N4 #02a-32, Nanyang Avenue, Singapore, 639798"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henry","family":"Johan","sequence":"additional","affiliation":[{"name":"Fraunhofer IDM@NTU, Nanyang Technological University, NS1-1 Level 5, 50 Nanyang Avenue, Singapore, 639798"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hock Soon","family":"Seah","sequence":"additional","affiliation":[{"name":"Multi-plAtform Game Innovation Centre (MAGIC), Nanyang Technological University, XFrontiers Block, 02-M1 Research Techno Plaza, 50 Nanyang Drive, Singapore, 637553; School of Computer Engineering, Nanyang Technological University, Block N4 #02a-32, Nanyang Avenue, Singapore, 639798"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"11138","reference":[{"key":"18_CR1","unstructured":"Grand Theft Auto III (DVD). Rockstar Games, 2001."},{"key":"18_CR2","unstructured":"Just Cause II(Steam). Eidos Interactive, 2010. Available at http:\/\/store.steampowered.com\/app\/81901."},{"key":"18_CR3","unstructured":"The Elder Scrolls V: Skyrim (Steam). Bethesda Softworks, 2011. Available at http:\/\/store.steampowered.com\/app\/7282501."},{"key":"18_CR4","doi-asserted-by":"crossref","first-page":"3868","DOI":"10.1109\/ROBOT.2005.1570711","volume-title":"Proceedings of the 2005 IEEE International Conference on Robotics and Automation","author":"E. Plaku","year":"2005","unstructured":"Plaku, E.; Kavraki, L. E. Distributed sampling-based roadmap of trees for large-scale motion planning. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 3868\u20133873, 2005."},{"key":"18_CR5","volume-title":"The AAMAS-2013 Workshop on Cognitive Agents for Virtual Environments","author":"K. Samperi","year":"2013","unstructured":"Samperi, K.; Hawes, N.; Beale, R. Improving map generation in large-scale environments for intelligent virtual agents. In: The AAMAS-2013 Workshop on Cognitive Agents for Virtual Environments, 2013. Available at http:\/\/www.cs.bham.ac.uk\/~nah\/bibtex\/papers\/samperietal2013cave.pdf."},{"issue":"10","key":"18_CR6","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.1007\/s00371-013-0837-x","volume":"29","author":"N. M. Wardhana","year":"2013","unstructured":"Wardhana, N. M.; Johan, H.; Seah, H. S. Enhanced waypoint graph for surface and volumetric path planning in virtual worlds. The Visual Computer Vol. 29, No. 10, 1051\u20131062, 2013.","journal-title":"The Visual Computer"},{"issue":"2","key":"18_CR7","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"P. E. Hart","year":"1968","unstructured":"Hart, P. E.; Nilsson, N. J.; Raphael, B. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics Vol. 4, No. 2, 100\u2013107, 1968.","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"issue":"1\u20132","key":"18_CR8","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/0004-3702(95)00111-5","volume":"85","author":"R. C. Holt\u00eb","year":"1996","unstructured":"Holt\u00eb, R. C.; Mkadmi, T.; Zimmer, R. M.; MacDonald, A. J. Speeding up problem solving by abstraction: A graph oriented approach. Artificial Intelligence Vol. 85, Nos. 1\u20132, 321\u2013361, 1996.","journal-title":"Artificial Intelligence"},{"key":"18_CR9","first-page":"1392","volume":"3","author":"N. Sturtevant","year":"2005","unstructured":"Sturtevant, N.; Buro, M. Partial pathfinding using map abstraction and refinement. In: Proceedings of the 20th National Conference on Artificial Intelligence, Vol. 3, 1392\u20131397, 2005.","journal-title":"Proceedings of the 20th National Conference on Artificial Intelligence"},{"issue":"1","key":"18_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1613\/jair.2293","volume":"30","author":"V. Bulitko","year":"2007","unstructured":"Bulitko, V.; Sturtevant, N.; Lu, J.; Yau, T. Graph abstraction in real-time heuristic search. Journal of Artificial Intelligence Research Vol. 30, No. 1, 51\u2013100, 2007.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"6","key":"18_CR11","doi-asserted-by":"crossref","first-page":"1004","DOI":"10.1137\/0216064","volume":"6","author":"G. N. Frederickson","year":"1987","unstructured":"Frederickson, G. N. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing Vol. 6, No. 6, 1004\u20131022, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"18_CR12","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1007\/11427186_13","volume":"3503","author":"E. K\u00f6hler","year":"2005","unstructured":"K\u00f6hler, E.; M\u00f6hring, R. H.; Schilling, H. Acceleration of shortest path and constrained shortest path computation. Lecture Notes in Computer Science Vol. 3503, 126\u2013138, 2005.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR13","doi-asserted-by":"crossref","first-page":"776","DOI":"10.1007\/978-3-540-39658-1_69","volume":"2832","author":"D. Wagner","year":"2003","unstructured":"Wagner, D.; Willhalm, T. Geometric speedup techniques for finding shortest paths in large sparse graphs. Lecture Notes in Computer Science Vol. 2832, 776\u2013787, 2003.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR14","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1090\/dimacs\/074\/03","volume-title":"The Shortest Path Problem: Ninth DIMACS Implementation Challenge","author":"M. Hilger","year":"2009","unstructured":"Hilger, M.; K\u00f6hler, E.; M\u00f6hring, R. H.; Schilling, H. Fast point-to-point shortest path computations with arc-flags. In: The Shortest Path Problem: Ninth DIMACS Implementation Challenge. Demetrescu, C.; Goldberg, A. V.; Johnson, D. S. Eds. American Mathematical Society, 41\u201372, 2009."},{"key":"18_CR15","first-page":"219","volume":"22","author":"U. Lauther","year":"2004","unstructured":"Lauther, U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Geoinformation und Mobilit\u00e4t\u2013von der Forschung zur praktischen Anwendung, Vol. 22, 219\u2013230, 2004.","journal-title":"Geoinformation und Mobilit\u00e4t\u2013von der Forschung zur praktischen Anwendung"},{"key":"18_CR16","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/11427186_18","volume":"3503","author":"R. H. M\u00f6hring","year":"2005","unstructured":"M\u00f6hring, R. H.; Schilling, H.; Sch\u00fctz, B.; Wagner, D.; Willhalm, T. Partitioning graphs to speed up Dijkstra\u2019s algorithm. Lecture Notes in Computer Science Vol. 3503, 189\u2013202, 2005.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR17","first-page":"258","volume-title":"IEEE Symposium on Computational Intelligence and Games","author":"D. Harabor","year":"2008","unstructured":"Harabor, D.; Botea, A. Hierarchical path planning for multi-size agents in heterogeneous environments. In: IEEE Symposium on Computational Intelligence and Games, 258\u2013265, 2008."},{"key":"18_CR18","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/978-3-540-28633-2_13","volume":"3157","author":"D. Mould","year":"2004","unstructured":"Mould, D.; Horsch, M. C. A hierarchical terrain representation for approximately shortest paths. Lecture Notes in Computer Science Vol. 3157, 104\u2013113, 2004.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR19","first-page":"100","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics","author":"R. J. Gutman","year":"2004","unstructured":"Gutman, R. J. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In: Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics, 100\u2013111, 2004."},{"key":"18_CR20","first-page":"129","volume-title":"Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments","author":"A. V. Goldberg","year":"2006","unstructured":"Goldberg, A. V.; Kaplan, H.; Werneck, R. F. Reach for A*: Efficient point-to-point shortest path algorithms. In: Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments, 129\u2013143, 2006."},{"key":"18_CR21","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/11561071_51","volume":"3669","author":"P. Sanders","year":"2005","unstructured":"Sanders, P.; Schultes, D. Highway hierarchies hasten exact shortest path queries. Lecture Notes in Computer Science Vol. 3669, 568\u2013579, 2005.","journal-title":"Lecture Notes in Computer Science"},{"issue":"6","key":"18_CR22","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. W. Floyd","year":"1962","unstructured":"Floyd, R. W. Algorithm 97: Shortest path. Communications of the ACM Vol. 5, No. 6, 345, 1962.","journal-title":"Communications of the ACM"},{"issue":"1","key":"18_CR23","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","volume":"9","author":"S. Warshall","year":"1962","unstructured":"Warshall, S. A theorem on boolean matrices. Journal of the ACM Vol. 9, No. 1, 11\u201312, 1962.","journal-title":"Journal of the ACM"},{"key":"18_CR24","first-page":"156","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. V. Goldberg","year":"2005","unstructured":"Goldberg, A. V.; Harrelson, C. Computing the shortest path: A* search meets graph theory. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 156\u2013165, 2005."},{"key":"18_CR25","first-page":"74","volume-title":"Proceedings of the Eighth Symposium on Abstraction, Reformulation, and Approximation","author":"A. Felner","year":"2009","unstructured":"Felner, A.; Sturtevant, N.; Schaeffer, J. Abstractionbased heuristics with true distance computations. In: Proceedings of the Eighth Symposium on Abstraction, Reformulation, and Approximation, 74\u201381, 2009."},{"issue":"5","key":"18_CR26","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/j.cag.2013.03.004","volume":"37","author":"R. Oliva","year":"2013","unstructured":"Oliva, R.; Pelechano, N. NEOGEN: Near optimal generator of navigation meshes for 3D multi-layered environments. Computers & Graphics Vol. 37, No. 5, 403\u2013412, 2013.","journal-title":"Computers & Graphics"},{"key":"18_CR27","first-page":"3526","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"W. G. Toll Van","year":"2011","unstructured":"Van Toll, W. G.; Cook IV, A. F.; Geraerts, R. Navigation meshes for realistic multi-layered environments. In: IEEE\/RSJ International Conference on Intelligent Robots and Systems, 3526\u20133532, 2011."},{"issue":"1","key":"18_CR28","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik Vol. 1, No. 1, 269\u2013271, 1959.","journal-title":"Numerische Mathematik"},{"key":"18_CR29","volume-title":"Toward more realistic pathfinding","author":"M. Pinter","year":"2001","unstructured":"Pinter, M. Toward more realistic pathfinding. 2001. Available at http:\/\/www.gamasutra.com\/features\/20010314\/pinter_01.htm."},{"key":"18_CR30","volume-title":"The Boost Graph Library (BGL) (version 1.57)","author":"J. Siek","year":"2014","unstructured":"Siek, J.; Lee, L.-Q.; Lumsdaine, A. The Boost Graph Library (BGL) (version 1.57). 2014. Available at http:\/\/www.boost.org\/libs\/graph\/."},{"key":"18_CR31","unstructured":"The OGRE Team. OGRE\u2014Object-oriented Graphics Rendering Engine (version 1.7.3). 2011. Available at http:\/\/www.ogre3d.org\/."},{"key":"18_CR32","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-3-540-70918-3_3","volume":"4393","author":"D. Wagner","year":"2007","unstructured":"Wagner, D.; Willhalm, T. Speed-up techniques for shortest-path computations. Lecture Notes in Computer Science Vol. 4393, 23\u201336, 2007.","journal-title":"Lecture Notes in Computer Science"},{"key":"18_CR33","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1109\/ICRA.2014.6907070","volume-title":"2014 IEEE International Conference on Robotics and Automation","author":"F. M. Garcia","year":"2014","unstructured":"Garcia, F. M.; Kapadia, M.; Badler, N. I. GPU-based dynamic search on adaptive resolution grids. In: 2014 IEEE International Conference on Robotics and Automation, 1631\u20131638, 2014."}],"container-title":["Computational Visual Media"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/10750449\/10897397\/10897400.pdf?arnumber=10897400","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T18:38:23Z","timestamp":1762367903000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10897400\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6]]},"references-count":33,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1007\/s41095-015-0018-0","relation":{},"ISSN":["2096-0662","2096-0433"],"issn-type":[{"type":"electronic","value":"2096-0662"},{"type":"print","value":"2096-0433"}],"subject":[],"published":{"date-parts":[[2015,6]]}}}