This week I've been recovering from the great time I had showing Space Station Continuum at EGX Rezzed last weekend. The response was absolutely fantastic, and I'm immensely grateful to everyone who played the game and shared their thoughts and excitement for its future.
The game also managed to attract the attention of a variety of games journalists and YouTubers. Here's a couple of the videos published so far:
- Many A True Nerd - EGX Rezzed 2018
- Skeletorus - An Interview with N-Body Solutions at EGX Rezzed 2018
Thanks to the testing by players at Insomnia 62 at the end of last month, the demo shown at EGX Rezzed was much more stable and allowed players to spend a lot more time with it. As a result, there were some truly enormous and complex stations made by some particularly engaged players (thank you!) which began to show some cracks in the existing astronaut pathfinding system. In short, they were getting lost.
Astronauts in Space Station Continuum each handle their own movement. They choose a target location based on what they need or want to do, and find a route to that location using a pathfinding algorithm. This algorithm is based on the A* Search Algorithm - common in computer science for a range of applications. Unfortunately, the current implementation looks like it was written by somebody who had skimmed a couple of articles on A* pathfinding and thrown something together that looked vaguely similar. That's because it was!
I first designed the pathfinding system in Space Station Continuum many months ago, during the earlier prototyping phases of development. It worked, for the most part, but struggled with finding its way around more complicated space stations full of dead-ends. It's something I've been meaning to revisit for some time now, and this past week I finally dived back into it.
What was wrong?
The existing implementation shared some similarities with a functioning A* algorithm, but had a couple of important pieces missing. First, it wasn't generating the open set (also called the open list) correctly. And second, it wasn't properly calculating the cost of each possible path. This resulted in astronauts being unable to find their way to their destination in anything other than the simplest of stations. This was obvious fairly early in development, so I had made them capable of pretending they had already reached their target any time they got lost. This meant they could eat, sleep, and even use the bathroom in rather inappropriate places.
Changing the current implementation to fix these problems was going to be time consuming, messy, and inefficient. So I scrapped the whole thing and started again.
Rather than explaining A* pathfinding myself, here's an excellent video to do it for me:
https://www.youtube.com/watch?v=-L-WgKMFuhE
A big difference between the solution described in the video and the one used in Space Station Continuum is the lack of a grid-based navigation system. Instead it uses a number of "Navigation Nodes" placed at appropriate locations within each of the station modules. These act as a guide to show the astronauts where they can and cannot go. By showing these nodes and colouring them differently, we can visualise how the algorithm works.
- The blue node shows the destination
- The red nodes show rejected paths
- The green nodes show the chosen path
It's quite interesting to watch the astronauts moving around with the nodes turned on. It seems that they're now able to cope with much larger and more complex stations than the one shown above, and I haven't seen them going to the bathroom in the hallways for a while! Perhaps I'll leave this visualisation mode in as a toggle-able option in the upcoming Alpha of the game so you can see it too.
That's it for this week. I'm going back to watching astronauts navigate some cruelly-designed mazes to get to the bathroom. See you next time!
- John