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)
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
