Devam Ediyor

505826 Astar Pathfinding with Alternate Heuristics

Create the Project

Extract the project folders and files from the archive [url removed, login to view] 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:


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:


// update the menu by checking this option and unchecking the others




g_heuristicType = Euclid;


CurrentSearchButton = ID_BUTTON_ASTAR;


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.

Beceriler: Her şey Kabul, Makale Yeniden Yazım, Excel, Web Sitesi Yönetimi

Daha fazlasını görün: pathfinding alternate heuristics, writing statements excel, writing height, writing folders, writing algorithm program, types algorithm, string search algorithm, string algorithm, solution algorithm, node excel, method writing article, manhattan method, manhattan distances, manhattan distance algorithm, manhattan algorithm, int size, extract number string, creating algorithm, create table chart, create bar chart, archive top, algorithm string, astar alternate heuristics, pathfinder, name naming

İşveren Hakkında:
( 3 değerlendirme )

Proje NO: #2251751