AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Computational Visual Media Article
PDF (1.5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Research Article | Open Access

Subregion graph: A path planning acceleration structure for characters with various motion types in very large environments

Nicholas Mario Wardhana1,2( ), Henry Johan3, Hock Soon Seah1,2
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.
Fraunhofer IDM@NTU, Nanyang Technological University, NS1-1 Level 5, 50 Nanyang Avenue, Singapore, 639798.
Show Author Information

Abstract

Abstract 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 graph-based 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%.

Keywords

path planning accelerationvery large environmentsmotion typesabstraction

Electronic Supplementary Material

Video
41095_2015_18_MOESM2_ESM.mp4
Download File(s)
41095_2015_18_MOESM1_ESM.pdf (2.3 MB)

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. In: Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 3868–3873, 2005.
Crossref
[5]
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.
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[14]
Hilger, M.; Köhler, E.; Möhring, 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–72, 2009.
Crossref Google Scholar
[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.
Crossref Google Scholar
[17]
Harabor, D.; Botea, A. Hierarchical path planning for multi-size agents in heterogeneous environments. In: IEEE Symposium on Computational Intelligence and Games, 258–265, 2008.
Crossref
[18]
Mould, D.; Horsch, M. C. A hierarchical terrain representation for approximately shortest paths. Lecture Notes in Computer Science Vol. 3157, 104-113, 2004.
Crossref Google Scholar
[19]
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–111, 2004.
[20]
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–143, 2006.
Crossref
[21]
Sanders, P.; Schultes, D. Highway hierarchies hasten exact shortest path queries. Lecture Notes in Computer Science Vol. 3669, 568-579, 2005.
Crossref Google Scholar
[22]
Floyd, R. W. Algorithm 97: Shortest path. Communications of the ACM Vol. 5, No. 6, 345, 1962.
Crossref Google Scholar
[23]
Warshall, S. A theorem on boolean matrices. Journal of the ACM Vol. 9, No. 1, 11-12, 1962.
Crossref Google Scholar
[24]
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–165, 2005.
[25]
Felner, A.; Sturtevant, N.; Schaeffer, J. Abstraction-based heuristics with true distance computations. In: Proceedings of the Eighth Symposium on Abstraction, Reformulation, and Approximation, 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.
Crossref Google Scholar
[27]
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–3532, 2011.
Crossref
[28]
Dijkstra, E. W. A note on two problems in connexion with graphs. Numerische Mathematik Vol. 1, No. 1, 269-271, 1959.
Crossref Google Scholar
[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/.
Crossref
[32]
Wagner, D.; Willhalm, T. Speed-up techniques for shortest-path computations. Lecture Notes in Computer Science Vol. 4393, 23-36, 2007.
Crossref Google Scholar
[33]
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–1638, 2014.
Crossref
Computational Visual Media
Volume 1 Issue 2,
June 2015
Pages 105-118
DOI: 10.1007/s41095-015-0018-0
Cite this article:
Wardhana NM, Johan H, Seah HS. Subregion graph: A path planning acceleration structure for characters with various motion types in very large environments. Computational Visual Media, 2015, 1(2): 105-118. https://doi.org/10.1007/s41095-015-0018-0

674

Views

17

Downloads

1

Crossref

N/A

Web of Science

2

Scopus

0

CSCD

Altmetrics
Revised: 16 August 2015
Accepted: 29 August 2015
Published: 16 October 2015
© The Author(s) 2015

This article is published with open access at Springerlink.com

This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.
Return