Transcript pptx
Review IMGD 4000 Engine Architecture Types • Broadly, what are the two architecture types discussed for game engines? • What are the differences? Pathfinding with Waypoints • What is one potential problem with pathfinding using waypoints? • What is a potential fix to the problem above? Pathfinding with Waypoints • What is one potential problem with pathfinding using waypoints? Ans: blind spots, waypoint generation, kinky paths • What is a potential fix to the problem above? Ans: fine-grained graphs, flood fill, path smoothing Pathfinding with a NavMesh • Is a Navmesh a replacement for A*? Why or why not? Pathfinding with a NavMesh • Is a Navmesh a replacement for A*? Why or why not? Ans: No. A Navmesh is a replacement for a waypoint graph. Instead of points, the graph nodes are polygons, covering the walkable area. A* can still be used to chart the path. Tuning Pathfinding • Sketch you how might you “time slice” to limit the CPU load of pathfinding Tuning Pathfinding • Sketch you how might you “time slice” to limit the CPU load of pathfinding Ans: Divide search algorithm into “cycles” (e.g., one ply). Create a PathPlanner that stores progress along path and registers search with game engine (Path Manager). Object requests path to destination with PathPlanner. Create a PathManager that allocates out “cycles” to registered PathPlanners. Game engine (PathManager) allows for fixed number of cycles per tick. Camera Control • Related to advanced camera control: – What is “zoning”? – What are “dynamics”? – What is “blending”? – What are “rails”? Camera Control • Describe the design of a camera zoning approach. • How can you design camera dynamics not to move the camera with every movement of the player? Camera Control • What is blending? • As part of blending, what is ease? Basic Game AI • What is a decision tree? • What are strengths vs. weaknesses? • What is a hierarchical finite state machine? Why use it versus a “flat” state machine? • Where is the “knowledge” in the above? How else might we approach AI? Examples? Autonomous Movement • What are the three main components of the “steering” model? What does each do? Autonomous Movement • What are the three main components of the “steering” model? What does each do? Ans: Action Selection – chose goals and plans Steering – Calculate trajectories, apply forces Locomotion – apply mechanics of motion Steering force for Seek • Given a vehicle with mass and velocity and a target, describe how “seek” works Steering force for Seek • Given a vehicle with mass and velocity and a target, describe how “seek” works Ans: target velocity desired velocity steering force Combining Forces • What is the blended approach to combining steering forces? • What is the prioritized approach to combining steering forces? Combining Forces • What is the blended approach to combining steering forces? Ans: All steering forces are called, with weights providing balance • What is the prioritized approach to combining steering forces? Ans: Steering forces are prioritized, called in order until one or max force is reached Basic Game Physics • What does step size matter when simulating game physics? Basic Game Physics • What does step size matter when simulating game physics? – Step size determines how often objects in the game governed by physics principles are updated. When using approximations, such as numerical integration, more frequent updates result in less error, but at the cost of more CPU overhead. Basic Game Physics • How can physics step size be decoupled from frame rate/game loop rate? Basic Game Physics • How can physics step size be decoupled from frame rate/game loop rate? – Provide for a step rate less than the frame rate – Each time the physics update is called, calculate how long it has been since the last update. Divide that time by the step rate. – Perform physics updates at the step rate until “caught up” to the current time (close enough to be less than one step size) Collision Detection • What is intersection testing? Collision Detection • What is intersection testing? – A form of collision detection where an object is extruded from current location to predicted location at the end of the step – This new volume is checked for overlap with other objects. If there is an overlap, there is a collision. – The location of the overlap provides the location of the collision and can be used to compute the time. Collision Detection • Using overlap testing, how can you determine exactly when/where the collision occurred? Collision Detection • Using overlap testing, how can you determine exactly when/where the collision occurred? – A common technique is to use binary search where the time delta is backed up by half and rechecked. If collision, back up by half again. If no collision, go forward by half. – Continue until “close enough” (within a delta) – typically about 5 iterations.