April Monthly Checkup

Has it been another whole month?!? Where does the time go? Here's my current goals checklist on my journey towards becoming a Game Developer.

	Create a finished game. I did some good work on my SkyCop demo, finally getting a playable demo posted. I plan to design a smaller-scale (possibly 2D) game at some point but need to work on learning more fundamentals first.
	Use personal projects to test different rendering techniques and programming methods. Check! See the SkyCop reference above.
	Continue learning and be competent enough to explain design decisions. In addtion to keeping up on the latest feeds for major game sites and participating in a couple forums, I've purchased five new books! Admittedly three of them were recommended for Ian Schreiber's Game Design Concepts course. The one I'm probably most excited to dig into is Game Coding Complete, which I'm hoping will be a good reference for proper structure and best practices. Despite these positive steps, I can't mark this item completed just yet. I am still learning, after all.
	Start networking! I'm staying active in a couple forums and planning to participate in a local IGDA chapter. The only problem is the local Columbus chapter (which I would still be a couple hours away from) appears to not be meeting at this time, so I may have to wait to participate with the Triangle chapter after we move to NC later this year. Attending the SIEGE conference is still a possibility, or I might consider a visit back up this way to check out the GameX Games and Media Expo.
	Play more games! I haven't bought a shiny new game to play yet, but I have tried out some independent games on Armor Games. Crush the Castle, where you get to use a trebuchet to destroy castles, is actually a lot of fun! Nonetheless I think I need to get better versed in newer games to mark this item completed.
	Update the outdated resume. This is a new goal and a worthy one I think will help me focus even better on my target. Darius Kazemi has some great tips on writing a resume for a game company and I plan to update my resume soon.

"If you wanna be rich, you gotta do rich people stuff." - Dave Ramsey
"Wanna be a Game Developer? Do Game Developer stuff!" - Me

See any holes in my plan or have useful tips/pointers to help get me further along? Post a comment!

Point-Plane Collision Detection Explained

In my previous post I presented a function for detecting collision of a point in 3D space with a plane (surface of an object). It works well enough in my SkyCop demo because all I need to check is if the tip of the primary ship intersects the surface of other ships. Here's a description of the code, broken into seven steps to help you understand this basic form of collision detection.

1)	Understand the Plane Equation: Ax + By + Cz + D = 0
	The plane equation tells us that a point (x,y,z) is on a plane having normal vector (A,B,C) and distance D from the origin when Ax + By + Cz + D = 0. If we plug in A, B, C, D, x, y, z and get any value other than zero, the point (x,y,z) is not on the plane. Also note that since the dot product of vectors (A,B,C) and (x,y,z) equals Ax + By + Cz, we can rewrite the Plane Equation as DotProduct(N, P) + D = 0 for N=(A,B,C) and P=(x,y,z).
2)	Get the collision surface's normal vector.
	As noted above, in order to detect if a point is on our collision surface (such as a wall we want to prevent the player from running through), we need to know the normal vector perpendicular to the surface. A normal vector is computed by taking the cross product of two vectors on the plane. The simplest 2D plane we can create in 3D space is a triangle with three vertices (call them vP1, vP2, and vP3) and I will focus on a triangular collision surface for simplicity. We compute the normal vector by generating a vector from vP1 to vP2 and another from vP2 to vP3 and then take the cross product of those two vectors to obtain the normal vector. Finally, the normal vector is normalized (made to have a length of 1.0) to simplify calculations. vN1 = (vP2 - vP1); vN2 = (vP3 - vP2); D3DXVec3Cross(&vNormal, &vN1, &vN2); D3DXVec3Normalize(&vNormal, &vNormal);
3)	Get plane distance using the Plane Equation.
	Using our revision of the Plane Equation, DotProduct(N, P) + D = 0, we can solve for D to get D = -DotProduct(N, P). So we compute D by plugging in the normal vector and any point on the plane; any of the triangle surface's three vertices will suffice. d = - D3DXVec3Dot(&vP1, &vNormal);
