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