Please use your reply to this blog post to detail the following:
- Please give a full description of the nature of your A* project. How did you implement the assignment? Did you use Pygame or some other UI environment? Why did you choose the environment you selected?
- What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
- What was the best online tutorial you found to help you understand and implement the A* algorithm? If you used more than one resource, list all the URLs.
- How could this assignment be improved for future AdvCS classes?
- Include your Github repo URL so your classmates can look at your code.
Take the time to look through the project posts of your classmates. If you saw any project or project descriptions that pique your interest, please reply or respond to their post with feedback. Constructive criticism is allowed, but please keep your comments civil.
1) To begin our A* project, we followed an online tutorial to build a basic understanding of how the algorithm worked. Moreover, we started by initializing our start and end values to zero so that we could ignore any children values that returned to the starting position (due to first checking if g and h were equal to zero). After this, we started an infinite loop that would run until we found our end position. Then, after enumerating our current square, we added the current node to the closed list from the open list if its f value was smaller than our past node’s. Next, we checked to see if we had found our goal (endpoint) and if we did, we referenced the parent node of the final node and then each parent node of that node until we reached the starting position. After checking if we had found our end goal, and if we hadn’t yet, we created 8 nodes from the current node known as the children nodes which represented each possible move from that point. Using these children nodes, we then created their h, g, and f values (h being the length to the end goal, g being the number of steps to get to the node, and f being the sum of these two values). Finally, we added the children to the closed list and started the loop over again. On a related note, we did use a UI environment of sorts, however, it was not from Pygame and instead was created by Hutch late last Wednesday night with a little online/AI help. This UI environment proved to be very useful when attempting to determine what values were being added to the closed and open lists and when, as it displayed nodes added to different lists with different colors.
2) As I mentioned before, we were having a bit of trouble identifying what values were being added to the open and closed lists. However, after using the UI environment Hutch developed, we were able to see that our confusion was mainly stemming from the fact that the code from the tutorial was not working correctly. Moreover, one of our continue statements resulted in our code inaccurately adding values to the open and closed lists even if they were already in said lists, which explains why we were so confused as to why it was getting stuck in corners every now and again.
3) https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2
4) I think it may have been beneficial to spend more time focusing on how exactly this could be implemented into real-world applications. Moreover, while I understand that it can and is used for navigation (such as Google Maps does) I feel that there are a lot more use-case scenarios that I simply still do not understand.
5) https://github.com/GMebane525/AStar.git
1) Our project was a basic A star pathfinding algorithm which attempted to find the best path in a maze based on f, g, and h values. The g value is the distance a given point is away from the start value, and the h value is a heuristic—the estimated distance from a point to the endpoint calculated using the pythagorean theorem. The f value was equal to the sum of these two values. From each node that we were at, we would create 8 “children” nodes that represented the 8 possible moves from our current position. The f value was then calculated for each of these children nodes and added to the closed list. We would move to the node with the smallest f value in the closed list, and keep repeating this until we eventually got to our endpoint. We did implement a UI through matplotlib. This was done by Hutch with the help of ChatGPT, and this created our maze in 2d and showed the path our algorithm took from the start point to the endpoint, along with every value that it added to the closed list.
2) Our code was having trouble because our original algorithm from the tutorial seemed to get stuck moving between 2 positions back and forth repeatedly. We figured out that this was due to us repeatedly adding values to the open and closed lists even though they were already there, which was causing the issue.
3) https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2
4) I think that one way that this could be improved for the future would be with, as Gil already commented, more of an emphasis on real-world implications with A star pathfinding. For example, I feel like I really learned in-depth with the Iris-Setosa project and our creative project in that unit (NBA draft statline predictor) all the different ways Machine Learning could be harnessed. I don’t really feel like I have a great grasp on how A star can be used.
5) https://github.com/anandjss/Astar