4)	Classify the start and destination points.
	Now that we've determined the collision surface's normal vector and distance from the origin (A, B, C, and D) we can use the Plane Equation for something really cool: determining if a given point lies on the plane! When we plug a point P=(x,y,z) into the left side of our revised plane equation DotProduct(N, P) + D we get a result value, p. If p > 0, the point is in front of the plane. If p < 0, the point is behind the plane. And of course we know that if p = 0 the point lies on the plane. Since we're only concerned with detecting collisions for moving objects, there must be a start position where the object moved from (pstart) and a destination position (pdest) to which the object is moved. The trick is realizing that a collision only occurs if these two positions have different locations in relation to the plane -- if they're both in front of or both behind the plane, no collision occurred and we can return from the function. p = (D3DXVec3Dot(&vNormal, &pStart) + d); if ( p > 0.0f ) pStartLoc = PlaneFront; else if ( p < 0.0f ) pStartLoc = PlaneBack; else pStartLoc = OnPlane; p = (D3DXVec3Dot(&vNormal, &pDest) + d); if( p > 0.0f ) pDestLoc = PlaneFront; else if (p < 0.0f ) pDestLoc = PlaneBack; else pDestLoc = OnPlane; if (pStartLoc == pDestLoc) return false;
5)	Get the ray.
	At this point we know that an intersection did occur! Great, but there is a small problem; we don't know where it occurred, which is equally important. The plane that was crossed is an infinitely expanding plane in 3D space, often called a hyperplane, so we need to check if the collision occurred within the bounds of our collision surface's borders. Computing the vector, called a "ray", from our object's start position (pstart) to its destination position (pdest) helps determine where the collision occurred. The vector is normalized to simplify calculations. ray = pDest - pStart; D3DXVec3Normalize(&ray, &ray);
6)	Get the intersection point.
	Vector math tells us that we can access points along a ray from pstart to pdest using the formula (pstart + ray * t). Since we know that a point along our ray from pstart to pdest definitely intersects the plane, we use the plane equation to determine the value of t below. Note that I've plugged the intersection point (pstart + ray * t) into the Plane Equation instead of a generic (x,y,z) because we know that point lies on the plane. I've also renamed pstart to "s" and the ray to "r" for brevity. A(sx + rx*t) + B(sy + ry*t) + C(sz + rz*t) + D = 0 A*sx + A*rx*t + B*sy + B*ry*t + C*sz + C*rz*t + D = 0 DotProduct(N, s) + t*DotProduct(N, r) + D = 0 t = - (DotProduct(N, s) + D) / DotProduct(N, r) We've already computed the normal vector N=(A,B,C) as well as the plane distance D and the ray so we can calcuate t. Then we plug it into our formula to get the actual intersection point on the plane. t = - (d + D3DXVec3Dot(&vNormal, &pStart)) / D3DXVec3Dot(&vNormal, &ray); intersect = pStart + (ray * t);
7)	Determine if intersection hit the collision surface!
	We're almost there! We determined the intersection point where our object collided on a hyperplane corresponding to the collision surface. So the final question is, "Does the intersection point fall within the bounds of our collision surface?" In order to answer that question we compute vectors from the intersection point to the surface vertices and measure the angles between those vectors. If we form a complete circle, we know the point lies within the bounds of our collision surface! v1 = intersect - vP1; v2 = intersect - vP2; v3 = intersect - vP3; D3DXVec3Normalize(&v1, &v1); D3DXVec3Normalize(&v2, &v2); D3DXVec3Normalize(&v3, &v3); // Angles around intersection should total 360 degrees (2 PI) thetaSum = acos(D3DXVec3Dot(&v1, &v2)) + acos(D3DXVec3Dot(&v2, &v3)) + acos(D3DXVec3Dot(&v3, &v1)); if (fabs(thetaSum - (2 * D3DX_PI)) < 0.1) return true; else return false;

