AI: Movement - Introduction The AI Model For Game

1y ago
67 Views
393.43 KB
88 Pages
Last View : 1d ago
Transcription

AI: Movement - Introduction The AI model for game architecture:– Movement is the most basic component of the model Movement is distinguished from animation– Movement is a large-scale operation It deals with getting agent from one position to another– Animation represents a smaller scale Concerned with the details of how agent’s components transform This aspect not driven by the AI1

AI: Movement - Introduction (2) The movement algorithm is represented by the following flow chart– Input is geometric data Represents both the agent’s and world’s states– Output is also geometric data representing the agent’s and world’s states– Actual io parameters and outputs depend on context Movement can be categorized as kinematic or dynamic (a steering behavior)1. Kinematic– Does not consider acceleration– Is essentially one-speed– Agent starts at full speed, moves to desired location, and stops2

AI: Movement - Introduction (3)2. Steering behavior– Referred to as dynamic since it changes with time Physics-based– Called steering behavior because it controls direction of agent Term coined by Craig Reynolds, who developed flocking behavioralgorithm– Algorithm requires agent’s current position, velocity, and forces actingon the agent– Output is resultant force or acceleration acting on agent– The output is used to modify the agent’s current velocity– the overall behavior for an agent at rest: The agent accelerates to speed Cruises til nears destination Decelerates to a stop Vectors– Will need a data structure to represent vectors, as they have many uses:direction, velocity, acceleration, etc.– A data structure that represents vectors should include1. Data members(a) x component(b) z component(c) magnitude (length), computed as v x2 z 22. Methods(a) normalize(), which converts a vector into a unit vector Tv̂ x/magnitude z/magnitude(b) Vector addition Tv v1 v2 x1 x2 z1 z2where T T, v2 x2 z2v1 x1 z1(c) Scalar multiplication T Tv n x z n x n z3

AI: Movement - Introduction (4) Representation1. Static representation– This represents agent position and orientation with no motion data(a) 2D representationi. Agent modeled as a 2D point wrt movementii. Movement is in x-z planeiii. Orientation is represented as an angle between the z-axis and thevector to the agent (rotation about y-axis) Assumes a right-handed coordinate system(b) 2.5D representation Position represented as a 3D point Orientation represented as in 2D Providing agent remains upright, can disregard orientation wrt yand x-axes· Simplifies math considerably y coordinate ignored except when agent jumps, falls, or climbs4

AI: Movement - Introduction (5)– An alternative is to represent orientation as a unit vector Tω̂ sin ωs cos ωs– Implementation Data members would include(a) A point data type for position(b) A float for the orientation Optionally, you would want to provide a way for generating the vectorrepresentation of the orientation(a) It could be another data member, or(b) A method that converts the float representation to a vector (asindicated above)5

AI: Movement - Introduction (6)2. Kinematic representation– Velocity/motion data is now incorporated Have both linear ( motion) and angular ( orientation) Linear represented as a vector: ( x, z) per second Angular (rotation) represented as radians/degrees per second– Implementation Data members would include(a) A point data type for position(b) A float for the orientation(c) A vector for the velocity(d) A float for the rotation Do not confuse orientation and rotation· Orientation is a direction in which the agent is facing· Rotation is the rate of change of the orientation6

AI: Movement - Introduction (7) Steering behaviors return accelerations for linear and angular change– Implementation of steering data structure Data members would include, in addition to static members,1. A vector for the linear acceleration2. A float for the angular acceleration– Given a linear acceleration, change in position can be calculated using P vt 12 at2– Since t2 is generally very small, the Newton-Euler 1 integration update isfrequently used instead P vt– Frame rate can be used in place of time if a steady frame rate is maintained Using time allows for calculations that produce steady p based onactual update times– The kinematic representation can be modified using the following algorithmupdate (Steering s, float t){position velocity * t;orientation rotation * t;velocity s.linearAcceleration * t;rotation s.angularAcceleration() * t;} The steering data would be returned to the agent by some behavior thatthe agent is executing– Orientation There is nothing that requires an agent to face the direction of motion,but it is usually desired When agent changes direction, could simply change orientation accordingly, but this is unrealistic A simple algorithm is to have the agent rotate by one half the angulardifference between the heading and orientation over a sequence of frames7

