Pathfinding:

A Comparison of Algorithms

Anatoly Preygel

February 27, 1999

Magnet Science pd.3

Miss Matthews

Table of Contents

Abstract *

Introduction *

Project Overview *

General Pathfinding Information *

The Algorithms *

The A* Algorithm *

Uses *

Experimental Design *

General *

Variables and Trials *

Materials and Methods *

Materials *

Procedure *

Data *

Conclusions *

Acknowledgments *

Bibliography *

Appendix 1- Glossary *

Appendix 2- Code *

Appendix 3- Explanation of Programs *

Appendix 4- Maps *

Abstract

The goal of this project is to determine which pathfinding algorithms are most effective under varying circumstances in terms of the number of node expansions and the cost of the path they find. Dijkstra, best-first (heuristic) and A* (which is a 50/50 combination of the above) as well as 101 modified A* algorithms where Dijkstra and best-first were mixed in proportions from 0% to 100% (each with Euclidean, Manhattan and heuristics) were evaluated. The hypothesis was that in most cases the A* algorithm would be the most effective overall. Three programs have been created: to generate and record the cost and number of nodes expanded for each algorithm; to show the path, given a map and algorithm; to generate graphs that show the effectiveness of different algorithms on a given map taking into account different weights put on the cost and node expansions. After running the programs on 15 maps, it was found that the Manhattan heuristic is better than the other heuristics both in terms of the cost and node expansions. It was also found that it is never necessary to have more Dijkstra than heuristic in modified A* algorithms. In order to find the cheapest path, the A* algorithm should be used, in order to expand the least nodes the best-first algorithm should be used. This project has applications in the fields of robotics, games, traffic design, smarter Internet routers that deliver packets to their destination faster; these would require research with more algorithms and types of maps.

Introduction
Project Overview

This project deals with different pathfinding algorithms. Its goal is to find out how effective current pathfinding algorithms are. The algorithms were run on various maps, and were compared in terms of the cost of the path that they find and the number of times they needed to expand a node (not necessarily the number of nodes expanded, as these algorithms can expand nodes twice). The comparisons were done using computer programs written specifically for this project and which were run for all the algorithms on 15 different maps. In order to do this project it is necessary to know about pathfinding in general as well as to understand the specific algorithms.

General Pathfinding Information

Pathfinding or shortest path algorithms are any computer algorithms that find a way to get from one place to another (called the start and the goal or end, respectively). Most algorithms deal with grids of data, called maps, which store the cost of each node, or point on the grid (Fig. 1). These algorithms try to find a path along the grid (moving in only the four cardinal directions, or the four cardinal directions as well as the four diagonals) with the lowest total cost, or distance (Fig. 2). Another goal of all these algorithms is to find this path as quickly as possible while using as little memory as possible and still find the best path. There are many such algorithms each one optimized for certain conditions.

The Algorithms

There are many algorithms that are commonly known and used. These algorithms range from the simple to the complex. The simplest approaches are to go toward the goal until some sort of obstacle is reached then turn in another direction, and tracing around the edges of obstacles (Fig. 3). This is an example of a "blind-search", where the algorithm does not rely on any information about the cost of the path to the goal in selecting the next node to expand. A list of other algorithms in this "blind-search" group are the breadth-first search, the bi-directional breadth-first search, Dijkstra’s algorithm, depth-first search, iterative-deepening depth-first search. There are also some algorithms that plan the whole path before moving anywhere. Best-first algorithm expands nodes based on a heuristic estimate of the cost to the goal. Nodes, which are estimated to give the best cost, are expanded first. The most commonly used algorithm is called A* (pronounced A star), which is a combination of the Dijkstra algorithm and the best-first algorithm.

The different algorithms work in different ways. The breadth-first search begins at the start node, and then examines, or expands, all nodes one step away, then all nodes two steps away, then three steps, and so on, until the goal node is found. This algorithm is guaranteed to find a shortest path as long as all nodes have a uniform cost (Fig. 4). The bi-directional bread-first search is where two breadth-first searches are started simultaneously, one at the start and one at the goal, and they keep searching until there is a node that both searches have examined. The final path found is then the combination of the path from the start to the intersection node, and the path from the goal to the intersection node. Dijkstra’s algorithm (named after its developer, E. Dijkstra) looks at the unprocessed neighbors of the node closest to the start, and sets or updates their distances (in terms of cost, not number of nodes) from the start (Fig. 5). The Dijkstra algorithm expands the node that is farthest from the start node, so it ends up "stumbling" into the goal node just like the breadth-first search; it is guaranteed to find the shortest path. The depth-first search extends nodes (it extends a node’s descendants before its siblings) until it either reaches the goal or a certain cut-off point, it then goes onto the next possible path (Fig. 6). The iterative-deepening depth-first search is like the depth first search, but the cut-off point starts at the straight line distance to the goal, and once all nodes up to that point have been expanded the cut-off point is incremented and the search is run again. The best-first search algorithm is a heuristic search algorithm, meaning that it can take into account knowledge about the map; it is similar to Dijkstra’s algorithm, but it goes to the node closest to the goal, instead of the node farthest from the start (Fig. 7).

The A* Algorithm

