Richard Marks
202192397
Administrator
Member
Respect: 3425
Offline
Posts: 1027
happy


« on: May 16, 2009, 07:51:01 AM » 

MATHEMATICS IN PROGRAMMING PROGRAMMER'S WORKSHOP CONFERENCE JULY 7  JULY 14, 1988 by SYSOP JL
Like everything else related to programming, there are the inevitable reference books for mathematics also. I generally have several reference books around either here near my computer or at work so I can look up formulas, constants or basic relationships. The type of books you might need would depend on the type of program you are doing. For general use, an encyclopedia may be sufficient to find basic relationships and physical constants. For electronics I use Allied Radio's "Electronics Handbook". It covers the basics you might need for programming. For physical constants and commonly used formulas the book "C.R.C. Standard Mathematical Tables" published by the Chemical Rubber Company is the best basic reference. For more advanced problem solving in programming you should seek a book on numerical methods. It is rather old but I still find "Arithmetic Operations in Digital Computers" by R. K. Richards published by D. Van Nostrand to be useful. For the necessary formulas and tables related to your computer you should refer to your computer manual and a programmer's reference guide. The "Commodore 64 Programmer's Reference Guide" published by CBM and Sams is the best reference for the graphics and sound capability of your computer. For specific topics that may not be covered by any general math reference you keep handy, visit the public library.
I know that the idea that you might need to know some mathematics for programming can sound intimidating. But you don't need to be a mathematician to be successful at it. All you need is to have the ideas for writing the program and the perseverence to find out how. I'll try to cover some of the common things now. I would encourage anyone who wants to know how to solve a problem to research it in a reference book or the library rather than to just ask. You don't learn how to solve a problem by getting the answer from someone else.
A common game idea based on a mathematical formula is the ballistic trajectory game such as a cannon firing at an enemy. The path that the shell follows is known as a ballistic trajectory. When a shell is fired upward at an angle it starts with a constant speed and direction. It will continue with this velocity unless some force changes that. The main force which changes its velocity is gravity. Gravity only acts in a vertical direction (the Y axis on your computer screen). The shell's velocity in the horizontal direction will remain constant unless you include the effects of air resistance (drag) or wind. Drag acts in opposition to the direction of motion of the shell and wind alters the horizontal velocity of the shell in combination with the drag.
First of all, given this problem you don't need to sit down and write a big long equation for the motion of the shell. You can, particularly with computers, take it a step at a time working logically towards a solution. To start with you need the initial seperate X and Y velocities, XV and YV. To get them you use the trigonometric relationships YV = V * SIN(A) and XV = V * COS(A). These relationships are used a lot in computer games and graphics and are pretty fundimental. For example in sprite movement on the screen. You don't need to memorize them if you just remember that the SIN of zero degrees is zero. So Y for a zero degree vector (with respect to the horizontal) is zero, which is obvious, and therefor the Y component uses the SIN function and the X component uses the COS function. Back to the problem... For V in these equations you use the muzzle velocity (or sprite speed, etc) in screen displacement units per update rate time. For example, if you use a BASIC loop that takes 0.25 seconds per loop and you want to show the trajectory at 10 pixel increments then V is 10 and it is in units of 10 pixels per 0.25 second. If the elevation angle you have to start with is in degrees you have to convert it to radians for the BASIC SIN() and COS() functions. If you remember that 2*PI radians = 360 degrees (a full circle) then you can get A (in radians) = A (in degrees) * PI / 180. Your program will run faster if you assign a variable CF = PI/180 once near the start of the program then in your real time calculations use RA = DA * CF (RA is angle in radians, DA is angle in degrees and CF is the conversion factor). If you are working in machine language then your V may be in some binary fraction of a pixel per 60Hz IRQ interrupt. Guess at a value to start with and adjust it to make it look right on the screen.
Once you have the initial velocities in X and Y then you can set up the first position vs time equation. Distance = velocity * time so X = XV * T and Y = YV * T. Since we had the SIN() and COS() things figured out we get Y = T * V * SIN(A) and X = T * V * COS(A). Now you can add to these the effects of gravity (on Y) and drag (on V) or wind (on X) if you want it. Gravity is an accelleration factor. Earth normal gravity is 32 feet per second per second. To scale this to your screen display you would need to relate teh muzzle velocity (or your sprite speed) in screen display units per update time to the equivilant in feet per second. Unless you are trying to do an exact simulation it may work out just as well for program design purposes to guess at a value that is easy to work with then adjust it later so it looks right. Otherwise, apply a scaling factor in your design that is equal to the number of feet per screen display increment. So if you have a scale that is 320 pixels (full screen width) for 960 feet your scale is 3 feet per pixel and the accelleration of gravity is therefore approximately 11 pixels per second per second. Or in units of the screen update rate time it is 11 * .25 * .25 or 11/16 pixel per update interval per update interval.
The Y distance that the projectile moves over a time interval is AC * T * T where AC is acceleration. So now you can add this effect to the Y from before. Actually, on your screen Y starts at 0 at the top of your screen and increases downward. So the initial Y velocity is negative, the effect of gravity is positive and the initial starting point (Y value) is some positive value of Y. Get the signs right when you write the code. If you use a drag factor on the velocity (V) and you want to be realistic about it then the drag produces an accelleration opposing the velocity. The accelleration is the drag force divided by the mass of the projectile. The drag force is roughly proportional to the velocity squared times the frontal area of the projectile. You can approximate this as some constant that you guess at times the velocity squared then adjust the constant later so it looks right. This velocity correction for drag is applied to the velocity V in the equations for XV and YV. So to include drag you must do this calculation first to be realistic. In practical terms you could apply the drag to only the X term since the accelleration due to drag is small compared to the accelleration due to gravity in the Y direction.
This example has centered on the ballistic example but most of the principles apply also for just moving sprites around the screen. If the sprite is moving at an angle with respect to the horizontal then the trigonometric relationship XV = V * COS(A) and YV = V * SIN(A) will still hold true. The reason for applying these formulas to sprite movement is that the velocity in the direction of sprite travel will then be constant as the sprite changes angle due to bouncing off objects or traveling in a curved path.
One additional comment on this before I go on. Positions that you calculate in these equations will be floating point values. That is, there will be a whole part and a fractional part of the answers. You will be representing screen locations as integer values however when you plot or position to these screen locations. In BASIC this is relatively easy to handle just by using real numbers for constants and variables. In machine language however you will need to use and store fractional parts for intermediate values. You can easily accomplish this by using the most significant byte or bytes of a position variable as the integer part and keeping one or two (depending on the accuracy you want) bytes additional for the fractional part. One byte of fractional extension will give you a maximum error per calculation of 1/256 or approximately 0.4%. That is usually enough unless you are simulating a golf game, pool game or long term planetary motions. Remember that errors will accumulate. If you are doing 60 screen position updates per second you could be accumulating an error of as much as 72% per second with a one byte fractional extension. For machine language you will want to build a table of SIN() and COS() values at least for the increments of angles that you will be using. In simple cases this may only be 0, 30, 45, 60 and 90 degrees. For large numbers of angles you may want to use the relationship SIN(A) = COS(90A) for angles in degrees, or SIN(A) = COS(PI/2  A) for angles in radians to reduce storage space although that may slow down your program. Storing tables of SIN() and COS() function values is preferable to calculating the exact SIN or COS values which take a lot of time to do.
If you are attempting to calculate a final position or result you may want to use a simulation technique instead of trying to come up wiht a formula for the final answer. For example, if you are given the problem of computing how much total money you will pay in 20 years on a home loan you can easily just simulate the monthly principal and interest payments you will make. Simulate the 240 payments and keep a running total of the principal and interest amounts and you will have the answer in a couple of seconds, even at BASIC speeds. Otherwise you could go searching through some math books and look for the formula, or derive it yourself and then write a program that will give you the answer in a fraction of a second. Simulation is an excellent approach to solving complex mathematical problems on a computer just for this reason. You can spend relatively little time formulating the problem for the computer to solve by simulation and let it do the work as opposed to spending lots of time deriving equations so the computer will have little work to do. To put it another way, most times the little extra computation time required to solve a problem by simulation is well worth it compared to spending a lot of time writing a program optimized for speed.
Another technique used sometimes to solve mathematical problems is successive approximation or one of its variations. For many simultaneous equations these numerical methods are the ONLY practical way of solving them. Perhaps an example would help here. Let's go back to the ballistic trajectory problem and find out where the shell impacts on uneven ground. We already know the set of equations to solve that will give the X and Y position of the shell at any given time after it is fired. If we have another equation for the elevation of the ground above/below the elevation of the firing point (the 'equation' may be a table of range vs terrain height too) for different X displacements then we can solve the equations simultaneously to find the impact point. To use successive approximation to solve this one we would take increments of T and solve for X and Y positions of the shell. Then using the X position of the shell determine the Y value for the terrain height. If the shell's Y position is above the ground's Y position yet then we take the next increment of T. If it is below the ground then back up one increment of T, make the time increment smaller by 1/10 as much, and again go forward in time with the shell motion with the smaller time increments. You will need to program an exit from this iterative process when the shell and ground Y positions are exactly equal (unlikely) or when the time increments or X position errors become as small as you need for an accuracy limit. In the preceeding example I used linear successive approximation which is probably the only type you will ever need. If you get into a situation where it is essential that the computation time be reduced then there are alternative methods which give faster convergence to a solution. One example is to use binary multiples such that every time you go one step too far the increment that you use is reduced by half. This is the principle of binary searches and can be made to converge approximately 3.3 times as fast as the method shown. Another example is Newton's method where the next guess at a solution is determined by subtracting the ratio of the function value and the value of the function's first dirivative from the preceeding guess. For a second order function this method converges to a solution approximately 100 times faster than linear successive approximation as I have shown it.
One of the most important points to remember about programming and mathematics is that exact solutions to real problems are rarely possible. The best you can do is to arrive at a solution to some degree of accuracy that is acceptable. Keep track of the error sources and watch out for how errors can accumulate. If, as noted earlier, errors accumulate too much then redefine your algorithm or intermediate calculation accuracies to get what you need.
