Month: April 2014

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.

Mazer: Core Game

Posted on

After that previous Mazer post about breadth-first graph traversal, or as I put it: wavefront propagation, I got couple of people asking “how do you make a game out of that?”. So, I’d like to talk about how that works and the ideas I tried before I got there.

I wanted to make an action puzzle game. One that has short gameplay loops where the player achieves something every few seconds. I also wanted to make it as procedural as possible so I can avoid having to hand-craft levels and play-test them to verify they are achievable. In a way the game would need to generate a “level” and setup it up in a way that:

  • it’s playable – it doesn’t result in an impossible scenario where there is no winning move
  • challenging – challenges the player in-line with where they are on the difficulty curve
  • fair – not having a win-win strategy that the user can apply without solving the puzzle
  • it has a short game loop – user is presented a new puzzle every few seconds

 

Take 1: The One Tap Mechanic

My first idea was to make a game where the player would asses the playing field – the maze – then apply a single tap/click to make their move. They would watch the game unfold and get a win/lose result.

After thinking this through for a while I settled on a reverse “estimated time of arrival” mechanic. This involves:

  1. Game generates a maze
  2. Game selects 3 locations in the maze as exits. Each exit is numbered – 1 to 3.
  3. Player has to tap on location in the maze that would be the start point.
  4. A wave propagates through the maze from the start point and the exits need to be reached in order – that’s success.
  5. If the wave reaches an exit before it’s order has come that’s a fail.

I liked that idea. It required player to “solve the maze” with regards to the 3 exits and estimate the starting location. It required them to think before they acted. To make this a challenge I decided to add time pressure. Given infinite time anyone would be able to trace the mazes and the make the perfect move… if time is ticking down there is incentive to act quickly.

To satisfy my “it’s playable” condition I decided to get the game to select an start point and solve the maze using Dijkstra’s algorithm then record in what order were the random exits reached. That would guarantee that there is always a valid solution. In a way the game would play the maze behind the scenes and do a few calculations before presenting it as puzzle the user. This carried on to be a recurring theme in the final game.

Core loop FAIL screen.
Core loop FAIL screen.

At this point I had written zero lines of code for this game. It was all in my head and my paper notebook. It was still a Zombie Bus.

I set out to prototype. I wrote a maze generator. It was a simple maze generator that didn’t create any loops in the maze. Between any two points in the maze there was exactly one direct route and there were no isolated parts – no unreachable parts of the maze.

It was at this stage I realised this mechanic would have a win-win strategy. All the user had to do was tap/click very close to the first exit and given the “no-loops” generated maze the exits would usually be reached in the right order. I could still make this work by guaranteeing there would be loops in the maze and that exits are generated in a such a way that maze loop presented alternative routes between the exits and the start point… but that seemed like desperately holding onto idea that wouldn’t be able to provide generic game puzzles players can enjoy without considerable post-processing of those mazes.

Take 2: Tap The Exits In Order Mechanic

I decided to move on to and come up with different approach. I knew liked the idea of mazes, estimated time of arrival and self verifying maze puzzles. It wasn’t a big departure to switch the roles of the game and the player. The game would be generating the start point and the exits but now the user would be assigning the order. User would have to tap on the exits in the oder they would be reached from the the start point.

This also made the mechanic more presentable to the user. They now had to solve the maze 3 times (incrementally if they can) judging which exit would be reached first, second and so on. It was a lot more straightforward than the reverse-engineer of start point the first mechanic above.

Level up/Success screen.
Level up/Success screen.

This did mean that I would lose some of the speed in terms of game loop repetition. Players would have to tap multiple times now. It also opens the can of worms of user input. When is the player solution final? I didn’t want to a “confirm”/”GO” button in there so I decided to have the last exit seals the solution mechanic. However, if player had made a mistake prior to that last input they’d have a chance to change their mind so I had to implement a toggle on/off for exits to accommodate that – adding the fact that the player is assigning order it’s not the most clean of input mechanic.