AI: Movement - Kinematic Movement Algorithms - Intro These take static agent (and target) data as input and output a velocity– They do not use acceleration, but may smooth changes in v Simple orientation– Generates a new orientation aligned with a new direction of motion– AlgorithmgetNewOrientation(orientation, velocity){if (velocity.magnitude ! 0.0)return arctan(velocity.x/velocity.z);elsereturn orientation;}– If v 0, the current orientation is maintained For kinematic movement, must use static model for kinematic Steering output,since kinematic motion does not involve accelerations– Implementation of kinematic steering data structure Data members would include1. A vector for the velocity2. A float for the orientation The assumption would be that behaviors are implemented as classes in anobject-oriented language8

AI: Movement - Kinematic Movement Algorithms - Behaviors1. Kinematic seek behavior Data members(a) Static information (position, orientation) for the agent and target(b) Max speed of agent Methods(a) getSteering()– AlgorithmgetSteering (target){KinematicSteering s;s.velocity target.position - agent.position;s.velocity.normalize();s.velocity * maxSpeed;s.orientation 0.0;return s;}– Note: The text includes a call to getNewOrientation() method This method should be part of the agent’s code to be consistentwith steering behavior implementation2. Kinematic flee behavior Same as kinematic seek behavior, but with sign of v reversed3. Kinematic arriving behavior Kinematic seek is intended for pursuing a fleeing target– Agent never catches up If the agent can catch or arrive at the target, the behavior will need to bemodified– Since the agent moves at max speed, it will tend to overshoot the target,which will result in oscillation around the target9

AI: Movement - Kinematic Movement Algorithms - Behaviors (2) Solutions:(a) Agent stops when within some predefined radius of target(b) Agent slows down as nears target– This can still cause oscillation, but not as severe(c) Combine both of the above– Have a large radius to signal start of speed reduction– Have a smaller radius for stopping Text deceleration algorithm based on a fixed time-to-target Implementation– Data members(a) Static information (position, orientation) for the agent and target(b) Maximum velocity(c) Radius that signals when to start slowing down(d) An arbitrary time that indicates how long it should take the agent toreach the target10

AI: Movement - Kinematic Movement Algorithms - Behaviors (3)– Methods(a) getSteering() AlgorithmgetSteering (target){KinematicSteering s;s.velocity target.position - agent.position;if (s.velocity.magnitude radius)return null;s.velocity / timeToTarget;if (s.velocity.magnitude maxSpeed){s.velocity.normalize();s.velocity * maxSpeed;}s.orientation 0.0;return s;} The net effect of the getSteering() computations for v is demonstrated by the following exampleConsider agent at (0, 0) and target at (64, 0)Agent’s max speed 16Time to target 2time012 3 4 5distance to target644832 16 8 4v32 16 24 16 16 8 4 211

AI: Movement - Kinematic Movement Algorithms - Behaviors (4)4. Wandering behavior The agent simply travels at max speed in the direction of the current orientation– As the name implies, the orientation varies randomly– This is implemented by the steering method Implementation– Data members(a) Static information (position, orientation) for the agent(b) Maximum velocity(c) Maximum rotation– Methods(a) getSteering() AlgorithmgetSteering (target){KinematicSteering s;s.velocity agent.orientation(vector rep) * maxSpeed;s.orientation randomBinomial() * maxRotation;return s;}(b) randomBinomial() Method randomBinomial() returns a value 1.0 x 1.0, generating values near 0.0 with greater probability AlgorithmrandomBinomial (){return random() - random();}12

