Math Programming Tips From 1988

(1/1)

**Richard Marks**:

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(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.

Navigation

[0] Message Index