Convoy is a game mode in Vox Machinae in which 1 to 4 players co-operatively escort a convoy of 3 trucks from a start point to an end point. Along the way random side objectives will become available that grant rewards to players for the duration of the mission. If the convoy reaches the end point, the players have won the match. The match is lost if all 3 convoy trucks are destroyed.
The biggest hurdle to overcome during the development of the game mode was deciding where to go. It's not as simple as picking a start and end point. We also need to answer what route we take from A to B? Is that route fun? Is that route long enough?
As a programmer, it's hard not to think about this problem in terms of a node based graph. In this case, a directional node based graph. (see Screenshot)
Our graph will consist of nodes with the following properties.
A position vector representing where the node is in world space.
Bitflags for flagging a node as a Start, End, or Intermediate node. A node can be any combination of these.
Connections. These will be pointers to other nodes that can be traversed to from the owning node.
Important to note that for node connections to be bi-directional, two nodes must reference each other. It is important to have directional connections so that designers can markup levels with directionally contextual paths.
Once a level is marked up with the appropriate node graph, we can then run the following algorithm.
We begin by determining how long we want the path to be, and select a random start point from all nodes flagged as a start point in the graph.
We then use a Depth First Search (DFS) and begin traversing the graph picking random connections to un-visited nodes. The reason we are using DFS and not A* or Breadth First Search (BFS) is because we want to derive a random path. Not the shortest path. Note: anytime we derive a part of the path that creates a triangular shape, we can truncate the previous node from the path. (See top down screenshot)
We keep traversing until we build a path of appropriate length and ta'da. We're done. Except we'll have nonsensical paths that likely end up having the start next to the finish.
That was the first iteration. But to make better more sensible paths that cross through the center of the level, we need to make use of those Intermediate nodes.
Instead of using DFS, we'll use BFS. And we'll start by picking both a start and an end node that are roughly the distance we want to travel. We'll make sure these nodes are on mostly opposite sides of the level. Then we'll pick one or two intermediate nodes that run somewhat perpendicular to the direction of the start to end nodes.
Traversing the graph will begin at the start node. Whichever intermediate node we hit first becomes the first checkpoint. Begin traversing again from the intermediate node (never visiting nodes that are already part of the path) until we hit any other intermediate nodes that we've flagged, then finally to the end.
Picking only one intermediate point is also a good option, especially for highly vertical maps where two nearby intermediate points could result in a very long windy path.
This all generally results in a path that spends a bit of time in the center of the map on the way to an end point with a travel distance larger than what we asked for. (Which is why the distance variable should only be regarded as a 'suggestion')
Thankfully, in Vox these graphs are very small. Multiple paths are created, then compared against distance and "other factors", to pick the best one.
