Re: Programming question

On Thu, 28 Oct 1999 15:14:04 -0600, you wrote:

>Thanks for all the replies.
>These posts have got some of the wheels turning in my brain.
>Just a few comments.
>
>Previously I was think of using a "reverse" lookup table like Zonn
>suggested, and I might go that route now after he suggested doing a binary
>search on it. (binary search had slipped my mind and I was planning on
>starting at one end and just moving through the table, which would have
>averaged 128 loops) I'm actually currently doing lots of calculations with
>data from lookup tables. I.E.- collision detection.

If you really want to do a lookup table there's a few things you can
do to make it even more straight forward.

Start with the 16 bit number. If the upper at bits are zero, use the
lower 8 bits as a lookup into a table of sqrt results for the values
of 0-255.

Else shift left the 16 bits until the high order bit is set, keep
track of how many shifts were needed, then use the upper 8 bits - 128,
as an index into a lookup table.

The lookup table you use will be 1 of 8 lookup tables of 128 bytes
each, and is dependent upon how many shifts were needed to set the
high bit.

If no shifts were needed, then use the upper byte to index all sqrt
values from 0x8000 to 0xFF00, if one shift was needed then index the
table consisting of the sqrts of 0x4000 to 0x7F80, etc.

This technique allows you to maximize your precision (especially in
the smaller were the precision is needed) while keeping your table
sizes small.

Using 8 bits as an index gives you 8 tables of 128 bytes each and 1
table of 256 bytes, for total of 1272 bytes of table spaces.

Since there is only 1024 starting positions in the original Space War
(you may have more in the Atari hardware), this table size would
suffice for Cinematronics hardware.

By using the same technique but only using the top 7 bits of a number
your table sizes become 9 tables of 64 bytes and 1 of 128 bytes for
704 total bytes, and in this case probably an unnoticeable drop in
precision.

>I had considered using gravity in something like 16 steps, but I still need
>the straight line distance to determine which ring I'm in. (as well as to
>normalize the vectors)

I doubt if that technique would allow you to orbit.

By lowering the lookup to using only the top 4 bits you gat 12 tables
of 8 bytes and 1 table of 16 bytes for 112 bytes. Dividing the range
of answers to 112 possible outcomes still beats 16 levels of gravity,
and 112 bytes is not much to sacrifice for that.

The description sounds complicated, the code is really simple
consisting of little more than 0 to 8 shifts, and a single lookup.
Much easier and faster, than the binary lookup.

I've used this technique for many non-linear functions, in small
embedded processors, it works very well. You can plug in any function
in place of 'sqrt()' when precalculating your tables.

If you have any questions don't hesitate to send me an email.

-Zonn
Received on Thu Oct 28 17:51:07 1999