×

Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments. (English) Zbl 1428.68328

Summary: Modern computer graphics applications commonly feature very large virtual environments and diverse characters which perform different kinds of motions. To accelerate path planning in such a scenario, we propose the subregion graph data structure. It consists of subregions, which are clusters of locally connected waypoints inside a region, as well as subregion connectivities. We also present a fast algorithm to automatically generate a subregion graph from an enhanced waypoint graph map representation, which also supports various motion types and can be created from large virtual environments. Nevertheless, a subregion graph can be generated from any graphbased map representation. Our experiments show that a subregion graph is very compact relative to the input waypoint graph. By firstly planning a subregion path, and then limiting waypoint-level planning to this subregion path, over 8 times average speedup can be achieved, while average length ratios remain as low as 102.5%.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science

Software:

BGL; Algorithm 97; Boost
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Grand Theft Auto III (DVD). Rockstar Games, 2001.
[2] Just Cause II(Steam). Eidos Interactive, 2010. Available at http://store.steampowered.com/app/81901.
[3] The Elder Scrolls V: Skyrim (Steam). Bethesda Softworks, 2011. Available at http://store.steampowered.com/app/7282501.
[4] Plaku, E.; Kavraki, L. E., Distributed sampling-based roadmap of trees for large-scale motion planning, 3868-3873 (2005) · doi:10.1109/ROBOT.2005.1570711
[5] Samperi, K.; Hawes, N.; Beale, R., Improving map generation in large-scale environments for intelligent virtual agents (2013)
[6] 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-1062, 2013. · doi:10.1007/s00371-013-0837-x
[7] 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-107, 1968. · doi:10.1109/TSSC.1968.300136
[8] Holtë, 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-2, 321-361, 1996. · doi:10.1016/0004-3702(95)00111-5
[9] Sturtevant, N.; Buro, M. Partial pathfinding using map abstraction and refinement. In: Proceedings of the 20th National Conference on Artificial Intelligence, Vol. 3, 1392-1397, 2005.
[10] 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-100, 2007. · Zbl 1183.68222
[11] Frederickson, G. N. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing Vol. 6, No. 6, 1004-1022, 1987. · Zbl 0654.68087 · doi:10.1137/0216064
[12] Köhler, E.; Möhring, R. H.; Schilling, H. Acceleration of shortest path and constrained shortest path computation. Lecture Notes in Computer Science Vol. 3503, 126-138, 2005. · Zbl 1121.90413 · doi:10.1007/11427186_13
[13] Wagner, D.; Willhalm, T. Geometric speedup techniques for finding shortest paths in large sparse graphs. Lecture Notes in Computer Science Vol. 2832, 776-787, 2003. · Zbl 1266.68234 · doi:10.1007/978-3-540-39658-1_69
[14] Hilger, M.; Köhler, E.; Möhring, R. H.; Schilling, H.; Demetrescu, C. (ed.); Goldberg, A. V. (ed.); Johnson, D. S. (ed.), Fast point-to-point shortest path computations with arc-flags, 41-72 (2009) · Zbl 1204.90114
[15] Lauther, U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background. In: Geoinformation und Mobilität-von der Forschung zur praktischen Anwendung, Vol. 22, 219-230, 2004.
[16] Möhring, R. H.; Schilling, H.; Schütz, B.; Wagner, D.; Willhalm, T. Partitioning graphs to speed up Dijkstra’s algorithm. Lecture Notes in Computer Science Vol. 3503, 189-202, 2005. · Zbl 1121.68356 · doi:10.1007/11427186_18
[17] Harabor, D.; Botea, A., Hierarchical path planning for multi-size agents in heterogeneous environments, 258-265 (2008)
[18] Mould, D.; Horsch, M. C. A hierarchical terrain representation for approximately shortest paths. Lecture Notes in Computer Science Vol. 3157, 104-113, 2004. · doi:10.1007/978-3-540-28633-2_13
[19] Gutman, R. J., Reach-based routing: A new approach to shortest path algorithms optimized for road networks, 100-111 (2004)
[20] Goldberg, A. V.; Kaplan, H.; Werneck, R. F., Reach for A*: Efficient point-to-point shortest path algorithms, 129-143 (2006) · Zbl 1428.68215
[21] Sanders, P.; Schultes, D. Highway hierarchies hasten exact shortest path queries. Lecture Notes in Computer Science Vol. 3669, 568-579, 2005. · Zbl 1162.68505 · doi:10.1007/11561071_51
[22] Floyd, R. W. Algorithm 97: Shortest path. Communications of the ACM Vol. 5, No. 6, 345, 1962. · doi:10.1145/367766.368168
[23] Warshall, S. A theorem on boolean matrices. Journal of the ACM Vol. 9, No. 1, 11-12, 1962. · Zbl 0118.33104 · doi:10.1145/321105.321107
[24] Goldberg, A. V.; Harrelson, C., Computing the shortest path: A* search meets graph theory, 156-165 (2005) · Zbl 1297.05230
[25] Felner, A.; Sturtevant, N.; Schaeffer, J., Abstractionbased heuristics with true distance computations, 74-81 (2009)
[26] Oliva, R.; Pelechano, N. NEOGEN: Near optimal generator of navigation meshes for 3D multi-layered environments. Computers & Graphics Vol. 37, No. 5, 403-412, 2013. · doi:10.1016/j.cag.2013.03.004
[27] Toll, W. G.; Cook, I. A. F.; Geraerts, R., Navigation meshes for realistic multi-layered environments, 3526-3532 (2011)
[28] Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik Vol. 1, No. 1, 269-271, 1959. · Zbl 0092.16002 · doi:10.1007/BF01386390
[29] Pinter, M. Toward more realistic pathfinding. 2001. Available at http://www.gamasutra.com/features/20010314/pinter_01.htm.
[30] Siek, J.; Lee, L.-Q.; Lumsdaine, A. The Boost Graph Library (BGL) (version 1.57). 2014. Available at http://www.boost.org/libs/graph/.
[31] The OGRE Team. OGRE—Object-oriented Graphics Rendering Engine (version 1.7.3). 2011. Available at http://www.ogre3d.org/.
[32] Wagner, D.; Willhalm, T. Speed-up techniques for shortest-path computations. Lecture Notes in Computer Science Vol. 4393, 23-36, 2007. · Zbl 1186.68594 · doi:10.1007/978-3-540-70918-3_3
[33] Garcia, F. M.; Kapadia, M.; Badler, N. I., GPU-based dynamic search on adaptive resolution grids, 1631-1638 (2014) · doi:10.1109/ICRA.2014.6907070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.