AI: Movement - Steering Behaviors, Introduction These behaviors incorporate acceleration (both linear and angular) and compute changes in each All behaviors are based on the kinematic data of the agent (and target, ifwarranted)– Implementation1. Data members would include(a) A point data type for position(b) A float for the orientation(c) A vector for the velocity(d) A float for the rotation(e) A float for the max speed2. Methods would include(a) getSteering() This returns a steering object that containsi. Accelerationii. Rotation– Agents will include an update() method This method use the results of the steering behavior to compute a newvelocity and orientation update()update (Steering s, float maxSpeed, float time){//Update posn and orientationposition velocity * time;orientation rotation * time;//Update v and rotationvelocity s.linearAcceleration * time;rotation s.angularRotation * time;//Clamp vif (velocity.magnitude maxSpeed) {velocity.normalize();velocity * maxSpeed;}}.} Some behaviors will require multiple target inputs13

AI: Movement - Steering Behaviors, Introduction (2) Steering behaviors are hierarchical– Start with a set of primitives– More complex behaviors arise by combining results of multiple primitivebehaviors that an agent is executing– Generally do not create specific complex behaviors Variable matching– Term given to behaviors that try to match one or more kinematic elementsof an agent with the corresponding ones of the target E.g., orientation, v, position– Generally a behavior will match only one If try to match several, frequently results in conflicts E.g., position and v14

AI: Movement - Steering Behavior Primitives, Seek and Flee Seek will1. Calculate direction to target (like kinematic case)2. Accelerate to max speed in that direction3. If v vM ax, v is clamped to vM ax– Note that this is done after the fact, and not by the steering behavior Drag can also be taken into account– Drag imposes a limit on the max speed an agent can attain It eliminates the need to check if v has exceeded the max– If the target is moving, the agent will spiral in toward the target and orbitaround it With drag, the orbiting is eliminated15

AI: Movement - Steering Behavior Primitives, Seek and Flee (2) Implementation– Data members1. agent: Kinematic information (position, orientation, v, rotation) for theagent2. target: Kinematic information for the target– Methods1. getSteering() AlgorithmgetSteering (target){KinematicSteering s;s.linearAcceleration target.position - linearAcceleration * maxAcceleration;s.rotation 0.0;return s;} Orientation is not included since it is its own behavior Flee– Like its kinematic counterpart, flee is simply seek with the sign of v reversed16

AI: Movement - Steering Behavior Primitives, Arrive and Leave As discussed above, the target of seek is assumed to be moving– If the agent catches the target, it will spiral in and orbit the target– Arrive is designed to stop when it reaches the target When nearing the target, the agent will decelerate– The algorithm will use two radii1. One to signal the beginning of deceleration2. One to signal a distance acceptably close for stopping– The speed up to the outer radius is maxSpeed– The speed anywhere within the inner radius is 0– Speed is interpolated between the two radii Target v is determined based on time, and a is adjusted accordingly Implementation– Data members1.2.3.4.agent and target: Agent and target kinematic datamaxAcceleration, maxVelocity: Acceleration and velocity limits of agentinnerRadius and outerRadius: Arrive and slow radiitimeToTarget: Time alloted for reaching target17

AI: Movement - Steering Behavior Primitives, Arrive and Leave (2)– Methods1. getSteering() AlgorithmgetSteering (target){kinematicSteering s;direction target.position - agent.position;distance direction.magnitude;if (distance innerRadius)return null;if (distance outerRadius)targetSpeed maxSpeed;elsetargetSpeed maxSpeed * distance / outerRadius;targetVelocity y * targetSpeed;s.linearAcceleration targetVelcocity - agent.velocity;s.linearAcceleration / timeToTarget;if (s.linearAcceleration.magnitude maxAcceleration) tion * maxAcceleration;}s.rotation 0.0;return s;} Leave– This is not the opposite of arrive– This behavior most likely wants to reach max accerelation immediately,rather than slowly speeding up– A more appropriate opposite is flee18

AI: Movement - Steering Behavior Primitives, Align Tries to match agent’s orientation with that of target Acts like arrive– Want rotation 0 when reach target value Do not want to simply perform target.orientation agent.orientation– Must take into account the fact that the agent could rotate clockwise orcounterclockwise to match the target’s orientation– Unless the rotation is π, one will be smaller than the other– Want the agent’s rotation to be in range [ π, π]– Can take advantage of the fact that rotation resets every 2π radiansLet φ θ ωif π φ π, φ φif φ π, φ φ 2πif φ π, φ φ 2π19