The A* algorithm (Fig. 8) works much like the Dijkstra and best-first algorithms only it values nodes in a different way. Each node’s value is the sum of the actual cost to that node from the start and the heuristic estimate of the remaining cost from the node to the goal. In this way it combines the tracking of previous length from Dijkstra’s algorithm with the heuristic estimate of the remaining path from the best-first search. The A* algorithm is guaranteed to find the shortest path as long as the heuristic estimate is admissible (an admissible heuristic is one that never overestimates). If the heuristic is inadmissible then the A* algorithms won’t find the shortest path (or a path at all), but it will find a path faster and using less memory. While the heuristic must never overestimate, the closer it is to being correct the more efficient the A* algorithm will be; in fact, the Djikstra search is an A* search, where the heuristic is always 0. This algorithm also makes the most efficient use of the heuristic function, meaning that no other algorithm using the same heuristic will expand fewer nodes and find an optimal path, not counting tie-breaking among nodes of equal cost. One of the problems of the A* algorithm, as well as many other pathfinding algorithms, is that they take up a large amount of memory by storing all previous nodes or all previously take paths. There are some variations of the A* algorithm that are made to use less memory, these include the iterative deepening A* (IDA*) search and the simplified memory A* (SMA*) search. Some common heuristics for the A* algorithm are Manhattan distance (difference x plus difference y), Euclidean distance (the straight line distance), and the larger of the difference in x coordinates and the difference in y coordinates. Other variations on the A* algorithm may be accomplished by changing the ratio in which the heuristic is mixed with the distance so far, standard A* has this as a 50:50 ratio.

Uses

Pathfinding algorithms have many uses. These algorithms are useful in the field of robotics, because they can be used to guide a robot around difficult terrain without constant human intervention. This would be useful if the robot were on another planet like Mars, where some terrain must be avoided, but due to the extreme distances involved, controlling it completely via remote control would be impossible (too much delay in the radio transmission). It could also be useful if the robot were to operate underwater, where radio waves could not get to it. Pathfinding algorithms could also be used in almost any case where a vehicle needs to go somewhere, while avoiding obstacles, without human intervention. Another use is in computer games where something needs to be moved from one place to another avoiding any walls or other obstacles in the way. These algorithms could also be used to find the shortest way to drive between two points on a map, the best way to route e-mail through a computer network, or the shortest way to run telephone wires through existing conduits. Some of the algorithms mentioned earlier would be better for this than others due to the fact that each one has very different characteristics and is good at different things.

Experimental Design

General

The goal of this science project is to determine which pathfinding algorithms are most effective under varying circumstances in terms the cost of the path they find and the number of times they expand a node. The hypothesis was that the A* algorithm will be the most effective overall. The control for this experiment is the A* algorithm.

Variables and Trials

The independent variables were the algorithm and the map. The dependent variables were the cost of the path, and the number of times a node was expanded. This simulation used 15 maps. These maps ranged from nearly empty to a maze; this allowed algorithms to show what circumstances they were best at. Any other variables, such as the computer it was run on, were kept constant. Since this is a computer simulation, each algorithm only needed to be tested on each map once, so the number of trials per algorithm per map was one. A total of 15 maps were tried, and 303 algorithms were tried (3 heuristics, and 101 values of the mixing variable for each heuristics). Thus there were evaluated 300 A*-like algorithms (not counting the 3 A* algorithms), where the heuristic and Dijkstra parts were not evenly weighted. The three A* algorithms, where the heuristic and Dijkstra parts were the same, were tested also and used as controls for the other algorithms.

Materials and Methods

Materials

One IBM Compatible computer
Microsoft Visual Basic 6.0
Microsoft Visual C++ 6.0

Procedure

Research information about pathfinding algorithms.
Use that information to write a program that given a map file (file containing data about the "world" in which the pathfinding algorithm will be run) will use all the different pathfinding algorithms on the map, and for each algorithm store the cost of its path and the number of nodes it expanded. This program must include the following pathfinding algorithms: Dijkstra, best-first, A* (and variants of it with different ratios of Dijkstra to heuristic). The Dijkstra algorithm’s evaluation of a node is usually written as g(n); it is the cost to the node from the start and the best-first algorithm’s evaluation of a node is written as h(n), which is a heuristic evaluation of the remaining cost from the node to the goal. A* evaluates nodes based on the equation where n is the node, and the variants of A* are algorithms expressed as where n is the node, , and x is controlling the mixture between pure heuristic and pure Dijkstra (x=1 is pure Dijkstra, x=0 is pure heuristic). (See appendices 2 and 3)
Make 15 maps for this program to use.
Run program one with these maps.
Make a second program, which when given a specific algorithm and a map, will show the path produced and the nodes that were expanded in finding this path. This program will aid in testing the first program, as well as visualizing the paths produced. Now use it to test the first program. (See appendices 2 and 3)
Make a third program, which will take all the data from the first program and use the formula , where , L is the cost of the path, and t is the number of times a node was expanded. C thus takes into account different weights put on the cost and number of nodes expanded. This program will make a two-dimension graph with the x-axis representing the value of x (in the equation mentioned in step 2), while the y-axis will represent the value of . The graphs will use different colors to represent the value of C at that given point, for a given map, algorithm, and heuristic. (See appendices 2 and 3)
Run the third program.
Analyze the final data and draw conclusions from this data.

