This Week In Veloren 45

This week, we get a glance at some of the ideas behind pathfinding, both at a macro and micro level. We also see optimizations to networking, as well as the current state of the design working group. Also, a new edition of "This Month in Rust GameDev" has come out!

- AngelOnFira, TWiV Editor

Contributor Work

Thanks to this week's contributors, @Acrimon, @Shandley, @Adam, @Songtronix and @Treeco!

@Acrimon is working on the underlying message system for networking. Optimizations to this will improve the connection from the client to the server. @chrischrischris has been working on pathfinding and has significant progress on prototypes.

The design working group put the topic of conditions on temporary hold for now, since they should have enough to start designing skill trees for the combat system. You can check out the WIP formal document on conditions and status effects, as well as the preliminary steps. @danach has been working on the definitions for biomes, and you can see that document here.

Pathfinding by @chrischrischris

One of the major goals in Veloren is to create a world that feels alive and dynamic and to provide a sort of simulated world over time. A major component of this world will be cities and civilizations which interact with each other. To provide this experience, an essential component is for entities to be able to travel and explore.

Think of trading caravans being able to navigate long roads between cities, guards patrolling castle gates, and villagers walking from their homes to the market. The first step to making this a reality is adding intelligent pathfinding. For Veloren's pathfinding implementation, we wanted to focus on modularity and reusability. There are three major components:

1: A*

A generic A* algorithm which knows nothing about the world, but does know how to find the shortest path in an abstract graph. For people not familiar with the algorithm, its goal is to be given a graph and a heuristic and find a short path without having to scan the entire graph. To learn more about it, check out this excellent reference on Red Blob Games.

2: Translation To World

The block pathfinding component which connects the A algorithm above and blocks in the world. Its job is to use the ReadVol API to transform coordinates in the world to a graph that A can use.

3: Macro Scale

This is a chunk pathfinding component that connects #1 and #2. This exists to make the pathfinding more efficient across long distances. It works by partitioning the world up into chunks and ignoring large amounts of contiguous blocks that are non-traversable.

Imagine this scenario: A NPC is trying to find a path from one civilization to another across a large distance, with an ocean in between the two cities. There is a bridge connecting the two cities right in the middle of the ocean. If we only use a block pathfinding algorithm, then we look at every block in the ocean until we find the bridge.

However, with this system, we can instead look at chunks of blocks. If there were 500 blocks of ocean and then the bridge, and the chunk size was 100, then we would only have to look at 5 chunks of ocean before finding the bridge instead of 500. This macro-scale pathfinding is still in the works.

I am currently working on adding ray casting to detect if the path has become invalid. This can happen when blocks are placed and blocking off the old path, or explosions destroying terrain. My project partner is also working on making it hierarchical, by having NPCs create paths along chunks and then along blocks for more efficient pathfinding.