AI: Movement - Steering Behavior Primitives, Align (2) Like arrive, use two ”radii”– Are actually intervals, since orientation is a scalar Implementation– Data members1.2.3.4.agent and target: Agent and target kinematic datamaxAcceleration, maxRotation: Acceleration and rotation limits of agentinnerRadius and outerRadius: Arrive and slow radiitimeToTarget: Time alloted for reaching target20

AI: Movement - Steering Behavior Primitives, Align (3)– Methods1. getSteering() AlgorithmgetSteering (target){kinematicSteering s;rotation target.orientation - agent.orientation;rotation mapToRange(rotation);rotationSize abs(rotation);if (rotationSize innerRadius)return null;if (rotationSize outerRadius)targetRotation maxRotation;elsetargetRotation maxRotation * rotationSize / outerRadius;targetRotation * rotation / rotationSize;//**incorporate directions.angularAcceleration targetRotation - agent.rotation;s.angularAcceleration / timeToTarget;angularAcceleration abs(s.angularAcceleration);if (s.angularAcceleration.magnitude maxAngularAcceleration) {s.angularAcceleration / angularAcceleration;s.angularAcceleration * maxAngularAcceleration;}s.linearAcceleration 0.0;return s;} The linesangularAcceleration abs(s.angularAcceleration);s.angularAcceleration / angularAcceleration;normalize the angular acceleration2. mapToRange() AlgorithmmapToRange(float rotation){if (rotation PI)return rotation - 2 * PI;if (rotation -PI)return rotation 2 * PI;return rotation;} LookAway– Simply add π to result of Align, and use that as the target rotation21

AI: Movement - Steering Behavior Primitives, Velocity Matching Refers to having agent move with same velocity as target Text notes it is most important when dealing with combined behaviors (seefollowing topics) Arrive behavior can be modified to achieve this Implementation– Data members1. agent and target: Agent and target kinematic data2. maxAcceleration, maxRotation: Acceleration and rotation limits of agent3. timeToTarget: Time alloted for reaching target– Methods1. getSteering() AlgorithmgetSteering (target){kinematicSteering s;s.linearAcceleration target.velocity - agent.velocity;s.linearAcceleration / timeToTarget;if (s.linearAcceleration.magnitude maxAcceleration) tion * maxAcceleration;}s.rotation (0.0);return s;}22

AI: Movement - Delegated Steering Behaviors, Introduction This type of behavior delegates actions to other behaviors It calculates a target value (e.g., position, orientation, velocity), and calls onanother behavior to generate the steering output This effectively represents a hierarchy of behaviors The text implements these in terms of inheritance23

AI: Movement - Delegated Steering Behaviors, Pursue and Evade In Seek, an agent moves toward a target based on the target’s position– When the target is moving - assumed by Seek - the agent is alway movingtoward a location that the target will no longer be occupying by the timethe agent gets there Pursue attempts to predict where the target is heading, and determines anintercepting direction based on the target’s current position and velocity The algorithm presented here is based on the one developed by Craig Reynolds– It assumes the target will maintain its current velocity in the short term– Steps:1. Find distance to target2. Find time to target if travel at max speed This is used as the look ahead time3. Determine the target’s position at the end of this time (assuming currentvelocity) This is the target for the agent– The result is that the agent will make a series of adjustments as it closesin on target– Since the calculated time could be large, and the target may try evasivemaneuvers, want a limit on the time Pursue delegates to Seek24

AI: Movement - Delegated Steering Behaviors, Pursue and Evade (2) Implementation– Data members1. agent and target: Agent and target kinematic data2. maxPredictionTime: Look ahead time limit3. newTarget: a simulated target that represents the goal the agent is aiming for– Methods1. getSteering() AlgorithmgetSteering (target){direction target.position - agent.position;distance direction.magnitude;speed agent.velocity.magnitude;if (speed distance / maxPredictionTime)predictionTime maxPredictionTime;elsepredictionTime distance / speed;newTarget copy(target);newtarget.position target.position target.velocity * prediction;agent.Seek.getSteering(newTarget);} Note: The text has Pursue extend the Seek class Seek has a target data member, which the text directly manipulatesin the above algorithm - not good· I instead chose to pass the goal target as a parameter to Seek’sgetSteering() method (the original takes no arguments) Evade– Delegates to Flee– If the target is not moving, will result in oscillation of agent around target– To remedy, delegate to Arrive instead25

