I decided to write small weekly updates on my progress towards a playable alpha version of Citybound. This first one will be quite modest, as I'm currently still very involved in my day job. Soon, my responsibilities there should become less, though.

What I did:

• Code cleanup and refactoring to allow for upcoming changes
• Complete rewrite of pathfinding
• First compatability testing on different PCs & Macs

Technical details of the new pathfinding method

Before, pathfinding was done using an all-pairs-shortest-path database that contained every possible shortest path in the city. Although lookup during runtime was very quick, it used a lot of memory, required a lengthy pre-computation step for large cities and was hard to update on-the-fly (for example when adding or removing roads).

Now, cars perform an A* search for pathfinding and the results are cached, so subsequent cars that drive a similar route can again just look-up a lot of existing information without doing a full path search themselves.

The effective difference in runtime compared to the old method is negligible and a lot less memory is required (only around 1/10 of all paths seem to be actually used by cars).

Also, there is no pre-computation step, you can react to changes in the road network much faster (cached paths expire after a customizable lifespan) and you can adjust the balance of memory vs. CPU load (by limiting the amount of cached paths).

What I'll probably do next:

• Pathfinding info view: show a single car's current path
• Road operations: remove roads, automatically create intersections for crossing roads
• Full camera control (mouse & keyboard)
• User interface for zoning