Pittsburgh is a beautiful city, at least the part I'm living in. The streets of my neighborhood, lined with stores, a mix of antique restaurants and contemporary fashion salons, feel so fresh, clean, and perhaps even a little romantic at dusk.
That's what I felt about my project when I finally created a working animation of my grid, minus the romantic part. I took Mr. Corica's suggestion on repeatedly drawing the graph during the algorithm's execution to simulate live animation. New versions of the graph would draw over previous versions so quickly that to the human eye, it would seem as if every iteration of my code's draw function only adds newer elements to the graph. To make this happen would, of course, also require a wait function that runs in between iterations, as otherwise only the final state of the graph would be observable. Javascript is a single-threaded language, so it doesn't offer a built-in sleep function that pauses the code without killing the entire browser. My first solution attempt was a sort-of self-loop, a loop that calls itself with a working timer in between iterations. However, the loop had to be hardcoded and I couldn't find a way to break out of it once A*'s termination requirement was met (either having reached the end state or having filled the entire graph without finding an end state). Luckily, my second solution worked. I used an asynchronous function, denoted by the keyword "async", to run the main function of my code. This allowed for a simple custom-made sleep function to work, called upon in the async function and preceded by the keyword "await". Once the timer problem was solved, I had a graph that could display any square dimension (limited only by runtime efficiency, 100 x 100 blocks gets a little slow), have any start and end blocks, a changeable weight to scale A*'s efficiency, and animated blocks of different colors flow through the graph to visualize the algorithm's execution.
The last thing needed was to actually chart the shortest path produced by the algorithm. My version of the algorithm does not actually keep track of the shortest path during its execution. Rather, it looks for the most optimal way to reach the end block in a non-linear fashion, meaning the algorithm might explore multiple different blocks across the graph at the same time. Since I did record all the blocks that the algorithm at one point deemed the lowest minimum value (closest to the end) in a boolean array, generating the shortest path simply required backtracking from the end block to the start block by repetitively finding the next adjacent block with a true value in the boolean array that is closest, of the previous block's neighbors, to the start.
After producing what is, in my opinion, a good looking animated graph with cool colors, I met with Dr. Likhachev again. For my remaining time at the lab, I will be working on creating the same animation feature for ARA*, an improved and more efficient version that Dr. Likhachev himself wrote years back.
That's what I felt about my project when I finally created a working animation of my grid, minus the romantic part. I took Mr. Corica's suggestion on repeatedly drawing the graph during the algorithm's execution to simulate live animation. New versions of the graph would draw over previous versions so quickly that to the human eye, it would seem as if every iteration of my code's draw function only adds newer elements to the graph. To make this happen would, of course, also require a wait function that runs in between iterations, as otherwise only the final state of the graph would be observable. Javascript is a single-threaded language, so it doesn't offer a built-in sleep function that pauses the code without killing the entire browser. My first solution attempt was a sort-of self-loop, a loop that calls itself with a working timer in between iterations. However, the loop had to be hardcoded and I couldn't find a way to break out of it once A*'s termination requirement was met (either having reached the end state or having filled the entire graph without finding an end state). Luckily, my second solution worked. I used an asynchronous function, denoted by the keyword "async", to run the main function of my code. This allowed for a simple custom-made sleep function to work, called upon in the async function and preceded by the keyword "await". Once the timer problem was solved, I had a graph that could display any square dimension (limited only by runtime efficiency, 100 x 100 blocks gets a little slow), have any start and end blocks, a changeable weight to scale A*'s efficiency, and animated blocks of different colors flow through the graph to visualize the algorithm's execution.
The last thing needed was to actually chart the shortest path produced by the algorithm. My version of the algorithm does not actually keep track of the shortest path during its execution. Rather, it looks for the most optimal way to reach the end block in a non-linear fashion, meaning the algorithm might explore multiple different blocks across the graph at the same time. Since I did record all the blocks that the algorithm at one point deemed the lowest minimum value (closest to the end) in a boolean array, generating the shortest path simply required backtracking from the end block to the start block by repetitively finding the next adjacent block with a true value in the boolean array that is closest, of the previous block's neighbors, to the start.
After producing what is, in my opinion, a good looking animated graph with cool colors, I met with Dr. Likhachev again. For my remaining time at the lab, I will be working on creating the same animation feature for ARA*, an improved and more efficient version that Dr. Likhachev himself wrote years back.
Sounds like you are making a breakthrough with your work! Will be interesting to see your results in the fall.
ReplyDelete