Billy Brandstetter

CS 476 

 

 

 

Technical Objectives:  To graphically illustrate the shortest path between two points using an A* algorithm.  The algorithm will create a path and consider obstacles with different levels of movement cost. The program will allow users to pick any grid size they desire, and draw different levels of terrain cost on the grid. After picking a start and destination location, a path will be created using the A* algorithm.

 

 

Plan of Action:  This is a list of what I will need to accomplish in order to complete this project.

 

  1. Load a window that will be drawn on, and to handle user input using GLUT.
  2. Allow the user to choose a grid size, and draw that grid to the screen using OpenGL.
  3. Create a menu to allow the user to select different options.  Here are a few.
    1. -Select starting point
    2. -Select destination point
    3. -Draw obstacles
    4. -Create path
  4. Handle mouse input to allow user to select a starting point, destination point, and draw obstacles on the grid. 
  5. Handle mouse input even when the window is resized and the pixel values are changed.
  6. Allow user to create shapes (square, circle, maybe ellipse) on the grid, rather than just drawing single points.
  7. Allow user to select a cost level for each obstacle drawn (most likely levels 1-10, maybe more) and put this in the menu.
  8. Create a linked list class to handle the open and closed list of the A* algorithm.
  9. Create an A* algorithm using the data that the user created on the current grid.
  10. Create the presentation for the project.

 

 

 

These are some screenshots of the project so far!

In this screen shot, the path decided to go around the high cost terrain (bright green), yet decided to go right through the lower cost terrain (dark green). The brighter the green, the slower it is to move across.

 

 

NEW! 4/25/03

The application will now show the areas where the A* algorithm examined. As you can see the path around the high cost terrain was evaluated, but it was still cheaper to travel through it.

5/10/03 UPDATE

Some new features have been added to the application.

1. First, the user is now able to choose between two different heuristics when finding the path. The two choices are the Manhattan heuristic and the Diagonal Heuristic.

notes: After implementing both of them, you can definitely see that the Diagonal heuristic does a better job with accuracy, but ends up evaluating between 2-3 times more squares than the Manhattan heuristic. The reason I allow the user to choose is because A* is really application specific. If you using this for a game, I would recommend using the Manhattan Heuristic because a few more steps taken in the path probably wont be recognized by the player. Most gamers would rather see speed over accuracy. The Manhattan heuristic is definitely faster than the Diagonal heuristic. On the other hand, if this were a military or NASA project using some robot on Mars, I would suggest using a heuristic like the Diagonal heuristic where every bit of accuracy counts.

Here are some screen shots showing the difference in heuristics:

 

Looking back on these two screen shots, you can see that when using the Manhattan heuristic the path took 34 steps with a total movement cost of 694 and it evaluated 8,479 squares until the path was found.

The Diagonal heuristic, on the other hand, found a path that took 58 steps, but more importantly only a total movement cost of 684 which is faster than what the Manhattan found. It did, however, have to evaluate 11,780 squares to find this path.

So the choice is yours in whether 10 less movement costs with the Diagonal heuristic is worth the extra 3,301 squares to be evaulated. Like I saide A* is very application specific which makes it so cool. The Manhattan and Diagonal heuristics are probably the most popular (especially on a square grid), but I may add some others and experiement even more.

2. Next, a turning penalty cost was implemented to give a more desirable and smoother path. The user now has the option to set a turning penalty (which adds an extra cost to their G-value if the direction is changed) to smooth out the path. This sometimes won't be the shortest path, but in some cases (like games) a better looking path is better than the shortest one, especially when the difference in path sizes are very small.

notes: Above, I mentioned there are now two heuristics to choose from. The Diagonal heuristic is much better when dealing with other modifiers such as terrain movement cost, and turning penalties. So when setting the turning cost higher than zero, the Diagonal heuristic does a much better job than the Manhattan heuristic.

Here are some screen shots showing an original path and then the smoother path using a turning cost modifier:

This path above uses the Diagonal heuristic with no turning penalty. Notice how the path follows the edge of the wall and zig-zags with it.

 

This path uses the Diagonal heuristic but with a turning penatly of 5. This path is much smoother and used the same amount of steps to get to the goal. This path's total movement cost is 20 more than the other. That's because four turns were made at a cost of 5 each. So essentially, this path takes the same amount of steps and looks better. However, it did evaluate 1,033 more squares.

 

 

Download: Source Code and Executable (WinZip) here.

Source Code and Executable also available here.

View Powerpoint Presentation here.

Project Report available here.

This program and all source code is protected under the GNU General Public License.

 

Alternate Projects:

Pong

Paint

Air Hockey

Tanks