Race Track Editor

First Steps & Editor Utilities

My first step in implementing Race Track in Unity was to decide on a level representation. I chose to keep each grid point as a separate GameObject and work with all of them from a separate manager. A more centralized implementation could avoid any extra GameObject overhead and give much better memory performance, but for the sake of rapid prototyping, I chose the simpler solution. Since I chose to limit tracks to a 100 x 100 (later 50 x 50) grid, I didn't expect the overhead to matter too much.

On this page, I'll refer to grid points in the game as graph nodes (or just nodes). Since the game board maps exactly to the pathfinding graph, I find using the algorithmic term more convenient and descriptive. In the code, you'll also see these referred to as the Node and NodeManager classes

The manager class keeps track of all the nodes in a simple array, and when initializing the map, would perform a simple flood-fill/breadth-first search to determine how far each node was from a finish node. This would be crucial later on in the A* heuristic function, so pre-computing it as I built a level was a useful foresight. Creating this flood-fill algorithm also required me to implement a GetNeighbors method, which will be the bases for pathfinding steps as well. 

Pathfinding with A*

With enough editor utilities that setting up test levels was a breeze, I started on pathfinding. Before I elaborate on that process, it's worth thinking a little bit more about how and why A* is needed to pathfind for this game. At first glance, it actually seems simple to perform A* on a grid-based level, using taxi-cab or Euclidean distance as an obvious heuristic. In fact, doesn't my flood-fill setup algorithm solve that problem already? 

The Pathfinding Graph

The answer is no, it's not simple at all. Even though the playing field is very simple to work wtih, the mechanism that we need to optimize against isn't simple at all. The way you maintain velocity in Race Track makes it quite difficult to avoid crashing at times, and the fastest path (by number of moves) is rarely the same as the shortest path (by Euclidean or taxi-cab distance traveled). You can arrive at the same square with different velocities based on the path you've taken, and that will dictate where you can go next. Rather than a simple 2D grid representing the pathfinding graph, we have to pathfind against a graph where every space in the level has a separate node in the graph for every possible velocity you could have when you arrive there. One way to view it is as a 4D grid, where two dimensions represent your location, and the other two represent your velocity. Making a move certainly changes your location, but your velocity at the new location needs to be encoded as well. We can't reuse nodes here because A* needs to track visited nodes, but we don't want it to skip visiting a node with some faster velocity just because it discarded that node when it was moving slowly. An immediate consequence here is that the pathfinding graph is almost intractably large. Even a small level with only 50 location nodes would require a pathfinding graph with thousands of nodes, or perhaps even more depending on how high of a velocity can be attained in the level.

This means that pre-generating the pathfinding graph is practically impossible since it would require brute-forcing all possible paths through the level. But if I'm doing that, I wouldn't need A* at all, since brute-forcing all paths would certainly find the shortest one along the way. Unfortunately, the size of the graph would scale at least quadratically with the number of nodes, and quickly become too large to compute efficiently.

Instead, I chose to generate the graph dynamically, not calculating a pathfinding node's neighbors until I encounter that specific location and velocity in the middle of the algorithm. This allows me to rely on the efficiency of A* to keep the generated portion of the graph relatively small, and avoid any expensive pre-computation at the start. 

Implementation and Heuristics

Although I was using a slightly more complex version of the algorithm, the process of implementing A* really felt more like a task in object-oriented design than in algorithms. For example, I spent a lot of time overloading methods like GetNeighbors to perform the appropriate work based on what type of object was passed in, which allowed me to abstract away a lot of logic when I didn't need to worry about it. A function like GetNexts that calculates legal next moves from a certain position takes two steps: Calculate the center location based on the current velocity, and then return a list containing that square and all its neighbors. Having code that already performed the second half of that task (including all array out-of-bounds error detection) made this process quite simple because I didn't have to re-invent any wheels when adding game logic on top. 

With my game logic embedded in the graph generation, the rest of the algorithm falls out pretty simply. I use a priority queue for the open list of nodes to explore next, and a hash set to store already explored nodes to make sure I don't backtrack. C# language features like IEnumerator make it easy to dynamically generate the graph without disrupting the flow of logic, and I used delegates for my heuristic function to allow for more tinkering later on. In no time at all, I had a working algorithm and I was ready to test it against some real levels made by my peers.

For the first version, I used a very simple heuristic. I was optimizing for the fewest number of moves, so the total cost estimate for a node is the number of moves already made added to that node's flood-fill distance to any goal node. This is akin to assuming that from any given point, the algorithm will move one node at a time toward the goal on the shortest path.

Admissible Heuristics and Optimal Pathfinding

Although A* is an incredibly efficient tool for pathfinding in games, it takes a lot of caution to ensure that you get optimal pathfinding. Because the core of the algorithm relies on a heuristic function to "guess" what moves are more helpful to make than others, it's important to have an effective heuristic. A bad heuristic will simply lead the algorithm in the wrong direction and take longer to run, but a "perfect" one could allow you to skip evaluating any nodes that aren't on or near the optimal path. But the real catch is that an ineffective heuristic function can actually cause the algorithm to fail to find the optimal path and return with one that isn't the fastest.

