int main(void)
{

My Blog

Posted 02/17/12 @ 11:09pm - By Ross

Interviews

Interview questions are the bane of my existence. Something about someone waiting on you to solve a problem causes me to second guess everything I do. However, I do find them interesting to think on after the interview is over. In a recent interview I was asked a question about removal of spaces from a string. My first take on the problem came up with the standard O(n2) version of the algorithm.

Here was my take on it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void TrimSpaces(char* word, int size)
{
  int ii, jj;

  for(ii = 0; ii < size;ii++)
  {
    if(word[ii] == ' ')
    {
      for(jj = ii; jj < size - 1; jj++)
      {
        word[jj] = word[jj + 1];
      }
      size--;
    }
  }
}

It’s a fairly straightforward implementation. Loop through and find each space and then shift over all the other characters in the string. In use it actually shouldn’t be too bad since spaces are typically less than half of the characters in a string. Regardless, it’s still not as efficient as it could be.

So as I laid in bed the other night a better solution occurred to me that can be done in linear time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void TrimSpaces(char* word, int size)
{
  int ii;
  int offset = 0;

  for(ii = 0; ii < size;ii++)
  {
    if(word[ii] == ' ')
    {
      offset++;
    }
    else
    {
      word[ii - offset] = word[ii];
    }
  }
}

In going through the string we simply keep track of how many spaces we have, then we know how much to shift the string as we go.

Another possibility is the allocation of a new string and copying over all characters except for spaces. This works well if you must preserve the original string. However, if you are merely editing the string an in place solution is superior.

Posted 02/15/12 @ 5:13pm - By Ross

Dashed Lines!

So I recently have been playing around with shaders on my Android project and with the removal ofĀ stippling from the OpenGL I thought that I had found the perfect opportunity to use a shader. With some thoughts in mind I decided to search the interwebs to see if I was thinking along the right lines. Unfortunately there isn’t much out there on OpenGL ES 2.0 yet. So it fell to me to come up with something that would work, and work it does!

The basic premise was pretty simple. Find out the world coordinates of each fragment and then, using that, determine it’s length from the line origin. Then plug that into a cosine function and alternate drawing it based off if the value returned is negative or positive.

The key to the whole thing is sourcePoint being passed in as the origin of the line. It’s also worth noting that I pass in the modelview matrix and multiply it with the vertex to determine where it is in world space. The use ofĀ positionĀ as aĀ varyingĀ variable is also important since it is interpolated based off all the vertices that affect it. This allows for theĀ positionĀ variable in the fragment shader to be the actual position of the fragment in world space.

With all this, I determine the distance between those two points and then use the cosine function (modified based off how I want the dashes to look) to decide to draw it or not.

So without further ado, here is my vertex shader:

1
2
3
4
5
6
7
8
9
10
11
12
uniform mat4 u_modelViewProjectionMatrix;
uniform mat4 mv;
attribute vec4 a_position;
attribute vec4 a_color;
varying vec4 v_color;
varying vec4 position;

void main() {
  gl_Position = u_modelViewProjectionMatrix * a_position;
  position = mv * a_position;
  v_color = a_color;
}

and the fragment shader:

1
2
3
4
5
6
7
8
9
10
11
12
precision mediump float;
uniform vec2 sourcePoint;
varying vec4 v_color;
varying vec4 position;

void main() {
  if (cos(0.1*abs(distance(sourcePoint.xy, position.xy))) + 0.5 > 0.0) {
    gl_FragColor = vec4(0,0,0,0);
  } else {
    gl_FragColor = v_color;
  }
}
Posted 02/08/12 @ 3:31pm - By Ross

GLES2 conversion

The game I’m developing for Android utilizes an open source OpenGL library called AndEngine. I’ve been experimenting with it for about a year now and finally feel as though I’ve got a solid handle on it. But about a month ago I got thrown a curve ball. The core got a huge update as they converted it to support OpenGL ES 2.0. While this is great as it increases it’s functionality, there is a whole new slew of relearning I had to do.

So what changed? First off, the use of a VertexBuffer manager that is now referenced on all drawn objects. This obviously follows from the other big benefit of going to ES 2.0, programmable shaders! I haven’t yet played around with writing my own GLSL programs as I’ve been updating my code to work with the new update, but it’s high on my list to see what it can do. Another nice change is the division of extensions out of the main library. The library itself was starting to get bloated with the inclusion of things like the tmx file format and box2d physics.

The best thing about the conversion is I got a HUGE performance increase after the upgrade. Previously, zooming out all the way on the tmx map would drop frame rates down to the teens. Now it rarely dips below 50. This is credited to big improvements with tmx handling and the A* path generation along with better hardware use.

Another nice side effect is I’ve been going through and rewriting a lot of my code to clean it up. This project started during my junior year in college and there were many mistakes to be found. Not to say it’s now perfect, but it is much better than what it was.

Posted 01/08/12 @ 12:57am - By Ross

Balancing Act

For those that haven’t been following theĀ competitiveĀ gaming scene, there has been a big surge in the last year or two. So much so that esports, as it is known, has started generating some big money. Two games in particular seem to be drawing the biggest crowd (and most of my attention). These two games are League of Legends and Starcraft II.

What I find unique about each game is that they seem to take a much different approach to achieving a balanced gameplay system. Starcraft II, as with the original, is a tightly knit balance between each of its three races. Zerg plays aggressive and relies on numbers for an advantage, Protoss relies on the strength of its units to crush the opponents, and Terran has versatility to adapt and slowly take control of the map. The races are themed and units are set (at least until the expansion) with small tweaks as needed. It’s a fragile arrangement that requires meticulous and somewhat timid changes to the system.

League of Legends, on the other hand, seems to take the opposite approach. Releasing champions every few weeks and potentially changing the game dramatically. This is not to say that Riot (the developer of League of Legends) is careless, simply that they take a different approach. Relying on the frequent changes allows for the game to stay fresh and new strategies to constantly evolve.

The reason I find the difference so interesting is that both seem to be working. Starcraft II has seen great success across the world and League of Legends has grown tremendously since its first MLG appearance. I find this to be a compelling example of two different trains of thought providing equal success. I take it as a lesson that you shouldn’t always force yourself to follow one path just because someone else has done it. Whats important is the feedback youĀ receiveĀ and the passion you put into your project.

Posted 01/04/12 @ 8:18pm - By Ross

Bring the noise

Well it started with my RoadBuilder class and my research into procedural generation. There was one thing I kept on seeing during my research and that was noise generation techniques. In particular, Perlin noise.

So what, you may ask, is Perlin noise? To answer this, we must first look at what noise is. Conceptually, noise can be thought of as random looking numbers that can be consistently generated based off input. Rereading that it sounds a little cryptic so think of it this way. If I give you a number, you can give me a random number that corresponds to that number. Here is a theoretical chart that would represent a input corresponding to an output:

1 : 22
2 : 8
3 : 34
4 : 3
5 : 16

An input of 1 would correspond to an output of 22, an input of 2 corresponds to an output of 8, etc. The output of this magic function appears to be random, but whenever you give me 1, you get 22 back. That magic function is a noise generating function. So the question of what that magic function might look like probably comes to mind, andĀ that’sĀ where we get into Perlin noise.

Disclaimer: This section contains
Math

(more…)

Posted 10/10/11 @ 2:43pm - By Ross

Diablo 3 bug on skeleton king

So while browsing the web today I ran across a video that displayed an interesting bug in Diablo 3. Take a look for yourself to see what I’m talking about.

I got into the D3 beta several weeks ago thanks to a friend. Unfortunately the content currently available is pretty limited and I powered through it in about a week. Still, it’s interesting to see bugs like this crop up. In particular this bug interests me as I think I know the cause and the fix. Of course I have to preface this as a guess as I haven’t seen any code and am basing this solely offĀ intuition.

For those that don’t know, the beta ends at the skeleton king and you get a nice splash message informing you that you’ve completed the beta. About a week before I got into the beta there was an update saying that they changed that message to display after the skeleton kings death. Seems like a pretty innocent change as that message covered up a cool piece of animation. However, I think someone didn’t think it through all the way.

That splash screen was likely tied to the completion of the quest line. By changing it to appear after the animation (and loot drop) a bug was introduced where you can simply exit the game before the quest is registered as complete. This lets you come back and continue from the last waypoint (right outside the skeleton kings chambers).

This fix should be straight forward, just make the loot drop after the animation. How easy that is to change? good question. Another possible fix that might be even easier is to revert the change they made. That splash message won’t need to be displayed in retail so the change is really unneeded. Without more knowledge of the system it’s tough to determine the appropriate fix, but either are good starting points.

I find this particular instance of a bug interesting as I realized the cause almost immediately after reading about it. It’s rare that a bug is so simple (if I’m right), especially if you aren’tĀ familiarĀ with the system in question. Still, it’s a good example of how a bug can be introduced off a smallĀ aestheticĀ change that you might not expect to affect anything.

Posted 10/09/11 @ 6:09pm - By Ross

Ah, to be a noob again…

So for those that don’t know, I’m TA’ing for CptS 121 again this semester and enjoy it quite a bit. I’ve always had aĀ tenuousĀ relationship with school growing up so it almostĀ surprisesĀ me that I enjoy teaching so much. It’s strange to see the same mistakes I made being repeated by others and not being able to convince them that I know what I’m talking about. I think of Elrond from Lord of the Rings and how humanity just ignores his words of warning, despite his wisdom and experience. But I digress, TA’ing has been a good experience and I’ve learned a ton from it.

Speaking of which, I got an e-mail today from one of the students inquiring about game development. Naturally I wasĀ ecstatic to find someone else interested in the topic. I’ve met several people at WSU that talk about game development fondly, but rarely with substance. It’s ironic that I’m now the elder from which to seek knowledge when I feel like I’ve barely stepped into the subject myself. But it got me thinking about where I was when I first showed up at WSU dreaming of making games.

When you first start coding, developing a game seems like an unobtainable goal. The complexity is not only overwhelming, but daunting to say the least. I compare that to how I feel now and, while still daunting, it’s no longer overwhelming. I’m doing it with Right to Rule and makingĀ surprisingĀ progress. I don’t know when the change happened, between freaking out about midterms and starring down the clock as I frantically try to finish a project, it just clicked. I had no mentor to ask how it was done, I just tried and what happened…happened.

I suppose that’s my MO though. I’ve always been headstrong when I decide on a goal. I’m reminded of Day[9]Ā and his unabashed attitude to doing what you love. I’ll stumble all the way there, but I’ll get there. I guess it now falls to me to help those that were once like me.

Posted 10/06/11 @ 9:19pm - By Ross

RoadBuilder Done!

That was a lot of work…far more than I expected but it’s finished. And this pretty much sums up how I feel.

I’ll have to do a post breaking down the logic of the entire thing, but suffice to say that it’s a bit messy having to account for all the special cases thatĀ ariseĀ from having a graph and parsing each 3×3Ā quadrant. But it’s done and looks pretty good. Take a look at what it looks like:

Procedural generation ftw!

return 0;

}