Archive for January, 2008

Write a Function to Detect if a Linked List is Corrupt?

January 28th, 2008 No comments

Code Sample: Visual Studio 2005 Solution and .cpp

This is a pretty common interview question to ask C++ programmers. The key to solving this one is to write a nested loop. The outer loop iterates through the nodes. The inner loop checks each node’s next pointer member for corruption (node that points to a previous one in the list). 

More efficient solutions can be found if you search, “How to Detect a Circular Linked List” such as the solution described here.

bool IsCircular(Node* head)
      bool circleFound = false;
      bool tailFound = false;

      if (head && head->next)
          Node* slower = head;
          Node* faster = head;

               slower = slower->next;
               faster =  faster->next->next;
               tailFound = ! (faster && faster->next);
               if ( ! tailFound )
                   circleFound = (slower == faster || slower == faster->next);                                         
          while ( ! tailFound && ! circleFound)

     return ( circleFound );

Sandbox MMORPGs Upcoming

January 25th, 2008 29 comments

Great definition of a Sandbox MMORPG:

“Sandbox is a style game where the objectives are not predefined by the developer, you are given a world with some minimal predefined rulesets and you make your own game in it. Like a childs sandbox, which is just a box of sand, the actual game comes from the childs imagination and doesn’t have a set objective such as Ludo for instance.”

Not every MMO abides by that definition below but some do to a degree. So I’ve listed them here.

Here is a list of Sandbox MMORPGs I’ve come across:

RealmLords is an Indie MMO that calls itself a ‘Half Sandbox’

Earthrise – Science Fiction MMORPG cast in the future. Warcry posted an interview with the CEO. From what I understand, their parent company is the same one that owns Warcry which I think is very cool

W.E.L.L. Online – Science Fiction MMORPG. There is also an unofficial international forum for it. [Update: appears canceled, not updated since 2008]

Link Realms – Fantasy MMORPG that will allow players to create their own “realm”. Features skill-based development, building houses, etc

Citadel of Sorcery is a sandbox type of hybrid I’ve just heard about

Mortal Online will be a full PVP MMO with no Levels and a dynamic world controlled by players

Fallen Earth will be a partial sandbox featuring a Classless system, exciting futuristic setting, and responsive combat

Infinity will be a full blown, space MMO

I think all 3 will use an open skill system. I find it interesting there are a lot of folks out there willing to take a chance on skill-based development.

There are also many other Sandboxes and games “close” to Sandbox. Here’s the List (add more if I’m missing some):

Saga of Ryzom – Skill-based MMORPG

Starport – Space, 2d MMO. Has full collision detection, aim/dodge, takeover planets, quests, no grinding for skills, etc. Very fun game!

DEICIDE Online – skill-based mmorpg (no Classes) and no Levels

Darkfall Online – was in development for a long time before finally releasing for online purchase. Features skill-based development, dodge, strafe, aim, full collision, own land, and total freedom. It’s pretty fun mmorpg from the bits I played where your player skill can contribute to winning encounters in PVP/PVE

Asheron’s Call 1 – realtime dodging and aim, skill-point system, etc

EVE Online – Time Based character advancement (similar to use based skill system) , deep crafting, politics, player owned world, salvaging, tough penalties for death, PVP, PVE. Very, very fun and looks great!

Ultima Online – This is Daddy, one of the first. The first Sandbox I know of. The Classic UO was skill-based, not heavily itemized (at least Classic UO, pre-Age of Shadows expansion), etc

Wurm Online – Open Sandbox, Skill-based RPG developed in Java. Very original work

Second Life – Pure Sandbox MMO

Jumpgate Evolution also looks pretty sweet. Not sure if it will be a Sandbox at all but at least it should be Classless…

Runescape is also a sandboxy MMORPG with skill-based gameplay instead of Classes

Global Agenda and SOE’s The Agency will probably try something new




Neocron 2

Endless Ages


WWII Online


The Agency




I’ve always been a fan of RTS since the early Starcraft days and probably a little before that due to the Total Annihilation stuff made by Chris Taylor. Anyway below is a list of Persistent Online RTS games. Will also add a partial multiplayer RTS list below it. I stress partial because there are so many its too much to track them all.

Persistent Online RTS List:



Beyond Protocol

Saga by Sega


Categories: MMO, RPG Tags: , ,

Job Manager, Futures, Async Resource Loading, and Atomics

January 21st, 2008 No comments

