Après tout, ils sont chez Pixar aujourd’hui…
Avoir des agents intelligents qui apprennent en temps réels, qui sont capables de prendre des décisions informées, un rêve d’intelligence artificielle :
In this paper, we consider a simultaneous planning and learning problem. One motivating application lies with navigation on an initially unknown map under real-time constraints.
As an example, consider a robot driving to work every morning. Imagine the robot to be a newcomer to the town. The first route the robot finds may not be optimal because traffic jams, road conditions, and otherfactors are initially unknown. With the passage of time, the robot continues to learn and eventually converges to a nearly optimal commute.
Note that planning and learning happen while the robot is driving and therefore are subject to time constraints.
Present-day mobile robots are often plagued by localization problems and power limitations, but their simulation counter-parts already allow researchers to focus on the planning and learning problem. For instance, the RoboCup Rescue simulation league (Kitano, Tadokoro, Noda, Matsubara,Takahashi, Shinjou, & Shimada, 1999) requires real-time planning and learning with multiple agents mapping out an unknown terrain.
Pathfinding is done in real time as various crises, involving fire spread and human victims trapped in rubble, progress while the agents plan.
Similarly, many current-generation real-time strategy games employ a priori known maps. Full knowledge of the maps enables complete search methods such as A* (Hart, Nilsson, & Raphael,BULITKO & LEE1968) and Dijkstra’s algorithm (Dijkstra, 1959).
Prior availability of the maps allows pathfinding engines to pre-compute various data to speed up on-line navigation.
Examples of such data include visibility graphs (Woodcock, 2000), influence maps (Pottinger, 2000), space triangulation (Kallmann,Bieri, & Thalmann, 2003), state abstraction hierarchies (Holte, Drummond, Perez, Zimmer,& MacDonald, 1994; Holte, 1996; Botea, M¨uller, & Schaeffer, 2004) and route waypoints (Reece,Krauss, & Dumanoir, 2000).
However, the forthcoming generations of commercial and academic games (Buro, 2002) will require the agent to cope with initially unknown maps via explorationand learning during the game, and therefore will greatly limit the applicability of complete search algorithms and pre-computation techniques.
Incremental search methods such as dynamic A* (D*) (Stenz, 1995) and D* Lite (Koenig &Likhachev, 2002) can deal with initially unknown maps and are widely used in robotics, including DARPA’s Unmanned Ground Vehicle program, Mars rover, and other mobile robot prototypes (Herbert,McLachlan, & Chang, 1999; Thayer, Digney, Diaz, Stentz, Nabbe, & Hebert, 2000). They work well when the robot’s movements are slow with respect to its planning speed (Koenig, 2004).
In real-time strategy games, however, the AI engine can be responsible for hundreds to thousands
of agents traversing a map simultaneously and the planning cost becomes a major factor. To illustrate:
even at the smaller scale of the six-year old “Age of Empires 2” (Ensemble-Studios, 1999),
60-70% of simulation time is spent in pathfinding (Pottinger, 2000). This gives rise to the following
1. How can planning time per move, and particularly the first-move delay, be minimized so that each agent moves smoothly and responds to user requests nearly instantly?2. Given real-time execution, local sensory information, and initially unknown terrain, how can the agent learn a near-optimal path and, at the same time, minimize the learning time and memory required?
De plus, le rendu volumique est très en vogue dans l’industrie lourde (médecine, recherche…). Raison de plus pour rester à jour.
Les fluides sont l’une des dernières technologies à être introduite à la boite à outils de la physique temps réel. Joe Stam avait déjà débroussaillé le sujet il y a quelques années à la GDC.
In this paper we present a simple and rapid implementation of a fluid dynamics solver for game engines. Our tools can greatly enhance games by providing realistic fluid-like effects such as swirling smoke past a moving character. The potential applications are endless. Our algorithms are based on the physical equations of fluid flow, namely the Navier-Stokes equations. These equations are notoriously hard to solve when strict physical accuracy is of prime importance. Our solvers on the other hand are geared towards visual quality. Our emphasis is on stability and speed, which means that our simulations can be advanced with arbitrary time steps. We also demonstrate that our solvers are easy to code by providing a complete C code implementation in this paper. Our algorithms run in real-time for reasonable grid sizes in both two and three dimensions on standard PC hardware, as demonstrated during the presentation of this paper at the conference.
[ RTFD ]
Une technique très belle de collage d’image !
We present a user-friendly system for seamless image composition, which we call drag-and-drop pasting. We observe that for Poisson image editing to work well, the user must carefully draw a boundary on the source image to indicate the region of interest, such that salient structures in source and target images do not conflict with each other along the boundary. To make Poisson image editing more practical and easy to use, we propose a new objective function to compute an optimized boundary condition. A shortest closed-path algorithm is designed to search for the location of the boundary. Moreover, to faithfully preserve the object's fractional boundary, we construct a blended guidance field to incorporate the object's alpha matte. To use our system, the user needs only to simply outline a region of interest in the source image, and then drag and drop it onto the target image.
La simulation sonore réaliste est peu être l’une des prochaines frontières techniques que les jeux auront à dépasser. C’est un problème ardu car peu connu par les développeurs d’aujourd’hui. Ce papier semble plutôt prometteur…
Simulating sounds produced by realistic vibrating objects is challenging because sound radiation involves complex diffraction and interreflection effects that are very perceptible and important. These wave phenomena are well understood, but have been largely ignored in computer graphics due to the high cost and complexity of computing them at audio rates. We describe a new algorithm for real-time synthesis of realistic sound radiation from rigid objects.
[ PAT ]
Quelle évolution depuis GLIDE ! Les shaders sont désormais indispensable, et maintenant qu’ils vont être disponible dans l’espace console, j’ai hâte de voir le résultat. Quoi qu’il en soit, voici une technique pour ajouter du détail et du contraste à une scène.
We investigate a non-photorealistic shading model, inspired by techniques for cartographic terrain relief, based on dynamically adjusting the effective light position for different areas of the surface. It reveals detail regardless of surface orientation and, by operating at multiple scales, is designed to convey detail at all frequencies simultaneously.
La théorie des couleurs et l’harmonie sont souvent sous-estimées. La notion d’harmonie est en soi fascinante, alors j’ai trouvé ce papier très intéressant. Harmoniser automatiquement une image est une opération qui peut être très utile, en particulier si elle est simple d’utilisation pour le grand public.
La gestion de la foule est en train de devenir un problème majeur, mais a la portée de nos technologies. Voici un excellent papier sur le sujet :
Human crowds are ubiquitous in the real world, making their simulation a necessity for realistic interactive environments. We present a real-time crowd model based on continuum dynamics. In our model, a dynamic potential field simultaneously integrates global navigation with moving obstacles such as other people, efficiently solving for the motion of large crowds without the need for explicit collision avoidance. Simulations created with our system run at interactive rates, demonstrate smooth flow under a variety of conditions, and naturally exhibit emergent phenomena that have been observed in real crowds.
[ Crowd Flows ]
La réduction automatique de la complexité des simulations physiques a beaucoup d'avenir, et c'est le sujet du papier du jour:
Computer graphics researchers have made great strides towards simulation of complex phenomena for special effects and other off-line applications. A much less explored but equally important domain is interactive virtual worlds including training simulations, computer games, and other situations where interactivity is required. This project explores the use of model reduction to achieve drastically faster simulations of complex, high-dimensional phenomena. Our current work focuses on incompressible fluids. Within this context we have found that:
- Speedups of up to 5 orders of magnitude are possible.
- Kinetic energy can be preserved.
- Moving objects can be correctly incorporated into the flow.