New Video!
On 1/28/2010, I made a video called Math in RTS games. It is basically an updated version of this document, though there are a few topics I didn't cover in detail such as DirectX. Also, I didn't rehearse it well due to my lack of time, so if you get confused you may also want to look here, especially with the unit movement section.
About:
This document was originally my way to explain parts of the code which would take too much code to explain in comments. I now realize that I got carried away with this and tried covering practically every part of the code. I no longer plan to explain features beyond version 0.1.4 here, but I plan to support the document up to the 1.0.x releases. (I'd have to rewrite a bunch of it to update it for the 1.1.x releases, which I might do sometime.) If you want to help program Afdarts, this document might be a nice starting point.
Organization:
This section only covers the organization that doesn't belong in any other section. This document would be a mess if I put all organization information here.
My project contains the following code files: frmApp.frm (main form), frmSpl.frm (splash screen form), modEng.bas (engine for DirectX and related), modFc.bas (faction AI module), modIndi.bas (engine for simulating individuals) and clsCmd.cls (command button class). Most of this document is about modIndi.bas, though I explain parts of frmApp.frm and modEng.bas.
I found Visual Basic classes annoying in the way that people have to use properties instead of defining variables as public and that they don't let people return custom types (such as custom vertex types) or make them into parameters. Strangely enough, regular code modules don't have these limitations, so my workaround was to put all the variables that would otherwise be in classes into a public type in a module and all of the subs or functions into the module with a different prefix for each type, passing the types as byref. It isn't technically object oriented, but it's so close it might as well be.
After Form_Load in frmApp.frm initializes some of the program, it calls MenuLoop. If the user starts a new game, GameLoop will be called. GameLoop calls UpdateIndis and Draw. See the comments in the code for a description of these sub-routines.
I want to note some definitions that I made up to avoid confusion in my program. Usually in RTS games, each person or building is a unit, but in military (or at least Total War game) terms, an organized group is a unit. Since the movement in my game was inspired by the Total War series, I decided to call each group a unit, which left the problem of what to call each individual. I decided to call them individuals.
Unit Movement: (PosFinalGet, FlanksGet, and SendLinear)
The main part where PosFinalGet and SendLinear are called are near the top of UpdateIndis, though they are called elsewhere.
I wanted to make the units move in a realistic and organized way. So that the individuals aren't limited in what directions they can move, I decided to not make the game tile-based (though I store the individuals' positions in longs instead of floats) and to store the movement in event types. My game contains 2 event types: teHM (type events high-level or unit movement) and teLM (type events low-level or individual movement). Each unit has its own array of event types named evm (short for event movement), and eHM and eLM are arrays for each unit. Therefore, the code to access an event in my game would look something like eHM(unit).evm(command_number) or eLM(individual).evm(command_number). Whenever a new unit command is given, the program increases the size of the evm part of the eHM array and puts a minimal amount of information into it. During the game loop, UpdateIndis adds to the evm part of the eLM array so that finding the current position of an individual is simply a matter of solving a linear or quadratic equation.
Form_MouseUp:
The key to selecting and moving units is 2 handy DirectX functions called D3DXVec3Project and D3DXVec3Unproject. D3DXVec3Project is explained well at this web page. D3DXVec3Unproject is like the first, but returns the 3D coordinate VOut from the screen coordinate V. See the code for more details on how to use these.
PosFinalGet:
After the left and right flank of a unit's destination is found, UpdateIndis calls the function PosFinalGet in modIndi.bas to get the destinations of the individuals. I wanted the formations to be rectangular with each row and column equally spaced apart, but the formation is allowed to be rotated. An x and y spacing distance coordinate is needed when rotation is involved, and to get those sine and cosine are needed. Don't get too worried. Sine and cosine can be slow if the input is an angle, but if the inputs are the lengths of the sides of a right triangle, they are a simple matter of division (and unfortunately one square root).
It's quite easy to get those side lengths. The horizontal one is calculated by subtracting the x parts of the left and right flank coordinates, while the vertical one by subtracting the y parts. The diagonal one is calculated by using the Pythagorean theorem or by using the distance formula, which are related by the way. To make the formation shape, first number the individuals in the unit. Then, take the individual number and divide by how many individuals fit between the flanks (use the diagonal length calculated earlier and it's important to round down) to get the y position relative to the left flank, and take the remainder to the the x position. These values can then be multiplied appropriately by the sine and cosine to rotate the formation and added to the position of the left flank to get the final position. This position is then passed on to the function ColAvoid to make sure it does not overlap with the final positions of other individuals.
A note about speed. The distance formula involves a square root, and we can't just square both sides because we are solving for a variable, not checking to see if a statement is true as in the case of collision detection. It also appears that many functions that come with Visual Basic (including the sine and cosine and square root functions) are inline functions (look into a C++ introduction), which I don't think Visual Basic supports in user-defined functions, causing my attempts to make faster versions of the functions to fail. At least one square root call which can be shared between sine and cosine is better than solving a slow sine, slow cosine, 2 arctangents, and 2 square roots, which would have happened if I tried using the slow sine and cosine. Also, even 1,000 square roots can generally be calculated quickly enough to not make a big difference if calculated only when a unit is moved, and if I cared to optimize the program I could have just solved these sines and cosines once per each time a unit (instead of an individual) is moved, which would probably involve about 20 units max.
FlanksGet:
In every RTS I know of, it is possible to tell a selection of individuals to move where the mouse down and up positions are the same. This requires finding the left and right flanks when only one position is given, which requires looking back at the flanks before. The following diagram may help explain how to do this. The red lines indicate line segments between the starting flanks at the bottom and the ending flanks at the top.
Notice that the tangent of the large triangle (distance 2 ÷ distance 3) is equal to the cotangent of the small triangle (distance 4 ÷ distance 5). This is important, since we need but don't know distance 4 and distance 5 while distance 2 and distance 3 are easy to calculate using the same method as the triangle side lengths a few paragraphs above. To get distances 4 and 5, multiply distances 2 and 3 by the ratio of the hypotenuses (diagonal sides) of the triangles. To find the flanks, add or subtract (it depends on the flank) half of either distances 4 and 5 (it depends if you're getting the x or y value) to where the user told to move the unit.
SendLinear:
Now that we have the final position of the individual, we have to move it there. This takes more code than the other 2 sub-routines, but it is more straightforward. First, calculate the position where the individual starts based on the time and equations in the eLM type. If the individual doesn't have any health, make sure it stops moving and there is no need to tell it to move. Next, add 2 individual events: one to move and one to stop. For the event in which the individual moves, first find how long it takes to get there by finding the distance it needs to move and dividing it by the individual's speed. Then, get x and y equations by getting the line through the 2 points in which the x of the points is the time and the y is the position. The 1st point is the starting position and time and the 2nd point is the ending position and time. To avoid overflow errors, I recommend making the starting time 0 and the ending time the time it takes to get to the final position.
Individual Movement: (most of UpdateIndis and ColRespondB)
The top part of UpdateIndis tells individuals how to move to their destination, which is covered in Unit Movement. Everything below that is about collisions and individual-level following. The collisions code has very much evolved over time, and the notable milestones so far have been versions 0.1.0 (individuals on multiple tiles), 0.1.1 (circle-based response), 0.1.2 (individuals eventually go to an unoccupied place), 0.1.4 (circle-based detection and smoother response with buildings), 0.2.1 (separation of individuals), 0.2.3 (individuals immediately go to an unoccupied place), and 1.1.1 (check for collisions 1 update early then remove individuals smoothly, not described here). I give credit to David Conger for writing Physics Modeling for Game Programmers, which much of the collision simulating is based on.
UpdateIndis collision detection:
Collision simulation is divided into 2 different subjects: collision detection and collision response. I'll start with collision detection.
Much research is being done on collision detection. I don't want to use fancy collision detection because it is easy to put many individuals in an RTS game. One of the simplest solutions is to pretend that each individual is surrounded by a sphere or circle, and if the distance between the individuals is less than the sum of the radii, then there is a collision. This works, but is slow because of the square root required when solving for distance. However, since this is checking to see if a statement is true instead of solving for a variable, it is much faster to square both sides of the equation and cancel out that square root, leaving one with a much faster check.
Silly as I was, originally I thought that I could predict where the individuals would collide with satisfactory frame rates, even if it lagged a bit when the user first tells a unit to move. When I tried it out by telling all 1,300 individuals on the map to move at the same time (and this was before it was working properly), the program froze for about 3 seconds if compiled and for about 15 seconds in the Visual Vasic IDE.
I would get even worse results if I used the circle check like that because the circle check would need to be done much more often. However, there is a way to speed up the collision detection that works for the circle check but unfortunately not as well for the predicting. Instead of checking all individuals against all other individuals, one can first put the individuals into tiles and use the circle check when the tiles overlap. In my game, the width and length of one of these tiles is the diameter of the smallest individual type.
In my RTS, the amount that the frame updates is directly related (in most cases) to the time that has passed. If the program checks for collisions every frame, the game will run differently on slow computers and fast computers and depend on the frame rate. I want multiplayer to only send unit commands (though I haven't added the feature yet), so I checked for collisions at fixed times. The time until the next check is the shortest length of time it takes for an individual to move one diameter (different individual types may move at different speeds).
ColRespondB:
Before I get any further, I want to note that my game takes health from individuals after a collision is detected. They then act like usual, which is explained below.
First, for an amount of time that depends on the type the individual is, the individuals will bounce off each other based on a physics formula. This time (sorry) I copied the bouncing formula without completely understanding it, but I'll try to give you an overview of how to get to it. For a 100% elastic collision, combine conservation of momentum and conservation of energy. For a 100% nonelastic collision, get a weighed (they may have different masses) average of the speeds of the individuals. For collisions in between, there is a elasticity variable which can be solved for and used, but I'm not sure how that works.
This formula (found in the sub-routine ColRespond) only works for 1d collisions (on a line), but most programs will need to handle 2D or 3D collisions. The program will temporarily rotate the speeds of the individuals using the right triangle definitions of sine and cosine so that the x and y axes are like shown in the blue line segments above. Next, plug in the speeds of the balls traveling toward each other into the formula. If the resulting speeds are 0, the individuals will move at random speeds. Then, add how fast the individuals are moving parallel to each other. Since this accelerates individuals in certain situations and is not good at removing individuals, the program removes the individuals. A short period of time after bouncing off each other, the individuals will try to go back to where they were trying to go earlier.
UpdateIndis following:
This is not the best way to do it, but in my game health is taken as part of the collision response. If an individual is told to follow, it will move to the closest individual if it is not colliding with something and is not moving, as implemented in the code after collision detection.
DirectX: (modEng.bas)
modEng.bas:
Sorry, I don't want to write a long explanation about how DirectX works when there are so many others, but it may be worth reading this anyway. The code in my DirectX engine (modEng.bas) looks most like the code from the book Visual Basic Game Programming with DirectX by Jonathan Harbour, but too late into writing it I found out that the website directx4vb.vbgamer.com covers almost every DirectX topic better. The only DirectX topics that it didn't cover that the book did were how to use the D3DXSprite object and how to put a texture on a "primitive" 3D object. I'm careful to say DirectX topics because the book covers some other topics pretty well (mostly doing graphics with the Windows API), but if all you want to learn is DirectX with Visual Basic, I would recommend reading the DirectX4VB website then maybe looking into the book for the 2 topics it covers.
You should set zenable to 1 instead of True, otherwise the z-buffer won't work on some computers. When calling D3DXMatrixPerspectiveFovLH, set the aspect parameter to the y resolution ÷ the x resolution, otherwise it will look a little stretched, especially on widescreen monitors. I'm surprised neither the website or book I mentioned did that 2nd tip.
The key in getting lighting to work is generating triangle normals, and using the code in the DirectX4VB website only works if the vertices are in clockwise order. If you are being unconventional like me and use triangle strips (you should probably use meshes), the vertices almost always alternate between clockwise and counter-clockwise order. If you do this, you therefore have to add a little extra code like in the function P3SetBuf in modEng.bas.
If you use DirectInput for getting mouse input, DirectInput automatically hides the mouse (or at least from what I've read). This forces you to draw the mouse in the game, but if your program lags, the mouse movement also lags, making it hard to get the mouse to where you want. Since it is often easy to make RTS games lag by putting many units onscreen, I decided to encapsulate Visual Basic's mouse movement instead just to keep track of where the mouse is and what buttons are pushed down.
For information on the easy way of projecting a 3D point onto the screen or vice versa, see Form_MouseUp.
Draw:
I chose to make some updating certain little things not related to drawing optional in case I decided to have alternate ways to do them. If UpdateIndiPos = True, then it will find the current position of each individual. Since the program does not necessarily update events at the time shown during a frame, the program has not had any need to do this until now. Draw also updates camera movement.
Drawing the ground and individuals is not particularly hard, and most of the code doing this is devoted to animations when individuals have no health. This is done by adding a coefficient of the old position to a coefficient of the new position and calculating the coefficients linearly based on time. It gets more interesting when it comes to showing which units are selected. Usually in RTS games, units selected show a health bar above them. However, at least in my attempts, drawing the health bars on all 1,300 people caused the frame rate to drop from 30 FPS (frames per second) to 8 FPS, so after a while I decided instead to draw a model under each selected individual as done in Rome and Medieval 2 Total War. Notice that I used alpha blending (great for transparency effects) to make the circle image not draw black pixels and set the light color to change the color of the image. After adding lighting, setting colors for each vertex no longer worked.
After this, the program draws projectiles, the select box (if needed), the make units bar, and text in that order. The order is important because we do not want, say, make unit buttons drawing above the mouse, thus hiding it. This program does not draw the mouse in DirectX, but I hope you get the idea. I even paid attention to this with 3D objects because though I enabled z-buffers to hopefully do this automatically, some computers do not support z-buffers and I do not want the ground hiding units or other objects.