In order to ensure that your pathfinding will be optimal, you need to guarantee that your heuristic function is "admissible". This is a property of a heuristic that essentially asks it to always underestimate the remaining distance. Classic heuristics like Euclidean distance on simple 2D graphs are easily admissible -- the shortest path can't be shorter than a straight line from A to B. But if your heuristic overestimates the remaining distance even once, the algorithm can discount paths entirely, even if they actually would be faster overall. 

New Heuristics?

As it turns out, it's actually quite difficult (if not impossible) to write an effective and admissible heuristic for Race Track. The way that players tend to speed up and slow down on straightaways and corners is pretty hard to quantify in a simple way, meaning that most simple heuristics (like my flood-fill distance) end up drastically overestimating and opening up the potential for sub-optimal pathfinding from A*. 

I tried implementing a new heuristic that would better model the car's movement in Race Track. During my preprocessing, I ran a BFS on the grid, allowing all moves of length 5 or less that didn't pass through a wall -- essentially modeling a car that always drives at a speed of 5 with instant cornering. Assuming that the track doesn't allow players to exceed a speed of 5 on optimal paths (which is *usually* true in my experience), this heuristic would never overestimate the number of moves. It would match or exceed speed on straightaways, but with perfect cornering, it never needs to slow down on sharp corners. 

Unfortunately, this heuristic failed for an entirely different reason. Many spaces near the start will appear equidistant since some granularity is lost when assuming the car always moves at a speed of 5 -- if the estimation is that the best path has n moves, you might have to go 10 squares away to reach squares that are estimated to be n - 2 moves. But starting out at a speed of 0, it could take 4 moves to travel that far, and during that time A* has no guidance and must do an exhaustive search of the first four moves. This issue compounds exponentially the more that this heuristic underestimates distances, and I found in practice that it slows down pathfinding to the point of unusability.

An Open Pathfinding Problem

Based on my time constraints for the project, I wasn't able to experiment any further with effective heuristic functions. This started to exceed my experience with A*, and I wanted to dedicate more time to the level editor functionality I wanted to add. The flood-fill heuristic was pretty good, and it's able to beat inexperienced players with ease. More optimal heuristics probably exist, but they need to find a way to ensure admissibility without underestimating so much that they lose too much performance. I suspect future iterations would need to factor the current speed into account when evaluating a node, while also encoding an understanding of upcoming turns and straightaways in the preprocessing. It's certainly a problem I'm willing to return to in the future if the need should arise.

Level Editor and Playability

Up to this point, I had mostly been building levels using my Editor utilities and testing in play mode. However, my ultimate goal for the project was to have an in-game level editor to allow my peers in class to build their own digital levels and experiment with my pathfinding implementation. Porting my Editor code to work in-game with native input handling was pretty straightforward, and I was able to add some quality-of-life features like an "Auto Wall" function that surrounds all existing track tiles with walls. I also included a button to check the pathfinding on the level as you build, allowing the user to quickly visualize the fastest path in the level.

Next, I decided on a method for saving these generated levels to a text file through a simple ASCII encoding. I note the size of the full level grid (50 x 50 by default) and then just write out the state of the level in a grid of characters, using different letters for walls, track tiles, and finish lines, and save the result as a .RSL (Racing Sim Level) file. Loading a level from a file was equally straightforward, allowing me to re-use my level instantiation code yet again to generate the level as I read the text file. 

Play With Friends and With AI

Once I could easily save and load a level from a file, I added functionality to play the game against a friend (with pass-and-play multiplayer) or against the computer's pathfinding. This is all done with some simple state-based code that forces players to take turns and includes some convenience tools like highlighting available moves for each player and tracing their path as they go. I also made sure the editor saved the level before loading the gameplay scene to ensure that no changes were lost while testing against the computer or against a friend. I even made sure that the editor could generate a name for your track if you don't provide one, while still avoiding overwriting existing tracks. (As a result, most of my testing tracks were called something like "Test Track (3) (1) (1).rsl")

Race Track Retrospective

I'm actually very proud of what I was able to accomplish in only 10 days of (part-time) work on this project. I encoded the rules of the game and wrote essential editor utilities for working with game levels. Then I wrote pathfinding code for the game from scratch and learned a lot about the theory behind A* along the way. My pathfinding wasn't perfect, but it was much better than most of my friends were at the game, so it's hard to complain. Then, I added robust level-editing and testing features to the game and published a version that my friends could work with themselves. To have accomplished all of this (without a huge amount of difficulty) in such a short period of time is no small feat, and I'm proud of what I made and what I learned along the way.

Of course, this isn't to say that the final product was perfect. I've discussed at length the issues with the pathfinding, but there are also several other bugs in the project. I've seen some issues occasionally with level saving/loading, and it's unstable at times to the point of corrupting save files. I didn't put any effort into teaching the use of the level editor, and the game's UI is clearly still using Unity's default sprites. I see my final product as a strong prototype or proof-of-concept for a real digital Race Track, and with twice as much time I can easily imagine going through to fix those issues. For the moment I think I'm done with Race Track, but maybe I'll return to it in time for next year's class to use it for demos.