Loading...
3 results
Search Results
Now showing 1 - 3 of 3
- Influence-based motion planning algorithms for gamesPublication . Amador, Gonçalo Nuno Paiva; Gomes, Abel João PadrãoIn games, motion planning has to do with the motion of non-player characters (NPCs) from one place to another in the game world. In today’s video games there are two major approaches for motion planning, namely, path-finding and influence fields. Path-finding algorithms deal with the problem of finding a path in a weighted search graph, whose nodes represent locations of a game world, and in which the connections among nodes (edges) have an associated cost/weight. In video games, the most employed pathfinders are A* and its variants, namely, Dijkstra’s algorithm and best-first search. As further will be addressed in detail, the former pathfinders cannot simulate or mimic the natural movement of humans, which is usually without discontinuities, i.e., smooth, even when there are sudden changes in direction. Additionally, there is another problem with the former pathfinders, namely, their lack of adaptivity when changes to the environment occur. Therefore, such pathfinders are not adaptive, i.e., they cannot handle with search graph modifications during path search as a consequence of an event that happened in the game (e.g., when a bridge connecting two graph nodes is destroyed by a missile). On the other hand, influence fields are a motion planning technique that does not suffer from the two problems above, i.e., they can provide smooth human-like movement and are adaptive. As seen further ahead, we will resort to a differentiable real function to represent the influence field associated with a game map as a summation of functions equally differentiable, each associated to a repeller or an attractor. The differentiability ensures that there are no abrupt changes in the influence field, consequently, the movement of any NPC will be smooth, regardless if the NPC walks in the game world in the growing sense of the function or not. Thus, it is enough to have a spline curve that interpolates the path nodes to mimic the smooth human-like movement. Moreover, given the nature of the differentiable real functions that represent an influence field, the removal or addition of a repeller/attractor (as the result of the destruction or the construction of a bridge) does not alter the differentiability of the global function associated with the map of a game. That is to say that, an influence field is adaptive, in that it adapts to changes in the virtual world during the gameplay. In spite of being able to solve the two problems of pathfinders, an influence field may still have local extrema, which, if reached, will prevent an NPC from fleeing from that location. The local extremum problem never occurs in pathfinders because the goal node is the sole global minimum of the cost function. Therefore, by conjugating the cost function with the influence function, the NPC will never be detained at any local extremum of the influence function, because the minimization of the cost function ensures that it will always walk in the direction of the goal node. That is, the conjugation between pathfinders and influence fields results in movement planning algorithms which, simultaneously, solve the problems of pathfinders and influence fields. As will be demonstrated throughout this thesis, it is possible to combine influence fields and A*, Dijkstra’s, and best-first search algorithms, so that we get hybrid algorithms that are adaptive. Besides, these algorithms can generate smooth paths that resemble the ones traveled by human beings, though path smoothness is not the main focus of this thesis. Nevertheless, it is not always possible to perform this conjugation between influence fields and pathfinders; an example of such a pathfinder is the fringe search algorithm, as well as the new pathfinder which is proposed in this thesis, designated as best neighbor first search.
- Real-time 3D rendering of water using CUDAPublication . Amador, Gonçalo Nuno Paiva; Gomes, Abel João PadrãoThis thesis addresses the real-time simulation of 3D water, both on the CPU and on the GPU. The stable fluids method is extended to 3D, and implemented both on the CPU and on the GPU. The GPU-based implementation is done using the NVIDIA Compute Unified Device Architecture API (Application Programming Interface), shortly CUDA. The stable fluids method requires the use of an iterative sparse linear system solver. Therefore, three solvers were implemented on both CPU and GPU, namely Jacobi, Gauss-Seidel, and Conjugate Gradient solvers. Rendering of water or its velocities, of the moving obstacles, of the static obstacles, and of the world are done using Vertex Buffer Objects (VBOs). In the CPU-based version standard OpenGL VBOs are used, while on the GPU-based version OpenGL-CUDA interoperability VBOs and standard OpenGL VBOs are used.
- xTrek: An Influence-Aware Technique for Dijkstra and A* PathfindersPublication . Amador, Gonçalo; Gomes, AbelWe propose a new pathfinding technique called xTrek that combines conventional pathfinding and influence fields; that is, we are introducing a new influence-sensitive pathfinder or influence-aware pathfinder. The leading idea of influence-aware pathfinding is to avoid unwanted regions and/or converge to desired regions of the search space during the path search. As shown throughout the paper, this region avoidance/convergence is more striking using our technique than in other field-aware pathfinders as, for example, risk-adverse pathfinders and constraint-aware navigation pathfinders. Furthermore, our technique constrains the search space even more than such state-of-the-art influence-aware pathfinders, aiming to reduce the memory space consumption, to speed up pathfinding computations, and at the same time to have better control on the paths to be discovered.