So the biggest difference between Breadth First and Dykstra’s algorythm is the ability to include movement costs. You want the shortest path (in terms of movement cost) to be “tested” over and above the longer paths. For that, you need to be able to “tweak” the search order. In C++, the first thing that would spring to mind is to use a PriorityQueue instead of a Queue. PriorityQueues allow you to basically “insert” a node based on its priority so if test point 1 has an edge movement cost of 5, and test point 2 has an edge movement cost of 3, you want to test point 2 and its neighbors BEFORE you test 1 and its neighbors.
A Queue won’t work for this, and even a List of Waypoints won’t work for this, you need a list that holds a pair of values… the Waypoint, and the Priority…
So for that, we need a wrapper class
class PQWaypoint {
public float priority=0;
pubic Waypoint waypoint;
}
Now we can make a List to be our queue…
When you want to enqueue:
for(int i=0;i<queue.Count;i++){
{
if(itemtoadd.priority>=queue[i].priority)
{
queue.Insert(i,itemtoadd);
}
}
When you want to dequeue,
item=queue[0];
List.Remove(item);
So I went ahead and made a PriorityQueue class, just to make things a little easier… and more extensible…
my PriorityQueue is completely reuseable, but VERY bare bones…
public class PQItem
{
public float priority = 0;
}
/// <summary>
/// Very simple PriorityQueue system, using Lists.
/// To make this extensible, Queue items should be data classes that inherit PQItem.
/// </summary>
public class PriorityQueue
{
List<PQItem> priorityQueue = new List<PQItem>();
public int Count
{
get
{
return priorityQueue.Count;
}
}
/// <summary>
/// Returns the first item in the queue, which by default has the lowest priority
/// </summary>
/// <returns></returns>
public PQItem Dequeue()
{
PQItem result = priorityQueue[0];
priorityQueue.Remove(result);
return result;
}
/// <summary>
/// Enqueues an item, based on item.priority's value.
/// </summary>
/// <param name="item"></param>
public void Enqueue(PQItem item)
{
if (priorityQueue.Count == 0)
{
priorityQueue.Add(item);
return;
}
for (int i = 0; i < priorityQueue.Count; i++)
{
if (item.priority <= priorityQueue[i].priority)
{
priorityQueue.Insert(i, item);
return;
}
}
priorityQueue.Add(item); //only reached when priority is highest.
}
}
Notice that PQItem ONLY contains the priority. That’s by design, because I want this PriorityQueue to be extensible. I want to be able to use it for Waypoints, but later, I might want to use PriorityQueue to determine which character has the next move based on his or her speed… So the class just works with the PQItem data class… it’s up to you when you use it to create the actual data class that will hold the Waypoint…
class PQWaypoint: PQItem //Inherits from PQItem, will automatically have a .position field.
{
public Waypoint: waypoint;
}
It’s very important that the fields be public! Otherwise you won’t be able to read them in the search code…
Now that you have this PriorityQueue class, the rest is relatively easy…
First, of course, you need movement costs on the waypoints… I added this to Waypoint:
public Int MovementCost=1; //Actually, i used a serialized field and a getter, but you know how that works.
Now… in your Pathfinding class, where you run the breadth first search… use a PriorityQueue instead of a Queue…
PriorityQueue queue = new PriorityQueue(); //Don't worry about the <PQWaypoint> part.
PQWaypoint pqWaypoint = new PQWaypoint();
pqWaypoint.waypoint = start; //seed it with the starting waypoint
pqWaypoint.priority = 0;
queue.Enqueue(pqWaypoint);
So… because we inherited PQWaypoint from PQItem, queue.Enqueue will accept PQWaypoint even though it calls for a PQItem. To the PriorityQueue, they’re the same…
while (queue.Count)>0
{
pqWaypoint = (PQWaypoint)queue.Dequeue(); //I used a typecast here since Dequeue returns a PQItem
Waypoint test = pqWaypoint.waypoint;
// Run your code just like you would before using test
Now, when you get to the part where it’s time to add the neighbors to the queue… we need to Enqueue a PQWaypoint, not a Waypoint…
PQWaypoint newPQWaypoint = new PQWaypoint();
// Setting the priority to be the movement cost that it took to get to test + the movementcost of the waypointToAdd
newPQWaypoint.priority = pqWaypoint.priority + waypointToAdd.MovemementCost;
newPQWaypoint.waypoint = waypointToAdd;
queue.Enqueue(newPQWaypoint);
What happens is that as you add each neighbor, the movement cost for that tile is added to the amount of time to get to the tile you’re testing from… So for the first tile, priority is 0 (because you started there)… each of its neighbors when enqueued will get 0 + waypoint.movemencost…
-1,1(1) 0,1(1) 1,1(1) 2,1(1) 3,1(1) 4,1(1) 5,1(1)
-1,0 (1) S (0) 1,0(5) 2,0(5) 3,0(1) 4,0(1) F(1)
-1,-1(1) 0,-1(1) 1,-1(1) 2,-1(1) 3,-1(1) 4,-1(1) 5,-1(1)
In the above example, we’re starting at S… it’s the first enqueued, with a priority of 0…
0,1 will be enqueued with a priority of 1 (0 + 1)
1,0 will be enqueued with a priority of 5 (0 + 5)
0,-1 will be enqueued with a priority of 1
-1,0 will be enqueued with a priority of 1
Now in the order in the queue will be
-1,0(1)
0,-1 (1)
0,1(1)
1,0 (5)
Now -1,0will be the test…
-1,1 will be enqueued with a priority of 2 (1 + 1)
-1,-1 will be enqueued with a priority of 2 (1 + 1)
0,-1 (1)
0,1(1)
-1,-1(2)
-1,1(2)
1,0 (5)
Test 0,-1 (1)
1,1 will be enqueued with a priority of 2(1+1)
0,1(1)
1,1(2)
-1,-1(2)
-1,1(2)
1,0 (5) //Notice that 1,0 remains at the end of the queue
This pattern will continue until 4,1 is enqueued (5 moves)… only THEN will 1,0 be high enough in the queue to test. Since the surrounding tiles will have been explored, it’s likely that a path will have been found long before any path going through that tree tile will get used…
That being said, once you implement this with multiple entities in the scene and more blocked tiles, then you’d find that they do eventually select tree tiles.
And here’s a video example of my enemies skipping “tree tiles”
The enemies “prefer” the lighter color tiles, but if they’re blocked, they’ll choose the darker tiles.
Some more familiar with A* and Dykstra’s algorythm will quickly point out that my solution differs from some of the classical solutions… but for the sake of this project, it’s more than adequate to implement terrain cost without imposing too much overhead.