13 Feb, 2013, lakedoo23 wrote in the 61st comment:
Votes: 0
=I built a path generating class based on BFS algorithm in my client, not sure if this will help any but couldn't hurt to check it out.
The code is in C# but I am sure it could be retrofitted for any language your using as it doesn't have anything too crazy.

In the example I am going from map 1, room 1 to map 1, room 10. Simple example but just for proof of concept.


The world I populated looks like this…

# <== Map 1, Room 10
|
#-#-#
| | |
#-#-#
| | |
#-#-#
^
Map 1, Room 1

public class Pathfinder
{
private static Dictionary<uint, NodeType> WorldNodes = new Dictionary<uint, NodeType>();

public Pathfinder()
{
PopulateWorldNodes();

NodeType startRoom = WorldNodes[NodeType.GenerateKey(1, 1)];
NodeType stopRoom = WorldNodes[NodeType.GenerateKey(1, 10)];

List<string> path = FindPath(startRoom, stopRoom);
}

/// <summary>
/// Popular your world with rooms, using map and room coordinate system.
/// </summary>
private void PopulateWorldNodes()
{
// create current room with map, room numbers
NodeType node = new NodeType(1, 1);
// add some exits and rooms linked to current room.
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 2));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 3));
// add the room to the world collection of rooms.
WorldNodes.Add(node.CurrentCoordinates.Key, node);

// repeat as many as you want!
node = new NodeType(1, 2);

node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 1));
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 4));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 6));

WorldNodes.Add(node.CurrentCoordinates.Key, node);


node = new NodeType(1, 3);
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 1));
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 6));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 7));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 4);
node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 2));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 5));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 5);
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 4));
node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 6));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 9));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 6);
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 5));
node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 3));
node.Exits.Add(NodeType.Direction.East, new NodeType.CoordinateType(1, 8));
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 2));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 7);
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 3));
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 8));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 8);
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 9));
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 6));
node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 7));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 9);
node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 8));
node.Exits.Add(NodeType.Direction.West, new NodeType.CoordinateType(1, 5));
node.Exits.Add(NodeType.Direction.North, new NodeType.CoordinateType(1, 10));

WorldNodes.Add(node.CurrentCoordinates.Key, node);

node = new NodeType(1, 10);

node.Exits.Add(NodeType.Direction.South, new NodeType.CoordinateType(1, 9));

WorldNodes.Add(node.CurrentCoordinates.Key, node);


}

public class NodeType
{
public enum Direction
{
North,
South,
East,
West,
Northwest,
Southwest,
Northeast,
Southeast,
Up,
Down
}

public class CoordinateType
{
public CoordinateType(int map, int room)
{
MapNumber = map;
RoomNumber = room;
Key = GenerateKey(map, room);
}

public int MapNumber
{get;set;}
public int RoomNumber
{get;set;}
public uint Key
{get;set;}
}

public CoordinateType CurrentCoordinates;
public Dictionary<Direction, CoordinateType> Exits = new Dictionary<Direction, CoordinateType>();

public NodeType(int iMap, int IRoom)
{
CurrentCoordinates = new CoordinateType(iMap, IRoom);
}
// create a hash up of the map and room values for indexing.
public static uint GenerateKey(int map, int room)
{
return (uint)((map << 16) | (room & 0xFFFF));
}
}

/// <summary>
/// Main processor for finding shortest path between 2 vertices.
/// </summary>
/// <param name="iStartNode"></param>
/// <param name="iStopNode"></param>
/// <returns></returns>
public static List<string> FindPath(NodeType iStartNode, NodeType iStopNode)
{
Dictionary<NodeType, bool> visitedNode = new Dictionary<NodeType, bool>();
Dictionary<NodeType, NodeType> tracePath = new Dictionary<NodeType, NodeType>();

NodeType currentRoom;

Queue<NodeType> pathingQueue = new Queue<NodeType>();

pathingQueue.Enqueue(iStartNode);

visitedNode.Add(iStartNode, true);

int retries = 5000;
// Keep going til we either run out of rooms or our retry count has expired.
while (pathingQueue.Count != 0 || retries == 0)
{
// dequeue the next room in the queue for processing.
currentRoom = pathingQueue.Dequeue();
// check to see if the current room is our destination.
if (currentRoom.Equals(iStopNode))
{
break;
}
else
{
// checkeach exit for the room for other rooms to add to our queue for processing.
foreach (KeyValuePair<NodeType.Direction, NodeType.CoordinateType> nKey in currentRoom.Exits)
{
NodeType nextRoom = WorldNodes[nKey.Value.Key];

if (nextRoom.CurrentCoordinates.MapNumber != 0)
{
// if the room isnt in our trace collection then we need to add it.
// this will pair the parent and child nodes together for later unwinding.
if (!tracePath.ContainsKey(nextRoom))
{
pathingQueue.Enqueue(nextRoom);
tracePath.Add(nextRoom, currentRoom);
}
}
}
}

retries–;

}



return CreatePath(tracePath, iStartNode, iStopNode); ;

}

private static string GetDirection(NodeType iCurrent, NodeType iNext)
{

foreach (KeyValuePair<NodeType.Direction, NodeType.CoordinateType> nKey in iCurrent.Exits)
{
if (iNext.CurrentCoordinates.Key == nKey.Value.Key)
{
return nKey.Key.ToString();
}
}

return string.Empty;

}

public static List<string> CreatePath(Dictionary<NodeType, NodeType> iTrace, NodeType iStart, NodeType iStop)
{

List<string> directions = new List<string>();

NodeType rootNode = new NodeType(0, 0);
NodeType childNode = iStop;

while (!rootNode.Equals(iStart))
{

rootNode = iTrace[childNode];

directions.Add(GetDirection(rootNode, childNode));

childNode = rootNode;
}

return directions;
}
}
60.0/61