AI: Movement - Delegated Steering Behaviors, Face The agent faces the target The algorithm determines the orientation of the target wrt the agent– It then rotates to face in that direction Face delegates to Align for the orientation Implementation– Data members1. agent and target: Agent and target kinematic data2. newTarget: a simulated target that represents the goal the agent is aiming for– Methods1. getSteering() AlgorithmgetSteering (target){direction target.position - agent.position;if (direction.magnitude 0.0)return target;newTarget copy(target);newtarget.orientation ing(newTarget);}}26

AI: Movement - Delegated Steering Behaviors, FaceHeading Note: Text refers to this as ”Looking where you’re going” In the kinematic behaviors, the agent’s orientation is simply set - a discontinuou

As discussed above, the target of seek is assumed to be moving { If the agent catches the target, it will spiral in and orbit the target { Arrive is designed to stop when it reaches the target When nearing the target, the agen

Related Documents:

May 02, 2018 · D. Program Evaluation ͟The organization has provided a description of the framework for how each program will be evaluated. The framework should include all the elements below: ͟The evaluation methods are cost-effective for the organization ͟Quantitative and qualitative data is being collected (at Basics tier, data collection must have begun)

On an exceptional basis, Member States may request UNESCO to provide thé candidates with access to thé platform so they can complète thé form by themselves. Thèse requests must be addressed to esd rize unesco. or by 15 A ril 2021 UNESCO will provide thé nomineewith accessto thé platform via their émail address.

̶The leading indicator of employee engagement is based on the quality of the relationship between employee and supervisor Empower your managers! ̶Help them understand the impact on the organization ̶Share important changes, plan options, tasks, and deadlines ̶Provide key messages and talking points ̶Prepare them to answer employee questions

Chính Văn.- Còn đức Thế tôn thì tuệ giác cực kỳ trong sạch 8: hiện hành bất nhị 9, đạt đến vô tướng 10, đứng vào chỗ đứng của các đức Thế tôn 11, thể hiện tính bình đẳng của các Ngài, đến chỗ không còn chướng ngại 12, giáo pháp không thể khuynh đảo, tâm thức không bị cản trở, cái được

Le genou de Lucy. Odile Jacob. 1999. Coppens Y. Pré-textes. L’homme préhistorique en morceaux. Eds Odile Jacob. 2011. Costentin J., Delaveau P. Café, thé, chocolat, les bons effets sur le cerveau et pour le corps. Editions Odile Jacob. 2010. Crawford M., Marsh D. The driving force : food in human evolution and the future.

Le genou de Lucy. Odile Jacob. 1999. Coppens Y. Pré-textes. L’homme préhistorique en morceaux. Eds Odile Jacob. 2011. Costentin J., Delaveau P. Café, thé, chocolat, les bons effets sur le cerveau et pour le corps. Editions Odile Jacob. 2010. 3 Crawford M., Marsh D. The driving force : food in human evolution and the future.

MARCH 1973/FIFTY CENTS o 1 u ar CC,, tonics INCLUDING Electronics World UNDERSTANDING NEW FM TUNER SPECS CRYSTALS FOR CB BUILD: 1;: .Á Low Cóst Digital Clock ','Thé Light.Probé *Stage Lighting for thé Amateur s. Po ROCK\ MUSIC AND NOISE POLLUTION HOW WE HEAR THE WAY WE DO TEST REPORTS: - Dynacó FM -51 . ti Whárfedale W60E Speaker System' .

Glossary of Social Security Terms (Vietnamese) Term. Thuật ngữ. Giải thích. Application for a Social Security Card. Đơn xin cấp Thẻ Social Security. Mẫu đơn quý vị cần điền để xin số Social Security hoặc thẻ thay thế. Baptismal Certificate. Giấy chứng nhận rửa tội