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. I used Pygame to show the A* algorithm on an 8-directional grid to find the optimal path between user-selected start and end nodes. The algorithm takes into account the weight of diagonal movements as √2 and non-diagonal movements as 1. The user selects the size of the grid (up to 100 x 100), the start and end nodes, obstacle nodes (which can’t be traversed), and which heuristic to use (among Manhattan, Euclidean, and Diagonal). This allows the user to compare the efficiency and accuracy of the different heuristics on the grid. The program will then animate the algorithm by showing nodes in the open list in green, nodes in the closed list in red, and the final path in yellow, and print the amount of nodes explored, the length of the path, and the total cost in the terminal. I chose Pygame because it’s easily implemented in Pycharm and Flint knows it pretty well; I’ve also used it before in the Game Design class.
2. The steepest part of the learning curve was understanding the open and closed lists and how A* (and Dijkstra) “pop” the lowest cost node from the open list and process it, then add it to the closed list. Once I understood how the algorithm loops through the lists, the idea of f(n) as “cost” and how h(n) biases the algorithm towards nodes in the geometric direction of the end node made a lot more sense.
3. The best online tutorial was the Stanford one listed in the assignment overview. It did a good job explaining the evolution of pathfinding algorithms from breadth-first to A*.
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
I also used the Wikipedia entry:
https://en.wikipedia.org/wiki/A*_search_algorithm
4. Ultimately, I allowed the user to choose between Manhattan, Euclidean, and Diagonal heuristics so they could compare the relative efficiency and accuracy on the same layout. Given that it’s an 8-directional grid, the optimal heuristic is the Diagonal one because it most accurately estimates the diagonal distance as √2, whereas the Euclidean heuristic only evaluates the “as the crow flies” distance which doesn’t account for the limitations on movement. Manhattan is inadmissible because it will overestimate diagonal distances as x difference + y difference which is always greater than the hypotenuse.
5. I can’t really think of anything major. Maybe it could offer pointers on other grid layouts? I’m curious to see how pathfinding might change on curved grids.
6. https://github.com/Gabriel-WO/Project1_Pathfinding.git
Gabriel, I really enjoyed your project and your presentation. We had a few of the same ideas, such as implementing an 8-directional grid and letting the user switch between heuristics. I liked that you included a way for the user to keep the same grid configuration between runs so they could compare different heuristics on the same setup. I also appreciated your understanding of the open and closed lists in the pathfinding algorithms you showed; you explained the process for each algorithm in depth and in a way that was easy to understand. One thing for next time: even though your understanding of edge cost was clear, implementing mud or elevation in the program would let users explore those cases. Also, keeping a header at the top of the grid was a great way for me to check different stats; you printed out the results in the Python terminal, which is fine but tedious to switch between windows. I didn’t check out either of the sources you listed, but from a quick glance, they seem very informative. We differed in our heuristic results; you found diagonal to be the most efficient, while I found Euclidean to be the most efficient and always admissible. I’m not sure why; maybe our heuristic setups were a bit different. Finally, I also liked how you set up different files for each class. This is a more professional approach, and I want to incorporate it into my future projects.
Gabriel, your explanation of why Manhattan is inadmissible on an 8 way grid was one of the clearest I read, especially the way you described it as counting the legs of the triangle instead of the hypotenuse. Splitting the code into Node, Grid, and main made it really easy to follow, and it’s a more organized setup than a lot of projects. I liked being able to choose the grid size up to 100 x 100 and pick the heuristic with buttons, and the open list, closed list, and path colors make the search easy to watch. The C key that keeps the walls so you can test each heuristic on the same layout is a smart touch, because that’s the fairest way to compare them. We ended up with the same pick too, since your Diagonal heuristic is the octile formula I used for 8 way movement. One small idea for later is that you could add a check so paths can’t slip diagonally between two walls that only touch at a corner.
Really cool build! Adding 8-directional movement with weighted diagonals is a great touch. Most implementations stick to standard 4 way grids, so accounting for the sqrt2 cost makes it feel much more natural. Your breakdown of why Manhattan becomes inadmissible on an 8 way grid is spot on, and letting the user toggle between Manhattan, Euclidean, and Diagonal heuristics directly in the UI is awesome for seeing admissibility trade offs in real time. Printing out the total nodes explored alongside the path cost in the terminal gives a really clean benchmark of how each heuristic actually performs. One small idea if you ever feel like expanding it. did you run into “corner cutting” when moving diagonally between two adjacent barrier blocks? Adding a quick check to prevent squeezing diagonally between blocked orthogonal tiles can make barrier navigation look super polished.
1. I used Pygame for my UI environment since it was very easy to use. I implemented the assignment using constants, a cell class, all three heuristics, an A* function, and a main function. All of my code was in one file: main.py. When the program runs, the user sees a 25×25 grid. The first click will set the start node, the second click will set the end node, and subsequent clicks or drags will set walls (which the algorithm must navigate around). The user can also add mud (triple the edge cost) by pressing the M key and clicking/dragging on the grid. Pressing H lets the user change the heuristic the algorithm runs, allowing the user to compare the efficiency and admissibility of each. A header above the grid shows the current heuristic, a timer starts when the program runs (press the space bar), and the final cost of the optimal path. Clicking R resets the grid for another run.
2. The steepest part of the learning curve for this project was understanding the pathfinding processes. I understood the heuristics relatively quickly, but understanding how BFS, Dijkstra, and A* worked was difficult. I also struggled to understand FIFO and priority queues at a high level. Additionally, I found the greedy property hard to understand. Overall, the hardest part was understanding how the algorithms worked; I had to use many Flint sessions and reference articles to grasp the topics.
3. I thought that Flint was the most helpful tool for me to understand both the algorithms themselves and the heuristics involved in A*. Additionally, the Geeks for Geeks article helped me understand the basic processes behind A* and the differences between pathfinding algorithms. https://www.geeksforgeeks.org/dsa/a-search-algorithm/
4. I allowed the user to switch between the Manhattan, Diagonal (Chebyshev), and Euclidean heuristics with a header at the top showing the current heuristic, time, and cost of optimal path to allow the user to compare the relative efficiency and admissibility of each heuristic on an 8-directional grid. On my 25×25 grid, Manhattan was the fastest on simple setups because it overestimates the heuristic, leading to quicker advancement toward the goal node. However, on more complicated configurations, Manhattan wasn’t always admissible, and Euclidean+Diagonal was more efficient and always found the optimal path. Overall, I found Euclidean the most efficient heuristic on my grid, but on a larger 8-directional grid, the floating-point computations slowed Euclidean down a good bit.
5. Not sure, to be completely honest. I liked this as an introductory assignment. Nothing from me since we haven’t done much else with ML or reinforcement learning yet.
6. https://github.com/garrbearzhou/Project1_Pathfinding
Garrett, I really liked your project. It’s impressive how much you fit into one file while keeping it easy to follow, and your comments explain what each part does. The header showing the heuristic, time, and cost makes it really easy to compare runs without switching windows. Adding mud was a great call too, since that’s what makes the cost side of A* actually matter, and being able to toggle between walls and mud with M makes setting up a map quick. I also liked that you can drag to draw walls instead of clicking every cell. Your README does a nice job walking through BFS, Dijkstra, and A* step by step, and your explanation of the greedy property in Dijkstra was really clear. We set up the priority queue the same way, with a counter as a tiebreaker in heapq, so it was cool to see we landed on the same idea. One small idea for improvement is showing the number of explored cells in the header next to the time so you can easily compare how much work each heuristic does.
The mud mechanic is a really cool addition. Adding weighted terrain like that makes testing the heuristics way more cool than just using normal walls, because you actually get to see the path bend around high cost tiles instead of only going around hard barriers. Your point about Manhattan running faster on simple setups because it overestimates made a lot of sense, it basically turns it more greedy and pushes it straight to the goal even if it sacrifices admissibility on an 8 way grid. Also neat that you noticed the floating-point math slowing down Euclidean on bigger grids, a lot of people overlook how much those extra square root calculations can add up during pathfinding.
1. Project description, implementation, and UI environment
My project is an A* pathfinding explorer written from scratch in Python. It runs on a grid with walls and mud. Mud costs 5 to walk through and open ground costs 1, and you can switch between 4 way and 8 way movement, where a diagonal step costs √2. I wrote BFS, Dijkstra, Greedy Best First, and A* as one search loop where the only thing that changes is the priority. BFS uses steps, Dijkstra uses g, Greedy uses h, and A* uses g + h. That made the comparison fair, and it shows how A* grows out of the other two: BFS plus edge costs gives you Dijkstra, and Dijkstra plus a heuristic gives you A*. The search is a Python generator that pauses after every cell it expands. The visualizer uses that to animate the search, and the benchmark and tests run the exact same code to the end.
There are three parts. The first is a PyGame visualizer where you can draw walls and mud and switch the algorithm, heuristic, diagonal movement, and heuristic weight. Pressing TAB runs every method on the current map and shows a comparison table. The second is a benchmark that runs every method on 300 random maps for each movement mode and compares everything to Dijkstra’s cost. The third is 128 tests covering edge cases and checking that paths are optimal.
I used PyGame. The assignment asked for it, but it also fits well since it’s plain Python, allowing the visualizer to import my search code directly. Drawing a grid of colored squares is simple in it, and the event loop made keyboard controls and painting walls with the mouse easy. The one problem was that PyGame looked blurry on my Mac’s Retina screen, so I added a small window file that draws at the real pixel size.
2. Steepest part of the learning curve
The steepest part was pixelation issues. Origianlly, my interface didn’t look good, so I brainstormed and storyboarded a better interface and prompt engineered that into implemenation. However, it came out super pixely so I had to tune it specifically to my Mac’s retina display.
On the concept side, the hardest idea was admissibility once diagonals are allowed. Manhattan distance is perfect for 4 way movement, but with diagonals it overestimates, because it counts a diagonal step as 2 when it really costs about 1.41. In my benchmark, Manhattan with diagonals looked faster (312 cells expanded) but missed the cheapest path on 28% of maps. That’s when it clicked for me that a faster heuristic isn’t a better one if it breaks the guarantee.
3. Best online tutorials
The best one by far was Red Blob Games. It builds A* up step by step from BFS to Dijkstra, with interactive diagrams, which is exactly how I structured my code. The heuristics page is also where I got the cross product tiebreak idea.
4. Which heuristic and why
I implemented six (zero, Manhattan, Euclidean, Chebyshev, octile, and octile with a tiebreak) so I could compare them. My main pick is octile for 8 way movement, and Manhattan for 4 way. The heuristic should match how the agent actually moves. Manhattan is the exact distance on open ground when you can only go up, down, left, and right. Octile is the exact distance when diagonals cost √2. The closer h gets to the real cost without going over, the fewer cells A* has to explore.
The numbers backed this up. With 4 way movement, A* Manhattan expanded 351 cells compared to Dijkstra’s 778 and always found the cheapest path. With 8 way movement, octile expanded 397 compared to 775, also always optimal. Euclidean and Chebyshev were also safe, but they were looser guesses, so they explored more cells.
I also added my own adaptation, a tiny tiebreak based on a cross product, which favors cells near the straight line from start to goal. On an open map from (2,5) to (37,28) with diagonals, plain octile expanded 66 cells and my tiebreak version expanded 36, with the same path cost.
5. How the assignment could be improved
It would be neat to give the whole class the same set of test maps, so we could compare our results with each other directly instead of each of us benchmarking on our own random maps. Lastly, the assignment could ask for a small experiment with numbers, like cells expanded and path cost, and not just a working demo.
6. GitHub repo
https://github.com/gspamula/Project1_Pathfinding
ji
Ganapathi, I really enjoyed your project and presentation. Some strong points in your project were your user interface and your test files. Your UI was fantastic, which is why I was surprised to hear that the steepest part of the learning curve was pixelation and the UI. You had lots of great buttons, and it just looked very professional overall. Your testing files are something I want to incorporate into my future projects. You were able to back up every claim you made with numbers, which is why your heuristic choices were definitely optimal, since you did hundreds of tests for each heuristic on randomly generated setups. I also really liked that you conducted tests on each algorithm, which allowed you to gain a better understanding of how they worked and their efficiency in comparison to each other. Speaking of heuristics, I really liked how many additional heuristics you added. That was going above and beyond, so I really liked your effort and curiosity on that part. One improvement is that, instead of running 3 algorithms while only showing one, which is excessive in my opinion, give the user the same autonomy to choose between algorithms and heuristics, but only show the selected combination for the animation. That would make the project more useful for the average user. Overall, you did a great job!
Ganapathi, your project was really impressive. Adding mud that costs 5 was a great idea, because that’s what actually shows why Dijkstra is better than BFS. When every square costs the same, they basically do the same thing, so the mud made that comparison mean something. My favorite part of your post was the result about Manhattan with diagonals. It expanded fewer cells but missed the cheapest path on 28% of maps, which is a really clear example of how a faster heuristic isn’t always a better one. I also thought the cross product tiebreak was clever, since going from 66 cells to 36 with the same path cost is a big improvement for such a small change. One thing I’d be curious about is how the tiebreak does on maps with a lot of walls and mud, since your example was on an open map. It would be interesting to see if it still helps that much when the straight line from start to goal is blocked.
I really appreciated how detailed your UI was; it made it a lot easier to compare the efficiency and accuracy of all the different algorithms and possible A* heuristics. I also liked how your presentation used data from the project to compare the algorithms across different scenarios. Using the mud added a lot of depth to the project, and together with all the different heuristics and test files made the project feel professional and very detailed. I thought the analysis of why the Manhattan heuristic isn’t ideal—even though it’s fast—was great and encouraged me to think about how those tradeoffs might appear in other daily programs.
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 built an interactive pathfinding visualizer using Pygame, setting up the board through an object-oriented grid layout. Every square on the board is its own Spot object that keeps track of its row, column, visual coordinates, and whether it acts as a wall, while constantly checking its four cardinal neighbors to make sure it only looks at valid, unblocked paths. The heart of the algorithm runs on Python’s PriorityQueue, which stores (f_score, count, spot) tuples where a simple counter prevents the program from crashing whenever two spots end up with the exact same score. I went with Pygame over something static like Tkinter because it gave me immediate control over mouse events and drawing frames, letting users click to place start and end points, drag out barrier walls, and watch the open set, closed set, and final path draw right across the screen in real time.
What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
The toughest part was shaking off the rust with Pygame and figuring out how to smoothly weave the visual animations directly into the algorithm’s search loop. It had been a while since I touched Pygame, so mapping raw mouse pixel clicks to actual row and column coordinates in the 2D grid took some patience, and I used Flint and Gemini as sounding boards to get back up to speed on window handling and event loops. On top of that, making the visualization step through live instead of just freezing and spitting out a finished path meant calling draw functions right inside the node evaluation logic, which was tricky to balance without bogging down the app.
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.
The most helpful resource was Tech With Tim’s A* Pathfinding Tutorial (https://www.youtube.com/watch?v=JtiK0DOeI4A). It did a fantastic job helping me understand theoretical pathfinding concepts and create readable Python code, specifically when it came to configuring the priority queue, breaking score ties with a counter, and tracing back parent pointers to draw the final path.
Which heuristic did you choose to implement, and why?
I went with the Manhattan distance formula because it matches up naturally with a four-way orthogonal grid. Since the visualizer doesn’t allow diagonal moves and every step costs the exact same amount, Manhattan distance represents the actual minimum number of squares an agent has to walk across an open grid. When I tested Euclidean distance, its straight diagonal calculations underestimated the actual path cost and caused the algorithm to check a bunch of unnecessary nodes, whereas Manhattan distance provided a much tighter, admissible bound that made the overall search noticeably faster.
How could this assignment be improved for future AdvCS classes?
Adding a basic visual guideline or a quick rubric outlining what a solid interface should look like would help a lot. Since this was my first time really designing an interactive graphic interface, it was hard to tell how far to go with ui polish beyond simply getting the algorithm to display on screen. Having a small list of expected basics would give students a clear target to aim for instead of having to guess what the interface needs.
Include your Github repo URL so your classmates can look at your code.
https://github.com/ym616/Project1_Pathfinding.git\
Yash, I really liked your project. Making every square its own Spot object that keeps track of its neighbors was a smart way to set up the grid, and it probably made the rest of your code a lot easier to follow. I also liked that you showed the open set and closed set while the search was running instead of just the final path, since that makes it much easier to see how A* is deciding where to go. It was cool that you tested Euclidean against Manhattan and explained why Manhattan works better on a grid without diagonals. That shows you actually understood the heuristics instead of just picking one. One thing you could add is a counter on the screen that shows how many squares each search checked. That way you could switch between heuristics and compare them with actual numbers, not just by looking.
1.I built A* from scratch in Python with a Pygame visualizer. You paint walls on a 40×40 grid, set a start and goal, and watch the search animate one step at a time. Number keys switch between four heuristics so you can compare them on the same board, and a status bar shows how many squares each search checked. I also wrote a separate script, compare.py, that runs BFS and all four heuristics on four fixed boards and prints the results.
I used Pygame because the assignment recommended it, I have experience with it from Game Design, and it’s a good fit for a grid: drawing squares is simple, and its event loop handles mouse clicks and key presses easily.
2.Understanding why my first working version colored in a whole rectangle of squares instead of heading straight to the goal. It looked like a bug, but it wasn’t. On an empty grid, lots of routes are equally short, so hundreds of squares tied for the same score. I fixed it by breaking ties toward squares that had already traveled further, which kept the shortest path but cut the search from the whole rectangle down to 59 squares. Figuring out that the code was correct but needed a tie-breaker taught me more about how A* works than writing it did.
3. I used the Red Blob Games article linked in the project to introduce me to the pathfinding algorithms and how they worked.
https://www.redblobgames.com/pathfinding/a-star/introduction.html
For any questions I had about pathfinding algorithms or heuristics, I asked Claude. I also used Claude for explanations, debugging, and structuring the code; this is documented in my README.
4. I tested four: Manhattan, Euclidean, Chebyshev, and weighted Manhattan. Manhattan worked best. My board only allows up, down, left, and right movement, and Manhattan counts exactly those moves, so its guess is exactly right on open ground. Euclidean and Chebyshev assume you can move diagonally, so they guess too low and search much more. Weighted Manhattan searched about the same as Manhattan but sometimes returned a longer path.
5. I really enjoyed this assignment and having the freedom to choose our own heuristics to test. However, you could also assign people to test one heuristic and then present that one heuristic, so that we are all presenting about something different.
6. https://github.com/solomonhornstein/Project1_Pathfinding.git
It was cool that you created a comparison script that could automatically collect the data for you. I would also be interesting to tune the weighted manhattan to find the optimal ratio in terms of minimal nodes searched and quickest results. It was cool to see that you were able to implement four different heuristics. Writing more inline comments describing the functions in your code may be something to do more of in the future. Nice work.
Solomon, your #2 is similar to what I ran into. On an empty grid where the start and end are in opposite corners, all my algorithms explored all the cells because they tie with the same ‘f’ value. I did not fix the tieing issue, so my algorithm was not as efficient.
The tie breaker fix was really smart. That rectangle issue on open grids gets so annoying, so favoring nodes with higher g-scores to cut it straight down to 59 squares is a great solve. Also i like that you made compare.py to test everything on fixed boards instead of just testing by eye in the visualizer. Makes the data on node counts way cleaner. Good stuff man.
1. For my project I used Pygame in Pycharm. I chose to use it because it’s somewhat easy to implement and doesn’t require other libraries or applications. Once the main file is run a window opens and all program interaction happens there. There is no console interaction. I have three main files. The game loop file, comprising of most of the pygame necessities; the grid file, which sets up the grid tile logic; and the pathfinding file which includes the A* algorithm and runs grid file functions. UI operates the main functions of the program, incrementing the algorithm, setting the heuristic, showing the paths, and restarting. It also displays step number(of the algorithm) and path length. The user can create walls as obstacles and explored routes are shown in orange; the green route is the optimal route and the red lines are all the paths to specific nodes.
2. The steepest part of the learning curve was understanding how to recreate an algorithm generically. I didn’t want to copy/have AI make the structure, so I had to fully understand it conceptually before making the algorithm. It was also difficult to know where to start since the algorithm can only really be tested once all the components are put together. I started by creating specific functions like bestF() to get the best F score from a list of nodes.
3. This youtube video helped explain a few more of the details of A*: https://www.youtube.com/watch?v=i0x5fj4PqP4&t=1s. The interactive elements were very helpful: https://www.redblobgames.com/pathfinding/a-star/introduction.html.
4. The best heuristic for my 4 directional movement system is manhattan, however both manhattan and euclidean can be selected in my program. Because no diagonal movement is possible, the Euclidean takes a zigzag pattern. Manhattan takes less time to calculate so is better for this setup.
5. It would be interesting to go in depth after completing the project with in class explanations of optimizations and use cases. Knowing what corners can be cut or what types of computations take the most time would add more context.
6. Include your Github repo URL so your classmates can look at your code.
https://github.com/KingstonH27/Project1_Pathfinding.git
Kingston, I liked how you implemented buttons to control the program instead of the keybinds that everyone else used. It must have been difficult, but it was unique to see and made your UI the best. I also really like the idea of displaying the algorithm incrementally, because it definitely would help in showing the heuristic importance in exploring cells with A*.
1. I used PyGame on a 30 by 30 square grid. Instead of just A*, my program runs BFS, Dijkstra, and A*, as well as A* with the less efficient Euclidean heuristic. My grid has the option for mud terrain, which costs 5 instead of the normal 1. The reasoning for weighted terrain was to show the difference in BFS and Dijkstra, because without weighting the cost and explored tiles return nearly the same. My project uses PyGame because drawing the grid is simple and building the UI was relatively easy with the help of Flint and Claude.
2. The steepest part of the learning curve for me was understanding the difference in the algorithms and how searching for cells and exploring them is different than creating a final path. I kept thinking that the path was build while expanding, instead of that the algorithm writes down explored cells and their parent as it expands. I finally got that once the goal is explored, the program backtracks the path with the lowest cost to build the final path.
3. The RedBlobGames article (https://www.redblobgames.com/pathfinding/a-star/introduction.html) was the most helpful to me. This visual also gave me inspiration for the weighted terrain in my design. Seeing the algorithms in action helped me grasp the evolution from BFS -> Dijkstra -> A*. Claude was also very helpful because it helped me understand the code that was being written, and also gave me outlines from which I would write code instead of just giving me the answers flat out.
4. I chose to implement a Manhattan heuristic because my program only allows 4-directional movement and it gives exactly the fewest possible moves. It never guesses too high, making it an admissible heuristic on all boards, so A* finds the cheapest path and explores the least. I also have a Euclidean setting just for visualization, but it is not the preferred heuristic. This is because Euclidean works better on an 8-directional program because of the lower result it returns for a diagonal movement(manhattan returns 2, euclidean returns sqrt(2)).
5. I think having one universal test maze would be good to help compare implementations between students, instead of the current project scenario where the results comparing algorithms only matter within our own projects.
6. https://github.com/toanshdesai/Project1_Pathfinding.git
I really liked how you incorporated both different heuristics for the A* algorithm and Dijkstra’s/BFS. That made it a lot easier to compare all three different algorithms. I also liked how you chose a Manhattan heuristic for the 4-directional grid; a lot of people did 8-directional grids, so I thought it was unique. Your explanation of how A* evolved from BFS and Dijkstra’s was detailed and worked well with the visual representation you had.