There are a couple caveats to this method of collision detection. The first is that the triangle surface vertices vP1-vP3 must be specified in clockwise order so the surface normal vector is computed correctly. We also have to allow for a small margin of error in the calculation of the sum of angles due to the lack of floating-point precision. Finally, I've read that this method should only be used on convex (as opposed to concave) polygons which do not curve inward on themselves.

I know this is very low-level and there are probably simpler ways to do it (bounding boxes/spheres come to mind...), but it's kinda neat to see how the math makes it work! Please feel free to post comments/questions to let me know what you think of this tutorial. I hope it provides a clearer understanding of what's going on under-the-hood in basic point-plane collision detection.

Quick 'n Dirty Point-Plane Collision Detection

A couple weeks ago I was in a frenzy to implement collision detection in my SkyCop demo. Sure, I planned to go back and study it in more detail at some point, but for the moment I just wanted to get something done so I could avoid flying through enemy ships and start blowing them up. After a few days of searching, I quickly realized that collision detection is no trivial task; it's a field of study all on its own! I started with this flipcode article that served as a good introduction but left me a bit confused. After more research and trial-and-error I had a working example function that I would like to share with anyone needing to feed that same primal urge to get something working quickly.

The function, written in C++ for Direct3D 9, determines if a single point will cross a triangular plane (parameters vP1-vP3 specified in clockwise order). Parameter prevPos is the initial position your character/camera/object moves from and curPos is the position to which it will be moved. For example, if you want to detect if an FPS player will collide with a wall, you would call this function with the camera's initial position as prevPos and its predicted next position [prevPos + (speed * direction)] as curPos. Submit a comment if you have any questions, and keep in mind I will discuss the code in detail in a future post.

Btw, I'm sure there are engines that handle all this stuff for you, but since I haven't gotten into those yet it was a nice exercise for me. And I do apologize for the ugly formatting. I'll work on making code selections look better in future posts!

enum PlanePosition
{
   PlaneFront,
   PlaneBack,
   OnPlane
};

bool IntersectsTriangle(D3DXVECTOR3 prevPos, D3DXVECTOR3 curPos, 
          D3DXVECTOR3 vP1, D3DXVECTOR3 vP2, D3DXVECTOR3 vP3)
{
    float p, d, t, thetaSum;
    PlanePosition prevLoc, curLoc;
    D3DXVECTOR3 ray, v1, v2, v3, vNormal, intersect;
 
    // Compute normal vector for the plane
    v1 = (vP2 - vP1);
    v2 = (vP3 - vP2);
    D3DXVec3Cross(&vNormal, &v1, &v2);
    D3DXVec3Normalize(&vNormal, &vNormal);

    
    // Compute plane distance
    d = - D3DXVec3Dot(&vP1, &vNormal);

    
    // Classify positions using planar equation
    p = (D3DXVec3Dot(&vNormal, &prevPos) + d);
    if ( p > 0.0f ) prevLoc = PlaneFront;
    else if ( p < 0.0f ) prevLoc = PlaneBack;
    else prevLoc = OnPlane;

    
    p = (D3DXVec3Dot(&vNormal, &curPos) + d);
    if( p > 0.0f ) curLoc = PlaneFront;
    else if (p < 0.0f ) curLoc = PlaneBack;
    else curLoc = OnPlane;
        
    if (prevLoc == curLoc) return false;
   
    // Crossed the plane, did intersect occur inside triangle?
    // Get normalized ray
    ray = curPos - prevPos;
    D3DXVec3Normalize(&ray, &ray);

    
    // t = point along ray where intersection occurs
    t = - (d + D3DXVec3Dot(&vNormal, &prevPos)) 
        / D3DXVec3Dot(&vNormal, &ray);

    
    // Get intersection point on the plane
    intersect = prevPos + (ray * t);

    
    // Determine if intersection is within triangle plane
    // Angles around intersection should total 360 degrees (2 PI) 
    v1 = intersect - vP1;
    v2 = intersect - vP2;
    v3 = intersect - vP3;
    D3DXVec3Normalize(&v1, &v1);
    D3DXVec3Normalize(&v2, &v2);
    D3DXVec3Normalize(&v3, &v3);
 
    thetaSum = acos(D3DXVec3Dot(&v1, &v2)) 
             + acos(D3DXVec3Dot(&v2, &v3)) 
             + acos(D3DXVec3Dot(&v3, &v1));

    
    // If sum == 2PI we have an intersection!
    if ((thetaSum >= ((2 * D3DX_PI) - 0.1)) && 
        (thetaSum <= ((2 * D3DX_PI) + 0.1)))
    {
        return true;
    }

    
    return false;
}

