Creating a search graph to represent the TileMap, which in turn represents the terrain. 2) Writing of a declaration for the PathSearch class and initial (likely empty) methods for compilation.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Structure
The project should be broken into several smaller steps:

1) Creating a search graph to represent the TileMap, which in turn represents the terrain.
2) Writing of a declaration for the PathSearch class and initial (likely empty) methods for compilation.
3) Development of a visual debugging strategy using the drawing functions of the TileMap.
4) Implementation of a Breadth-First Search, then modifying it into a Greedy Best-First Search.
5) Modification of the Greedy Best-First Search into a Uniform-Cost Search, and then into an A* Search.
6) Optimization of the A* algorithm to meet speed / benchmark requirements.

User Interface (UI)
The UI for the path planner is provided for students so that they may focus on implementing the search algorithm itself within the existing code base (as is common in the game and other industry sectors). Upon launch, the planner will load the default map and run the search algorithm’s initialization routine. For example, the search implementation might build and display a search graph upon initialization (Figure 1).

Figure 1. Path planner application upon initial load, displaying a search graph built by the search algorithm.

Time Map Display
The tiles that represent the terrain are displayed, along with any drawing engaged by the search algorithm, in the Tile Map Display (bottom-left). Heavier terrain weights are represented by darker tiles, while black tiles represent untraversable terrain. The red flag represents the starting point and the green flag the goal location. Button Controls
The Button Controls across (top) the user to control the search as identified (Table 1).
 
Icon Name Shortcut Description    

 

Open Tile Map 

Ctrl+O Brings up a file dialog. Once you select a file, all memory allocated to the old tile map is freed, a new tile map is loaded from that file, all search algorithms are reset, and all node counters are zeroed out.    

Reset All 
Delete Resets all search algorithms and zeroes all node counters.    

 

 

Reset Search 

Backspace Resets the current search algorithm and updates the node counters. If all search algorithms have been reset this way, then each pair of constructed/destructed counts should match.    

Run / Pause 

Spacebar When enabled and currently paused, runs the search algorithm until it reaches the goal tile, animating its progress in the meantime. If pressed while the search algorithm is still running, it becomes paused. As soon as the search algorithm reaches the goal tile or can make no further progress, this button will be disabled.    

Step 

+ When enabled, runs the search algorithm for exactly one iteration and then pauses it. As soon as the search algorithm reaches the goal tile or can make no further progress, this button will be disabled.    

 

 

 

Time Run 

Tab Resets the search algorithm, then runs the search algorithm until it reaches the goal tile, but does not animate its progress. The number of iterations shown is replaced by the elapsed time from initialization to finish.  
Table 1. Search Application Controls

Settings Pane
There are also a several that can be changed in the Settings pane (upper-right). These include the starting and goal locations, as well as the time limit for a single step or full algorithm run. Finally, for full algorithm runs, the number of times to run the search can be adjusted up from one to determine timing performance. Note that the minimum tile radius is for display only and cannot be changed.

State Space
Some game engines – including the planner in this project – use hexagonal tiles, as they are equidistant from their neighbors (unlike square tiles, which have a different distance to neighbors in cardinal directions compared to diagonal neighbors). This simplifies and speeds up path calculations. However, this makes storing and retrieving tiles in a typical 2D array less straightforward. An example is outlined below (Figure 2). Each tile also holds a terrain weight which identifies the cost of trafersing through a tile.
 
 
Array Column    
Row 0 1 2 3    
0 X ✔ ✔ -    
1 ✔  ✔ -    
2 X ✔ ✔ -    
3 - ✔ ✔ X    
4 - ✔  ✔    
5 - ✔ ✔ X  

Figure 2. Layout of hexagonal grids (rows and columns). Figure 3. How tile information is stored in an array.

In this diagram, the dashed yellow lines separate the tiles into logical columns. The offset from the current tile (0, 0) to its neighbors is marked; odd rows have offsets as outlined MAGENTA and even rows have offsets as outlined in CYAN. BLACK tiles indicate offsets that are invalid depending on the odd or even row location of (0,0). Note that these are not the same as the obstacle tiles in the tile map. We can see how these data would be stored in a 2D array (Figure 3). For any tile whose row coordinate has an odd value, the tiles that are adjacent to it follow the pattern of the magenta tiles. For any tile whose row coordinate has an even value, the tiles that are adjacent to it follow the pattern of the cyan tiles.

It is recommended that students build a private helper method in their search class to determine the adjacency of Tile objects to simplify identification of neighboring locations, e.g.:

private bool areAdjacent(const Tile *lhs, const Tile *rhs)

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of