I coded all three implementations this weekend. The Job Manager is a basic bare bones implementation in which accepts Job requests and delegates these services to various worker threads. It tries to fully leverage the target platform by analyzing the hardware and counting the logical processors. Next, as jobs come in the Job manager begins to delegate these tasks to the appropriate threads.

Job Managers are the way to go for multi-core architectures they really help software fully leverage the underlying hardware plus it abstracts some of the nitty details from programmers.

The first test for the Job Manager this weekend was to fire off an Async File Job in which handles streaming a package. Works pretty well aside from some issues with Resource management (problems in other parts of the codebase). My engine was already split into separate render/game logic threads so it wasn’t too painful of an addition to include support for asynchronous file loading.

Also implemented an Atomic Class which is a lock-free programming paradigm. Lastly I took a crack at writing a C++ Future templated type in which employs an Atomic that can be accessed by different threads concurrently to mark when data is ready for consumption.


  • Caller sends in a reference to a Future they created locally. Like Future<Package*>&. This reference is stored within the Async Job
  • The Job manager ensures that all package dependencies have been loaded first. If not, it goes to load them (create a Job to load it).
  • If a child Job task was spawned, we check back in a few frames to see if it’s complete. If so, we register the package in the main thread.
  • Once all dependencies are resolved we proceed to spawn a Job to concurrently stream the content
  • Once loaded, we populate the Future<Package*> reference with the PAckage we just loaded
  • The caller from the main thread will wait until the package has been loaded if it’s not ready. So far the Job is always ready for me by the time I need it though. So I havent had to pause the main thread yet

Burnout Paradise

January 15th, 2008 2 comments

Interesting, I wanted to implement realtime destroyable geometry with GODZ UT but the BSP (binary space partitioning) that Unreal engine used at the time really got in my way. So after a few weeks of fighting with BSP I finally gave up

Very cool to see this technology in motion on consoles. Burnout Paradise is an open, free roaming environment that is a lot of fun to play online I might add. Full blown sandbox pretty much from what I can tell. EA has really got a great lineup in store 😛

Categories: Programming Tags: ,

Kingdom Under Fire: CoD Continued

January 14th, 2008 2 comments

Been playing KuF: CoD with my bro still. On release day a Level 60 joined our party -and- get this, she leveled up. Apparently, there is not really a huge disparity between Veteran and Newbies in this game. Our party had level 10s for goodness sake. The RPG system is still very basic stuff. You level up and get points. However, its more of a skill-point system then a Traditional Level/Class system. Apparently, your avatar does not automatically grow stronger at level up but rather- the game let’s you allocate your skill points directly. I vastly prefer this type of system for coop RPGs because if my friend plays the game without me- I can still join up when I get time and still be an asset to the party.

They appear to softly ‘gate’ items. A lowbie can pickup a powerful weapon however, they just appear to use up a lot more SP (stamina) then they have. I like this- they appear to be discouraging newbies from using veteran weapons rather then outright disallowing them. There is no “Level based numbers” attached to items but rather they specify the minimum value of each attribute you must have in order to wield it.

They appear to have Class restrictions that restricts experimenting with different equipment. Typical stuff that we see in almost every single rpg, the warrior cannot pickup a bow, blah blah. One interesting thing, apparently spells are shared amongst the Classes. There does not appear to be a dedicated healer type. So, basically everyone appears to pursue learning Heal spells. I kinda like that element it makes characters a bit more diverse.

Character Custimization blows. I’m not sure what they were thinking I’ve seen much better custimization in single player RPGs. My bro and I look the exact same and apparently always will be (yes even with armor on). They let you put on little details to distinguish yourselves though so I put on a hat.

Free For All PVP

January 14th, 2008 No comments

Free For All PVP (aka Deathmatch) is one of the most controversal subjects you can ever discuss. Depending upon the view of a gamer on this subject you can normally determine everything else about them. Many that like FFA PVP (at least in theory) also usually like the idea of a Sandbox game, no Levels, no Classes, and other extremes.

In order to determine it’s popularity amongst devoted PVP fans I’d suggest loading up Call of Duty 4 and checking out server activity. This is no where near fully accurate but it at least gives us some clue what many prefer. Team Deathmatch appears to be vastly more popular amongst PVP types (hence the popularity on Team Fortress 2, Counterstrike, and Battlefield series).

