Path-finding in CrossCode news

The path finding algorithm of CrossCode was just recently developed, but works already fairly well. Overall, we’re pretty enthusiastic about the result. That’s why we’re happy to answer your requests to share some of the ideas and optimizations behind this new feature.

For starters, we have a short video demonstrating the overall performance of the path finding and the underlying data structures.

If you find those results convincing, here is how we did it:

Requirements on the path finding

Let’s first talk about what we wanted to achieve with path finding.

1. Entities should navigate to the target efficiently (close to shortest route), even in complex environment
2. Entities should be able to navigate over different height levels of the map. (e.g. jump on container, jump from one container to the other and down again)
3. The navigation should work in real-time and fast enough to be recalculated repeatedly.

The default solution to finding the optimal path to a target in an arbitrary complex environment is the A* search algorithm.

Optimized Navigation Map

The performance of the A* search algorithm heavily depends on the choice of graph structure it is applied on. We do not simply use a tile structure (e.g. the collision map) for this, mostly for performance reasons (one node per tile means a LOT of nodes). Instead, we created an optimized structure, which we call NavMaps. We already discussed these structures (and how they are created in the level editor) in a previous weekly report.
Nodes of our NavMaps cover multiple tiles and are connected with all adjacent nodes (called neighbor nodes). For each neighbor node, we also store all the edges where the nodes touch exactly. The perfect shape for a NavMap node is a large rectangle.
Here an up-to-date visualization of a NavMap in-game.

Performing the A* Search

To find out how the A* Search works in general simply check out the wiki article. We use the algorithm exactly as described on that page. There a just two functions that we should explain in more detail:

heuristic_cost_estimate(node, goal)This function should estimate the cost to go from node to goaldist_between(node1, node2)This function should compute the cost to travel from node1 to node2. Here is the important thing: At first we were lazy and simply implemented these functions my measuring the distance from the center of the nodes.

And here is why this doesn't work:

How do we reach our target (red point)? Simply go over node 5 and 8, right?

Wrong! By measuring the distance from the center of all the nodes, it seems shorter to take the path over node 6. This is obviously not the shortest path, though.

How to do it better: instead of measuring from the center of each node, we measure from the point on which we enter the node. We approximate this point by taking the average position of the edges between the nodes.

This way, the heuristic works much better with our NavMap structure.

Moving between nodes

With our A* search performed we get a list of nodes we need to traverse to get to our target. However, we’re not quite done yet. Since our nodes tend to be large and connected via multiple edges the next question is: How exactly do we go from one node to the other?

Our plan here is to go to our target (red point, again) crossing node 12. Going from node 6 to 12, we can choose among 3 edges to cross. Between node 12 and 15, we have exactly one very wide edge. So we need to determine two things:

1. On which edge between the nodes do we cross?
2. On which point on the edge to we cross?

The first approach we took: Let’s cross the edges on the point that is closest to the current position. However, this doesn’t work too well in this case:

The next idea: Cross edges and points closest to the target.

This works much better already, but still not that optimal. The best solution we found so far is to cross the edge and point closest to the line between the current position and the target:

This option provides the path closest to the optimal solution (which is the straight line to the target). In case you wonder why we always cross orthogonally over edges: this makes the path finding more stable for complex routes.

Moving over multiple levels

As we mentioned before, an important requirement for our path finding is navigation over multiple heights. Entities can jump on higher platforms, from one platform to another and fall down. All these options should be considered in our path finding as well.

You might have noticed that jumping for the player in CrossCode is pretty much automatic: you just move toward an edge to fall down or jump to another platform, or you move toward a wall to jump up. Using such an automatic jumping system makes path finding with jumping fairly simple: we only need to find a path that leads the entity toward the right walls and edges – the jumping happens automatically.

To make all this work, we first need to expand our NavMap to all height levels. Let’s start with the ground level:

Here we specify nodes only for the ground level, ignoring the top of the containers. We connect those nodes to the upper level, by mapping arrow symbols next to them. We obviously do this only where it is possible to jump up (e.g. nearby conveniently places cardboard boxes). Edges touching the arrow symbols are stored as “jump-up-edges” (visible in white) and connect to nodes of the upper level.

And here we have the NavMap of the upper layer, where we do not only specified nodes on top of containers, but also on the empty space between containers – the space that can be crossed by jumping. The nodes over empty space are called AirNodes and are handled a bit differently from normal nodes. We ignore AirNodes during the A* Search. Instead, we connect all neighbours of an AirNode directly with each other, storing additional information such as jump distance. That way, we can correctly decide, if an entity can actually cross an AirNode by jumping (not all entities will be able to jump the same distance).
As for all the white edges that you see on the right half: this time they are “jump-down-edges” that lead back to the lower level. Those edges are computed automatically and don’t require any special tiles.

Let's jump!

Now we got our NavMap extended to all levels. The Path-Finding algorithm is exactly the same as before, it only includes the nodes of all levels. So let’s say we want our protagonist to move to a target (red point) on top of a container like so:

Running the same algorithm as before we get the following path:

Note that the dark red line shows the path on ground level (we really don’t consider height for the path-finding at all). The lighter red line is the path correctly mapped to the upper level.

And this works! By simply moving across the lower white edge we jump up the container, moving across AirNode 19, leading us to jump all the way to our target.

Obviously our AI-controlled mouse friend can now do exactly the same:

Oh the wonders of technology!

Ups!

This concludes our technical post about path finding. I hope some of you can take a few good ideas from that. There are obviously a lot of more details to be considered, but this pretty much covers the basic algorithm.

Any feedback or questions? Comments are below as usual!