A* Search Algorithm: Snowman Pathfinding

As a follow-up to my minesweeper game, I wanted to develop a pathfinding algorithm on a similar platform.  At the same time, I had modeled a snowman, so I decided to use it to collaborate my modeling skills with my programming skills.

This project uses the A* (A-star) Search Algorithm to generate a path from one point to another on a grid system, finding the shortest way to the destination grid without running through walls.  The grid settings are fully customizable in that you can get the maximum row and column as well as the number of walls present in the grid system.

I have to say that this project is very relevant to my field of study because pathfinding algorithms such as this relate to my interests in game development and artificial intelligence.

So how does it work?  When the user clicks on a point on the grid, the program will convert the clicked position to the corresponding grid object.  This grid object is then set as the destination.  The grid object that the snowman is currently on will be set as the start position.  Then, in an iterative loop, the program will find the grid objects adjacent to the current grid (which will be the starting grid object to begin with).  We will calculate the F cost of each grid object.  The F cost is the sum of the G cost and H cost.  G cost, as represented by my program, is the distance from the current grid object to the adjacent grid object.  H cost is the distance from this adjacent grid object to the destination grid object.  The adjacent grid object that has the lowest F cost will then be new current grid.  This process will repeat until either the destination grid object becomes the current grid or the entire grid system has been essentially exhausted in search.

Here are some screenshots of the program at work:

We click on the point opposite of the snowman in relation to the two walls.

The snowman calculates the shortest path to the destination and begins moving.

Seen in a different angle, we see that the snowman has made it to the destination.


That's it for now.  Thanks for reading!

SCJAS Research Award - First Place in Oral Presentation

This past Saturday, I went to University of South Carolina Aiken to present my research at the statewide annual South Carolina Junior Academy of Sciences.  There were over 300 other student presenters.  The event took the whole day.  I attended many of the presentations and many of them were excellent.

The awards ceremony took place late in the afternoon, and to my pleasant surprise, my research presentation took first place in the Math / Computer Science Mentored Research branch.  I was honored to receive the award.  It was something I couldn't have done without the help of my research advisor, Mrs. Bunn, who has listened and advised me during hours of my practice presentations.  So, thank you!