Re: computing a straight line through a grid

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


On Saturday, August 23, 1997 11:29 PM, Andrew Helm [SMTP:ashe@IGLOU.COM]
wrote:
> On Sun, 24 Aug 1997, Gary Barnett wrote:
<snip>
>
> 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.

Agreed. That seems to be the way to do it. thanks :-)

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

I have created a 3 layer terrain map for each room. Builders enter the
terrain features for each room into an OLC menu. The reasoning behind
all this is to provide reasonable line of site to ranged weapons, as well
as provide things like cover, hiding and range calculations for grenade
explosions, mines and other affects are of note as well as the ability
to put a stream through a room and have the person in a boat traveling
down it at the speed of the current.

It also allows weapon reach, facing and retreat options.

The ability to create low walls, trees, and any other reasonable terrain
element (up to 255 total for each layer..) only takes 363 bytes per entry.
Multiple rooms can point to a terrain entry, and a linked list in each
room is used to store terrain state info (square burning, etc)

I've created the routines to display this info to the player as best as is
possible with telnet and ascii. (read: color is darn near required)

This terrain map also allows things to be hidden underground or for
a plane to fly overhead. A player can dig a hole at location b7 in a
seldom used room and have a good chance that it won't be dug up
by anyone wandering by for a good long while; though it might rust or
otherwise be destroyed :-)

The obvious challenge is how to make mobs use all the possibilities
that this opens up. The ability to find the 'best' route from a to b is
partly
for mobs that need to rush the player who's firing his gun at the mob.

The best part is that you don't have to junk your room structure to add
it, provided you are willing to ignore the scale problems that a fixed
grid imposes on a room. I called it a design consideration and decided
to go with it. It adds quite a bit more than it annoys, IMHO.

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

It's CircleMUD.. but not a stock question :-)

Thanks for the links!

BTW Anyone ever done artillery on a mud? Anti-Aircraft guns? Great fun :-)

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