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.
- Which heuristic did you choose to implement, and why?
- 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. My A* project explored how different heuristic functions perform on different types of grids and paths. I compared Manhattan and Euclidean distance on more gridlike, random, and mazelike maps. I used pygame for my ui. I chose it because feel like I am pretty competent in pygame.
2. The steepest part of the learning curve for this project was analyzing how to make grids that would be really good for one but awful for the others in order to highlight the difference in pathfinding.
3. I used flint as my online tutorial.
4. I implemented both manhattan and euclidean because those are the 2 most popular heursitic algorithms.
5. It felt very basic almost like it was hard to find a way to achieve a deeper usage of this without making a seperate project. I feel like it could be more learn about it but then make a game or project or something that utilizes the algorithm (not just analyzing the algorithms).
6. https://github.com/nataliemcwhorter/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 implemented a customizable 28×20 grid where the user can change the start/end points, add/remove obstacles, and save/load previous or pre-generated maps. The UI was done with use of Pygame. A* was implemented with a generator, allowing the user to see the progress of the pathfinding algorithm live.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
Making A* was actually pretty straightforward. There was some annoyances with debugging the UI, but I already had some good experience working with Pygame from the previous project, so they didn’t end up being that big of a deal.
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 used AI to help me implement the algorithm, not any one particular online tutorial.
Which heuristic did you choose to implement, and why?
I chose the manhattan distance heuristic. I did this because I limited my agent to moving only in four directions, as I wasn’t a fan of the “wall skipping” that could happen with diagonal movement. Since movement was limited, there wasn’t any point in using Euclidean heuristics, so Manhattan was the most obvious choice.
How could this assignment be improved for future AdvCS classes?
I think we could’ve used one week less on the first project and one week more on this one, and with that extra week we could’ve implemented A* into a game, like we did with RL.
Include your Github repo URL so your classmates can look at your code.
https://github.com/Freedomplaza/project3
1. I made a trailblazer A* algorithm that generates terrain and uses a 3D Euclidean algorithm to implement A*. I used a package called PyVista, which is used for displaying 3D meshes. I also used it for some animations for my slideshow. It is really easy to use and it looks much better than the normal packages like Matplotlib.
2. It took me a while to get my head around how A* works so I think that was the hardest learning curve. I had to draw out a grid and move around pieces on it so I could figure it out. All of the terrain stuff looked complicated but it was mostly based on videos and it didn’t take that long to set up.
3. I used this DataCamp article https://www.datacamp.com/tutorial/a-star-algorithm for the base system of my code and it was a really good explanation overall. I used ChatGPT for advice on turning it into a 3D algorithm which didn’t end up being that difficult.
4. I used Euclidean with the addition of a c^2 in order to make it 3D ((a^2+b^2+c^2)^1/2). Because the mountains are free space, and I allowed movement diagonally (and vertically, because movement horizontally involves movement up the mountain), a Manhattan heuristic wouldn’t really make sense so I went with Euclidean.
5. I feel like some spin on the assignment that could make it have more applications could make it cooler because A* itself can be pretty easy to implement.
6. https://github.com/valenmoore/AStar-Trailblazer.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?
I implemented A* path finding into my project in order to compare the difference between two heuristics, manhattan and euclidean, in four directional movement. I implemented these heuristics through their respective equations, and set up a grid with a start and end where both heuristics would compete to find the optimal path. In order to visualize this, I used pygame to show the start, goal, explored nodes, non-explored nodes, walls, and path to better track how the two heuristics differ from each other. In addition, I used a bunch of different statistical measures like time, nodes explored, path length, etc in order to determine which heuristic would be better.
2.) 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 for me was understanding why manhattan would actually be more efficient than euclidean in 4-directional movement. Because Euclidean calculates straight-line distance, I thought it would be more efficient, but because I implemented 4-directional movement it could only move up/right/left/down.
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.
To be honest, my best tutorial was definitely flint which grabbed information from lots of different websites I assume. I had flint walk me through what A* actually was and how it worked, so that was really the only source I worked with.
4.) Which heuristic did you choose to implement, and why?
I chose both manhattan and euclidean to implement in my project because I wanted to compare the two to see which one was faster. I didn’t want to say I chose manhattan because I assumed it would be faster, I wanted to know with data to back it up that it would be.
5.) How could this assignment be improved for future AdvCS classes?
I think the assignment was a little bit vague in my opinion. I made a relatively simple project that showed manhattan and euclidean distance at work, while other people combined their project to a real life scenario or game.
6.) Include your Github repo URL so your classmates can look at your code.
https://github.com/pieter-sauer/A-Star-Pathfinding.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?
I implemented A* path finding into my project to compare and contrast 3 heuristics: Manhattan, Euclidean, and Octile. I used PyGame to create a grid that allowed the user to pick a starting and ending point as well as have the option to create or generate the walls. The user would then choose which heuristic they wanted to implement and the path as well as the explored nodes would be displayed. Afterwards, the time elapsed, nodes explored, and length of the path would be displayed as well as which heuristic was used.
2) What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
My biggest learning curve/discovery was trying to understand the difference between Euclidean and Octile. I was very confused as to why both of them used 8-directional movement and what their difference was. Once I was able to figure out the difference it became something really interesting for me. I thought that it was very interesting how both Octile and Euclidean would typically find the same path but Octile would explore less nodes than Euclidean because Euclidean would often underestimate due to its straight-line distance.
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.
I worked with Flint to help me understand A* and it was very useful.
4) Which heuristic did you choose to implement, and why?
I implemented Manhattan, Euclidean, and Octile because I wanted to compare the differences between them. Especially since I was working on a graph with mazes, the most optimal heuristic to use differs between many factors. I wanted to explore what it was about the paths I chose that would make my optimal heuristic what it was.
5) How could this assignment be improved for future AdvCS classes?
I really liked that we learned about A* in class and discussed it and also had the programmed Flint to help us with it but the assignment itself and how we were supposed to integrate our learning was a little confusing and I just had to follow Flints’ advice which is fine but if I was less confused I think I could’ve come up with something more creative.
6) https://github.com/Emma-Bernstein18/Project03_Pathfinding
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?
My project was creating a Missing Piece Sliding puzzle. There is a grid of scrambled tiles with an equal number of rows and columns, with one tile missing. The player slides the tiles into the empty space in an attempt to organized the scrambled tiles. To implement the visual aspect of the game I used pygame. I chose pygame because it was a library I know and I am comfortable using. My project also wasn’t very visually demanding, just a pop-up screen with sliding squares, so I could use a simple library.
2. What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
a) was understanding a_star in a technical level. I was able to understand the theory pretty easily, the the heurstics weren’t too bad. The main issue was trying to understand what order my code should be in. I thought that the heuristic calculations would be the first thing I do, but in the code I ended up finding/using, it was the last thing in the loop. b) was having to go through the files and find what i needed to change so that i could make the code also accommodate 4×4 puzzles(had to change hardcoded 3 values to user input and implement hexadecimal), use my instance_checker class, and some other minor changes.
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.
https://blog.goodaudience.com/solving-8-puzzle-using-a-algorithm-7b509c331288
https://github.com/AbdElRahmanOsama182/8-Puzzle
https://www.geeksforgeeks.org/dsa/a-search-algorithm/
4. Which heuristic did you choose to implement, and why?
I started with manhattan and euclidean because they were simple, but functional quite different, which let me test how they functioned when movement was limited to 4 directions. Like I thought, the euclidean model overestimated and took longer because it would look for move that couldn’t be made, while manhatten only looked at 4 directional moves that could be made. At the reccomendation of flint, I added linear conflict as another heuristic, because its a heuristic that works well on missing piece puzzles. It uses the same math at manhattan, but before it chooses the least cost nodes, it adds conflicting tiles to the cost. For each tile it sees blocking the path it wants to go, it adds 2 to the score to simulate moving around the conflicting tile.
5. How could this assignment be improved for future AdvCS classes?
I think there’s a lot of repetition and people choose the most simple heuristics. Adding challenges that encourage people to go into different, more complex directions (instead of just improving the gui) would be helpful to them and make for a better presentaiton day.
6. Include your Github repo URL so your classmates can look at your code.
https://github.com/LanceHackman/Project03_Pathfinding.git