AI for Game Developers [-]

AI for Game Developers The components of the vector shown in this figure are as follows: figs/app_ueq02.jpg The cosines of the direction angles seen in these equations are known as direction cosines. The sum of the squares of the direction cosines is always equal to 1: figs/app_ueq03.jpg Normalize The Normalize method normalizes the vector, or converts it to a unit vector satisfying the following equation: figs/app_ueq04.jpg In other words, the length of the normalized vector is 1 unit. If v is a nonunit vector with components x, y, and z, then the unit vector u can be calculated from v as follows: figs/app_ueq05.jpg Here, |v| is simply the magnitude, or length, of vector v as described earlier. Here's the code that converts our Vector class vector to a unit vector: inline void Vector::Normalize(void) http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_002.htm (2 of 6)7/24/05 1:43:02 AM

AI for Game Developers { float m = (float) sqrt(x*x + y*y + z*z); if(m <= tol) m = 1; x /= m; y /= m; z /= m; if (fabs(x) < tol) x = 0.Of; if (fabs(y) < tol) y = 0.Of; if (fabs(z) < tol) z = 0.Of; } In this function tol is a float type tolerance, for example, float const tol = O.OOOlf; Reverse The Reverse method reverses the direction of the vector, which is accomplished by simply taking the negative of each component. After calling Reverse, the vector will point in a direction opposite to the direction in which it was pointing before Reverse was called. inline void Vector::Reverse(void) { x = -x; } y = -y; z = -z; This operation is illustrated in Figure A-3. Figure A-3. Vector Reversal figs/app_fig03.jpg Vector Addition: The += Operator This summation operator is used for vector addition, whereby the passed vector is added to the current vector http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_002.htm (3 of 6)7/24/05 1:43:02 AM

AI for Game Developers component by component. Graphically, vectors are added in tip-to-tail fashion as illustrated in Figure A-4. Figure A-4. Vector Addition figs/app_fig04.jpg Here's the code that adds the vector u to our Vector class vector: inline Vector& Vector::operator+= (Vector u) { x += u.x; Y += u.y; z += u.z; return *this; } Vector Subtraction: The -= Operator This subtraction operator is used to subtract the passed vector from the current one, which is performed on a component-by-component basis. Vector subtraction is very similar to vector addition except that you take the reverse of the second vector and add it to the first as illustrated in Figure A-5. Figure A-5. Vector Subtraction figs/app_fig05.jpg Here's the code that subtracts vector u from our Vector class vector: inline Vector& Vector::operator-=(Vector u) { x -= u.x; } y -= u.y; z -= u.z; return *this; Scalar Multiplication: The *= Operator http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_002.htm (4 of 6)7/24/05 1:43:02 AM

AI for Game Developers This is the scalar multiplication operator that's used to multiply a vector by a scalar, effectively scaling the vector's length. When you multiply a vector by a scalar, you simply multiply each vector component by the scalar quantity to obtain the new vector. The new vector points in the same direction as the unsealed one, but its length will be different (unless the scale factor is 1). This is illustrated in Figure A-6. Figure A-6. Scalar Multiplication figs/app_fig06.jpg Here's the code that scales our Vector class vector: inline Vector& Vector::operator*=(float s) { x *=s; } y *=s; z *=s; return *this; Scalar Division: The /= Operator This scalar division operator is similar to the scalar multiplication operator except that each vector component is divided by the passed scalar quantity. inline Vector& Vector::operator/=(float s) { x /=s; } y /=s; z /=s; return *this; Conjugate: The - Operator The conjugate operator simply takes the negative of each vector component and can be used when subtracting one vector from another or for reversing the direction of the vector. Applying the conjugate operator is the same as reversing a vector, as discussed earlier. http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_002.htm (5 of 6)7/24/05 1:43:02 AM

AI for Game Developers Vector Vector::operator-(void) return Vector(-x, -y, -z); inline { } http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_002.htm (6 of 6)7/24/05 1:43:02 AM

