computing a straight line through a grid

From: Gary Barnett (gbarnett@POLARNET.COM)
Date: 08/23/97


I've been stumped trying to find a fast way to do the following calculations.

Given the following grid: (10x10)

  A B C D E F G H I J
0 . . . . . . . . . .
1 . . . . . . . . . .
2 . . . . . . . . . .
3 . . . . . . . . . .
4 . . . . . . . . . .
5 . . . . . . . . . .
6 . . . . . . . . . .
7 . . . . . . . . . .
8 . . . . . . . . . .
9 . . . . . . . . . .


What kind of a routine would you create if you needed to perform the
following actions?

1) A straight line computation from one spot to another for the purposes
   of determining if there are any obstacles in the way (mobs, objs, terrain)

2) A best fit approach for determining a walking path from one spot to
    another using the data present about objs, mobs, terrain features.

I've been trying to devise a method to do it w/o a lot of processor cycles.

So far the best I've been able to come up with is this:

1) Compute angle of travel.

2) Plot grid locations into an array following the path.

3) Examine array for objstacles and assign aim penalties, etc.

Computing the angle, plotting the path and examining the array
takes a good deal of time. I'm looking for a better way of determining
the grid locations a bullet would pass through on it's way to the target.

The array can be junked, of course, but the rest of it still takes a good
deal of time.

For the best fit, I'm stumped as to how to do it other than a take a
step, evaluate best next step. repeat. This is unsuitable for use in
mobile_activity :-)

Thanks for any input you may have (including references to the
correct books where I might find an algorithm for this sort of thing)

--Mallory







I can picture in my mind a world without war, a world without hate.
And I can picture us attacking that world, because they'd never
expect it.     - Jack Handey


     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
     +------------------------------------------------------------+



This archive was generated by hypermail 2b30 : 12/08/00 PST