/** information for paths.c **************************************
* *
* A lot of effort and time has been put into this code and *
* text. Permission to use it is granted provided that you *
* keep the headers intact. *
* I would like VERY much any comments/suggestions you might *
* have. If you use this code, I would appreciate very much a *
* mail just saying you did! :) *
* *
* Jorge Ribeiro Pereira, <evren_ash@hotmail.com> 20/12/1998 *
* *
******************************************************************/
*************************************************************
INDEX:
*************************************************************
SECTION 0 - Introduction - IMPORTANT
SECTION 1 - Why would you want to use this code?
SECTION 2 - Changes needed for this code to work
SECTION 3 - Replacing the older track/hunt code
SECTION 4 - The functions and example commands in
this code ( important )
*************************************************************
SECTION 0:
*************************************************************
I've tested this with Envy, but it should work on Merc based
muds. It can be easily altered to most other code bases
though. Some instructions might not be very accurate, since
I've recoded my Envy base nearly beyond recognition(kidding!),
so if something is completly non-understandable, please mail
me so I can fix this document. :)
For those who don't want to read this whole document, or
aren't really interested in new functions, the bottom line is
that the get_direction() function in paths.c is a replacement
for the find_path() function that ships with the code in
track.c(or hunt.c) files (think from SillyMud).
Also, if that's the only function you're planning to use, you
just need to perform step 1, 2 and 4 of section 2
(note for programmers)
I initially had included in this file versions of these functions
that didn't do the path length checking, that is, returned not the
best path, but only the first they could find. You can easily change
the existing functions to have that behavior (by just adding a "break"
after a path is found in the loop), though I doubt you'd want to.
Anyway, if you're by any means interested in that, or other
variations of this code, just mail me.
*************************************************************
SECTION 1:
*************************************************************
1) I believe this code to be a LOT faster then the code used
in any of the tracking codes I've seen so far. The trick is
in the "visited" field we add to room_index_data (see below)
which avoids the need for building a whole data structure to
keep track of the path's we've discarded(or other algorithm,
exclusion or whatever).
2) The get_direction function gets the BEST (shortest) path
between two rooms, which avoids that problem of beeing told
to go north, then beeing told to go south, then beeing told
to go north... (loop), because it's always following the
same path, and not just following the one that appears first
in memory (think this is fixed in some versions of the track
code, but not sure on which).
3) If you take a close look, you'll soon notice that the those
functions returning directions never even need to allocate any
memory, and that also adds a lot of performance increase, since
mallocing is a s l o w operation.
Also, there's a nifty function, get_dir_somewhere(), that given
a predicate function will look for the path to a room that matches
the predicate, and return the direction. get_path_somewhere() does
the same but returns a path, like get_path does. A predicate function
is a function that given a room pointer and an argument returns
TRUE or FALSE. This is looked into with more detail in section 4, and
is more simple then I it probably looks, just check out the code.
I also provide functions that will return the full path ( not
only a direction) towards a room.
*************************************************************
SECTION 2 - Changes needed for this code to work
*************************************************************
You can get this to work with these steps:
1) You need to add an extra field to the room_index_data
structure in merc.h. Add the line marked with ++:
-- merc.h ------------------------------------------------
struct room_index_data
{
ROOM_INDEX_DATA * next;
CHAR_DATA * people;
OBJ_DATA * contents;
EXTRA_DESCR_DATA * extra_descr;
AREA_DATA * area;
EXIT_DATA * exit [MAX_DIR];
++ bool visited; /* paths.c */
-----------------------------------------------------------
2) You need to declare the functions somewhere in merc.h
so they can be used anywhere. You could declare them
all in merc.h, together with the PATH_DATA type, but
you can keep them all in paths.c if you'e not planning
to use any other functions.
Add to your merc.h file:
-- merc.h ------------------------------------------------
++ int get_direction ( ROOM_INDEX_DATA *pOrig,
++ ROOM_INDEX_DATA *pDest, bool pass_doors );
---------------------------------------------------------
3) If you wish to test the example commands(see below), add the
command declarations to your merc.h:
-- merc.h --------------------------------------------------
++ DECLARE_DO_FUN( do_path );
++ DECLARE_DO_FUN( do_direction );
++ DECLARE_DO_FUN( do_whereto );
------------------------------------------------------------
4) Now all you need to do is adding the file to the Makefile
Add paths.o to the O_FILES variable in your Makefile, and
type "make" (this is the Envy procedure, not sure about others)
*************************************************************
SECTION 3 - Replacing the older track/hunt code.
*************************************************************
1) You need to replace the find_path() function with the
get_direction() function, wherever it shows up ( either track.c
or hunt.c ).
If you have none of these, I suggest you get the track
code from, eg: ftp.games.org, and then get back to this.
hint: if you have no idea, on the command line type:
grep -i "find_path" *.c *.h
1.1) in the do_track / skill_track function replace:
-- direction = find_path( ch->in_room->vnum,
-- victim->in_room->vnum,
-- ch, -40000, fArea );
with:
++ direction = get_direction( ch->in_room,
++ victim->in_room, TRUE );
1.2) in the hunt_victim function replace:
-- dir = find_path( ch->in_room->vnum,
-- ch->hunting->who->in_room->vnum,
-- ch, -40000, TRUE );
with:
++ dir = get_direction( ch->in_room,
++ ch->hunting->who->in_room, TRUE );
*************************************************************
SECTION 4 - The functions and example commands in this code
*************************************************************
Main functions in paths.c
get_direction : returns a direction for the shortest
path towards a room. This can be used
to replace the find_path function that
ships with the track/hunt code.
get_path : builds a list of the rooms that make
the shortest path between two rooms
get_dir_somewhere : given a function that takes a room and
an argument and returns TRUE or FALSE,
returns the shortest path to a room to
which that function evaluates TRUE.
get_path_somewhere : same as the above, but returns the path,
like get_path does.
( check the examples for these functions
in do_whereto() )
( the above functions take a boolean value as last argument that
when set to TRUE, will make the functions search paths through
doors. The first argument for them is a pointer to the origin
room, and the last argument a pointer to the destination room )
do_direction : a simple command that given a room vnum
will return the direction you have to
follow to get there. It's an example of
how to use get_direction()
do_path : a simple command that given a room vnum
will return the full list of direction
you have to take to get there.
follow to get to it. It's an example of
how to use get_path()
is_room_name : function that given a room pointer and
a string checks if the room has the string
in its name. Used as an argument to
get_dir_somewhere, to build the do_whereto
command(below)
do_whereto : an example command of how to use
get_dir_somewhere(). Given a string
argument returns the shortest path to a
room with that string as name.
// auxiliar functions
- Some of the functions above provide the entry point to recursive
functions. These have the same name with "_" as suffix.
(example: get_path() and get_path_() )
path_string : given a path, returns a string with the
directions (uses a static buffer).
free_path : frees the memory allocated for a path.
add_to_path : adds a room(from a direction) to a path.
new_path_data : creates an empty path data. It's the same
as using add_to_path on a NULL list.
WARNING: When using get_path and get_path_somewhere, don't forget
to free the memory for the path it returns by using
free_path. Check the do_path command for an example.
NOTE: You could well change the "malloc" in new_path_data
and append_path to use some other mem allocation code,
like alloc_mem.
THE END
-----------------------------------------------------------------------
- Evren ( Jorge Pereira <evren_ash@hotmail.com> )
Braga - Portugal, 20/12/1998