AI for Game Developers All Online Books Table of Contents View as Frames Vector Functions and Operators The functions and overloaded operators that follow are useful in performing operations with two vectors, or with a vector and a scalar, where the vector is based on the Vector class. Vector Addition: The + Operator This addition operator adds vector v to vector u according to the formula figs/app_ueq06.jpg Here's the code: inline Vector operator+ (Vector u, Vector v) { return Vector(u.x + v.x, u.y + v.y, u.z + v.z); } Vector Subtraction: The - Operator This subtraction operator subtracts vector v from vector u according to the formula figs/app_ueq07.jpg Here's the code: inline Vector operator-(Vector u, Vector v) { return Vector(u.x - v.x, u.y - v.y, u.z - v.z); } Vector Cross Product: The Operator http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_010.htm (1 of 4)7/24/05 1:43:12 AM

AI for Game Developers This cross product operator takes the vector cross product between vectors u and v, u x v, and returns a vector perpendicular to both u and v according to the formula figs/app_ueq08.jpg The resulting vector is perpendicular to the plane that contains vectors u and v. The direction in which this resulting vector points can be determined by the righthand rule. If you place the two vectors, u and v, tail to tail as shown in Figure A-7 and curl your fingers (of your right hand) in the direction from u to v, your thumb will point in the direction of the resulting vector. Figure A-7. Vector Cross Product figs/app_fig07.jpg In this case the resulting vector points out of the page along the z-axis, since the vectors u and v lie in the plane formed by the x- and y-axes. If two vectors are parallel, then their cross product will be zero. This is useful when you need to determine whether or not two vector are indeed parallel. The cross product operation is distributive; however, it is not commutative: figs/app_ueq09.jpg Here's the code that takes the cross product of vectors u and v: inline Vector operator^ (Vector u, Vector v) { return Vector( u.y*v.z - u.z*v.y, -u.x*v.z + u.z*v.x, u.x*v.y - u.y*v.x ); } Vector cross products are handy when you need to find normal (perpendicular) vectors. For example, when performing collision detection, you often need to find the vector normal to the face of a polygon. You can construct two vectors in the plane of the polygon using the polygon's vertices and then take the cross product of these two vectors to get normal vector. Vector Dot Product: The * Operator This operator takes the vector dot product between the vectors u and v, according to the formula figs/app_ueq10.jpg http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_010.htm (2 of 4)7/24/05 1:43:12 AM

