The World As Edges

The level geometry collision shapes are usually defined as different triangle collections that are organized in various natural and structural shapes and one thing that unifies them is that all that geometry has edges and you can categorize these edges.

With edges you can align traversal animations with handholds for grabbing the geometry.

In some of the earlier games I worked on the edge creation was done manually, users would have to tag each edge and there would be helpers in editors to highlight and find the edges but the last step of actually adding them was done by a user. Other systems like cover generation was also usually done manually. Only later after the designers had enough of a taste of that manual work would the voices be loud enough that such manual work would be unacceptable.

To analyze geometry you can iterate through all shapes in a level at build time or at runtime. 

The benefits for analyzing at build time is that you can do complex analysis of the shapes and all the edges and you don’t have to be super conscious about performance.

On the other hand the benefits of analyzing at runtime is that you can handle live editing of shapes and you can adjust the thresholds for the edge detection and the systems utilizing those edges.

The optimal solution for giving you all the benefits of a quick runtime and support for live editing and dynamic objects is to support both. The argument that often comes up when you’re building games makes it important to weigh both against each other and to consider the optimal solution against your timeline. It might turn out that doing something at runtime is a faster way to get started but you could easily end up in a situation where the performance is a hindrance and then you need to move it offline. 

In most engines there is a collision engine that allows you to find/iterate through collision geometry. That collision geometry is organized by some spatial partitioning system and it is generally quick to find geometry if you use bounds or overlap checks. In an offline build tool you can usually iterate through all the geometry of the level that you are working with.

In the runtime solution you can run a bounds overlap check at the position of the player and a certain distance around them to find all shapes that overlap.

Then from those shapes you take a few every frame to work on and make sure that they haven’t already been processed.

For each shape you can then go through all of their edges, with complex shapes you want to split the number of edges to process each frame.

For each face there is a number of edges and each of those edges can also be connected to another edge. Some of the edges can also have no connection and they will sometimes gain a connection by another piece of geometry being aligned to it. From this first pass each edge will be categorized as connected to another edge or unconnected (or invalid).

The first step is relatively simple and if you don’t need to care about one piece of collision geometry touching another or if the collision engine welds geometry together that is it. However if your levels come packed with lots of objects or if users can move geometry around to align with other pieces you will need another solution for merging edges between pieces of geometry.

What you can do here is create a lookup from shape to lists of edges and since those shapes are already organized in a spatial partition of some kind it is then just as quick to run another bounds overlap of each shape that is being added to check what is connected to it. Creating your own spatial organization for the edges can be more noise than it is worth, in that you will be adding and removing quite a few edges. However since you already have this organized in shapes you can then do quick analysis to check edges are inside a bounding box and then do the analysis to try and merge one shape with all already merged shapes.

To check if an edge is connected measuring the distance of the start and end with some small threshold can be enough. You also want to determine the face normal of each edge to determine what type of connection this is.

You can organized it in three different types : floor, corner and wall and then measure the angle difference between the two faces to determine if the edge is convex or not. 

For most use cases convex edges are what games care about. There are situations for surface analysis where the concave corners are also important.

This list of edges that was previously created is generally enough for most games with simple traversal and you can then also use some dynamic obstacle checks to verify that the edge is clear of obstacles.

However if you want to do something more complex like for example shimmying along a wall you also want to build a connection graph of edges. Solving this is important especially if you care about connections between different shapes.

The solution that you might come up with is a connectivity graph where each node in the graph is an edge with a start and end connection. Whenever you are adding an edge you again check nearby shapes and nearby edges and then look at the graph to see if those edges are connected to anything. An edge is connected if one of its points is a close distance to another and it can be considered connected if the direction of the edge is going in a similar direction of the edge that it is being connected to.

Another consideration that you need to be aware of is that edges can have their direction flipped compared to the edge that was being connected so for connectivity reasons each node needs to also be aware of if the edge was flipped in the connectivity analysis.

Since all those edges are connected to collision shapes we can simply do any type of spatial query that the collision system supports so we can do raycasts, shapecasts or shape overlaps to find the possible edges and then we can do tests against those edges and one that I like to use is a plane->segment intersection test that finds a point on the edge that you can align towards.