Generating routes for entities in virtual environments, such as simulated vehicles or synthetic human characters, is a long-standing problem, and route planning algorithms have been developed and studied for some time. Existing route planning algorithms, including the widely used A* algorithm, are generally intended to achieve optimality in some metric, such as minimum length or minimum time. Comparatively little attention has been given to route realism, defined as the similarity of the algorithm-generated route to the route followed by real humans in the same terrain with the same constraints and goals. Commercial game engines have seen increasing use as a context for research. To study route realism in a game engine, two developments were needed: a quantitative metric for measuring route realism and a game engine able to capture route data needed to compute the realism metric. Enhancements for recording route data for both synthetic characters and human players were implemented within the Unreal Tournament 2004 game engine. A methodology for assessing the realism of routes and other behaviors using a quantitative metric was developed. The enhanced Unreal Tournament 2004 game engine and the realism assessment methodology were tested by capturing data required to calculate a metric of route realism. 1. Introduction Entities in virtual environments, such as simulated vehicles or synthetic humans, move from place to place in the virtual environment. Algorithms to automatically generate those routes have been developed and studied for some time. The A* graph search algorithm, because of its simplicity and effectiveness, has been applied in a range of simulation environments, including Close Combat Tactical Trainer, Combat XXI, and OneSAF Objective System, and games such as Warcraft and Civilization; some of these applications use variants of the basic A* algorithm [4]. Most route planning algorithms, including A*, are designed to produce or approximate optimum routes, where optimality is measured in terms of some application-specific metric; examples include minimum distance for individual humans moving in urban terrain [5], minimum distance for vehicles moving in a road network [6], minimum exposure to threats for combatants moving in a battle area [7], or maximum sensor coverage for search platforms surveying a target area [8]. In contrast, very little attention has been given to producing realistic routes, where realism is defined as the similarity of the generated route to a route that would be followed by a real human in the same terrain with the
References
[1]
P. Fua, “McKenna MOUT Site, Fort Benning, Georgia,” 2009, http://www.ai.sri.com/~fua/rcvw/Benning.html.
[2]
D. R. Scribner and P. H. Wiley, “The development of a virtual McKenna Military Operations in Urban Terrain (MOUT) site for command, control, communication, computing, intelligence, surveillance, and reconnaissance (C4ISR) studies,” Tech. Rep. ARL-TR-4139, June 2007.
[3]
M. Dorfler, “Pogamut 2 IDE for Agents in UT2004,” 2009, https://artemis.ms.mff.cuni.cz/pogamut/tiki-index.php?page=Architecture/.
[4]
E. Beeker, “Potential error in the reuse of Nilsson’s a algorithm for path-finding in military simulations,” Journal of Defense Modeling and Simulation, vol. 1, no. 2, pp. 91–97, 2004.
[5]
Z. Shen and S. Zhou, “Behavior representation and simulation for military operations on urbanized terrain,” Simulation, vol. 82, no. 9, pp. 593–607, 2006.
[6]
J. E. Bell and P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Advanced Engineering Informatics, vol. 18, no. 1, pp. 41–48, 2004.
[7]
D. A. Reece, M. Kraus, and P. Dumanoir, “Tactical movement planning for individual combatants,” in Proceedings of the 9th Conference on Behavior Representation in Modeling and Simulation, pp. 301–308, Orlando, Fla, USA, May 2000.
[8]
D. R. Van Brackle, M. D. Petty, C. D. Gouge, and R. D. Hull, “Terrain reasoning for reconnaissance planning in polygonal terrain,” in Proceedings of the 3rd Conference on Computer Generated Forces and Behavioral Representation, pp. 285–306, Orlando, Fla, USA, March 1993.
[9]
D. Brogan and N. Johnson, “Realistic human walking paths,” in Proceedings of the Computer Animation and Social Agents, pp. 94–101, May 2003, New Brunswick, NJ, USA.
[10]
R. G. Burgess and C. J. Darken, “Realistic human path planning using fluid simulation,” in Proceedings of the 13th Conference on Behavior Representation in Modeling and Simulation, pp. 3–12, Arlington, Va, USA, May 2004.
[11]
D. E. Diller, W. Ferguson, A. M. Leung, B. Benyo, and D. Foley, “Behavior modeling in commercial games,” in Proceedings of the 13th Conference on Behavior Representation in Modeling and Simulation, pp. 257–268, Arlington, Va, USA, May 2004.
[12]
M. D. Petty, “Verification, validation, and accreditation,” in Modeling and Simulation Fundamentals: Theoretical Underpinnings and Practical Domains, J. A. Sokolowski and C. M. Banks, Eds., pp. 325–372, John Wiley & Sons, Hoboken, NJ, USA, 2010.
[13]
G. Hanold and D. Hanold, “Route generation for a synthetic character (BOT) using a partial or incomplete knowledge route generation algorithm in UT2004,” in MODSIM World, Virginia Beach, Va, USA, October 2009.
[14]
G. Hanold and D. Hanold, “A method for quantitative measurement of the realism of synthetic character (BOT) actions within the UT2004 virtual environment,” in MODSIM World, Virginia Beach, Va, USA, October 2009.
[15]
A. N. Marshall, J. Vaglia, J. M. Sims, and R. Rozich, “Unreal Tournament Java Bot,” 2006, http://sourceforge.net/projects/utbot.
[16]
F. Tence and C. Buche, “Automatable evaluation method oriented toward behaviour believability for video games,” in Proceedings of the 9th International Conference on Intelligent Games and Simulation, Valencia, Spain, November 2008.
[17]
M. R. Stytz and S. B. Banks, “Considerations for human behavior modeling interoperability within simulation environments,” in Proceedings of the Fall Simulation Interoperability Workshop, Orlando, Fla, USA, September 2006.
[18]
G. T. Hanold and M. D. Petty, “Developing a modeling and simulation environment and methodology for the measurement and validation of route realism,” in Proceedings of the Huntsville Simulation Conference, Huntsville, Ala, USA, October 2010.