AI for Game Developers The dot product represents the projection of the vector u onto the vector v as illustrated in Figure A-8. Figure A-8. Vector Dot Product figs/app_fig08.jpg In this figure, P is the result of the dot product, and it is a scalar. You can also calculate the dot product if you the know the angle between the vectors: figs/app_ueq11.jpg Here's the code that takes the dot product of u and v: // Vector dot product inline float operator*(Vector u, Vector v) { return (u.x*v.x + u.y*v.y + u.z*v.z); } Vector dot products are handy when you need to find the magnitude of a vector projected onto another one. Going back to collision detection as an example, you often have to determine the closest distance from a point, which may be a polygon vertex on one body (body 1), to a polygon face on another body (body 2). If you construct a vector from the face under consideration on body 2, using any of its vertices, to the point under consideration from body 1, then you can find the closest distance of that point from the plane of body 2's face by taking the dot product of that point with the normal vector to the plane. (If the normal vector is not of unit length, you'll have to divide the result by the magnitude of the normal vector.) Scalar Multiplication: The * Operator This operator multiplies the vector u by the scalar s on a component-by-component basis. There are two versions of this overloaded operator depending on the order in which the vector and scalar are encountered: inline Vector operator*(float s, Vector u) { return Vector(u.x*s, u.y*s, u.z*s); Vector operator*(Vector u, float s) } return Vector(u.x*s, u.y*s, u.z*s); inline { } Scalar Division: The / Operator This operator divides the vector u by the scalar s on a component-by-component basis: http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_010.htm (3 of 4)7/24/05 1:43:12 AM

AI for Game Developers Vector operator/(Vector u, float s) return Vector(u.x/s, u.y/s, u.z/s); inline { } Triple Scalar Product This function takes the triple scalar product of the vectors u, v, and w according to the formula figs/app_ueq12.jpg Here, the result, s, is a scalar. The code is as follows: inline float TripleScalarProduct(Vector u, Vector v, Vector w) { return float( (u.x * (v.y*w.z - v.z*w.y)) + } (u.y * (-v.x*w.z + v.z*w.x)) + (u.z * (v.x*w.y - v.y*w.x)) ); http://ebooks.servegame.com/oreaiforgamdev475b/app_sect1_010.htm (4 of 4)7/24/05 1:43:12 AM

AI for Game Developers All Online Books Table of Contents View as Frames Colophon Our look is the result of reader comments, our own experimentation, and feedback from distribution channels. Distinctive covers complement our distinctive approach to technical topics, breathing personality and life into potentially dry subjects. The animal on the cover of AI for Game Developers is a Ring-tailed lemur. Ring-tailed lemurs (Lemur catta) are found solely in Madagascar, an island off the coast of southeast Africa. Ring-tailed lemurs have a distinctive bushy tail with alternating bands of black and white rings. Their tails can reach lengths of up to 25 inches. They also have a black, pointed muzzle, which is typical among the various species of lemur. These lemurs prefer relatively open areas, such as rocky plains and desert areas, and typically travel on the ground, although they will sometimes walk on large limbs in trees. This differentiates them from other lemur species, which usually prefer forested areas and travel almost exclusively in trees. Similar to cats, Ring-tailed lemurs have a reflective layer in the back of their eyes. This allows them to have excellent night vision. Their tails are highly scented, and are used to warn other lemurs of approaching danger. The tails are also an integral part of the mating process. The males will use their scent to try and attract the females, and vicious \"stink fights\" can often erupt within the group. Ring-tailed lemurs live in groups of between five and thirty members. They have distinct hierarchies that are enforced by frequent, aggressive confrontations between members. Females, who stay in the group for their entire lives, dominate the group. Males will often change groups at least once during their lifetimes. Living in arid habitats, Ring-tailed lemurs quench their thirst with juicy fruits. They will also eat leaves, flowers, insects, and tree gum. Like most lemurs, Ring-tails have only one baby in any given year, although twins or even triplets are common when food is plentiful. Newborns are quite helpless and are carried around by the mother in her mouth until they http://ebooks.servegame.com/oreaiforgamdev475b/colophon.htm (1 of 2)7/24/05 1:44:03 AM

AI for Game Developers can hold on to her fur by themselves. They will then ride around on the mother's back. They first begin to climb after about three weeks and are usually independent after six months. They can live for up to 27 years in the wild. Darren Kelly was the production editor, Audrey Doyle was the copyeditor, and Kathryn Geddie was the proofreader for AI for Game Developers. Matt Hutchinson provided production assistance. Claire Cloutier provided quality control. TechBooks, Inc. provided production services and Ronald Prottsman wrote the index. Ellie Volckhausen designed the cover of this book, based on a series design by Edie Freedman. The cover image is a 19th-century engraving from Royal Natural History. Emma Colby produced the cover layout with QuarkXPress 4.1 using Adobe's ITC Garamond font. David Futato designed the interior layout. Techbooks, Inc. implemented the design. The illustrations that appear in the book were produced by Robert Romano and Jessamyn Read using Macromedia FreeHand 9 and Adobe Photoshop 6. This colophon was written by Darren Kelly. http://ebooks.servegame.com/oreaiforgamdev475b/colophon.htm (2 of 2)7/24/05 1:44:03 AM

AI for Game Developers All Online Books Table of Contents View as Frames Table of Contents Reviews Examples Reader Reviews Errata http://ebooks.servegame.com/oreaiforgamdev475b/ (1 of 2)7/24/05 1:44:15 AM

AI for Game Developers Academic AI for Game Developers By David M. Bourg, Glenn Seeman Publisher: O'Reilly Pub Date: July 2004 ISBN: 0-596-00555-5 Pages: 400 Written for the novice AI programmer, AI for Game Developers introduces you to techniques such as finite state machines, fuzzy logic, neural networks, and many others, in straightforward, easy-to-understand language, supported with code samples throughout the entire book (written in C/C++). From basic techniques such as chasing and evading, pattern movement, and flocking to genetic algorithms, the book presents a mix of deterministic (traditional) and non-deterministic (newer) AI techniques aimed squarely at beginners AI developers. http://ebooks.servegame.com/oreaiforgamdev475b/ (2 of 2)7/24/05 1:44:15 AM