Create the Project
Extract the project folders and files from the archive Pathfinder.zip into your project directory. You should be able to open the solution file (.sln) to start VisualStudio.
Run the program and examine the output. it should show one red near the top of the screen and one green at one near the bottom
Modify the Application
There are several changes that need to be made, including writing event handling code for the new menu items, creating new heuristic functionality, keeping track of and displaying) the number of nodes visited during an AStar search, and modifying the window size to accomodate the new output.
Create New Heuristic Functionality
In the AStartHeuristicPolicies.h file,
add an enumerated type for the new heuristic types just below the last #include statement:
enum HeuristicType {Euclid, DistanceSquared, Manhattan};
add an external declaration for a new global variable to store the current heuristic type:
extern HeuristicType g_heuristicType;
modify the method Heuristic_Euclid::Calculate() so that it will caclulate either a Euclidean distance, a distance squared or a Manhattan distance based on the value of the global variable g_heuristicType
you may also want to change the name of the Heuristic_Euclid class to just Heuristic since it may calculate other non-Euclidean distances
New Menu Item Event Handling Code
In the maincpp file,
add a declaration for a new global variable to store the current heuristic type:
HeuristicType g_heuristicType = Euclid;
in the WindowProc function in the code for the WM_CREATE message, add a statement to initialize the Euclidean Distance menu item to checked:
ChangeMenuState(hwnd, ID_HEURISTIC_EUCLIDEANDISTANCE, MFS_CHECKED);
in the WindowProc function after the code for IDM_VIEW_TILES, add a new case with event handling code for the Euclidean Distance menu item:
case ID_HEURISTIC_EUCLIDEANDISTANCE:
// update the menu by checking this option and unchecking the others
ChangeMenuState(hwnd, ID_HEURISTIC_EUCLIDEANDISTANCE, MFS_CHECKED);
ChangeMenuState(hwnd, ID_HEURISTIC_DISTANCESQUARED, MFS_UNCHECKED);
ChangeMenuState(hwnd, ID_HEURISTIC_MANHATTAN, MFS_UNCHECKED);
g_heuristicType = Euclid;
g_Pathfinder->CreatePathAStar();
CurrentSearchButton = ID_BUTTON_ASTAR;
break;
add two more case statements similar to the previous one for the DistanceSquared and Manhattan Distance menu items (the exact naming for the resource identifiers ID_… for these can be found in the resource.h file)
Keep Track of Number of Nodes Visited
in the file GraphAlgorithms.h, in the Graph_SearchAStar class add a data member to keep count of the number of nodes visited:
int m_NumNodesVisited;
in the method Graph_SearchAStar::Search(), initialize the m_NumNodesVisited to zero and increment this variable everytime the PriorityQueue’s insert method is called
in the PathFinder class add a data member to keep count of the number of nodes visited:
int m_NumNodesVisited;
in the PathFinder::CreatePathAStar method, store the number of nodes visited from the Graph_SearchAStar class after it has be constructed
m_NumNodesVisited = AStar.m_NumNodesVisited;
in the PathFinder::Render method, change the code that displays the search time to add code that will also output the number of nodes visited:
if (m_dTimeTaken)
{
//draw time taken to complete algorithm
string time = ttos(m_dTimeTaken, 8);
string s = “Time Elapsed for ” + GetNameOfCurrentSearchAlgorithm() + ” is ” + time;
// add the visited node count to the output – ceh
s += ” nodes searched = ” + ttos(m_NumNodesVisited) + ” “;
gdi->TextAtPos(1,m_icyClient + 3,s);
}
Modify the Window Size
In the file Constants.h, you can modify the width and height of the client window to accomodate the additional output.
Run the Application
Rebuild and Run the modified application.
Create a Spreadsheet for the Results
Run the program. Record the AStar results for each heuristic in an Excel table like this:
Heuristic Cost Elapsed Time Number of Nodes Visited
Euclidean Distance
Distance Squared
Manhattan Distance
Create a bar chart of the results in Excel.
Add a comment to the cell with the lowest time, briefly explaining why that heuristic is quicker than the others.
Include this chart in the archive you submit.
