Journal Reflection #4: Insights into your A* project

Please use your reply to this blog post to detail the following:

  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?
  2. What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
  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.
  4. How could this assignment be improved for future AdvCS classes?
  5. 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.

7 comments

Skip to comment form

  1. 1. Based on the description and steps in the first link that Mr. Cochran sent and what Tate told me about a project that previous classes did on navigating a trail, I decided to create a maze of the United States. When the window opens, the program generates a pixelated map of the United States with randomized blue and gray triangle blocks to represent bodies of water and mountains. As Ben pointed out, mountains and bodies of water are not this random in nature, but I wanted an easy way to simulate obstacles necessary for a maze. The starting point and ending point are represented by yellow blocks, and they stay the same on every reload of the maze. Each block is labeled with a number that represents the number of steps it takes (horizontal or vertical only, not diagonally) to get from the starting block to the current block. There are two buttons on the window, one allows you to reload a new map and one allows you to find the shortest path from the start point to the end point around the obstacles. When you press the button to find the shortest path, the program finds the blocks that represent the shortest path and turn them white to display them. The program finds this path quickly because at the beginning, when it calculated the step numbers for every block with a while loop through a list that added its neighbors to that list, it also kept track (as class data) of which block was the neighbor whose step count was labeled just before the current block was. So when the find shortest path button is pressed, the program starts with the destination block and looks at its class data to find out which was the previous block that led to the assignment of the step number to the current block, and then so on and so on until you reach the start block.

    I used pygame because I already was familiar with the basic mechanics from my Mancala project.

    2. The steepest part of the learning curve of this project was figuring out how to implement the find shortest path method. I did not understand the explanation of the article I was using, so I mostly just figured this part out on my own. It took a lot of guessing and checking to decide to use a class to store the previous move and the step numbers of a certain block, because originally I was stubborn and I wanted to use a 2D array of arrays instead of just using a 2D array of objects, which can store so much more data much more easily. Eventually, I figured it out and I definitely have a much better grasp on using objects in python and figuring out how to implement an algorithm on my own and on a time crunch.

    3. The explanation that I used was the first one Mr. Cochran sent: https://www.codementor.io/blog/basic-pathfinding-explained-with-python-5pil8767c1

    Honestly though, I didn’t really understand how this tutorial implemented the algorithm, so I used the basic concepts they were describing but figured out the application on my own. I also had to figure out how to make a US shape maze rather than a square maze on my own.

    4. I think one way that this assignment could be improved for future classes would be to give some more tutorials that have ideas for A* Pathfinding projects that are not just mazes, or are mazes with some kind of twist. I had some trouble trying to figure out what I wanted to apply the A* Pathfinding algorithm to, and maybe a maze is the only option, but I am sure that there are many other things out there that this could be applied to. I wouldn’t want to copy one, but it sparks my imagination to see other creative uses of an algorithm.

    5. Here is my GitHub repo: https://github.com/22ridley/PathFinding

  2. 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 allows the user to place start points and end points on a X by X grid and place barriers wherever they want. Once the user presses space, the algorithm begins searching and finds the most efficient path. The algorithm uses A star path finding, which has 2 functions added up, a g(x) + h(x) = f(x). g(x) is the distance it took to reach the current node and h(x) is the guess of how long it will take to go from the current node to the end. A star is efficient because it only goes in the direction that minimizes the total distance required, disregarding the other paths. The h(x) I chose was a modified version of manhattan distance, a heuristic prediction that states that the fastest distance between two points is an L shape. I multiplied the values by 2 and for some reason it made my algorithm more efficient. I used Pygame to implement this because it is the environment in which I had the most experience and this algorithm is fairly simple and doesn’t require that much efficiency.

    2. What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.

    I think applying the algorithm to the grid and designing the grid itself was the most difficult part. Choosing a heuristic function was fairly easy because using the grid, a manhattan distance was the most obvious (L shape distance). Trying to get the node to check up down left right was the hardest because I had to make sure that I did not go out of bounds. Making the grid itself probably took the most code overall.

    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.

    TechwithTim was the most helpful resource. He explained the intuition behind the algorithm and each step: https://www.youtube.com/watch?v=JtiK0DOeI4A&t=86s

    4. How could this assignment be improved for future AdvCS classes?

    I think that this algorithm is pretty intuitive and the resources given were good. I can’t think of anything off the top of my head that could be improved.

    5. Include your Github repo URL so your classmates can look at your code.
    https://github.com/Brian5998/AStarPathFinding

  3. 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 uses a pygame interface where the user is able to select a starting point, an ending point, and barrier points with a 50×50 grid. The algorithm then solves for the shortest path between the starting and ending points. I used the pygame package because of its extensive documentation and community support, and also because the best tutorial I found used pygame as well.

    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.

    The steepest part of the learning curve for this project was understanding the algorithm. At first, I read the Wikipedia entry on A* and only had a general understanding of the algorithm, but I was still confused about how the heuristics played into the weights of each node. Fortunately, after reading more, I realized that the algorithm was simpler than what the Wikipedia contributors would have you believe. The best resource for me was a YouTube video by creator Tech With Tim that explains the A* algorithm and gives a simple python implementation. You can find that tutorial here: https://www.youtube.com/watch?v=JtiK0DOeI4A&t=11s

    How could this assignment be improved for future AdvCS classes?

    I would perhaps make this project a 1-2 class group activity. Since the project was not complicated at all, and for me, it only entailed watching a tutorial and following along; I think that future classes would benefit from doing it class for only 1-2 classes, not taking up two weeks. I also think that implementing the algorithm in python is much less important than understanding how the algorithm works. So, perhaps, for future classes, you could skip over the python implementation of the algorithm and instead do a unit on pure algorithms/data structures. This unit would not involve programming and would only consist of understanding the logic and core principles behind commonly used algorithms.

    Include your Github repo URL so your classmates can look at your code.

    https://github.com/EmilianoGarciaLopez/a-star-pathfinding/

  4. 1. My program lets the user input a start point, end point, and barrier walls on a 50×50 grid and the algorithm responds with the shortest path between the start and end points. I used pygame since I am familiar with it, and the tutorial (that may have been similar to other tutorials used in our group) used it.

    2. I thought that the hardest concept to grasp was understanding not just the algorithm but the smaller parts that make up the A* algorithm. When I thought of how this project would work, I didn’t think too much about how the algorithm would actually work but once I looked into it I found out that there were more detailed parts like the heuristic function and different methods to measure distance.

    3. The best tutorial I found was made by Tech with Tim on YouTube, located here: https://www.youtube.com/watch?v=JtiK0DOeI4A&t=11s

    How could this assignment be improved for future AdvCS classes?

    4. I may have suggesting something like this before, but I think that some sort of optional mini-workshop about the basics of the algorithm would have been helpful for those (myself included) who did not have any prior knowledge about the subject. I also liked Emiliano’s recommendation of it being a group unit.

    5. https://github.com/tylerpowers/astar-pathfinding

  5. 1. I used pygame to create a maze and then attempted to get A* to work with it. I chose pygame since it was a graphics package I was familiar with and could set up an environment for relatively easily. The event queue and such are annoying to deal with, but once it’s set up all is well.

    2. Definitely finding the exact math for where to draw walls, it was a struggle. I still hate diagonal lines and the fact that the final answer was so convoluted. I was hoping it would be simple but nooooo instead we have “ny*x+y+ny+x+1”

    3. I used https://scipython.com/blog/making-a-maze/ to create the actual maze, though I used pygame as opposed to an SVG image (and so the pygame was where most of my struggles were). For the attempt at A*, I used https://www.youtube.com/watch?v=ob4faIum4kQ&t=562s which helped me understand A* in general but was not all that helpful for implementing it for a maze. The other guides I found that were actually for mazes were really complicated and I didn’t understand what they were doing (they were also like 90 minutes long and somehow made less sense than this much shorter video).

    4. I agree with Tyler’s idea of having a mini-workshop to explain A* before the project because while I understood the very general concept, the nitty-gritty of how it actually works was very confusing.

    5. https://github.com/RavenclawLunatic/MazeGenerating

  6. 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 used an online tutorial to learn about A* and implemented the code used by that resource. I then changed the algorithm to use a grid layout rather than outputting strings. The program creates a set of tiles and then the user chooses a “start” and an “end” as well as has the option to put up “blocks” where the path is not allowed to go. The user can then press the spacebar to generate and display the “most efficient” path.

    2. What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.

    Since the tutorial was fairly straightforward (although it did not explicitly walk me through the code and I had to do a lot of the understanding myself), the pygame was the most challenging aspect. While in the minesweeper project I had a mix of classes and unclassed functions, this time I tried to do things the “right way” and had all of the appropriate things in classes. Doing so, and integrating it with the A* algorithm, was challenging.

    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 can’t find the tutorial I used, but I did find the repo that the tutorial used, which is linked below:
    https://gist.github.com/Nicholas-Swift/003e1932ef2804bebef2710527008f44

    4. How could this assignment be improved for future AdvCS classes?

    The project sort of looks the same for everyone, because we did not really understand if there were many more applications, rather than just a map. It might be nice for the years to come to have a variety of projects and more creativity involved in this project rather than just following a tutorial, although I’m not entirely sure how to implement that.

    5. Include your Github repo URL so your classmates can look at your code.

    https://github.com/23ellaann/Advanced-Computer-Science.git

  7. 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?

    Graphs are the cheese of A*. They come in many flavors: 2D Array, Memory Refs, Arrayed, etc. For me, the 2D array cheese was a stinky mess. I’ll get into that later. What I chose was just a basic memory-ref-based graph. This meant a clean and simple connected graph system with nodes and edges. Each node had an xy coord in additon to storing references to its neighbor nodes. One node was the “start” node and another was the “goal” node. My A* algorithm tried (operative word “tried”) to find the shortest path between these two ndoes. I wanted the node structure to be aesthetically pleasing. At first, during testing, I just randomly assigned neigbors. This created unruly rats nests that where hard to understand. I then remembered one of those weird floaty node webpages that backend devs put in place to compensate for their lack of knowledge (Ella showed how the Darcside website had that). I eventually found something called delaunay triangulation, which is some fancy math that draws nice triangles between points. Like any good programmer, I found a library that did all the hard work for me. Throw the nodes in and boom, all the correct edges.

    2. What was the steepest part of the learning curve for this project? Please elaborate and explain your answer.
    2d arrays are some stinky cheese and I don’t like them. I initially tried making a maze-solving algorithm much akin to Charlotte’s project. But because I am both stupid and stubborn, I never looked up any tutorials to help me with the project. I was pushed all the way up to a week before the presentation, where I promptly switched over to what I have now. No regrets. In other news, go heaps are surprisingly easy to setup, granted you enjoy writing boilerplate code. My A* only sometimes worked correctly. but it was 85%. Passing grade.

    3. What was the best online tutorial you found to help you understand and implement the A* algorithm? If you
    Wikipedia, no pain no gain.

    4. How could this assignment be improved for future AdvCS classes?
    A workshop would be much appreciated.

    5. Include your Github repo URL so your classmates can look at your code.
    https://github.com/memsdm05/knotnauts

Leave a Reply