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.
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?
My A* project was a pathfinder for FRC games. I used A* on an 11×11 inch grid that I made over the FRC field. I used Pygame as it was a library that I was most familiar with in adding images and setting up a grid system.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
Initially, I used a 1×1 inch grid but that was far too slow. In using an 11×11 inch grid, I was able to discover some things about path smoothing and high level A* pathfinding, or hierarchical pathfinding. This allowed me to use a larger grid for fast pathfinding with a smoother path that was more realistic. It was difficult to find resources on these concepts, however, old literature was available.
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.
https://web.archive.org/web/20171022224528/http://www.policyalmanac.org:80/games/aStarTutorial.htm
https://web.archive.org/web/20170518005643/http://www.gamasutra.com/view/feature/131505/toward_more_realistic_pathfinding.php?page=2
How could this assignment be improved for future AdvCS classes?
I think that it is a good algorithm to learn about, however, using a real world implementation was the best part in my opinion. Requiring a real life implementation would make this project a lot more interesting.
Include your Github repo URL so your classmates can look at your code.
https://github.com/A0Prakash/Project03_A-.git
(1) My A* project uses Pygame to display both Euclidean and Manhattan heuristic algorithms in a grid space with drawable obstacles and changeable start and end locations. I chose Pygame because it is the UI library I am most familiar with and it allowed me to do what I wanted to with the project.
(2) The steepest part of the learning curve for this project was understanding exactly how the A* algorithm worked. At a base level, it made intuitive sense; however, there were some small bugs in my code that I only found after doing more research into details of the algorithm. For example, deciding when to use a Manhattan or Euclidean algorithm to make the route most efficient.
(3) The best resource I found was Sebastian Lague: https://www.youtube.com/watch?v=-L-WgKMFuhE&t=2s
(4) Honestly, I would assign this project as something you turn in and grade. I think the presentation was often repeating a lot of the same information and felt redundant.
(5) https://github.com/Ryan-Bauroth/A_Star_Pathfinding
1.
My A* project implements A* pathfinding on a square graph that connects a start and an end square that must navigate through obstacles. I used Pygame because I went off of a tutorial I found on YouTube. I used that environment not only because of the YouTube tutorial but also because of the Stanford Theory blog that visualizes A* on a similar interface, which uses a graph with squares rather than nodes. It also has the same open and closed node visualization.
2.
The steepest part of the learning curve was understanding the heuristics, as it was a little confusing. This was not too hard to understand, however, and the project in general was easier than the past two. The hard part about heuristics was just understanding the functions and how changing them affects the algorithm, and then other random things you can add to them like the tie-break factor I implemented.
3.
I used a Youtube video for the UI and class structure for the nodes:
https://www.youtube.com/watch?v=JtiK0DOeI4A
I used this theory blog for understanding A*: https://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
4.
I don’t really want to create more work for future AdvCS students, but I think making creativity a part of the rubric will incentivize more students to explore unique ways of implementation. I was not creative with mine.
5.
https://github.com/AndrewLim0314/Project03_Pathfinding
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?
I basically created a A* pathfinding visualizer on a grid. I was able to generate obstacles and was able to pathfind from a start to end point around the obstacles. I had different heuristics depending on if the user allowed diagonal movement or not. I chose to do a website (typescript + react) as my UI environment because of the fact that I am familiar with it and I like using it.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
The steepest part of the learning curve for this project is understanding what the algorithm actually does (which actually isn’t that hard). The YouTube video I watched explained the algorithm pretty well and even wrote sudo code for me to learn on and interpret into working code. I think also learning about the different types of heuristics you can use is also good.
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.
https://www.youtube.com/watch?v=-L-WgKMFuhE&t=470s&ab_channel=SebastianLague
https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#:~:text=Diagonal%20distance%23,the%20cost%20of%20moving%20diagonally.
How could this assignment be improved for future AdvCS classes?
Different types of obstacle suggestions for pathfinding around to the selected objective (depending on type of environment that is being pathfound)
Include your Github repo URL so your classmates can look at your code.
https://github.com/tslom/Project03_Pathfinding
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?
My A* project was a campus pathfinder that took in an encoded school map and produced an interactive PyGame interface that allowed a user to find directions from one door to another, customizing the type of route they wanted to use. Users could have options for accessible routes, normal routes, trailblazing routes, and rain-covered routes. I chose to use PyGame because I thought it would be the easiest way for users to interact with my A* algorithm.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
I had a hard time understanding exactly how to make my A* work on the project I had envisioned. I made a grid, which I ended up sort of stuck with, but looking back, I wish I had designed it more in terms of locations of points and the paths that connected them, which would have created a better representation of real-life campuses that was more intuitive to design and use.
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.
I spent a lot of time with both Wikipedia and ChatGPT trying to understand how A* works. I thought Wikipedia gave a great starting place to understand the goals of the A* algorithm and ChatGPT helped answer my questions and formulate options for implementations in my specific project.
How could this assignment be improved for future AdvCS classes?
I really appreciated the online resources to explore A*. I do think it would be nice to have more real-world implementations. I really enjoyed getting to work with campus maps, and I think future students would also enjoy making real-world projects.
Include your Github repo URL so your classmates can look at your code.
https://github.com/ori-moore/Project03_Pathfinding.git
My project is an AI that can allow the user to create topological graphs and run the A* pathfinding algorithm on them. I wanted to do something math-related, so I decided to take a topological approach with nodes, connections, and weights. I used the networkx library to visualize by graphs. I chose this environment because it matched what I wanted to do, and the documentation was clean.
The steepest part of the learning curve was probably implementing the A* pathfinding algorithm into my environment and optimizing it. It took some time to actually understand the algorithm, and then it took some time to apply it into my environment. I also wanted to optimize my heuristics, and it took some time to understand and evaluate them.
The best tutorial was probably this youtube video: https://www.youtube.com/watch?v=i0x5fj4PqP4&ab_channel=Tarodev. I find these kind of videos more effective than reading wikipedia pages.
I think this assignment could be improved if everyone did not have to present. It doesn’t take a lot of time for everyone to present, but I feel like presenting mostly the same thing gets a bit repetitive. This project was significantly easier than the other projects for me, so maybe this project could be the first project.
https://github.com/alexru26/Project03_ML.git
1) 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?
This project implements A* pathfinding algorithm using Chebyshev Distance. It allows users to interactively place start and end nodes for up to six colors on a grid and visualizes the shortest paths computed by the algorithm using previously drawn paths as barriers. Chebyshev Distance enables diagonal movement with the same cost as horizontal and vertical movement. The project was implemented using Python and Pygame, which was chosen for its ability to create interactive 2D grid environments and support real-time visualization of the algorithm.
2) What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
The most difficult part of the project was ensuring the program correctly handled user input for multiple colors while maintaining consistent behavior. Managing dynamic pathfinding and treating previously drawn paths as barriers required adjustments to the algorithm’s logic. Structuring the grid data for updates during the visualization process also presented challenges in integrating user interaction with the algorithm.
3) 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.
Amit’s A* pages for theoretical understanding (https://theory.stanford.edu/~amitp/GameProgramming/) Tech with Tim’s YouTube tutorial on implementing pathfinding visualizers in Pygame (https://www.youtube.com/watch?v=JtiK0DOeI4A)
4) How could this assignment be improved for future AdvCS classes?
The assignment could be improved by incorporating real-life applications of the A* algorithm. For example, we could simulate a delivery robot navigating through a warehouse or a game character finding a route in a dynamic environment to gain practical experience.
5) Include your Github repo URL so your classmates can look at your code.
https://github.com/Srao2020/Astar_ColorConnect.git
1. I used a Manhattan distance heuristic function within my A* finding algorithm between two nodes for a 50×50 grid. It optimizes the total “edge” cost of horizontal and vertical steps required to move from one point to another (up, down, left, right). I used Pygame as my UI environment because it was user friendly and easy to alternate. The Youtube tutorial I used also used this environment.
2. The steepest part was learning how heuristic functions worked and the differences between them. I didn’t have previous background knowledge and I originally wanted to use a different function to see if the heuristic function could be optimized from the tutorial I watched. I also switched it to a grid in order to make my program run faster.
3. https://www.youtube.com/watch?v=JtiK0DOeI4A&t=3846s
4. I think we should just turn the project in because the presentations overlap one another a lot of the time, which makes explaining it like the previous projects repetitive.
5. https://github.com/dani0621/Project03_Pathfinding.git
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?
I used pygame to create a visualizer to show my A* algorithm. I used it as the tutorial I used explained how to do it. I implemented it using manhattan distance, which did not allow for diagonal movement. My grid size was about 20×20, which can be easily changed I just preferred a smaller grid.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
For me it was understanding the concepts of the algorithms, and just figuring out how the different sets worked and why it did what it did. The visualizer would have been difficult for me if it wasn’t for the tutorial. It was also hard to find a good explanation for how it worked, as my youtube tutorial was great but I found it after a lot of resources that didn’t work quite as well.
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.
https://www.youtube.com/watch?v=JtiK0DOeI4A
How could this assignment be improved for future AdvCS classes?
The presentations don’t seem very helpful unless someone does something very different. Since everyone had the same algorithm, it made many of them very repetitive. I do like this project though, so it should be kept similar for future years.
Include your Github repo URL so your classmates can look at your code.
https://github.com/PrestonSwigart/Project03_AStarPathfinding
(1) I used Pygame and Snake to have the snake find the quickest way to the fruit. I chose this because it was a unique way to use A* which was not just a grid and also looked cooler. But there was nothing in addition to A* that helped the snake move which is why the snake would die upon not being able to find a path, because it would not change direction.
(2) Probably just learning about the different open and closed lists because they did not make as much sense intuitively because they seemed to be confusing based on the f score which was only lightly defined, but upon a little bit closer inspection they started to make sense.
(3) I generally used the links that you provided to us, with on the PDF, but I found https://www.redblobgames.com/pathfinding/a-star/implementation.html to be the most helpful because it showed an actual usage of A* that allowed the user to alter it easily while keeping some of the components they liked and still learning the general structure of A* and how it works.
(4) Maybe have them try to find a more creative way to show A* rather than just having every person do the same grid that just shows A* working, but rather a cool way to use it like Ori did with mapping the Upper School campus for the point of accessibility.
(5) https://github.com/CameronJMorris/Project03_Pathfinding.git
1. I implemented my A star algorithm using Pyvis visual library. Instead of a grid, I wanted to integrate the algorithm in a more practical sense, so I chose Pyvis where I could make a system/graph of node vertices and edges. For my visualization, I implemented a streamlit simulation which allowed the user to choose beginning and end vertices and the streamlit would display the graph with a green path. It fails very very rarely, and I couldn’t figure out why. If that happens, just restart the code and the simulation functions normally again.
2. For this project, I had the hardest time coding the actual A star algorithm and transferring the pseudocode concepts into actual code. For the algorithm to prioritize the nodes with the lowest f_score I implemented a heap but in order to get to the point I faced a lot of confusion in how to correctly differentiate visited nodes and not visited nodes and comparing how newly visited nodes were better than the path taken previously. I approached these problems through object-oriented design, where I predetermined the f, g, and h scores through equations of euclidean distance and built in coordinates instead of determining them as the pathfinding algorithm went.
3. Some of online resources I used were https://medium.com/@nicholas.w.swift/easy-a-star-pathfinding-7e6689c7f7b2, https://www.geeksforgeeks.org/a-search-algorithm/ for basic theory and pseudocode, https://www.youtube.com/watch?v=-L-WgKMFuhE&t=217s&pp=ygUQYSBzdGFyIGFsZ29yaXRobQ%3D%3D, https://www.youtube.com/watch?v=ySN5Wnu88nE&t=100s&pp=ygUQYSBzdGFyIGFsZ29yaXRobQ%3D%3D, https://www.lancaster.ac.uk/stor-i-student-sites/matthew-randall/2020/04/01/heuristic-search-part-1-introduction-and-basic-search-methods/#:~:text=Heuristic%20search%20is%20class%20of,the%20search%20on%20that%20area. I also referenced the pyvis documentation a lot.
4. Instead of focusing on visualization alone, if the concept of heuristic search can be made into a project, it would allow for more diverse projects. I also think it would be important to focus on this concept of a mental shortcut of AI where it follows traditional problem solving algorithms but also the instinct. And one example project from this unit can be a star but it can also be analytics/prediction, robotics, or optimization.
5. https://github.com/dbstjrgus/pathfinding.git
1. Description of the Project
The project is a Pathfinding Visualization Tool designed to demonstrate the functionality of the A* algorithm on a grid. Users can interact with a 2D grid by setting a start node, end node, and obstacles, then watch the A* algorithm explore nodes in real-time. The tool allows for comparisons between the Manhattan and Euclidean heuristics and provides features like speed control and dynamic visualization of node exploration and pathfinding.
2. Implementation Details
The project was implemented using Python and Pygame, a library for creating graphical applications and games.
Why Pygame?
Pygame is well-suited for interactive and visually rich projects. Its simplicity for rendering grids and real-time updates makes it an ideal choice for this visualization tool.
3. Steepest Part of the Learning Curve
The most challenging aspect likely involved understanding and implementing the A algorithm* itself, particularly:
The balance between the algorithm’s greedy and uniform-cost search aspects.
Managing the priority queue for open nodes and updating the g-scores and f-scores.
Optimizing the visualization process for real-time performance, especially with dense obstacle configurations or larger grids.
4. Best Online Tutorials and Resources
Algorithm Explanation*: GeeksforGeeks – A* Algorithm
5. Suggestions for Future Improvements
Incorporate more pathfinding algorithms (e.g., Dijkstra, BFS, DFS) for broader comparisons.
Enable dynamic grid resizing and adjustable obstacle density to allow students to test the algorithm in various scenarios.
Improve the visualization’s performance, especially for larger grids.
Add a feature to save and reload grid configurations to test different heuristics on the same obstacle arrangement.
6. GitHub Repository
The project repository URL is: https://github.com/a-me-lia/root.git