top of page
  • Discord
  • Youtube
  • X
  • Patreon
  • Reddit
  • Facebook
  • Writer's pictureGreygoo

SSS#4: Removing Zigzagging for Settlers: The Efforts Invested and Yet to Come(Part 3)

Updated: Apr 9

Although we have achieved some good feats by implementing a physics engine in our game (such as steering settlers), there is still much to be done for casual players to fully enjoy these in their gameplay. Today, we will discuss some challenges and potentials we may have in future development and what they mean for the game with the addition of a physics engine.

1. Navigation: For grid-based entity positioning, it is relatively straightforward to develop a navigation solution. The grid is a natural graph which mathematicians and computer scientists have spent much time analyzing. Finding a path in a reasonable amount of time between two nodes is one of the most studied problems. However, things become more complex if entities are allowed to stop between two tiles. It may seem that the graph approach is no longer feasible since it would imply we would need an infinite number of nodes for the entity to stop on. Fortunately, we can still use the graph by employing the correct abstraction for the node. In the navmesh that the majority of the gaming industry uses, each convex polygon represents a node in the graph. The reason for using convex polygons is that any point in a convex polygon can reach another point in a straight line without entering another node. Finding a path between two points is first done at the polygon level, and then, if a list of polygons is found, an algorithm is used to find a smooth path between points. Surprisingly, navmesh is often less expensive than a grid map due to the number of nodes needed to cover an area in a tile-based game. Navmesh can often combine multiple tiles (or an equivalent amount of area) into the same node, while a grid map must use one node per tile. Thus, choosing the right abstraction for the problem is key. In our case, since we want our entity to improve over Timber and Stone's zigzagging while maintaining good performance and allowing us to scale with the large map size, we must use a clever approach to abstract our search graph. This often requires taking spatial context into account, such as combining space in a room into nodes or a road into nodes, while providing dynamic changes to the graph. From the surface, it may still appear as a tile game, but we have to be smart about navigation to achieve what we promised.

2. Large World: We use a clever approach for storing the physical states of blocks in the physics engine, But we have not discussed dynamic and static entities much. It was mainly because performance does not scale well with the number of dynamic and static entities we want to place in the game. We always have thousands of entities for block chunks, and we need another 10,000+ for static entities. Unfortunately, there is some single-threaded overhead associated for each entity. One solution is partitioning the active simulated world into multiple zones, with one instance of the physics engine for each zone. There is additional complexity where you need to duplicate entities in multiple zones and resolve conflicts, but this allows the simulation to scale across multiple cores.

3. Multiplayer: Network synchronization is a difficult problem, especially when we have a large world, and it is not feasible for every client to simulate every object in the game world. At the end of the day, it would probably require some kind of partitioning between multiple clients while synchronizing as little data as possible for each entities.

4. IK Systems: We can pass additional physics information into the animation system to allow for better foot placement for settlers and other characters. However, this will be a low priority for us to implement.

While many difficulties and problems still lie ahead, we will be addressing them one by one in future posts while commited to push the boundary of the game to offer a captivating experience.

36 views0 comments
bottom of page