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.
/// <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));
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));
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));
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));
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));
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));
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));
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));
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); } } } }
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