Data

Table of Algorithm Comparison Charts

Map #	Manhattan	Euclidean	Max
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Table 1: The data produced by program 3 for the 15 maps

Each of these charts is the output of the third program mentioned above. The number on the left is the number of the map, as can be found in appendix 4. The origin on these graphs is the top-left corner. The vertical axis represents the value of (the amount of value placed on cost and nodes expanded) in the equation , with a being zero at the top and a being one at the bottom. The horizontal axis represents (the parameter that controls mixing between the heuristic and Dijkstra) in the equation , at the right it is Dijkstra and at the left it is pure heuristic. Values can (generally) only be compared accurately with other values in their own rows. Lower values are generally better (the lowest cost, or the least number of nodes expanded, are best). The color scale from best to worst is as follows (note: not all colors may appear on all graphs): black, dark blue, dark green, dark blue-green, dark red, dark violet, light brown, light gray, dark gray, blue, light green, light blue-green, red, violet, and yellow.

Conclusions

Each algorithm has its own advantages and disadvantages. Of the three heuristics tried, Manhattan almost always does better than the other two, and hence any algorithm using Manhattan will usually be better than its Max and Euclidean distance equivalents. In the equation , values of (variable that controls mixing of heuristic and Dijkstra) above .5, never generate a shorter path than the algorithm generates when is .5, and they almost always have to extend more nodes. Therefore, it is never necessary to use a value of x above .5. So we know that A* is the algorithm that expands the fewest nodes without increasing the cost of the path, since A* is guaranteed to find the shortest path. This means that the original hypothesis, that the A* algorithm would be most effective overall, was correct. A value of 0 for generally results in the highest-cost path, but the algorithm doesn’t need to expand as many nodes to find this path. So to get the cheapest path while not expanding more nodes than is necessary, a value of .5 should be used for (A* algorithm); to expand the least nodes regardless of what the cost of the path will be, a value of 0 should be used for (best-first algorithm). In either case, the heuristic function that should be used is Manhattan distance.

On many of these maps, there is a value of x where the number of nodes expanded increases sharply and the cost of the path decreases sharply; in those cases there is no way to get a real compromise between cost of the path and number of nodes expanded. Otherwise, a value between 0 and .5 could result in somewhat of a compromise. On certain maps, there is a range of (usually somewhere between .1 and .25) where the algorithm expands many more nodes than it does even as pure Dijkstra. This could be due either to rounding errors, or to inherent chaotic instability within the algorithm, causing small changes in the value of x to be able to have large and unpredictable changes in the results of the algorithm. In the case of the Manhattan heuristic, this range seems to never include the numbers 0 or .5, so those values should rarely if ever produce strange results.

All of these algorithms, tend to at their worst expand a very large number of nodes, or be very far off from the optimal path, when the average node cost for the map is higher than 1. This is because this causes the heuristic to be wrong by a higher amount, reducing the ability of the algorithms to quickly find the path. This can be seen on map 4, with the max algorithm and equal to about .05, nodes are expanded over 1400 times, which means on average, every node is expanded more than 3 times. This can also be seen in the case of map 8, where there is a point where the number of node expansions skyrockets. On the other hand, many of the other maps, such as maps 5 and 9, have a more gradual progression in the number of node expansions.

Several things were learned by this experiment. It showed that these algorithms work at their worst when the average node cost is high. It also showed that it is never necessary to have more Dijkstra than heuristic and that a 50/50 mix is guaranteed to find the shortest path, without expanding more nodes than necessary. While if the least number of node expansions is needed, than the best-first algorithm should be used. There are several reasons to be confident that the results are accurate. One reason is that this is a computer simulation, hence no outside factors had a chance to influence it. Another reason is that a part of the procedure involved testing the data produced by the first program, which was the foundation of the charts in the data section. Certain results can also be mathematically proven to be true (that Manhattan distance works better than the other two heuristics as well as the fact that A* is guaranteed to find the shortest path).

This project could be extended further. One way in which this could be done is by adding more algorithms, such as breadth-first, depth-first, IDA*, and SMA* as well as adding come bi-directional algorithms. Adding more maps, perhaps even maps of real-world places could also extend this project. You could also extend this project by changing the way in which nodes are represented, in order to allow for different costs going from a node’s neighbors to the node, as opposed to the current system where going into a given node from any of its neighbors has the same cost. This change would make the experiment better suited for some real-world application such as network communications, and going from city to city on a map (a normal map, not an array of nodes).

Acknowledgments

Several people have helped to make this project come together:

My parents, who have proofread this project at various levels, as well as providing new and interesting ideas.

My grandparents, who have helped plan planning and critiquing the board.

Bibliography

"Amit's Game Programmer Information." http://www-cs-students.stanford.edu/ ~amitp/gameprog.html. October 19, 1998.

"An optimal pathfinder for vehicles in real-world digital terrain maps." http://www. student.nada.kth.se/~f93-maj/pathfinder/index.html. 1996.

