There was no update last week since I was traveling. This was my first actual vacation since starting work on Starcom: Unknown Space. For the past six months or so I’ve been focused intensely on development, averaging around 55-60 hours of work a week. I really do enjoy most of the development process, so it often doesn’t even feel like work. Even so, I think it was helpful to take a solid block of time off to recharge.
On either sides of the trip, I did make some good progress on a new feature that ended up being fairly tricky to implement, but I think will be a solid QoL improvement: smarter autopilot.
The current autopilot just steers to a destination, trying to avoid immediate obstacles, but can’t take advantage of any fast-travel options.
The new autopilot can construct a route that uses discovered flingers and gateways to minimize travel time.
My initial thought was that this should be fairly easily implemented with A* (pronounced A-star), the go-to pathfinding algorithm for game dev. It’s fast, fairly easy to understand, and guaranteed optimal for any game whose routes can be expressed as a graph with approximately known travel “cost”.
Autopiloting the universe of Starcom: Unknown Space would seem to satisfy these requirements. A graph can be composed of the player’s starting position, the various fast-travel artifacts, and the destination. The cost is either very small for fast-travel, or the actual distance for normal space travel.
But it didn’t work: my first attempt was using an existing C# library, and when that failed, doing my own implementation based on some canonical pseudocode.
Looking closer, I realized that A* is only guaranteed to return the shortest path if the heuristic does not overestimate the actual cost. This was the source of the problem. In a typical A* implementation, you can use a straight line: the shortest path between two points (or the Manhattan distance in some cases). In this universe, that heuristic completely misses the point of advanced autopilot. The fastest route might be to head in the opposite direction of your destination towards a flinger, which leads even further away, to another flinger that leads further away still, finally to gateway that brings you close to your destination. Or maybe that gateway is further than you started, but is right next to a third flinger that leads straight there.
So the heuristic I ended up using was basically that gateways and flingers have near zero cost in the heuristic. The only thing that had a known cost was sailing through normal space. This means my implementation is not much different from Dijkstra’s algorithm, because the heuristic doesn’t have much information. And it’s the worst case version of Dijkstra’s algorithm because the graph is almost-fully connected (the player can fly between any two points and there’s no way of knowing in advance if that will help).
Fortunately, there are a finite number of fast-travel points in the game and path finding only needs to be done in the single frame when the player chooses to set a new destination (and the algorithm only needs to check known fast travel points). So probably not a high priority to optimize this.
Until next week!
– Kevin