Background Information
In the previous project, best first search was used to find the shortest route between two cities of Romania. The same search algorithms will be applied to a grid in this project.
Task to Complete
Develop a program to find the shortest path between any two blocks on a grid (square or hexagonal). This program must:
- be able to store a graph of nodes, and each node can have any number of adjacencies
- be able to find the shortest path between two cities using best first search (A* search, uniform cost search, and greedy search)
- display the result using graphics and be interactive with the user
November 13th, 2016
- copied and pasted search algorithms from Romania pathfinding project
- made tweaks to the code so that instead of working from a preset graph, each node creates the nodes around it as it is expanded
- changed the node data system to a axial coordinate system (for hexagonal grids)
- changed the heuristic so it represents the fastest route between two blocks with no obstacles in between
- added a system of recording the blocks that are walls within GraphSearcher (which stores a list of size-two arrays)
- prevents creating nodes that are at these locations
- tested the search algorithms via text input – it works!
November 15th, 2016
- today is actual an “extension day” to work on my project – I was absent for the previous classes; therefore, I will have to finish the project ASAP and I won’t be able to focus on too many details
- created a new display class with a paint method
- created an algorithm to map the coordinates of the mouse on the screen to hexagonal coordinates and vice versa
- using this algorithm, creating a way to display a background grid on the screen (using a nested for loop)
- also using this algorithm, creating a way to know which hexagon the mouse is hovering over
- in paint, drawing the background, highlighting the hexagon the mouse is hovering over, drawing the walls, drawing the start/end, drawing the path, drawing the fringe, and drawing the visited
- note: in the above, if the item to be drawn doesn’t exist (i.e. a search hasn’t been conducted yet), it is skipped
- calling paint each time the mouse is moved or pressed, a key is types, and every set number of iterations of the search algorithm (this number can be controlled to increase/decrease the speed of the search)
- adding a function to control which search to carry out with the 1, 2, and 3 keys
- adding a function to display/hide the grid background with the b key
- adding a function to clear the walls with the c key
- at this point, the program is pretty much complete.
Advertisements