Jackson, Philip C. Jr. Introduction to Artificial Intelligence. New York: Dover Publications, 1985.

Russel, Stuart and Norvig Peter. Artificial Intelligence: A Modern Approach. Upper Saddle River: Prentice Hall, 1995.

"Smart Pathfinding." http://www.gdmag.com/stout.htm. October 1996.

"Smart Unit Navigation." http://home.sol.no/~johncl/shorpath.htm. September 28, 1996.

Appendix 1- Glossary

Algorithm: A set of rules for solving a problem in a finite number of steps; in the scope of this project it refers to one of the pathfinding algorithms used.

Completeness: Whether or not an algorithm found a path.

Cost: The value given to a node to specify how passable it is. Also refers to the sum of the costs of all nodes along a path.

Distance: The length of a path, or the sum of the costs of all nodes along a path.

End/Goal Node: The point that is the algorithms’ destination.

Heuristic: In the scope of this project, a heuristic is either a function used to estimate the distance from the current node to the goal node, or the best-first pathfinding algorithm.

Map: A grid or array of points containing the cost of each point.

Node: A point on the map with a predefined cost.

Path: The sequence of moves leading from the start node to the goal node.

Start Node: The point where the pathfinding algorithm starts.

Appendix 2- Code

Listing #1: AStar.cpp

#include "AStar.hpp"

#include <iostream>

using namespace std;

bool operator == (const Point& a, const Point& b )

{

return (a.x==b.x)&&(a.y==b.y);

}

bool operator > ( const Node& a, const Node& b ){

return (a.fVal) > (b.fVal);

}

bool operator == ( const Node& a, const Node& b ){

return (a.coord==b.coord);

}

bool operator < ( const Node& a, const Node& b ){

return (a.fVal) < (b.fVal);

}

bool operator != ( const Node& a, const Node& b ){

return !(a.coord==b.coord);

}

greater<Node> comp;

bool m_Diag=false;

int AStar::doesContain(NodeQueue open, Node n)

{

for (int x=0;x<open.size();x++)

{

if (open[x]==n)

return x;

}

return -1;

}

Path AStar::run(Map map, Heuristic * h, float gv, void (__cdecl *func )(Node ex) )

