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)
[snip]
> 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:
http://theory.stanford.edu/~amitp/GameProgramming/
http://hem.passagen.se/fmj/pathfinder/index.html
http://www.imada.ou.dk/~breese/navigation.html
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: |
| http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
+------------------------------------------------------------+
This archive was generated by hypermail 2b30 : 12/08/00 PST