Dylan Hanson

• Allow user manipulation of blank 100x100 grid through coordinate entry
  • Enter origin coordinates
  • Enter destination coordinates
  • Enter coordinates of obstacles along path
    • OR: Obstacles randomly generated by computer
• Determine shortest coordinate path from origin to destination using Dijkstra's algorithm
• Visualize path using inline console text

The user interface is entirely console based. It is structured hierarchically as a series of titled, nested menus. At each menu, the user is given a list of options, each identified by a letter, as well as a brief description of the menu/action to be opened/performed upon selection.

***************************************
MENU TITLE
A > Sub-menu 1
B > Sub-menu 2
C > Action 1

A, B, and C are all options. By typing A into the command line, Menu 1 will be entered.

Note: Option recognition is case insensitive and error-proof

There are many situations throughout the program in which the user will need to input coordinates. These can be entered in two ways:

1. X,Y, with one coordinate pair on each line
2. X1,Y1 X2,Y2 X3,Y3 X4,Y4 X5,Y5 with multiple coordinates on each line, separated by spaces

Note: When prompted for one coordinate, even if the user enters multiple, the first one inputted will be used

It is key that the user be able to input their own obstacles. Obstacles can be added to the graph in two ways:

1. User input
   • User enters either a single coordinate for one obstacle, or two coordinates to define obstacle edges. When defining obstacles, you may not enter multiple coordinates on one line unless you are defining corners.
2. Random generation

Obstacles are randomly computer-generated by selecting a random point on the graph, then selecting a diameter from 1 to 6. A block of that size is then placed at the coordinates.

An iterative algorithm that finds the most direct path from the origin node to the destination node. It does this by assuming that the first path to reach the ending node is also the fastest (i.e. shortest) path.

1. All nodes have an intitial distance of infinity, except starting node, which has a distance of zero
2. Begin with current node. This will be starting node for first iteration
3. Find all edges connected to current node and save the length of each edge
4. For each edge:

5.  if (current_node.distance + edge.length < connected_node.distance) then (connected_node.distance = current_node.distance + edge.length)
   

( Essentially, this gives each node a tangible, shortest possible distance from the starting point ) 5. Find the node with the least distance in the ENTIRE GRAPH. This is now current node 6. If ending node has been visited, the shortest path has been found 6. Repeat steps 2 through 6 until ending node has been visited

None currently known