{

m_Diag=false;

NodeQueue open;

NodeQueue closed;

Path path;

Node start=map.start;

Node goal=map.goal;

start.cost=getMapAt(map, start.coord.x, start.coord.y);

start.gVal=0;

start.hVal=h->run(start,goal);

start.fVal=gv*(real)start.gVal+(1-gv)*start.hVal;

start.parentCoord.x=-1;

start.parentCoord.y=-1;

open=push(open,start);

Node n;

int newg;

NodeList children;

Node child;

int inOpen;

int inClosed;

int expanded=0;

while (!open.empty())

{

expanded++;

n = open.front();

if (func!=NULL)

(*func)(n);

pop_heap( open.begin(), open.end(), comp);

open.pop_back();

closed.push_back(n);

if (n==goal)

{

path=buildPath(open,closed,n);

path.expanded=expanded;

break;

}

else

{

children.clear();

children=getChildren(map, n);

while (!children.empty())

{

child=children.front();

children.pop_front();

newg=n.gVal+child.cost;

inClosed=doesContain(closed, child);

inOpen=doesContain(open, child);

if (inClosed!=-1)

{

child=closed[inClosed];

}

if (inOpen!=-1)

{

child=open[inOpen];

}

if ((newg<child.gVal)||((inOpen==-1)&&(inClosed==-1)))

{

child.parentCoord=n.coord;

child.gVal=newg;

child.hVal=h->run(child, goal);

child.fVal=gv*(real)child.gVal+(1-gv)*child.hVal;

if (inClosed!=-1)

{

closed.erase(closed.begin()+inClosed);

}

if (inOpen==-1)

{

open=push(open,child);

}

return path;

}

NodeQueue AStar::push(NodeQueue open,Node n)

{

open.push_back( n );

push_heap( open.begin(), open.end(), comp );

return open;

}

byte AStar::getMapAt(Map map, byte x, byte y)

{

return map.map[x+y*map.width];

}

NodeList AStar::getChildren(Map map, Node p)

{

NodeList nl;

Node c;

if (p.coord.x>0)

{

if (getMapAt(map,p.coord.x-1,p.coord.y)!=0)

{

c.coord.x=p.coord.x-1;

c.coord.y=p.coord.y;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if (p.coord.x<map.width-1)

{

if (getMapAt(map,p.coord.x+1,p.coord.y)!=0)

{

c.coord.x=p.coord.x+1;

c.coord.y=p.coord.y;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if (p.coord.y<map.height-1)

{

if (getMapAt(map,p.coord.x,p.coord.y+1)!=0)

{

c.coord.x=p.coord.x;

c.coord.y=p.coord.y+1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if (p.coord.y>0)

{

if (getMapAt(map,p.coord.x,p.coord.y-1)!=0)

{

c.coord.x=p.coord.x;

c.coord.y=p.coord.y-1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if (m_Diag)

{

if ((p.coord.x>0)&&(p.coord.y>0))

{

if (getMapAt(map,p.coord.x-1,p.coord.y-1)!=0)

{

c.coord.x=p.coord.x-1;

c.coord.y=p.coord.y-1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if ((p.coord.x>0)&&(p.coord.y<map.height-1))

{

if (getMapAt(map,p.coord.x-1,p.coord.y+1)!=0)

{

c.coord.x=p.coord.x-1;

c.coord.y=p.coord.y+1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if ((p.coord.x<map.width-1)&&(p.coord.y<map.height-1))

{

if (getMapAt(map,p.coord.x+1,p.coord.y+1)!=0)

{

c.coord.x=p.coord.x+1;

c.coord.y=p.coord.y+1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,c.coord.x,c.coord.y);

nl.push_front(c);

}

if ((p.coord.x<map.width-1)&&(p.coord.y>0))

{

if (getMapAt(map,p.coord.x+1,p.coord.y-1)!=0)

{

c.coord.x=p.coord.x+1;

c.coord.y=p.coord.y-1;

c.parentCoord=p.coord;

c.cost=getMapAt(map,p.coord.x-1,p.coord.y);

nl.push_front(c);

}

return nl;

}

Path AStar::buildPath(NodeQueue open, NodeQueue closed, Node goal)

{

NodeQueue p;

p=buildPath(open,closed,p,goal);

Path path;

path.cost=0;

int size=p.size();

path.path=new Node[size];

for (int x=size-1;x>=0;x--)

{

path.path[size-1-x]=p[x];

path.cost+=p[x].cost;

}

path.length=size;

return path;

}

NodeQueue AStar::buildPath(NodeQueue open, NodeQueue closed, NodeQueue p, Node goal)

{

p.push_back(goal);

Node n;

n.coord=goal.parentCoord;

if (doesContain(open,n)!=-1)

{

n=open[doesContain(open,n)];

p=buildPath( open, closed, p, n );

}

else if (doesContain(closed,n)!=-1)

{

n=closed[doesContain(closed,n)];

p=buildPath( open, closed, p, n );

}

return p;

}

Listing #2: AStar.hpp

#include "DTypes.hpp"

class AStar: public Search

{

public:

Path run(Map map, Heuristic * h, float gv, void (__cdecl *func )(Node ex) );

private:

int doesContain(NodeQueue open, Node n);

NodeQueue push(NodeQueue open,Node n);

byte getMapAt(Map map, byte x, byte y);

NodeList getChildren(Map map, Node p);

Path buildPath(NodeQueue open, NodeQueue closed, Node goal);

NodeQueue buildPath(NodeQueue open, NodeQueue closed, NodeQueue p, Node goal);

};

Listing #3: DTypes.hpp

#ifndef DTypes

#include <queue>

#include <deque>

#include <vector>

#include <functional>

#include <list>

using namespace std;

typedef unsigned char byte;

typedef double real;

struct Point

{

int x;

int y;

};

struct Node

{

int gVal;

real hVal;

real fVal;

struct Point coord;

struct Point parentCoord;

byte cost;

};

struct Map

{

byte width;

byte height;

byte *map;

struct Node start;

struct Node goal;

};

struct Path

{

struct Node * path;

int cost;

int expanded;

int length;

};

typedef vector<Node, allocator<Node> > NodeQueue;

typedef list<Node, allocator<Node> > NodeList;

class Heuristic

{

public:

virtual real run(Node s, Node g)=0;

};

class Search

{

public:

virtual Path run(Map m, Heuristic * h, float gv,void (__cdecl *func )(Node ex) )=0;

};

#define ASTAR 0

#define MANHATTAN 0

#define EUCLIDEAN 1

#define MAX 2

#define DTypes

#endif

Listing #4: Euclidean.cpp

#include "Euclidean.hpp"

#include "math.h"

real Euclidean::run(Node s, Node g)

{

return _hypot( s.coord.x-g.coord.x, s.coord.y-g.coord.y );

}

Listing #5: Euclidean.hpp

#include "DTypes.hpp"

class Euclidean:public Heuristic

{

public:

real run(Node s, Node g);

};

Listing #6: Manhattan.cpp

#include "Manhattan.hpp"

real Manhattan::run(Node s, Node g)

{

return abs(s.coord.x-g.coord.x)+abs(s.coord.y-g.coord.y);

}

Listing #7: Manhattan.hpp

#include "DTypes.hpp"

class Manhattan:public Heuristic

{

public:

real run(Node s, Node g);

};

Listing #8: Max.cpp

#include "Max.hpp"

real Max::run(Node s, Node g)

{

return (abs(s.coord.x-g.coord.x)>abs(s.coord.y-g.coord.y))?abs(s.coord.x-g.coord.x):abs(s.coord.y-g.coord.y);

}

Listing #9: Max.hpp

#include "DTypes.hpp"

class Max:public Heuristic

{

public:

real run(Node s, Node g);

};

Listing #10: PathDLL.cpp

#include <stdio.h>

#include <windows.h>

#include <limits>

#include "PathDLL.h"

#include "DTypes.hpp"

#include "Euclidean.hpp"

#include "Max.hpp"

#include "Manhattan.hpp"

#include "AStar.hpp"

BOOL APIENTRY DllMain( HANDLE hModule,

DWORD ul_reason_for_call,

LPVOID lpReserved

)

{

switch (ul_reason_for_call)

{

case DLL_PROCESS_ATTACH:

case DLL_THREAD_ATTACH:

case DLL_THREAD_DETACH:

case DLL_PROCESS_DETACH:

break;

}

return TRUE;

}

extern "C" void PASCAL freeMapMem(Map &m)

{

delete m.map;

}

extern "C" void PASCAL freePathMem(Path &p)

{

delete p.path;

}

extern "C" void PASCAL findPathF(const char* filename, int heuristic, int algorithm, float extraVal, Path &path)

{

Map map;

loadMap(filename, map);

findPathM(map, heuristic, algorithm, extraVal, path);

delete map.map;

}

extern "C" void PASCAL findPathM(Map map, int heuristic, int algorithm, float extraVal, Path &path)

{

findPathMC(map, heuristic, algorithm, extraVal, path, NULL);

}

extern "C" void PASCAL findPathMC(Map map, int heuristic, int algorithm, float extraVal, Path &path, void (__cdecl *func )(Node ex) )

{

extraVal+=numeric_limits<float>::epsilon();

Heuristic *h;

switch(heuristic)

{

case EUCLIDEAN:

h=new Euclidean;

break;

case MAX:

h=new Max;

break;

case MANHATTAN:

h=new Manhattan;

break;

}

Search *s;

switch (algorithm)

{

case ASTAR:

s=new AStar;

break;

}

path=s->run(map, h, extraVal, func);

delete h;

delete s;

}

extern "C" void PASCAL loadMap(const char* filename, Map &map)

{

FILE * fileStream;

fileStream=fopen(filename, "r");

byte *x;

x=new byte;

fread(x,sizeof(byte), 1, fileStream);

map.width=*x;

fread(x,sizeof(byte), 1, fileStream);

map.height=*x;

fread(x,sizeof(byte), 1, fileStream);

map.start.coord.x=*x;

fread(x,sizeof(byte), 1, fileStream);

map.start.coord.y=*x;

fread(x,sizeof(byte), 1, fileStream);

map.goal.coord.x=*x;

fread(x,sizeof(byte), 1, fileStream);

map.goal.coord.y=*x;

map.map=new byte[map.width*map.height];

fread(map.map,sizeof(byte), map.width*map.height, fileStream);

map.goal.cost=map.map[map.goal.coord.x+map.goal.coord.y*map.width];

map.start.cost=map.map[map.start.coord.x+map.start.coord.y*map.width];

_fcloseall();

delete x;

}

Listing #11: PathDLL.h

#include "DTypes.hpp"

extern "C" void PASCAL freeMapMem(Map &m);

extern "C" void PASCAL freePathMem(Path &p);

extern "C" void PASCAL findPathF(const char* filename, int heuristic, int algorithm, float extraVal, Path &path);

extern "C" void PASCAL findPathM(Map map, int heuristic, int algorithm, float extraVal, Path &path);

extern "C" void PASCAL findPathMC(Map map, int heuristic, int algorithm, float extraVal, Path &path, void (__cdecl *func )(Node ex) );

extern "C" void PASCAL loadMap(const char* filename, Map &map);

Listing #12: Batch.cpp

#include <windows.h>

#include <stdio.h>

#include <limits>

#include "PathDLL.h"

void generateOutput(char* filename, char* mapname, bool echo);

int main(int argc, char* argv[])

{

bool echo;

char * filename;

char * mapname;

if (argc<4)

{

filename="out.txt";

mapname="map.bin";

echo=true;

}

else

{

filename=argv[1];

mapname=argv[2];

echo=false;

if (argv[3]!="n\n")

echo=true;

}

generateOutput(filename, mapname, echo);

return 0;

}

void generateOutput(char* filename, char* mapname, bool echo)

{

FILE* fileStream;

fileStream=fopen(filename,"w");

float gv;

int rep;

Map map;

Path path;

loadMap(mapname, map);

if (echo)

printf("%s","Max\n" );

fprintf(fileStream,"%s","Max\n");

//for (gv=0;gv<1+numeric_limits<float>::epsilon();gv+=.02f)

for (rep=0;rep<=100;rep++)

{

gv=(float)rep*.01f;

findPathM(map, MAX, ASTAR, gv, path);

if (echo)

printf("%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

fprintf(fileStream,"%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

freePathMem(path);

}

if (echo)

printf("%s","Euclidean\n" );

fprintf(fileStream,"%s","Euclidean\n");

for (rep=0;rep<=100;rep++)

{

gv=(float)rep*.01f;

findPathM(map, EUCLIDEAN, ASTAR, gv, path);

if (echo)

printf("%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

fprintf(fileStream,"%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

freePathMem(path);

}

if (echo)

printf("%s","Manhattan\n" );

fprintf(fileStream,"%s","Manhattan\n");

for (rep=0;rep<=100;rep++)

{

gv=(float)rep*.01f;

findPathM(map, MANHATTAN, ASTAR, gv, path);

if (echo)

printf("%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

fprintf(fileStream,"%.2f\t%d\t%d\n",gv,path.cost,path.expanded);

freePathMem(path);

}

freeMapMem(map);

}

Listing #13: Batch.cpp

#include <stdio.h>

#include <stdlib.h>

#include <afx.h>

#include "DTypes.hpp"

#include "PathDLL.h"

NodeQueue expanded;

void ex(Node n)

{

expanded.push_back(n);

}

int main(int argc, char* argv[])

{

CString file="";

char* ifilename;

ifilename=argv[1];

char* ofilename;

ofilename=argv[2];

int heuristic=atoi(argv[3]);

int algo=atoi(argv[4]);

float extra=atof(argv[5]);

Path p;

Map m;

loadMap(ifilename, m);

findPathMC(m, heuristic, algo, extra, p, ex);

FILE *stream;

CString temp="";

temp.Format("%d\n",p.length);

file+=temp;

for (int rep=0;rep<p.length;rep++)

{

temp.Format("%d\n%d\n", p.path[rep].coord.x, p.path[rep].coord.y);

file+=temp;

}

temp.Format("%d\n", expanded.size());

file+=temp;

for (int rep2=0;rep2<expanded.size();rep2++)

{

temp.Format("%d\n%d\n", expanded[rep2].coord.x, expanded[rep2].coord.y);

file+=temp;

}

stream=fopen(ofilename, "w");

fprintf(stream, "%s",(const char *)file);

fclose(stream);

freeMapMem(m);

freePathMem(p);

return 0;

}

Figure #14: View.frm

Private Type AM

expanded As Integer

cost As Integer

End Type

Dim colN(0 To 100, 0 To 100) As Long, colX(0 To 100, 0 To 100) As Long, colE(0 To 100, 0 To 100) As Long, dataN(0 To 100) As AM, dataE(0 To 100) As AM, dataX(0 To 100) As AM

Dim cs As Single

Private Sub Clear()

View1.Cls

View2.Cls

View3.Cls

End Sub

Private Sub getFromFile(name As String)

If InStr(name, "_") <> 0 Then

name = Left(name, InStr(name, "_") - 1)

End If

If InStr(name, ".") <> 0 Then

name = Left(name, InStr(name, ".") - 1)

End If

Open name & ".txt" For Input As #1

Input #1, max

Input #1, Min

Input #1, algo

For X = 0 To 100

For Y = 0 To 100

Input #1, colN(X, Y)

Next Y

Next X

Input #1, algo

For X = 0 To 100

For Y = 0 To 100

Input #1, colE(X, Y)

Next Y

Next X

Input #1, algo

For X = 0 To 100

For Y = 0 To 100

Input #1, colX(X, Y)

Next Y

Next X

Close #1

View1.Picture = LoadPicture(name & "_1.bmp")

View2.Picture = LoadPicture(name & "_2.bmp")

View3.Picture = LoadPicture(name & "_3.bmp")

End Sub

Private Sub Command1_Click()

Clear

CommonDialog1.ShowOpen

getFromFile (CommonDialog1.FileName)

End Sub

Private Sub Form_Load()

CommonDialog1.InitDir = "C:\SciProj98-99\Programs\PicsCE"

End Sub

Private Sub View1_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colN(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colN(X, Y) / max))

End Sub

Private Sub View2_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colE(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colE(X, Y) / max))

End Sub

Private Sub View3_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colX(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colX(X, Y) / max))

End Sub

Listing #15: Visualize.frm

Private Type AM

expanded As Integer

cost As Integer

End Type

Dim colN(0 To 100, 0 To 100) As Long, colX(0 To 100, 0 To 100) As Long, colE(0 To 100, 0 To 100) As Long, dataN(0 To 100) As AM, dataE(0 To 100) As AM, dataX(0 To 100) As AM

Dim max As Single

Dim min As Single

Dim cs As Single

Private Sub Clear()

View1.Cls

View2.Cls

View3.Cls

End Sub

Private Sub Draw()

For X = 0 To 100

For Y = 0 To 100

View1.Line (2 * X, 2 * Y)-(2 * X + 2, 2 * Y + 2), QBColor(Int(14 * ((colN(X, Y) - min) / max))), BF

Next Y

Next X

For X = 0 To 100

For Y = 0 To 100

View2.Line (2 * X, 2 * Y)-(2 * X + 2, 2 * Y + 2), QBColor(Int(14 * ((colE(X, Y) - min) / max))), BF

Next Y

Next X

For X = 0 To 100

For Y = 0 To 100

View3.Line (2 * X, 2 * Y)-(2 * X + 2, 2 * Y + 2), QBColor(Int(14 * ((colX(X, Y) - min) / max))), BF

Next Y

Next X

End Sub

Private Sub getFromFile(name As String)

Print "Get: " & name

Open name For Input As #1

Input #1, algo

For X = 0 To 100

Input #1, nu

Input #1, dataX(X).cost

Input #1, dataX(X).expanded

Next X

Input #1, algo

For X = 0 To 100

Input #1, nu

Input #1, dataE(X).cost

Input #1, dataE(X).expanded

Next X

Input #1, algo

For X = 0 To 100

Input #1, nu

Input #1, dataN(X).cost

Input #1, dataN(X).expanded

Next X

Close #1

End Sub

Private Sub saveToFile(name As String)

Print "Save: " & name

SavePicture View1.Image, name & "_1.bmp"

SavePicture View2.Image, name & "_2.bmp"

SavePicture View3.Image, name & "_3.bmp"

Open name & ".txt" For Output As #1

Print #1, max

Print #1, min

Print #1, "Manhattan"

For X = 0 To 100

For Y = 0 To 100

Print #1, colN(X, Y)

Next Y

Next X

Print #1, "Euclidean"

For X = 0 To 100

For Y = 0 To 100

Print #1, colE(X, Y)

Next Y

Next X

Print #1, "Max"

For X = 0 To 100

For Y = 0 To 100

Print #1, colX(X, Y)

Next Y

Next X

Close #1

End Sub

Private Sub generateValues()

max = 0

min = 999999999

For X = 0 To 100

For a = 0 To 100

colN(X, a) = a / 100 * (dataN(X).cost) + (1 - a / 100) * dataN(X).expanded

If colN(X, a) > max Then

max = colN(X, a)

End If

If colN(X, a) < min Then

min = colN(X, a)

End If

Next a

Next X

For X = 0 To 100

For a = 0 To 100

colE(X, a) = a / 100 * (dataE(X).cost) + (1 - a / 100) * dataE(X).expanded

If colE(X, a) > max Then

max = colE(X, a)

End If

If colE(X, a) < min Then

min = colE(X, a)

End If

Next a

Next X

For X = 0 To 100

For a = 0 To 100

colX(X, a) = a / 100 * (dataX(X).cost) + (1 - a / 100) * dataX(X).expanded

If colX(X, a) > max Then

max = colX(X, a)

End If

If colX(X, a) < min Then

min = colX(X, a)

End If

Next a

Next X

If max = 0 Then

max = 1

End If

End Sub

Private Sub Batch_Click()

For X = 1 To 15

getFromFile ("C:\SciProj98-99\Programs\Txt\Out" & X & ".txt")

generateValues

Draw

Print X

saveToFile ("C:\SciProj98-99\Programs\PicsCE\VOut" & X)

Next X

End Sub

Private Sub Command1_Click()

Clear

CommonDialog1.ShowOpen

getFromFile (CommonDialog1.FileName)

generateValues

Draw

End Sub

Private Sub Command2_Click()

If IsNumeric(Text1.Text) Then

Clear

cs = Text1.Text

Draw

End If

End Sub

Private Sub Form_Load()

cs = 1

End Sub

Private Sub save_Click()

CommonDialog2.ShowSave

saveToFile (CommonDialog2.FileName)

End Sub

Private Sub View1_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colN(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colN(X, Y) / max))

End Sub

Private Sub View2_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colE(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colE(X, Y) / max))

End Sub

Private Sub View3_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

X = Int(X / 2)

Y = Int(Y / 2)

C.Caption = colX(X, Y)

Xc.Caption = X

Yc.Caption = Y

Col.Caption = Int(14 * (colX(X, Y) / max))

End Sub

Listings 1-10 comprise the DLL that is used by all the programs; it contains the actual code for the pathfinding algorithms. Listings 11-12 are the source code for what has throughout this report been called the first program. Listing 14 is the second program, although it needs the program that results from Listing 13’s compilation in order to use the DLL that actually runs the algorithms. Listing 15 is the third program, which uses the results of the first program.

Appendix 3- Explanation of Programs

The first program takes a map file as input. It then runs every single algorithm (all 303 of them) on the map. For each of these algorithms, it records (in a file) the cost of the path that the algorithm produced and the number of node expansions that occurred. This resulting file is later used by program three. This program runs from the command line without human interaction.

The second program has a GUI and required user interaction. In this program the user has to load a map. The map is then drawn. The user can also choose an algorithm, and have the path it produces and/or the nodes it expands drawn. That is how the pictures in Appendix 4 were produced. The user can then save the resulting picture.

The third program takes the file resulting from the first program as input. It then parses through this file and puts the cost and number of node expansions into an array. After that it uses the formula and the data it read in from the file to produce the charts that can be seen in the data section. This program uses three 101 by 101 arrays to have the values 0 to 1 (step .01) for both the value of a and x for all three heuristics, inputted into the equation above and it then stores the values of C for the given point. The program then draws the contents of the three arrays. The user can then save these three images, or investigate them by clicking on them. If a user clicks on an image they are given the coordinates of that point and the value in the appropriate array at that point.

Appendix 4- Maps

Figure 9: Map 1

Figure 10: Map 2

Figure 1: Map 3

Figure 12 Map 4

Figure 13: Map 5

Figure 14: Map 6

Figure 15: Map 7

Figure 16: Map 8

Figure 17: Map 9

Figure 18: Map 10

Figure 19: Map 11

Figure 20: Map 12

Figure 21: Map 13

Figure 22: Map 14

Figure 23: Map 15

In all of these maps, the start node is colored green and the goal node is colored red. The shortest path between those two nodes (or one of the shortest paths) is represented by the brown colored line segments. The blue grid shows the division between the nodes. Very light gray nodes represent nodes with a cost of 1; darker shades of gray represent costs 2 to 9. Nodes colored black are nodes that are totally inaccessible.