29 Jan, 2009, Omega wrote in the 2nd comment:

Nope, but if you get the pathfinding system installed on a stock-rom, you can get speedwalk directions right in the mud, from your exact location to whatever area you want to goto.

Been awhile since I seen that system kick'n around, if you cannot find it, I'll try and dig up my old copy.

I had it so when you'd type area's, it would list the speedwalk directions from your location. beside each area. Can't use it anymore with my worldmap. Fails to recognize it :P

Anyways, thats the best bet I'd say.

Been awhile since I seen that system kick'n around, if you cannot find it, I'll try and dig up my old copy.

I had it so when you'd type area's, it would list the speedwalk directions from your location. beside each area. Can't use it anymore with my worldmap. Fails to recognize it :P

Anyways, thats the best bet I'd say.

29 Jan, 2009, Omega wrote in the 3rd comment:

29 Jan, 2009, Guest wrote in the 4th comment:

i put in the snippit, but not sure how to work it…

rom doesnt have these so i put them in….

int lvnum; /* OLC - Lower vnum */

int uvnum; /* OLC - Upper vnum */

for this…..

void do_pathfind(CHAR_DATA *ch, char *argument)

{

CHAR_DATA *victim;

char arg[MAX_STRING_LENGTH];

char buf[MAX_STRING_LENGTH];

char *path;

one_argument(argument, arg);

if ((victim = get_char_world(ch, arg)) == NULL) return;

if ((path = pathfind(ch->in_room, victim->in_room)) != NULL)

sprintf(buf, "Path: %s\n\r", path);

else

sprintf(buf, "Path: Unknown.\n\r");

send_to_char(buf, ch);

return;

}

i either get path unknown or path with nothing after it…

i take it im supposed to put in a mobs name…

rom doesnt have these so i put them in….

int lvnum; /* OLC - Lower vnum */

int uvnum; /* OLC - Upper vnum */

for this…..

void do_pathfind(CHAR_DATA *ch, char *argument)

{

CHAR_DATA *victim;

char arg[MAX_STRING_LENGTH];

char buf[MAX_STRING_LENGTH];

char *path;

one_argument(argument, arg);

if ((victim = get_char_world(ch, arg)) == NULL) return;

if ((path = pathfind(ch->in_room, victim->in_room)) != NULL)

sprintf(buf, "Path: %s\n\r", path);

else

sprintf(buf, "Path: Unknown.\n\r");

send_to_char(buf, ch);

return;

}

i either get path unknown or path with nothing after it…

i take it im supposed to put in a mobs name…

29 Jan, 2009, Omega wrote in the 5th comment:

lvnum/uvnum

in rom it'll be low_vnum, high_vnum I believe.

you can find out easily in area_data, as thats where its getting your vnum information.

so if lvnum/uvnum are non-existant, it won't beable to find the area.

in rom it'll be low_vnum, high_vnum I believe.

you can find out easily in area_data, as thats where its getting your vnum information.

so if lvnum/uvnum are non-existant, it won't beable to find the area.

29 Jan, 2009, Guest wrote in the 6th comment:

i changed the lvnum's in pathfind.c to min_vnum's and the uvnum's to max_vnum's but still not working :(

-xrak

-xrak

29 Jan, 2009, Omega wrote in the 7th comment:

post the code in the pastebin, and I'll gander at it.

I'll see what we can do about it :)

** is very good at solving c/c++ bugs

I'll see what we can do about it :)

** is very good at solving c/c++ bugs

29 Jan, 2009, Guest wrote in the 8th comment:

this is the stock one, on mine lvnums are min_vnum and uvnums are max_vnums

void do_pathfind(CHAR_DATA *ch, char *argument)

{

CHAR_DATA *victim;

char arg[MAX_STRING_LENGTH];

char buf[MAX_STRING_LENGTH];

char *path;

one_argument(argument, arg);

if ((victim = get_char_world(ch, arg)) == NULL) return;

if ((path = pathfind(ch->in_room, victim->in_room)) != NULL)

sprintf(buf, "Path: %s\n\r", path);

else

sprintf(buf, "Path: Unknown.\n\r");

send_to_char(buf, ch);

return;

}

#include <sys/types.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <time.h>

#include "merc.h"

#define RID ROOM_INDEX_DATA

/* local varibles */

bool gFound;

/* local functions */

bool examine_room args (( RID *pRoom, RID *tRoom, AREA_DATA *pArea, int steps ));

void dijkstra args (( RID *chRoom, RID *victRoom ));

RID *heap_getMinElement args (( HEAP *heap ));

HEAP *init_heap args (( RID *root ));

/*

* This function will return a shortest path from

* room 'from' to room 'to'. If no path could be found,

* it will return NULL. This function will only return

* a path if both rooms where in the same area, feel

* free to remove that restriction, and modify the rest

* of the code so it will work with this.

*/

char *pathfind(RID *from, RID *to)

{

int const exit_names [] = { 'n', 'e', 's', 'w', 'u', 'd' };

RID *pRoom;

AREA_DATA *pArea;

static char path[MAX_STRING_LENGTH]; // should be plenty.

int iPath = 0, vnum, door;

bool found;

if (from == to) return "";

if ((pArea = from->area) != to->area) return NULL;

/* initialize all rooms in the area */

for (vnum = pArea->lvnum; vnum < pArea->uvnum; vnum++)

{

if ((pRoom = get_room_index(vnum)))

{

pRoom->visited = FALSE;

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

pRoom->exit[door]->color = FALSE;

}

}

}

/* initialize variables */

pRoom = from;

gFound = FALSE;

/* In the first run, we only count steps, no coloring is done */

dijkstra(pRoom, to);

/* If the target room was never found, we return NULL */

if (!gFound) return NULL;

/* in the second run, we color the shortest path using the step counts */

if (!examine_room(pRoom, to, pArea, 0))

return NULL;

/* then we follow the trace left by examine_room() */

while (pRoom != to)

{

found = FALSE;

for (door = 0; door < 6 && !found; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

if (!pRoom->exit[door]->color) continue;

pRoom->exit[door]->color = FALSE;

found = TRUE;

path[iPath] = exit_names[door];

iPath++;

pRoom = pRoom->exit[door]->to_room;

}

if (!found)

{

bug("Pathfind: Fatal Error in %d.", pRoom->vnum);

return NULL;

}

}

path[iPath] = '\0';

return path;

}

/*

* This function will examine all rooms in the same area as chRoom,

* setting their step count to the minimum amount of steps needed

* to walk from chRoom to the room. If victRoom is encountered, it

* will set the global bool gFound to TRUE. Running time for this

* function is O(n*log(n)), where n is the amount of rooms in the area.

*/

void dijkstra(RID *chRoom, RID *victRoom)

{

RID *pRoom;

RID *tRoom;

RID *xRoom;

HEAP *heap;

int door, x;

bool stop;

heap = init_heap(chRoom);

while (heap->iVertice)

{

if ((pRoom = heap_getMinElement(heap)) == NULL)

{

bug("Dijstra: Getting NULL room", 0);

return;

}

if (pRoom == victRoom)

gFound = TRUE;

/* update all exits */

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

/* update step count, and swap in the heap */

if (pRoom->exit[door]->to_room->steps > pRoom->steps + 1)

{

xRoom = pRoom->exit[door]->to_room;

xRoom->steps = pRoom->steps + 1;

stop = FALSE;

while ((x = xRoom->heap_index) != 1 && !stop)

{

if (heap->knude[x/2]->steps > xRoom->steps)

{

tRoom = heap->knude[x/2];

heap->knude[x/2] = xRoom;

xRoom->heap_index = xRoom->heap_index/2;

heap->knude[x] = tRoom;

heap->knude[x]->heap_index = x;

}

else stop = TRUE;

}

}

}

}