An interesting scenario started cropping up. Often exits would be at the same distance from the start point – presenting player with a hard to judge but always correct puzzle for those two exits. I did have to tweak the generation and setup algorithms to run the solution in the background and record the distances at all proposed exits and chose ones which different in travel distance. 

Time Rewards

Another area of experimentation was (and still is) time reward per solved maze. Do I:

  • give the player 1 second for every maze solved? (+1 seconds for every maze)
  • give them 1 second for every exit they successfully reach? (+3 seconds for 3 exits)
  • give them 1,2,3 seconds for respective exits? (+6 seconds for 3 exits)

The last one turned out to be very generous and was quickly dismissed. I’m currently running the middle one but I am finding that game can go on to last for a bit too long for my liking. Plus the user gets more time through the bonus levels…

 

Bonus Levels

Yes, there is more to this game. Even though what I just described is the core game loop – really it’s that simple. There are bonus levels where other maze algorithms are involved and pickups are collected, there is the scoring mechanic… and much more.

Stay tuned and I’ll see you next time.

 

Tuturnions FTW!

Aside Posted on

Tuturnions

Ver. 1.0

Introduction

Quaternions have been around for some time now. Sometimes game programmers use them for rotations in graphics – after all they (quaternions) have lots of good properties. Programmers have good properties too. As it happens people use them without understanding them… but they work all the same – another good property of theirs. Quaternions too.

Anyway, we are not here to talk about quaternions as we already know about them and if you don’t, fear not, there is tons of info on the web and if you really care there are even books… now if you are hardcore enough you can go into some geometric algebra but that’s another story…

We are going to discuss Tuturnions. So what are they?

1. Tuturnions – they tuturn things

Let’s revisit the average quaternion definition (I mean, definition as the average programmer, me, defines it):

“Quaternions – they look like 4D vectors, you know, and they rotate things in 3D, and you can interpolate them, and they take less storage than 3×3 matrix, and they are easy to invert and so on”.

So couple of days ago I was doing some 2D stuff and thinking… well doing 2D stuff definitely, thinking – not so much, but anyway, it popped in my head – if we have these quaternions that can rotate stuff in 3D how come there aren’t any cool 2D rotating entities and I’m stuck with these 2×2 matrices[1]. So, without wasting my time with googling and internet and other spoilers like that, I put my wheel inventing hat on and there they were – Tuturnions.

Now, I’ve got to warn you, most of these things I’m going to talk about can actually be done with a 2×2 matrix (or are equivalent to it). But unless there is some secret society against ignoring 2×2 matrices when it comes to rotations we should be safe – come to think of it, I haven’t googled that either.

So, here’s the rules:

  • We want to be able to convert between our Tuturnions and 2×2 rotation matrices easily
  • Easy to keep the Tuturnion constrained so it can rotate stuff ( Quaternions need to be normalized to rotate stuff – right? )
  • Easy to perform operations on them – inversion, rotation concatenation, interpolation, etc

2. Tuturnions – the 2D quaternions

In 2D if we are given an angle, lets call it theta, we can rotate a vector using the following equations:

X’ = cos(theta)*X – sin(theta)*Y

Y’ = sin(theta)*X + cos(theta)*Y

And you can easily see how that translates to a 2×2 matrix. If you don’t, you either need glasses or you don’t understand how matrices work – another excellent reason to keep reading.

Looking at these equations we can see that really, there is only one quantity involved here when it comes to rotation – the angle theta. But obviously, everyone knows that sine and cosine are quite expensive operations[2] so we don’t really want to deal with just the angle. Also angle would be a bit tricky to interpolate continuously without some conditional statements.

But here is an idea: instead of using the angle we could use sin(theta) and cos(theta) instead – revolutionary isn’t it? So our Tuturionon will have two components called C and S. I’ll leave you guessing which one is which. Also, they do sound like they should have two components – two-turniouns.

Basically, in many respects, our Tuturion is a 2D vector. In order to represent a rotation though it needs to be normalized so if we have a Tu(c,s) following has to hold true:

C2 + S2 = 1

…and if you check your school math, like I did, you’ll remember that:

cos(theta)2 + sin(theta)2  = 1