That Whole Networking Thing...

So, I'm on Twitter too, and I have mittens to thank for it. I read his GameDev.net post some time ago, have been kicking the idea around and finally signed up. The cool thing to me is that Twitter can be a great resource to see what's going on in the game industry from people who just enjoy working on games. Click the link above for a list of industry professionals you can follow on Twitter!

This brings me to one of my weakest points on my original checklist to becoming a game developer, which is also one of the most important to getting a job in the industry: networking. I've already been fortunate to meet some interesting people like Matt Zitterman and Grant Shonkwiler on the Game Career Guide forums, and I believe this is another step in the right direction to getting connected.

It's not always WHAT you know, but often WHO you know. What are you doing to get connected?

Play the SkyCop v1.0 Demo!

I haven't been posting as frequently lately, but for good reason. I've been hard at work on SkyCop, which I introduced about a month ago. Keep in mind this is nowhere near a full-featured game, which is why I'm calling it a demo. But it is playable and can be "won" by destroying all red enemy ships, which is pretty fun for at least a couple minutes! :)

Features include:

• 3D Movement/Rotation
• Speed Boost (multi-texturing)
• Energy Shield (alpha blending)
• Basic Collision Detection
• Enemy Target Indicator
• 3 Backgrounds
• 2 Camera Modes

Some obvious enhancements include the addition of music, sound effects, more guns, explosions, and artificial intelligence so the enemy ships can fight back! Alas, these will come in time as I continue to learn. Click the link below to try it out (press number 1 in the program for controls) and let me know what you think. Thanks for checking it out!

Download SkyCop v1.0 Demo

System Requirements: Windows OS, DirectX 9.0 runtime (available from Windows Update or searching online)

Important Disclaimer: I did NOT create the background images in the program. I used brightday1, brightday2, and grandcanyon located here, where they are listed as coming from free or (L)GPL sources.

Game Design Concepts

Professional game designer and teacher Ian Schreiber will be presenting an online course via his blog this Summer. From his introduction, it looks to be an interesting college-level course without the college price tag. The course will not cover game programming, but if you're at all interested in game design this is sure to be a great learning opportunity. Class starts June 29th. Check out his blog to learn more!

Ian Schreiber's Game Design Concepts

Winding Road Ahead

Credit: nwebster!

Tonight I was awakened to the importance of reading a book in its entirety before posting a book review. My thrill of chapters 6-8 on the concepts of Direct3D animation and texturing in Beginning Direct3D Game Programming, 2nd Edition has quickly been eroded by the exponential complexity of chapters 9 and 10 on the High-Level Shader Language (HLSL). I am excited to learn about lighting/shading, environment mapping, bump mapping, reflection, and other techniques described in these chapters. But two frustrating evenings of incomprehensible reading have led me to conclude, as noted by a few other reviews on Amazon as well, that the book is not truly written with the beginner in mind. So I'm taking a new path.

I'm shelving the book... for now. I think it is still a good reference (up until chapter 9 anyway) and may be of use once I gain a better introduction to the concepts described in the later chapters. Until then, there are other resources, such as DirectXTutorial.com and the SDK Documentation itself, that will hopefully provide a more gradual learning curve. Could this be a major turning point in my journey to become a Game Developer? Surely the resources I select to learn Direct3D will affect my growth, but only time will tell...

What resources have you used for learning Direct3D? What worthwhile programming reference/guide would you recommend to someone who has never written a single line of Direct3D code?