/* free the heap */

free(heap);

}

/*

* This function walks through pArea, searching for tRoom,

* while it colors the path it takes to get there. It will

* return FALSE if tRoom was never encountered, and TRUE if

* it does find the room.

*/

bool examine_room(RID *pRoom, RID *tRoom, AREA_DATA *pArea, int steps)

{

int door;

/* been here before, out of the area or can we get here faster */

if (pRoom->area != pArea) return FALSE;

if (pRoom->visited) return FALSE;

if (pRoom->steps < steps) return FALSE;

/* Have we found the room we are searching for */

if (pRoom == tRoom)

return TRUE;

/* mark the room so we know we have been here */

pRoom->visited = TRUE;

/* Depth first traversel of all exits */

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

/* assume we are walking the right way */

pRoom->exit[door]->color = TRUE;

/* recursive return */

if (examine_room(pRoom->exit[door]->to_room, tRoom, pArea, steps + 1))

return TRUE;

/* it seems we did not walk the right way */

pRoom->exit[door]->color = FALSE;

}

return FALSE;

}

/*

* This function will initialize a heap used for the

* pathfinding algorithm. It will return a pointer to

* the heap if it succedes, and NULL if it did not.

*/

HEAP *init_heap(RID *root)

{

AREA_DATA *pArea;

RID *pRoom;

HEAP *heap;

int i, size, vnum;

if ((pArea = root->area) == NULL) return NULL;

size = pArea->uvnum - pArea->lvnum;

/* allocate memory for heap */

heap = calloc(1, sizeof(*heap));

heap->knude = calloc(2 * (size + 1), sizeof(ROOM_INDEX_DATA *));

heap->size = 2 * (size + 1);

/* we want the root at the beginning */

heap->knude[1] = root;

heap->knude[1]->steps = 0;

heap->knude[1]->heap_index = 1;

/* initializing the rest of the heap */

for (i = 2, vnum = pArea->lvnum; vnum < pArea->uvnum; vnum++)

{

if ((pRoom = get_room_index(vnum)))

{

if (pRoom == root) continue;

heap->knude*= pRoom;*

heap->knude*->steps = 2 * heap->size;*

heap->knude*->heap_index = i;*

i++;

}

}

heap->iVertice = i-1;

/* setting the rest to NULL */

for (; i < heap->size; i++)

heap->knude*= NULL;*

return heap;

}

/*

* This function will return the smallest element in the heap,

* remove the element from the heap, and make sure the heap

* is still complete.

*/

RID *heap_getMinElement(HEAP *heap)

{

RID *tRoom;

RID *pRoom;

bool done = FALSE;

int i = 1;

/* this is the element we wish to return */

pRoom = heap->knude[1];

/* We move the last vertice to the front */

heap->knude[1] = heap->knude[heap->iVertice];

heap->knude[1]->heap_index = 1;

/* Decrease the size of the heap and remove the last entry */

heap->knude[heap->iVertice] = NULL;

heap->iVertice–;

/* Swap places till it fits */

while(!done)

{

if (heap->knude*== NULL)*

done = TRUE;

else if (heap->knude[2*i] == NULL)

done = TRUE;

else if (heap->knude[2*i+1] == NULL)

{

if (heap->knude*->steps > heap->knude[2*i]->steps)*

{

tRoom = heap->knude*;*

heap->knude*= heap->knude[2*i]; *

heap->knude*->heap_index = i;*

heap->knude[2*i] = tRoom;

heap->knude[2*i]->heap_index = 2*i;

i = 2*i;

}

done = TRUE;

}

else if (heap->knude*->steps <= heap->knude[2*i]->steps &&*

heap->knude*->steps <= heap->knude[2*i+1]->steps)*

done = TRUE;

else if (heap->knude[2*i]->steps <= heap->knude[2*i+1]->steps)

{

tRoom = heap->knude*;*

heap->knude*= heap->knude[2*i];*

heap->knude*->heap_index = i;*

heap->knude[2*i] = tRoom;

heap->knude[2*i]->heap_index = 2*i;

i = 2*i;

}

else

{

tRoom = heap->knude*;*

heap->knude*= heap->knude[2*i+1];*

heap->knude*->heap_index = i;*

heap->knude[2*i+1] = tRoom;

heap->knude[2*i+1]->heap_index = 2*i+1;

i = 2*i+1;

}

}

/* return the element */

return pRoom;

}

