Math Programming Tips From 1988


Richard Marks:
                          MATHEMATICS IN PROGRAMMING
                              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(90-A) 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.


[0] Message Index