Starship Builder - Crew Congestion & More

It's been a couple weeks since I last posted about Starship Builder, mostly because my progress since then has been lots of little improvements and not many big new features. But all those new improvements have added up, and I also have working on a significant new mechanic that I'd like to talk about, especially with regard to how it's programmed.

Here's a rough list of what's changed since the last post:

• Added crew congestion mechanic. (See below.)
• Replaced that ugly purple grid with a much nicer space background. A simple grid is overlayed on top of the background.
• Bullets fired from cannons now inherit the ship's velocity. (This is more physically realistic.)
• Tons of bug fixes and performance improvements.

Feel free to download the latest PC and Mac builds.

The significant new mechanic I mentioned above is "crew congestion". Essentially how it works is that, whenever two people are passing through each other in opposite directions, they will slow each other down. This is to emulate tight corridors where two people have to squeeze past each other to get by. But the people are smart, and they will try to avoid other people going in the opposite direction by taking a different route if they can. The result is that creating double-wide corridors or alternative paths can significantly increase the efficiency of your crew.

In the previous version of Starship Builder, a single person wanting to travel from point A to point B used a basic A* pathfinding algorithm to determine the shortest path from A to B, taking into account only the distance between points and travel speed (the rate at which the person can move through different parts of the ship, such as corridors vs thrusters).

In this new version, the A* algorithm is still used for pathfinding, but it also takes into account an estimated "congestion level" for each grid location. A grid location's congestion level is used to reduce the assumed speed at which the person can travel through that location. If the assumed speed is low enough, then the A* algorithm will naturally attempt to route around that location.

The way that congestion is estimated for grid locations is inspired by the way that ant colonies lay down scents to mark paths leading to food. After an ant finds a source of food, the ant will return to the colony, laying down a weak pheromone trail on its way back to the colony. This trail is a small suggestion for other ants to follow. Most ants won't follow, since the trail is very weak, but a few will, and when they find the food, they'll return, laying down more pheromone over top of the trail. As more and more pheromone is laid down, more and more ants will follow it to the food.

Congestion estimation in Starship Builder is inspired by these ant colonies, but it works in almost the exact opposite way. Whenever a person plans a path from point A to point B, a "virtual pheromone" is instantly applied to the entire path, but instead of persuading fellow crew to follow the path, it actually dissuades fellow crew from following the same path. The more virtual pheromone there is on any given grid location, the slower the "assumed speed" will be when the A* pathfinding algorithm runs. So the more people that travel along any given path, the more likely it will be for others to try to take a different path.