Game Physics: Broadphase – Overview

This post is part of my Game Physics Series.

As mentioned in this introductory post, a broadphase is the algorithm of choice to efficiently decide whether it is possible for two colliders to collide, without using the actual collision detection algorithm that is more expensive.

Typically, a broadphase keeps track of bounding volumes, usually AABBs, of all colliders. The broadphase produces a list of collider pairs whose AABBs are colliding. These collider pairs are then passed on to the collision detection algorithm to decide whether they actually collide.

Continue reading

Posted in Gamedev, Physics | 6 Comments

Game Physics: Motion Dynamics Implementations

This post is part of my Game Physics Series.

This post presents possible implementations of motion dynamics for a physics engine. For fundamentals of motion dynamics, please refer to this post.

Rigid Body Interface

Below is what a typical rigid body partial interface would look like (there’s more that is not shown). Note that the data format of choice here for orientation is a 3-by-3 matrix. Also present in the data member list are inverse mass, local & global inverse inertia tensors, and inverse orientation. These inverse properties would be used quite frequently during force/torque application, collision detection, and resolution; thus, it is a good idea to compute and store them per time step.

If the name of a property does not indicate whether it is in world space (global) or model space (local), it is in world space. The reason why some properties have both global and local version would become apparent later.

Continue reading

Posted in Gamedev, Physics | 15 Comments

Game Physics: Motion Dynamics Fundamentals

This post is part of my Game Physics Series.

Before delving deep into the programming aspect of physics engines,  I would like to first go over the fundamentals of motion dynamics. Unless specified otherwise, all discussion is in 3D. Also, when it comes to formula consisting of vectors and matrices, all vectors are considered to be column vectors.

Continue reading

Posted in Gamedev, Physics | 2 Comments

Game Physics: Introduction & Acknowledgements

This post is part of my Game Physics Series.

I shifted from being the graphics programmer to being the physics programmer for my DigiPen game team half a year ago as we started developing our junior project. Knowledge on game physics is considered “tribal knowledge”, in that there is no formal book or publication that covers every aspect of it; also, cutting-edge information is typically passed down through online articles, forum discussions, and gamedev community activities such as GDC lectures.

I felt like beginning tagging along this tradition and decided to start a game physics series on my blog, sharing what I have learned and perhaps my own thoughts as I carry on studying game physics. In this very first post of the series, I will go through what constitutes a constraint-based rigid body physics engine. Details on individual topics will be covered in future posts.

Continue reading

Posted in Gamedev, Physics | 7 Comments

Intrusively Linked Lists with Safe Link Destruction

This post is part of my Game Programming Series.

My current game project at DigiPen greatly benefits from “smart” intrusively linked lists that support multiple links per object and automatic link removal from lists upon destruction. My implementation was inspired by Patrick Wyatt’s implementation and Randy Gaul‘s implementation. Randy showed me both implementations.

The implementation I’m going to present here is probably not the most efficient, but it is STL-compatible in terms of iterators, and it can be used with the ranged-based for loop introduced in C++11. Such implementation has turned out to be very convenient while writing client code, and has never become a performance bottleneck for me.

Traditional V.S. Intrusively Linked Lists

First, let’s go over a quick overview of intrusively linked list and its comparison with traditional linked lists.

Below is a very straightforward implementation of a traditional doubly linked list node:

template <typename T>
struct ListNode
{
  ListNode *prev, *next;
  T data;
};

A link to the previous node, and link to the next node, and the data, simple. However, this implementation breaks down when we want to have the same data in multiple linked lists. This is a very common situation in a game engine; for instance, game objects are kept in a main game object list, as well as in a “to-be-destroyed” list that contains game objects that are marked for destruction at the end of current frame, so that we don’t have to loop through the (possibly very long) main list for a second time to check which game objects are marked for destruction at the end of each frame.

A fix to this problem using the traditional linked list is to make the node data a pointer, which points to the real data.

template <typename T>
{
  ListNode *prev, *next;
  T *data;
};

This brings up another problem: we can’t perform a constant-time node removal just by giving the data pointer to all the lists that contain it, because the actual data object and the nodes are de-coupled. Also, when the data is deleted from memory, we have to know which lists contain pointers to this data and remove the corresponding nodes beforehand. Too much bookkeeping. Yuck.

The solution to these problems is, you guessed it, intrusively linked lists.

Continue reading

Posted in C/C++, Gamedev | 5 Comments

Game Math: “Cross Product” of 2D Vectors

This post is part of my Game Math Series.

Cross Product in…2D?

So, the cross product of two 3D vectors is a 3D vector, which is in the direciton of the axis of rotation for rotating the first vector to match the direction of the second vector, with the smallest angle of rotation (always less than 180 degrees). What does “cross product” of 2D vectors mean, then?

I like to think of the “cross product” of two 2D vectors as a scalar, not a vector. How does this work? Basically, treat the 2D vectors like 3D vectors with their z-components equal to zeros, take their cross product, and the final result is the z-component of the cross product. Here’s what the implementation in C++ looks like:

// not the most efficient implementation
float cross(const Vec2 &a, const Vec2 &b)
{
  Vec3 v1(a.x, a.y, 0.0f);
  Vec3 v2(b.x, b.y, 0.0f);

  return cross(v1, v2).z;
}

Since the z-components of the 3D vectors built from 2D ones are zeros, the x-component and y-component of the 3D cross product are zeros. Thus, we can further optimize the implementation:

