Monday, Tuesday, and Wednesday of this week were long days of coding. Because I took the time to think out the whole algorithm and write every line of pseudocode, programming was the fun part. I have made the mistake of trying to start programming before I think everything out on some coding projects at Rice. After working so tediously on the different parts of the algorithm, it was very nice to see everything come together.
Implementing the core A-search algorithm was particularly interesting. Traditional A-star searches only take the location of a node (a point on the graph) into account, whereas the direction of a node (in our case, the direction of the track) is very important. Additionally, A-star calculates the neighbors on a given node by moving one node is some specified directions (usually 4- or 8-way movement), but we are moving from node to node via track parts that may or may not be viable moves depending on the immediate surroundings of the track. Because of this, I am calling our A-star search inventory-based, directed pathfinding.
My main issues came from merging the code that Bitarello had already written with my new code. I wrote separate classes and modules that implemented the A-star algorithm, but adapted to our specific problem. Bitarello had written some sections of the code without thinking about how they may be used later on, so I had to go back and make them compatible with my own modules.
Screenshot of the route generated (in blue) to end at the finish line.
By Wednesday, I had a working version of the algorithm. However, it was taking longer than expected to calculate. This was not only concerning because we want to save computing time and power, but because players must wait for the algorithm to finish before they can make any more changes to the track. The screen essentially freezes while A-star finds a path from start to finish. Because of this, I spent a lot of Thursday and Friday looking for ways to increase the efficiency of the algorithm. To find one path on a relatively small grid (say, 20x20x10), the algorithm can loop through the code thousands of times. Thus, even small changes in logic can have far-reaching effects on the runtime.
This week, PUCRS and TECNOPUC released some articles regarding the exchange between PUCRS and Rice. They seem very glad to have us here; I’ve had various conversations about how to maintain the relationship and what both universities can do to not only strengthen ties between our students, faculty, and resources, but also our cultures as a whole.