void do_pathfind(CHAR_DATA *ch, char *argument)

{

CHAR_DATA *victim;

char arg[MAX_STRING_LENGTH];

char buf[MAX_STRING_LENGTH];

char *path;

one_argument(argument, arg);

if ((victim = get_char_world(ch, arg)) == NULL) return;

if ((path = pathfind(ch->in_room, victim->in_room)) != NULL)

sprintf(buf, "Path: %s\n\r", path);

else

sprintf(buf, "Path: Unknown.\n\r");

send_to_char(buf, ch);

return;

}

#include <sys/types.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <unistd.h>

#include <time.h>

#include "merc.h"

#define RID ROOM_INDEX_DATA

/* local varibles */

bool gFound;

/* local functions */

bool examine_room args (( RID *pRoom, RID *tRoom, AREA_DATA *pArea, int steps ));

void dijkstra args (( RID *chRoom, RID *victRoom ));

RID *heap_getMinElement args (( HEAP *heap ));

HEAP *init_heap args (( RID *root ));

/*

* This function will return a shortest path from

* room 'from' to room 'to'. If no path could be found,

* it will return NULL. This function will only return

* a path if both rooms where in the same area, feel

* free to remove that restriction, and modify the rest

* of the code so it will work with this.

*/

char *pathfind(RID *from, RID *to)

{

int const exit_names [] = { 'n', 'e', 's', 'w', 'u', 'd' };

RID *pRoom;

AREA_DATA *pArea;

static char path[MAX_STRING_LENGTH]; // should be plenty.

int iPath = 0, vnum, door;

bool found;

if (from == to) return "";

if ((pArea = from->area) != to->area) return NULL;

/* initialize all rooms in the area */

for (vnum = pArea->lvnum; vnum < pArea->uvnum; vnum++)

{

if ((pRoom = get_room_index(vnum)))

{

pRoom->visited = FALSE;

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

pRoom->exit[door]->color = FALSE;

}

}

}

/* initialize variables */

pRoom = from;

gFound = FALSE;

/* In the first run, we only count steps, no coloring is done */

dijkstra(pRoom, to);

/* If the target room was never found, we return NULL */

if (!gFound) return NULL;

/* in the second run, we color the shortest path using the step counts */

if (!examine_room(pRoom, to, pArea, 0))

return NULL;

/* then we follow the trace left by examine_room() */

while (pRoom != to)

{

found = FALSE;

for (door = 0; door < 6 && !found; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

if (!pRoom->exit[door]->color) continue;

pRoom->exit[door]->color = FALSE;

found = TRUE;

path[iPath] = exit_names[door];

iPath++;

pRoom = pRoom->exit[door]->to_room;

}

if (!found)

{

bug("Pathfind: Fatal Error in %d.", pRoom->vnum);

return NULL;

}

}

path[iPath] = '\0';

return path;

}

/*

* This function will examine all rooms in the same area as chRoom,

* setting their step count to the minimum amount of steps needed

* to walk from chRoom to the room. If victRoom is encountered, it

* will set the global bool gFound to TRUE. Running time for this

* function is O(n*log(n)), where n is the amount of rooms in the area.

*/

void dijkstra(RID *chRoom, RID *victRoom)

