Re: A83: Calculating Distances Fast - any suggestions ?


[Prev][Next][Index][Thread]

Re: A83: Calculating Distances Fast - any suggestions ?




In a message dated 23/05/00 17:42:29 GMT Daylight Time, david@acz.org writes:

>> Since I really dont think there is a very good approximation
>> algorithm for distance (without tons of iterations), perhaps you can
>> attack the problem in a different manner.  For instance, I doubt when
>> drawing the lines for the vector based system you really need to know the
>> length of a straight line between the two points.
> Distance isn't used when drawing unfilled polygons, anyway.  But it has
> many, many other uses in a vector engine, such as collision detection.

It doesn't draw polygons ; it scales vector graphic objects and positions 
them on the display appropriately. [Not very appropriately, but near enough !]
It is imprecise, but it will draw 30 objects at 20 fps.... gotta keep that 
frame 
rate up :) 
 
>> I would suggest in your "drawing loop" you increment parallel counters for
>> X and Y using the slope of the line which could be easily calculated
>> beforehand. ie. X would increment by one, whereas Y would increment by
>> abs((y1-y0)/(x1-x0))
> In other words, use Bresenham's line algorithm?  :)

Ah beloved Bresenham ; I wrote quite a neat version for my Kernel file and
didn't use it for anything other than drawing frames on the Lode Runner
title screen, what a waste.

Well, I ended up going for a look up table ; given that all visible objects 
are
within 64 units, then it just uses (x div 4) | (y div 4) << 4 as an index into
the table. Boring, but near enough (mean error of +- 1), and (|x|+|y)) div 2 
is used to filter out objects fairly rapidly. 

Inaccuracies in the other calculations mean it isn't that accurate anyway; 
but at least if I make a box of objects it looks faintly rounded rather than 
star shaped when wandering around it.

Thanks for your suggestions.... now whaddamI gonna do with it ? Elite ?
or a 3DRPG (sort of)...... was inspired by the Vectrex game "Dark Tower",
but you younguns probably never played that..... have this idea for a rather
odd RPG without closed rooms ; kind of walking through forests, deserts
and dungeons. 

Paul Robson.