The 1D Radial Height Field

Posted on

It is common in games to use a generic, complex and powerful system to solve a small simple problem. There are many reasons for that:

  • developer is familiar with the system/tool – familiarity – we work faster with the tools we know how to use!
  • it’s available and needs no additional work – reuse – saving effort and money!
  • seems like the right “realistic” way to solve the problem – stay grounded
  • will solve the problem in all possible scenarios that would happen – be robust

All good reasons and I’m sure there are more. To illustrate this let’s take game physics and collision detection – often such a system in games. They can:

  • check for “line-of-sight”
  • use custom colliders (invisible walls) to solve game play problems
  • use it to ensure camera doesn’t get in a place where it won’t provide useful view to the player

These sound so common and natural. They are now standard uses of these systems in games and many people often wouldn’t think twice if they had to solve one of the above problems. I’m sure you can find other countless examples.

However…

… I want to talk about using a custom solution to solve a problem that would otherwise be solved by a generic system. In Mazer that would be the camera control and not letting it get in a place where random geometry would obscure the player’s view.

Using custom solution for camera control in Mazer. The line describes the area of safe camera movement.
Using custom solution for camera control in Mazer. The line describes the area of safe camera movement.

In Mazer the camera always looks at the top of the maze tower the player is constructing and is surrounded by other “leaderboard” towers. The camera position however is procedurally and programatically controlled to be “interesting” and “cool” with the music and gameplay. It can happen that the camera would intersect with surrounding towers obscuring the player’s view and rendering the game unplayable.

Simple brute-force solution to this problem would be to construct a camera frustum and check all surrounding towers for intersection. Easy enough to implement that solution has one major problem – it only provides us with the information that something bad has happened but not with the information needed to resolve the situation.

Next, more elaborate algorithms can be involved where we can have objects be physical entities (rigid-bodies) and just let them collide and slide against each other – never to intersect and get the player in trouble. That would solve the problem and perhaps look good too – one can never be sure before it’s implemented. However, it would be like using a massive hammer to hit a tiny nail.

The solution I use in Mazer uses a more simplistic yet robust approach. It is based on the knowledge that the camera is not completely free and there are various constraints that allow us to solve that problem in a different/targeted way.

Height Field (1D)

First a small detour into height fields. A height field is a scalar field of heights. Quite often you’d see that as a terrain representation where given 2D coordinates you can get the height of the terrain at that point.

hf_p1_1
Fig 1. Height field function using data control points.

A simpler form of this is a 1D height field. In essence that is just a function where given one coordinate “x” and evaluating the height field function h(x) you can get the height (or “y” coordinate).

This can be achieved with a polynomial of some fashion. For example f(x) = 2*x – x*x. That way we have a continuos solution and a known function that gives us a value at every (most) values of x.

However, if we have some data and we want our height function to match that data we can use an array of control points that specify the height at various values of “x” and an interpolation policy allowing the function to give a continuos result for any value of “x” (Figure 1). I find this to be a common scenario throughout development.

I’m using a linear interpolation here but a more complex methods of interpolation can provide a better (and higher order) continuity.

Height Field (1d) on a Circle 

Note: if anyone knows a better name for this method (there must be one), please let me know.

Now imagine we wrap the 1D height field over a circle. Now x is the angle in radians so any values outside the range of [0; 2*π] are equivalent to that range. So we need to define our h(x) just for that range.

If we have h(x) =0, our Circle Height Field will be just a dot. If we have h(x) = 1, our field will be a circle with radius 1.

Fig 2. Data points plotted on a circle.
Fig 2. Data points plotted on a circle. Note: in a proper implementation drawing the straight lines would be curved with the circle curvature as the 1D line is wrapped around the circle.

Figure 2 illustrates how our 1D data points height field above translates to this idea. It is the same field with the same data points but now plotted on a circle.

In code, I often need to plot the circle height field so I can visualise it and troubleshoot problems with my code. To do so we need to get a 2D point for every value of x. Here’s how we do this:

Vector2 GetCircleHeightFieldPoint(float x)
{
   //calculate the unit vector at X angle
   Vector2 unit = Vector2(fcos(x), fsin(x));

   //get the height at X angle
   float h = HeightFieldFunction(x);

   //combine them to get the point on our circle height field at that angle
   return unit*h;
}

