Re: computing a straight line through a grid Aug 23, 97 09:22:24 pm

From: Andrew Helm (ashe@IGLOU.COM)
Date: 08/24/97

On Sun, 24 Aug 1997, Gary Barnett wrote:

> I've been stumped trying to find a fast way to do the following calculations.
> Given the following grid: (10x10)

> 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)

Use the slope of the line. Take spot2's y, subtract spot1's y. Take
spot2's x and subtract spot1's x. Simplify the fraction. Then just
follow the slope.

For instance, say spot2 is 14 units north, and 7 units east of spot1.
First you get the slope (14/7 == 2/1), then you go 2 units north, 1
unit east, 2 units north, 1 unit east, etc. until you reach spot2.
You could also start out going 1 unit east, then 2 units north, etc.

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

Could you be more specific about the environment? Are you trying to do
this in a CircleMUD environment, or is it for some other game? The
reason I ask is that you were describing the space as a 2d grid (which
CircleMUD's rooms certainly don't form). If you're dealing with normal
2d or 3d space there are a couple algorithms you can try. A* is probably
what you want. You can find info on it and other cool stuff at:

If you're doing this for CircleMUD, however, just stick with the same
algorithm used in graph.c for the track skill. I'm sure it's
possible to use a better one, but the math is beyond me. :)

     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

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