{

RID *pRoom;

RID *tRoom;

RID *xRoom;

HEAP *heap;

int door, x;

bool stop;

heap = init_heap(chRoom);

while (heap->iVertice)

{

if ((pRoom = heap_getMinElement(heap)) == NULL)

{

bug("Dijstra: Getting NULL room", 0);

return;

}

if (pRoom == victRoom)

gFound = TRUE;

/* update all exits */

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

/* update step count, and swap in the heap */

if (pRoom->exit[door]->to_room->steps > pRoom->steps + 1)

{

xRoom = pRoom->exit[door]->to_room;

xRoom->steps = pRoom->steps + 1;

stop = FALSE;

while ((x = xRoom->heap_index) != 1 && !stop)

{

if (heap->knude[x/2]->steps > xRoom->steps)

{

tRoom = heap->knude[x/2];

heap->knude[x/2] = xRoom;

xRoom->heap_index = xRoom->heap_index/2;

heap->knude[x] = tRoom;

heap->knude[x]->heap_index = x;

}

else stop = TRUE;

}

}

}

}

/* free the heap */

free(heap);

}

/*

* This function walks through pArea, searching for tRoom,

* while it colors the path it takes to get there. It will

* return FALSE if tRoom was never encountered, and TRUE if

* it does find the room.

*/

bool examine_room(RID *pRoom, RID *tRoom, AREA_DATA *pArea, int steps)

{

int door;

/* been here before, out of the area or can we get here faster */

if (pRoom->area != pArea) return FALSE;

if (pRoom->visited) return FALSE;

if (pRoom->steps < steps) return FALSE;

/* Have we found the room we are searching for */

if (pRoom == tRoom)

return TRUE;

/* mark the room so we know we have been here */

pRoom->visited = TRUE;

/* Depth first traversel of all exits */

for (door = 0; door < 6; door++)

{

if (pRoom->exit[door] == NULL) continue;

if (pRoom->exit[door]->to_room == NULL) continue;

/* assume we are walking the right way */

pRoom->exit[door]->color = TRUE;

/* recursive return */

if (examine_room(pRoom->exit[door]->to_room, tRoom, pArea, steps + 1))

return TRUE;

/* it seems we did not walk the right way */

pRoom->exit[door]->color = FALSE;

}

return FALSE;

}

/*

* This function will initialize a heap used for the

* pathfinding algorithm. It will return a pointer to

* the heap if it succedes, and NULL if it did not.

*/

HEAP *init_heap(RID *root)

{

AREA_DATA *pArea;

RID *pRoom;

HEAP *heap;

int i, size, vnum;

if ((pArea = root->area) == NULL) return NULL;

size = pArea->uvnum - pArea->lvnum;

/* allocate memory for heap */

heap = calloc(1, sizeof(*heap));

heap->knude = calloc(2 * (size + 1), sizeof(ROOM_INDEX_DATA *));

heap->size = 2 * (size + 1);

/* we want the root at the beginning */

heap->knude[1] = root;

heap->knude[1]->steps = 0;

heap->knude[1]->heap_index = 1;

/* initializing the rest of the heap */

for (i = 2, vnum = pArea->lvnum; vnum < pArea->uvnum; vnum++)

{

if ((pRoom = get_room_index(vnum)))

{

if (pRoom == root) continue;

heap->knude

heap->knude

heap->knude

i++;

}

}

heap->iVertice = i-1;

/* setting the rest to NULL */

for (; i < heap->size; i++)

heap->knude

return heap;

}

/*

* This function will return the smallest element in the heap,

* remove the element from the heap, and make sure the heap

* is still complete.

*/

RID *heap_getMinElement(HEAP *heap)

