Westland Saga
Posted on January 22nd, 2018
A short Viking adventure filled with myth, magic and a little bit of pillaging.
(more…)
A short Viking adventure filled with myth, magic and a little bit of pillaging.
(more…)
I’ve been meaning to use virtual memory to manage game objects for quite some time. The idea of doing a copy on write to update an object while keeping a consistent readable version is still very tempting but I haven’t been able to work out the details just yet (or even if something like that makes sense). The next best thing is to have quick object allocations at predictable addresses.
(more…)
Recently I’ve finished writing a simple skeletal animation system for a, so far secret, project under development here. There are three parts to this system; the file formats, the exporter tool, and the code that actually does stuff with the animations.
(more…)
Say that one day you decide that you’re tired of of sending the (0, 0, 0, 1)
row vector to your GPU over and over again. The solution of course is to drop that row all together and use 3×4 matrices. (more…)
One of the secret projects currently in development here relies on TLS to maintain a secure connection with every player client. Because I am very excited about the project I didn’t plan too much and jumped in head first and started typing some code. (more…)
Say you want to draw a full screen quad in clip space. The straight forward way to do it is to draw two triangles to cover the viewport. But why waste two triangles when you can do the very same thing with just one?
Drawing a triangle with vertices a, b and c covers the entire screen. To interpolate a parameter across the quad so that it has values u0,v0 and u1,v1 at the opposite corners of the quad, set the parameter values on the three vertices as in the diagram above and in the table below.
Position | Parameter | |||
---|---|---|---|---|
x | y | u | v | |
a | -1 | 1 | u0 | v0 |
b | -1 | -3 | u0 | 2v1-v0 |
c | 3 | 1 | 2u1-u0 | v0 |
Up until recently I’ve been very good about using std::string for strings in all of my projects. In Kuiper 2 I decided that I wanted to try something different. String interning is a method of allocating strings such that there is only one instance of a particular string. For example:
// If all strings were interned then writing: const char *a = "Hello, world!"; const char *b = "Hello, world!"; // Then this would be true: if( a == b ) std::cout << "The strings are the same!" << std::endl;
The code segment above is meant as an illustration and won’t necessarily work as expected. It is possible to have the compiler combine all copies of identical string literals via “string pooling” using the /GF option in MSVC(I think GCC pools strings by default.) With pooling, the code above will work as expected but it only takes care of string literals. What about dynamically allocated strings?
To handle dynamic strings we will need to create our own string pool that will keep a unique copy of every string. Let’s keep the interface very simple:
// A wrapper around a const char *. This helps distinguish interned strings // from any other kind of string. class InternedString { const char *string_; public: InternedString() : string_( nullptr ) { } explicit InternedString( const char *string ) : string_( string ) { } const char *Data() const { return string_; } operator const char *() const { return string_; } bool operator ==( const InternedString &rhs ) const { return string_ == rhs.string_; } bool operator !=( const InternedString &rhs ) const { return string_ != rhs.string_; } }; // The string pool that will hold instances of interned strings. class Strings { class Impl; Impl *impl_; public: Strings(); ~Strings(); InternedString Internalize( const char *str ); };
Using this abstraction we will be able to write things like this:
Strings strings; InternedString a = strings.Internalize( "Hello, world!" ); InternedString b = strings.Internalize( "Hello, world!" ); // And this would be true. if( a == b ) std::cout << "The strings are the same!" << std::endl;
This is all neat and nice, but why would we want to do this?
Depending on your use-case there may be some benefits for interning strings. Here are some reasons why I decided to use interning in Kuiper 2:
Now for the dirty bit!
Essentially the string pool is nothing more than a set of strings where equality is determined by string equality. Internalizing a string involves a check to see if a copy of it is already in the set. If it’s in there we can just return a pointer to that string. If the string is not found then we have to make a copy, insert it into a set and return a pointer to the new copy. So let’s just write exactly that:
#include <cstring> #include <unordered_set>; // Hash for C strings. I think I got this from boost. class SimpleStringHash { public: size_t operator() ( const char *str ) const { size_t hash = 0; int c; while( c = *str++ ) hash = c + ( hash << 6 ) + ( hash << 16 ) - hash; return hash; } }; // Predicate for comparing strings by value. class StringPredicate { public: bool operator() ( const char *a, const char *b ) const { return a == b || strcmp( a, b ) == 0; } }; class Strings::Impl { // A customized unordered_set that compares and hashes elements as if // they were strings and not pointers. typedef std::unordered_set< const char *, SimpleStringHash, StringPredicate > StringSet; StringSet internalizedStrings_; public: ~Impl() { for( const char *str : internalizedStrings_ ) delete[] str; } InternedString Internalize( const char *str ) { if( str == nullptr ) return InternedString( nullptr ); StringSet::iterator i = internalizedStrings_.find( str ); if( i == internalizedStrings_.end() ) { // String not found so place it into the set. size_t length = strlen( str ); char *internalized = new char[ length + 1 ]; memcpy( internalized, str, length ); internalized[ length ] = '\0'; internalizedStrings_.insert( internalized ); return InternedString( internalized ); } return InternedString( *i ); } }; // Forward all calls to the PIMPL. Strings::Strings() : impl_( new Impl() ) { } Strings::~Strings() { delete impl_; } InternedString Strings::Internalize( const char *str ) { return impl_->Internalize( str ); }
That’s all there is to internalizing strings. In a future post I will talk about how to use a memory pool to keep all strings allocated in the same memory area.
In Kuiper the player’s ship has a trail of gems following it as it flies about. To achieve this effect we need two things. First, the position information of the player has to be collected every frame. Second, we need to be able to place objects evenly along an arbitrary path.
This part is pretty straight forward because all we need to do is store the player’s position in some sort of array or list. In Kuiper there is a queue that stores the historical position data. This works well as new positions are added to the back of the queue and old positions are popped off the front.
If the ship flew around on a plane or didn’t require interpolation, a list of positions would be sufficient. In Kuiper the ship flies around on the surface of a torus which is simulated by wrapping the player to the opposite side of the world when they fly out of bounds. Additionally the position of all the objects is smoothed for display in between physics updates. This can cause a problem during the frame that the player jumps to the opposite side of the world because the interpolation will make the ship appear to fly right across the screen! To remedy this we will also store the ship’s velocity at each frame and use it to calculate what the next, unwrapped, position should be for interpolation.
Here is the structure that goes into the queue:
struct HistoryPoint { glm::vec2 Position; glm::vec2 Velocity; HistoryPoint() { } HistoryPoint( const glm::vec2 &position, const glm::vec2 &velocity ) : Position( position ) , Velocity( velocity ) { } };
The math library I use is called GLM.
Given a history of positions and velocities we can figure out how to place objects along the player’s path. The idea is that we start from the beginning of the position history and take little steps until we get to the end. We keep track of the distance covered by the steps and every time it reaches a certain threshold we place an object there. Here is some code:
// The spacing parameter that will determine how far to walk until placing // the first object in the history. float spacing = parameters_.CrystalSpacing + parameters_.ShipSize; // Start from the most recent history sample. HistoryList::iterator i = positionHistory_.begin(); // Loop over all crystals that have been picked up. for( Entity &crystal : crystals_ ) { while( i != positionHistory_.end() ) { const glm::vec2 &p( i->Position ); const glm::vec2 &v( i->Velocity ); // This is the distance that that is traversed during the // frame of the history sample. float d = glm::length( v ) * dt; // If the spacing drops below 0 that means it's time to place // another object. if( spacing - d <= 0.f ) { // Entities are interpolated so we set the current position and the // position it will be at the next frame. crystal.Position = p; crystal.NextPosition = p + v * dt; // Reset the spacing and break to move on to the next crystal. spacing = 2.f * parameters_.CrystalSpacing - d; break; } // Take another step along the historical path. spacing -= d; ++i; } }
In the Point in Polygon Test post we used a Ray-Line Segment intersection test in order to figure out how many sides of the polygon intersected a test ray. This post will explain how that test was derived.
Find out if a ray with origin and direction
intersects a line segment with end points
and
.
This problem can be converted into a Ray-Ray intersection problem if you turn the line segment into a ray with origin and direction
but we are not going to do that. Well we are, but not explicitly.
Checking if two things intersect involves finding out if they share at least one common point. The first step is to express the ray and the line segment as sets of points.
In parametric form, the ray becomes
for
.
The line segment on the other hand is
for
.
Next we can set the two equations to be equal and find the values of
and
. Since there are two dimensions the equality can be split into the
and
counterparts and give us two equations to solve for the two unknowns. Once
and
are calculated the ray and the segment intersect if
and
. Under these conditions the point of intersection is on both the ray and the line segment.
The solution simplifies very neatly if you make some substitutions. Let ,
and
. Intuitively,
is just the direction perpendicular to
. The result:
The symmetry is pretty cool!