float cross(const Vec2 &a, const Vec2 &b)
{
  // just calculate the z-component
  return a.x * b.y - a.y * b.x;
}

What’s So Special About It?

Now we’ve see what the cross product of 2D vectors is mathematically, but what does it mean geometrically? As mentioned before, the cross product of two 3D vectors gives you a rotation axis to rotate first vector to match the direction of the second. We’re just extending the 2D space into 3D and perform the cross product, where the two vectors lie on the X-Y plane. The resulting 3D vector is just a rotation axis. However, since the two vectors are on the X-Y plane, this rotation axis would cause rotation only on the X-Y plane, so the axis is always parallel to the Z-axis.

If we reduce our dimension from 3D back to 2D, the rotation axis represents a rotation that is either clockwise (CW) or counter-clockwise (CCW). In other words, The sign of the 2D cross product tells you whether the second vector is on the left or right side of the first vector (the direction of the first vector being front). The absolute value of the 2D cross product is the sine of the angle in between the two vectors, so taking the arc sine of it would give you the angle in radians.

I used cross products of 2D vectors in Astrobunny (my first DigiPen freshmen game project), to decide whether the mouse cursor is on the left or right of the ship and determine which direction to steer.

Posted in Gamedev, Math | 9 Comments

Bending Solid Geometry in Planetary Annihilation

This post is part of My Career Series.

Two months ago, I started my internship at Uber Entertainment to work on Planetary Annihilation, which is currently in closed Alpha (you can still purchase Early Alpha Access into the game through Uber Store or Steam). Many people on the development team have worked on Total Annihilation and Supreme Commander, and you can see the similarities Planetary Annihilation share with these two games.

Planetary Annihilation is a next-gen real-time strategy game on a planetary scale, where players fight across multiple planets. Here’s the alpha release trailer that shows off Planetary Annihilation’s unprecedented epicness.

For the first 6 weeks of the internship, I spent most of my time on the in-game planetary camera and celestial camera. Recently I’ve moved on to polishing the procedural planet generation. My latest work that is worth mentioning is the bending of solid geometry.

Continue reading

Posted in Gamedev, Math, Programming | 20 Comments

Memory Management part 3 of 3: STL-Compatible Allocators

This post is part of my Memory Management Series.

In part 1 and part 2 of this series, I showed how to implement a fix-sized memory allocator and a C-style interface. Part 3 will demonstrate how to make an allocator that is compatible with STL containers.

STL Compatibility?

You probably have used various STL containers in C++, like vectors and lists:

std::vector<int> myVector;
myVector.push_back(1);
myVector.push_back(2);
myVector.push_back(3);

std::list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);

But do you know that these STL containers actually take a second template argument?

The second argument is for you to specify a custom memory allocator type that you’d like the containers to use. By default, the std::allocator class template is used, which is simply a wrapper around malloc and free. If we can crate an allocator class that conforms to the STL allocator interface, we can tell STL containers to use our allocator instead of the default one.

Continue reading

Posted in C/C++, Gamedev | 1 Comment

Memory Management part 2 of 3: C-Style Interface

This post is part of my Memory Management Series.

In part 1 of this series I showed how to implement a memory allocator that allocates fix-sized pages and blocks. Part 2 is going to cover how to implement a C-style interface like malloc and free that can deal with variable-sized memory allocation using this allocator. In the end, I’ll also show a way to add syntactic sugar by creating C++ function templates.

The C-Style Interface

So far, our allocator can only allocate fix-sized pages and blocks. Therefore, we need at least one individual allocator object for one specific block size. So how are we going to deal with variable-sized memory allocation? Well, we are not going to modify the allocator. Instead, we’re going to have a collection of allocators that allocate a wide range of different-sized memory blocks, and we will also build a look-up table to efficiently determine which allocator to use based on the memory block size requested by the client. This look-up table approach was inspired by a Randy Gaul, one of my classmates at DigiPen. You can check out his implementation here: header / source.

This is the interface we will be implementing:

Continue reading

Posted in C/C++, Gamedev | Leave a comment

Memory Management part 1 of 3: The Allocator

This post is part of my Memory Management Series.

Why Bother Building Your Own Memory Management System?

Memory management is crucial for game development. It is even more important for console game development, since consoles have hard memory limits. Many game developers rely on garbage collectors that come with some programming languages. As convenient as garbage collectors are, their behavior is not consistent and not always reliable. Perhaps one out of a hundred garbage collection cycle, the garbage collector needs to do a big clean up, so it drags a couple of frames down to 10fps. Very likely, you cannot foresee this performance hit; you game runs smoothly most of the time, but every now and then there’s a little lag. It’s playable, and the players might be fine with the sporadic lags; however, in order to perfect the player’s overall experience, you should aim for eliminating every possible performance hit.

Building your own memory management system is one improvement you can do.

In order to build a custom memory management system, a language that allows raw memory access is needed. Languages that come with built-in garbage collectors and do not allow low-level memory access are out of the question. Lots of PC games and most console games are developed in C++, and that is what I’m going to use here.

Part 1 of this series is going to cover the fix-sized memory allocator, the foundation the rest of the series is built upon. In part 2, I will show how to use the allocator to implement a C-style interface that supports variable-sized memory allocation, as well as create C++ function templates for syntactic sugar. Finally, part 3 is going to cover an allocator implementation that is compatible with STL containers.

Continue reading

Posted in C/C++, Gamedev | 5 Comments