{

RID *tRoom;

RID *pRoom;

bool done = FALSE;

int i = 1;

/* this is the element we wish to return */

pRoom = heap->knude[1];

/* We move the last vertice to the front */

heap->knude[1] = heap->knude[heap->iVertice];

heap->knude[1]->heap_index = 1;

/* Decrease the size of the heap and remove the last entry */

heap->knude[heap->iVertice] = NULL;

heap->iVertice–;

/* Swap places till it fits */

while(!done)

{

if (heap->knude

done = TRUE;

else if (heap->knude[2*i] == NULL)

done = TRUE;

else if (heap->knude[2*i+1] == NULL)

{

if (heap->knude

{

tRoom = heap->knude

heap->knude

heap->knude

heap->knude[2*i] = tRoom;

heap->knude[2*i]->heap_index = 2*i;

i = 2*i;

}

done = TRUE;

}

else if (heap->knude

heap->knude

done = TRUE;

else if (heap->knude[2*i]->steps <= heap->knude[2*i+1]->steps)

{

tRoom = heap->knude

heap->knude

heap->knude

heap->knude[2*i] = tRoom;

heap->knude[2*i]->heap_index = 2*i;

i = 2*i;

}

else

{

tRoom = heap->knude

heap->knude

heap->knude

heap->knude[2*i+1] = tRoom;

heap->knude[2*i+1]->heap_index = 2*i+1;

i = 2*i+1;

}

}

/* return the element */

return pRoom;

}

29 Jan, 2009, David Haley wrote in the 9th comment:

Use the code tags, Luke!

(Also, make sure to space out*so that it doesn't go all italics afterward)*

(Also, make sure to space out

29 Jan, 2009, Omega wrote in the 10th comment:

Example of getting a path..

Thats an example of its usage, that should nomatter where you are in the mud (so-long as it has an exit) give you a path to hassan in midgaard.

void do_pathtest(CHAR_DATA *ch, char *argument) {

const char *path = pathfind(ch->in_room, get_room_index(ROOM_VNUM_TEMPLE));

if(!path || path[0] == '\0')

send_to_char("Unable to find the path.",ch);

else

send_to_char(path, ch);

}

Thats an example of its usage, that should nomatter where you are in the mud (so-long as it has an exit) give you a path to hassan in midgaard.

29 Jan, 2009, Guest wrote in the 11th comment:

pathtest says Unable to find the path every time :(

30 Jan, 2009, Omega wrote in the 12th comment:

Hmm, odd..

I'll go through my code at home and track down the path system I used to use and see if it will be any help.

My recommendation is todo a series of logging through the pathfind function, and see where its dropping NULL.

I'll go through my code at home and track down the path system I used to use and see if it will be any help.

My recommendation is todo a series of logging through the pathfind function, and see where its dropping NULL.

30 Jan, 2009, Guest wrote in the 13th comment:

Thank you.

30 Jan, 2009, Scandum wrote in the 14th comment:

You could create a routine that saves the rom world as a tintin++ map file using the following format.

etc

dir is either n e ne s se w nw sw u d, dirflags are 1 2 3 4 6 8 9 12 16 32 respectively with n being 1 and d being 32.

Example:

Generating the map file should be fairly easy.

The only problem is if the maximum vnum is above 15000 in which case you'll have to adjust MAX_ROOM in tintin.h.

Once you load the map file in tintin you can display a map, and generate speed walks. Should be easier than getting a snippet working.

R {vnum} {0} {<078>} {vnum} { }

E {vnum} {dir} {dir} {dirflag}

E {vnum} {dir} {dir} {dirflag}

R {vnum} {0} {<078>} {vnum} { }

E {vnum} {dir} {dir} {dirflag}

etc

dir is either n e ne s se w nw sw u d, dirflags are 1 2 3 4 6 8 9 12 16 32 respectively with n being 1 and d being 32.

Example:

R { 1} {0} {<078>} {1} { }

E { 2} {e} {e} {2}

E { 21} {s} {s} {4}

R { 2} {8} {<078>} {2} { }

E { 3} {e} {e} {2}

E { 1} {w} {w} {8}

Generating the map file should be fairly easy.

The only problem is if the maximum vnum is above 15000 in which case you'll have to adjust MAX_ROOM in tintin.h.

Once you load the map file in tintin you can display a map, and generate speed walks. Should be easier than getting a snippet working.

Random Picks

0.0/14

Votes:0-Xrakisis