By iterating a number of  values of “x” in the range of [0; 2*π] we can get a full representation of the radial height field. All images below (screens from Mazer) use this method to visualise the field.

Camera  Control

How is that relevant to camera control?

Mazer screen with a radial height field.
Mazer screen with a radial height field used for camera control.

I calculate the area the camera can go without getting the user in trouble. I start with and empty height field function h(x) and then I plot, in the height field, all the obstacles that can obscure the camera view. In my case each obstacle is a box. Once projected on a circle it becomes a curve segment that I have to draw (project) on my h(x). There is more information about this process below.

Once I complete that I have a h(x) that gives me the maximum distance (height) the camera can be in at every angle. If I keep the camera within that limit I know I won’t get any visual problems. Even more, if I find that the camera has strayed into an area that is “not good”, I can immediately take remedial action in the right direction or quickly evaluate many other potential points the camera can go very cheaply.

For now I’ll just show a simple method that limits the camera within that height-field – if it goes beyond it, it limits the camera to the maximum distance.

Vector2 LimitCameraPosition(Vector2 cameraPosition)
{
   //get the "height" the current camera position is at 
   float height = length(cameraPosition);

   //normalise to get the unit vector
   Vector2 unit = normalise(cameraPosition);

   //convert to angle representation
   float angle = UnitToAngle(unit);

   //look up the height function to get the max height at that angle
   float maxHeight = HeightFieldFunction(angle);

   //limit the distance to that max height
   if (height > maxHeight)
   {
      return unit*maxHeight;
   } 

   return cameraPosition; 
}

In the code above there is a function to convert from a unit vector to an angle scalar (in radians). While that’s trivial using an atan2 function from the standard library, you have to remember to wrap that around and keep the angle in the range of  [0; 2*π].

float UnitToAngle(const Vector2& unit)
{
   //get angle
   float ang =  atan2(unit.y, unit.x);
   
   //keep it in the range 
   if (ang < 0.0f)
        ang += PI*2.0f;
    
   return ang;
}

Obstacle Drawing: Preparing a Useful Height Field

Mazer screen illustrating the "safe" camera field. Note how each box/column makes a dent into what is otherwise a perfect circle.
Mazer screen illustrating the “safe” camera field. Note how each box/column makes a dent into what is otherwise a perfect circle.

Now that we have the basics of our radial height field for camera movement we need a method to insert useful data in it. The method I use is to initalise the field to some default maximum value – at that point it’s just a circle with radius of “maximum value”.

Then I “draw” various obstacles that in-turn would “dent” the circle and make the function non uniform. In the Mazer case the obstacles are the “score” boxes.

For each box I find the bonding circle of that box in 2D and then from the centre and radius of that bound sphere I find two points determining the extents (in the height field circle) of the arc that it would take. Then I step through the line segment those two points define intersecting a ray (starting at the origin and pointing towards the step point on the segment) with the box obstacle itself.

Then I check if the distance to the intersection point is less than the distance stored in the closest control point in the field function and write it in. In a way this acts as a 1D circular depth-buffer.

Finally I do a low pass filter on the data (field) so that all edges are smooth and provide a more gradual response when I use it for camera control.

Performance

I look up the constructed field multiple times a frame. However that would be only for certain values of “x”.

Most performance hit is taken when I’m constructing the field and rasterising the obstacles in it. Right now I do that every frame and it has a resolution of 128 control points for the whole range of  [0; 2*π]. That gives me a good resolution for quality camera control and I haven’t seen any visible performance impact.

Other Applications

I’m sure this method has it’s applications in game AI. I know I’ve seen this visualised before in games (or debug information in games) and that’s how I got to know about it. I can think of AI agents using it to plot a 360 degree of threat so the AI can reason about the best course of action for that agent. Or maybe representing the audio “hearing” of the AI agent so it can reason about where the sounds are coming from and how to react.

This approach also shares similar ground with the “context maps” described in this post by @tenpn http://andrewfray.wordpress.com/2013/03/26/context-behaviours-know-how-to-share/

That’s it for now. See you next time.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s