Recent Posts

The biggest feature I've implemented into the game last year is asteroid obstacles. I wanted to add some variety to the battles since empty space offers limited tactical options. In order to make a difference, the asteroids would need to be either quite large or numerous so they form obstacles that need to be maneuvered around.

I set myself some ambitious goals:

  1. Support large asteroids with diameters of 1000 units or more (ship module grid squares are 1 unit).
  2. The asteroids must be able to move and rotate in the gameplay plane.
  3. The asteroid size, shape and look should have significant variety so they don't look copy pasted. They should also look somewhat realistic and generally interesting.
  4. Player and enemy ships need to be able to automatically navigate around the obstacles without collisions.

Graphics

The first goal already eliminates using simple 2D sprites as an option, since the texture resolution would need to be insane not to look very blurry or pixelated when zoomed in. The variety requirement also reinforces the need for a more elaborate solution. My solution was to use fully 3D rendered meshes with color and normal maps. This enables using dynamic lighting and having unique 3D rotation for each instance, which makes them look different enough. With random orientation, I would only need few different asteroid models. XNA provides tools for loading the models from common formats, but I had to implement custom logic and shaders to work with my deferred rendering and dynamic lighting system.

Asteroids of different shapes and sizes.

Rendering the asteroids as 3D models gives a sharp outline, but doesn't solve the problem of limited texture resolution by itself.  I bought a set of asteroid models with 4K resolution textures from Unity asset store, but even that is not nearly enough at close zoom. My solution to this is an old trick from game terrain texturing - blending in a separate tiling detail texture based on the zoom. I ended up using two levels of detail textures with their own normal maps. A tradeoff of this approach is that you will always lose some sharpness of the primary texture in the blending process. This is especially apparent when blending normal maps.

Pathfinding

Large obstacles require not only collision avoidance to keep the ships from breaking themselves, but also a proper pathfinding system to navigate around them. I first tried to add the 2D outlines of the asteroids in the calculations of the collision avoidance library I already have in place for ships, but its obstacle support seems to be geared toward static obstacles with simple geometry. Updating the obstacle data structure within the RVO collision avoidance library was too slow, but I could have worked around that with asynchronous update it if the avoidance calculations hadn't been too slow as well.

Without a solution in sight for collision avoidance, I started working on the navigation side of things. I figured that since the levels can be quite large and are likely to contain a fairly limited number of asteroids, it wouldn't make sense to use a basic uniform grid based navigation approach. A more modern and efficient approach to navigation is to maintain a navigation mesh of the level. This mesh can be used to find navigable paths for actors of different sizes, which is what I need since the ships can vary in size a lot. There are some nice navigation mesh generation and path finding libraries, but I concluded that integrating one could be a hassle. I also only need 2D navigation, but since I want to support moving and rotating asteroids, the navigation mesh needs to be fully dynamic.

I ended up making some simplifying assumptions in my implementation. The biggest one is that all obstacles need to be convex. The asteroids also have convex colliders in the physics engine since I didn't want to figure out a way to create a convex decomposition for the silhouette of a general 3D mesh. Limiting the obstacle shape to be convex makes things much easier for navigation, since offsetting  a convex shape doesn't produce self-intersections. This is important since navigating around an obstacle basically means following its shape at a certain minimum safe distance from the surface.

Generating the navigation mesh is a relatively simple but computationally expensive process, and it needs the radius of the navigating object as an input.
  1. Collect convex shapes of all obstacles in the level, transform to global coordinates.
  2. Enlarge all obstacle shapes by the navigating object's radius. Scaling won't produce correct result even with only convex shapes, a proper offset algorithm is needed. These new vertices will be your navigation points.
  3. Find and remove all navigation points where the navigating object wouldn't fit between the actual obstacles. This requires a lot of checks if a point is inside a shape. Luckily the Farseer physics engine I use had fast functions for this.
  4. Find out straight line navigability between all navigation points for an object of the given radius. I implemented this using the physics engine's raycasting functionality, by shooting two parallel rays at offset from the line between navigation points.