You must admit our Tuturnions look more like 2D quaternions now. Though if we were to say they looked like unit 2D vectors[3] we would be a lot closer to the mark but quite boring to talk about them.

2.1 Interpolation

Interpolation of rotation entities is important, especially if you are doing animation system or you just want to have some fun.

2.1.1 Lerp

We can linearly interpolate a Tuturnion – it is a 2D vector after all. If you can’t interpolate a 2D vector I think you probably need to cover some more basic material first, though I admit, it might be challenging to find such material but if you got so far with this article it’s obvious that you like a challenge.

Anyway after we interpolate we need to re-normalise the Tuturnion, so it represents a rotation once again.

2.1.2 Slerp

We could also interpolate our Tuturnions using Slerp.

Yes, turns out Slerp is not really just for quaternions (Slurprised? Me too!) and we can apply it to everything in order to interpolate. Although it kind of beats me, if it wasn’t to do anything with 3D and quaternions, why on earth would someone call it spherical linear interpolation. After all the Slerp uses sine and cosine functions of the angle between the interpolated quantities and if anything should be called circular linear interpolation – Clerp.

Bottom line: you can use Clerp to interpolate tuturnions.

2.2 Conversion

This chapter seems to require a lot of 2×2 matrix visualization and my “word” skills are as advanced as my math skills. Short story long you have a sine and cosine (from your Tuturnion) and you already know how to make a 2×2 matrix from that, don’t you?

As for the 2×2 matrix to Tuturnion it should be clear by now, but if you want me to spell it for you: given a rotation matrix M you get equivalent tuturnion T(m11, m12)

2.3 Operations

Just like quaternions and rotation matrices you can perform numerous operations on a Tuturnion.

2.3.1 Rotate a 2D vector

In order to rotate a 2D vector V(x,y) by a Tuturnion denoted by T(c,s) you need to (replacing from the formula above):

x’ = c*x – s*y

y’ = c*y + s*x

Looks incredibly like these equations I showed you before and the reason for that is simple: “if it works – don’t fix it”.

2.3.2 Combine rotations

You need to simply multiply (transform) the two tuturnions. In essence the operation is the same as rotating a 2D vector but again our Tuturnion could be a 2D vector but that would be a wild guess.

In our example we have T1(c1,s1) and T2(c2,s2) we get the result T(cr, sr):

cr = c1*c2 – s1* s2

sr = c1*s1 + s2* c2

We could spend some time deriving that this is actually true but I’ve always found that part boring to read in articles and to be honest it looks boring to write as well. In fact I don’t see why people bother…

2.3.3 Inversion

When you work with rotations, it happens some times, you want to rotate stuff backwards. In order to do that you need to invert your rotation entity.

With Tuturnions this is quite easy – you just need to invert your tuturnion’s S part and there you are. It may come as a surprise to you (thought if it does you probably need to stop reading and consider going into politics instead), but if you look at your 2×2 rotation matrix and transpose it, because that’s how you invert it apparently, you can see how the sign changes place but then again that could be some weird coincidence.

We can go on and provide some proof by actually inverting the angle and checking what happens to the sine and cosine functions then. I’ll leave that an exercise to the reader, though believe me, going to the gym will be a far better exercise.

3 Applications and future work

If you are developing a 2D skeleton animation system you could find tuturnions useful. They will compress quite well, bearing in mind you can actually compress them pretty much in to a single entity.

3.1 Future work

Integrate a special quantity Q in the Tuturnion so they sound more complicated.

Conclusion

We have introduced new powerful rotation entities for 2D. They resemble quaternions in many ways (or at least one – they rotate things). They are easy to work with and they eliminate the need for 2×2 matrices when it comes to rotation – especially useful if you have “a thing” against matrices. They do have a cool name (that’s mainly what marketing is banking on) and they save a whooping 8 bytes if you use them instead of 2×2 matrix.

 

 

[1] That’s a long sentence, isn’t it?

[2] Well, you can approximate and some hardware supports them natively but where is the fun in that?

[3] It is important that when you are talking about Tuturnions you always use T(c,s) and not T(x,y).