So then, at least amongst FPS gamers Team based PVP is in the lead. However, there is one flaw- most leading FPS games include friendly fire. Friendly Fire adds a nice dimension of realism- many times causing the death of an undisciplined force of players that lob around grenades and such. This concept is fairly foreign to MMORPGs which is a shame it’s a very nice anti-zerg feature. Would be very nice if we could at least get the concept of friendly fire into MMORPGs.

Next, I see a lot of posts whereas players label FFA PVP as ‘meaningless PVP’. Perhaps this may seem that way to them because they are accustomed to game developers leading them by the hand- giving them quests and rewards (whether they win or lose). No, FFA PVP is rather a sandbox element of sorts whereas players have the freedom to engage in PVP whereever/whenever they see fit. Here are a few reasons why FFA PVP can have meaning:

  • Gives players the freedom to fight against enemy Guilds
  • Gives players the freedom to help self regulate the server. Imagine if FFA PVP was in play and you see an Asian farmer harvesting/grinding. Well now you have the freedom to kill the farmer and if looting is in effect you can take his items. Self regulation.
  • Gives players the power to discipline griefers, ninja looters, and exploiters. In World of Warcraft if someone steals your epix there is really nothing you can do about it. If FFA PVP was in play, you could take back what is yours.
  • Gives players the freedom to fix Race vs Race imbalances. For instance, in City of Heroes- Hero vs Villain PVP is very imbalanced. It was desirable for the developers to provide FFA zones to allow players to fix game imbalances.

Of course, along with FFA PVP comes a bucket of potential problems like how to deal with griefing, etc. I’ve seen some really great blogs on integration of Justice systems and so forth. Now, there are other systems that can get us fairly close to FFA PVP such as a well done Factions system that allows players to run it (something akin to Guilds but on a more organized level). This could almost get us there and at the sametime- give players the freedom to self regulate.

One of the main problems with FFA PVP is that it is hostile to Casual audiences that do not want to group up. Additionally, it is obviously unkind to the less skilled. Lastly, there are a handful of gamers from Ultima Online that have a knee-jerk reaction at the very mention of the word even though there are FFA PVP systems out there (like EVE Online) that has provided such a great atmosphere the EVE community reacts very violently to the thought of a 100% PVE centric server. It’s simply unneeded. Right now one of the best FFA PVP games out there that I’ve seen is EVE Online.

Further Reading: 

Categories: FPS, MMO, PVP Tags:

Determine the Maximum Depth of a Binary Tree

January 11th, 2008 No comments

Code Sample: Visual Studio 2003 solution (.cpp included) 

 The trick to solving this problem is to use Recursion to iteratively search through each branch of our binary tree and tally up how many nodes each node contains. Once you realize you need to take one parameter (depth) and return the maximum size for each branch from “each” node then you’re on the right track. So, the main trick you must do is at each individual node, examine the child, left, and right sibling. Store the number of nodes each branch reports back and store it off. Later, compare all 3 results to find the best number then return this maximum depth you discovered back to the caller.

I can’t recall if I’ve seen a Binary Tree blow the Calling Stack on a small memory machine offhand but I’ve seen other complex recursion routines blow through the Call Stack. So if you’re ever asked why Recursion can possibly be bad is because of limited memory assigned to the Call Stack.

Write a Program to detect a Palindrome

January 9th, 2008 No comments

Code Sample: Visual Studio 2003 solution and .cpp

This is another pretty good interview question that often gets asked. It can’t hurt to already know what a Palindrome is before you get asked this question. Palindromes are words that are symmetrical somewhat. A word like DOOD or TAT can be flipped and mean the same thing. Yeah, I know I just made up those words but hopefully you get the gist. This example makes good use of Asserts and pointer arithmetic.

bool isPalindrome( const char* str )
size_t len = strlen( str );
const char* head = str;
const char* end = &str[ len-1 ];

while( len > 1 )
if( *head != *end )
return false;


// decrement from our string length count for each string_ptr move
len -= 2;

return true;

Categories: Interview Questions Tags:

Programmer Interview Questions

January 8th, 2008 3 comments

I’ve been in the game industry for a few years now. I’ve been on the receiving end (getting interviewed) and on the attacking end (the interrogator). Most game industry interviews focus on knowledge of C and C++ however it is still helpful to know how to deal with Number Ranges, Vectors (Cross, Dot product), and good ole fashioned problem solving.

The link below is really good it contains many questions you might get asked:

Off hand, I want to say at every single interview I’ve been asked at least one Bit Manipulation question, one question from the link above, perhaps a pointer question, smart pointers, and Big O notation which is explained in detail here and a more brief but very nice description can be found here. Know the complexity of array O(1), linear search O(N), hash table best- O(1) worst O(N), and binary search.

Others asked about preincrement operators and how they differ from post increment operators, Palindromes, detecting a corrupt node in a Linked List, differences between C and C++, recursive functions, bit operators, multiply a number by 8 without using mult/divide, etc. All of this is pretty much covered by the link above. Soon in the future I’ll give my own solutions for fun

Coding Horror has some good articles on phone interview questions (those aren’t game industry specific however). Keep in mind most game companies stick to C / C++.

Another pretty good subject is called ‘Bit Twiddling Hacks’. If you Goggle for this topic all sorts of interesting links will popup. These questions tend to be stuff I’d probably never ask a candidate but still they are probably very handy to know. I’d prioritize this as tricky, fringe stuff though thats just like handy to know. I’d prioritze the questions covered at the link above much higher (like Palindromes, etc)

Here is one interesting link for example:

Here’s a good example:

Determining if an integer is a power of 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here       

f = (v & (v - 1)) == 0;

Design Patterns is something that is asked at almost every interview too. This link provides a very nice list.

Programmer Math Questions

Some standard math questions usually deal with Dot products so you’ll want to know them backwards & forwards. The key is realizing that two vectors that are in the same directions is greater than 0 (dot product == 1 when they are perfectly parallel). Two vectors that are perpendicular will equal 0. Two vectors that face opposite directions will be less than zero. You can take dot product of vectors to get a scalar that allows us to measure distance + get the angle between two vectors using arccos / atan2. For practice, I’d highly recommend just playing around with basic unit vectors on paper. Such as taking the dot product of [1,0,0] DOT [1,0,0] (parallel) and [1,0,0] DOT [0,1,0] (othogonal) and [1,0,0] DOT [-1,0,0] (opposite). By that same token, you really want to know bout Cross Product and how you can take inverse sin to solve for theta as described here.

More advanced tests may concern the distance from a point to the plane + ray vs plane + ray vs sphere intersection

Object Oriented Questions

Method Overloading

Method Overriding


Virtual Inheritance

Design Patterns

Other subjects:
Difference between pre-increment and post-increment
Cast operators such as static_cast, dynamic_cast, const_cast, & reinterpret_cast
Good info about testing for Google (applicable to almost anywhere!)

Brain Teasers

Some developers like to ask “Brain Teasers”. Most of your AAA (triple A) game developers will not due to barely having enough time to cover the stuff covered above (3d math, C++ knowledge, etc). This is more common to business industry. One question I’ve been asked before is this about the City of Truth/Lies as discussed here.

How to Detect if a Pointer is 16-byte aligned?

January 8th, 2008 No comments

Code Sample: Visual Studio 2005 Solution, .cpp code 

I was asked this one once at a job interview for a Junior programming position many years ago. Usually such a thing is a concern for the Lead Engineer or the Low Level Optimization Engineers that are tasked with optimizing code to achieve ideal performance. For PC architecture, usually it is SIMD operands that require the 16 byte aligned structures. On the playstation 2, I believe this was a concern for the Vector Unit programmers.

 Nowadays we have the GPU, a specialized graphics unit that automatically takes care of memory alignment as long as you use a High Level language for graphics rendering (like HLSL). So, even a graphics programmer does not have to deal with such things these days unless you bypass the high level shading language and use ASM (assembly). I wrote a shader or two in ASM for the GPU back in the day back when it was believed HLSL did not compile optimal code.

This might be a great question to ask to help determine how experienced a programmer is at low level programming. But even if the programmer fails this question he can still be an excellent programmer yet- just not have been exposed to code at this low level before. At some development studios, there is usually just 1 or 2 ‘hitman’ that focus on code optimization (write code first, optimization last). I have heard of other studios that ‘write code and optimize first’ which is probably the stronger methodology. For heavy Matrix ops it can be desirable to of course employ 16 byte aligned Matrix structures. On some consoles, you might actually be required to allocate byte aligned memory and fire it off to the chip so for these positions an understanding of byte alignment is crucial. So my advice is to learn this subject when interviewing for any console programming position just to be safe!

#define IS_ALIGNED(_pointer, _alignment) ((((unsigned long) (_pointer)) & ((_alignment) - 1)) == 0)

Highly Recommended reading is the topic of Structure Padding. Along this same lines, here’s a nice topic on allocating memory along a boundary.