This process is way too heavy to do on-demand, since I want to support having up to a hundred or more small ships in battles. I chose to compromise accuracy by having the navigation mesh generation constantly running in its own background thread, calculating solutions for 2-3 different radiuses. One very important optimization in step 4 is a proven theory that shortest paths around obstacles will always follow the obstacle shapes and jump between obstacles tangentially. This is a very bad explanation, but in practice it allows reducing the point-to-point navigability calculation effort by something like 90%.

The picture below shows all generated navigable paths as gray lines, and a navigation solution from the red point to the green. The navigable paths depend on the radius of the navigating object, but can be reused to find navigation solutions between any two navigation points. To calculate a navigation solution between arbitrary points in the level, straight line navigability from the start and the end points to the existing navigation mesh need to be calculated first. After valid connections to the mesh are found, finding the optimal path is just a matter of a simple A* search.


I managed to make the actual navigation solution calculation asynchronous and thread-safe process as well. This allows running the navigation computations for multiple ships in parallel by using the .NET's task based parallelism that utilizes a thread pool. Since the navigation solutions don't need to be updated on every frame, the overall performance impact is actually quite manageable. Interestingly, performance worst case scenario with this kind of system is actually having many small asteroids scattered around the level, which leads to a very large number of navigable paths. Thankfully, large asteroids that obstruct each other is a more interesting setting from gameplay perspective.

Adding navigation support to the flight control system was bit of a pain by itself. The automatic flight system was quite complex already with multiple classes and somewhat independent logic constantly updating the movement target position. This was OK before, since changing the movement target was computationally very cheap, but updating the navigation solution on every frame is not feasible.

I ended up adding the navigation functionality into the most advanced WaypointFlightController class, which was previously only used for player's ships, and forcing all move-to-target commands to go through it. The current solution calculates path to the next waypoint only, and updates that solution on a timer about once a second or so. Constant obstacle movement and rotation is handled by retaining information about the parent obstacle in the waypoints, and always recalculating the global position of the navigation points based on the parent object's current position and orientation. Additionally, small changes to the source and target positions don't trigger recalculation of the whole navigation solution.

Remaining issues

Even with all the effort and clever solutions, the system is not without its flaws. There are few problems that aren't that easy to fix and so may linger for some time before I really get into them. Luckily, these don't have too much of a negative effect on general gameplay so my goals for this feature are pretty much met already.
  • No local collision avoidance. Because the proper collision avoidance was too heavy to use, currently the ships rely on the point-to-point flight control keeping them from crashing into the asteroids. This does not work very well in cases where ships try to avoid collisions with each other, or when chasing or fleeing enemies.
  • Navigation inside minimum offset distance of an obstacle. The raycasting method used for determining navigability between navigation points tends to break when the desired start or end points are inside the offset obstacle shapes. I have some workarounds in place for this, but it still sometimes results in the solution path jumping to a clearly sub-optimal navigation point and then finding its way to the target. In other cases a solution might not be found at all.
  • Camera clipping. The orthographic rendering along with very large asteroids cause near-plane clipping issues when zoomed in. My understanding of the clipping planes and Z-buffer is limited, so this might be quite solvable.
  • Z-buffer inaccuracy flicker. Rendering of large asteroids also suffers from some back facing triangles getting rendered in front of the correct ones. This happens at very specific zoom levels, but is is a very visible error because those triangles tend to get shaded very dark. For local lights to work I also need to render the Z position of pixels into a separate render target which, due to XNA buffer format limitations, has limited accuracy.
  • Asteroid silhouettes and the XY plane don't align. Since BFE is a 2D game, all action happens in the XY plane. However, the asteroids are rendered as true 3D geometries, where the edge pixels of the mesh can be at any Z height. The dynamic lighting is also calculated using proper 3D orientation and distance calculations. This causes confusing visuals with local lights, since a local light close to the apparent surface of the asteroid on the XY plane might actually be quite far from the surface in 3D.
  • Convex asteroid collision shapes. The asteroid models are not convex 3D shapes, so their silhouettes aren't convex 2D shapes either. Convex hull approximation of the asteroid silhouette is used in the physics engine and for navigation, which leads to the rendered edge of the asteroid sometimes being different from where collisions happen.

Posted by Tomi Monday, February 13, 2017

0 comments

Post a Comment