Hello, all
First of all, Jason: would you mind posting a link
to the other Tracking algorithm? (the one by Jorge Ribeiro
Pereira)
Second, After reformatting the current track code
snippet into readible code *sigh*, I can say that this
is probably the way I'd do it, except maybe either make
the hashing more transparent or get rid of hashing
entirely. (When your CPU performs 1 million *complex*
operations per second - for example-, is it really
necessary to shave 100K operations down to 50K
operations? Yes you save half the processing time, but
we're talking about milliseconds here.) This really
isn't that complex an algorithm. :-) ...once again,
coding style can easily obfuscate even a simple algorithm.
Here's my stab at what track.c is doing:
=== Begin at do_track/do_hunt and trace down through
function calls
{
Perform standard argument validation/command
processing
Find the first direction in the tracking path
{
Initialize hash trash
<A>
Loop through all exits in the current room
{
Check the current exit. If we should
traverse the exit, then do so.
{
If this is the target room, then
return success = the first
direction to travel in the track
path we just found.
Else, Recusrse into the current
room - call <A>.
}
}
}
If the first direction is valid, then tell the
player which way to go. (I'm Ignoring any
possible failures and randomness.)
}
=== The End!
Yes, this algorithm does use lots of memory and
could be slow with large areas, but with some creative
design, a command that takes a long time can be
processed over several updates transparent to the
player. :-) (You just have to format the processing
system into a series of steps, then only execute a
number of those steps per update while keeping track of
all progress so far.) And step based processing could
add a little bit of realism in that to track someone from
a distance can take a varying amount of time to find that
ever-present "clue" to which way they went.
It could also be modified to save a form of Tracking
structure too.
Tony
----- Original Message -----
From: "Jason Gauthier" <[EMAIL PROTECTED]>
To: "'Rom'" <[email protected]>
Sent: Thursday, November 07, 2002 8:30 PM
Subject: RE: Tracking Algorithm
> When I say 'track' that's just the generic term I use so people will
> understand what I'm talking about :)
>
> Specifically, it's the point A to point B algorithm I'm interested in.
>
>
> > -----Original Message-----
> > From: Josh [mailto:[EMAIL PROTECTED]
> > Sent: Thursday, November 07, 2002 8:24 PM
> > To: Rom
> > Subject: Re: Tracking Algorithm
> >
> >
> > Earlier this year there were some good discussions on how to
> > make a more realistic tracking code, that actually followed
> > someone, using a track_struct, and that faded over
> > time/weather/etc... Thats What I plan on doing for my
> > tracking codes when I get around to it. Tracking someone
> > that doesnt move is kinda silly;)
> >
> > Josh
> > (if your really interested i might have the emails save, but
> > there on the mailing list archives somewhere)
> >
> > ----- Original Message -----
> > From: "Mike Barton" <[EMAIL PROTECTED]>
> > To: "Jason Gauthier" <[EMAIL PROTECTED]>; <[email protected]>
> > Sent: Thursday, November 07, 2002 5:57 PM
> > Subject: Re: Tracking Algorithm
> >
> >
> > > I've long been using the standard track code (merc aged).
> > It's fairly
> > > complicated code, uses a lot of memory/CPU and is slow. While this
> > > type of algorithm is above my head, I'm wondering if any
> > others have
> > > been written? (Or tips for increasing the performance on the stock
> > > merc one?)
> >
> > I haven't ever seen a really good snippet for this either...
> > I've been meaning to play with some code along those lines
> > for quite a while now, but I just haven't had the time.
> >
> > When you're talking about this type of algorithm (minimum
> > spanning path on an unweighted, connected graph), the
> > complexity is very bad (at best O(m*n)), and there's just no
> > amazingly wonderful way to do it. The heuristic algorithms
> > to do it the fastest aren't simple, and the simple ways to do
> > it can be amazingly slow. There is at least a lot of
> > information on available.. it's a popular topic since it
> > basically has the same model as things like finding the best
> > route for traffic on a network.
> >
> > --Palrich.
> >
