Month: June 2007

This game is the first experience for me to work as the director on a project. I’ve discovered a good analogy to the feeling – being the captain of a warship. Your programmers are the gunners, your artists are the sailors, and the director is the captain.

A great programmer / gunner can do a lot of damage to the enemy with well-placed, accurate shots. A bad programmer / gunner can sink your own ship if you don’t court-marshal him in time.

Great artists / sailors can get you to your destination even through strong winds. Bad sailors can set you off course and make the programmer miss and make you late to your destination.

The captain is the most important – a simple decision early on about which ship to attack can win or lose the war, no matter what the gunners and sailors do. Picking the right crew is paramount, as in throwing overboard those who can’t manage on the ship.

I also understand now why directors / CEOs make so much money. It’s not that they provide that much more value, but the cost of failure is so great it’s worthwhile to pay 10X more for someone who is 10% better. It’s the same reason why lawyers make so much money. You’re not going to bargain hunt a $100 an hour lawyer over a $500 an hour one if failure means you go out of business or go to jail.

Just to illustrate the magnitude of the effect small decisions can make.

Good decisions I’ve made
Used Ogre: Saved about 40K and 3 months
Used FMOD: Saved about 5K and one month
Used Aria for billing, instead of writing my own solution: Saved the company
Setting up billing 4 months early: Saved the company (it didn’t get finalized until last week!)

Base decisions I’ve made
Used oFusion: Cost about 10K and one month
Used CEGUI: Cost about 2K and one week
Hired from India: Cost about 30K and 4 months

If you had somebody with the power to make decisions that important, money isn’t really an issue.

My game is about 90% ready for Alpha now. The DB is complete and tested, except for a few bugs. There’s no known significant bugs in multiplayer based on superficial testing. After a real gameplay test I think it will be ready. We have a real map prepared, although it needs polish. The fighters, weapons, items, XP settings all have reasonable settings which can be tweaked while playing. It’s possible to create accounts through the billing provider and I’m in the final stages of setting up a merchant provider. I am able to build on the development server and have a real database and game server ordered and coming. The webpage and forum is setup, although needs content.

I still have to test all the other game modes, fly the carriers around, test actually buying carriers, and importing external objects into levels. Also the explosion effects and other effects were never done well or right for carriers. This should all be straightforward though.

It’s about 2 1/2 months late right now to reach this point, assuming everything from here on out goes smoothly. The next major target is to get the server supporting and running properly with 500 players. Scaling at that point is just adding more servers. After that it’s just polish remaining really.

Games with only a few players (say 8 or less) can send all updates to all other players. In these types of games, most players are usually grouped together anyway, and even if they are not the overall bandwidth is low enough it’s not a big deal. The “wasted” bandwidth isn’t a bad thing necessarily. It makes programming easier, it’s more accurate, and you can do things such as game-level radars easily.

Games with more players, such as your average shooter (32-64) should only send updates to players that are nearby. The way they usually do this is to base frequency of sends on relevance. A player farther away gets fewer sends, a player I am facing gets more frequent sends. This is an O(n^2) problem because for every player I have to determine the orientation to every other player. In the worst case scenario of 64 players, this is 4096 operations. However, since this occurs at a maximum interval of your packet send rate, it’s not a big deal.

MMOGs such as mine, with many players (500 on one server) have the O(n^2) scenario as above, but there are too many players now. This would be 250,000 operations doing it the straightforward way. In my particular case, while I have a maximum send interval, I cheat on this in many ways, so in essence I need to recalculate this every frame.

The solution I came up with is to split up the world into a grid. Every update all objects go into one or more cells of the grid, depending on how big they are. This is an O(n) operation, and a pretty fast O(n). Then for each player, I query the grid to get the nearby neighbors. This goes into a sorted list, which I use to get a list of all nearby neighbors, as well as checking if a particular object is nearby.

Total cost is O(n) for the grid sectorization, and O(n) to go through each player to sort the nearby neighbors. Inserting into a sorted list is slower, but since there are on average only 10 items it’s not a big deal.

An “operation” is a bit misleading since different things that I do have different costs. But for the sake of argument…

500 players each with 10 objects nearby =

500 operations to place the players into the grid +
500 insert nearby objects. Assuming each insert is O(1) (it’s actually O(Log2(m) + O(m) where m is the number of nearby objects (10)), then this is Sum(1…10) = 55.

500 + 500*55 = 28,000. It’s a lot of operations, but still far less than 250,000, and scales linearly.

I further decrease this by using the fact that network nearby neighbors doesn’t have to be perfectly accurate. It’s good enough to update every 100 milliseconds, instead of every tick. So every 100 milliseconds I do the full-blown update. In other ticks I just cull out the deleted pointers and use the previous list.

This brings it down to an average of 933 operations per tick, assuming we do 33 milliseconds ticks.

Originally, as I implemented the bullet shooting code I would have the client send the bullet’s velocity,position, and orientation to the server. The server would verify these values for sanity and if they were reasonable it would accept them. Otherwise it would reject them.

It occurred to me this isn’t very cheat-proof, especially since I allow modders to change the model. While it would block the most extreme cheats, you could still angle your weapons, shoot slightly faster or slower, or even auto-aim.

I changed it to where I record all fighter positions for the last second in a circular queue. When a shoot packet comes in, I use the timestamp to look back in history to see where the fighter was on the server when the bullet was fired.

This is cheat-proof, pretty accurate, and the only thing you could modify is the timestamp. But there’s really no benefit from changing the timestamp, as any changes will simply make the shot less accurate.