Kevin Jenkins' Blog

PhysX doesn’t have a nudge feature, by which I can slightly adjust the position of an object, while still accounting for collisions. What I had to end up doing was adding a velocity to move me by an estimated amount for the next tick, then undo that velocity. Naturally this caused a lot of problems, such as breaking my maximum velocity limit, causing you to potentially hit walls at great velocity, and it’s inaccurate.

I’m surprised this feature doesn’t exist, since every networked game needs it.

I wonder what other physics libraries might have this feature?

Incidentally, I am not happy that PhysX requires you to use their system installer thing. Users are complaining about having to install so many dependencies, and that leftovers are left after they uninstall the game. I totally agree. This might even cost me sales. With a store bought game you have no choice, but with my game since there’s a free trial the user has a low investment and might just cancel the install.

Speaking of which, I am curious about why other programs I install don’t all prompt you to install the Visual Studio 2005 end user runtime. If I could get rid of that it would knock down my dependencies by 1/3.

I changed the movement algorithm today.

Formerly:

Client sends inputs (position, rotation, velocity, acceleration, angular rotation).
Check each field independently using some pretty loose and generous metrics. Do a raytrace to make sure the client didn’t go through a wall.
If any field is off by too much, just use the current values on the server, and force update the sender.

The problems with that are:
1. Requires a raytrace
2. Easy to cheat
3. Accuracy and visibility of lag depend on the client – slow clients give bad performance

I changed it to:

Client sends inputs (position, rotation, velocity, acceleration, angular rotation).
Clamp the timestamp to a maximum value
Look in the transformation state history to find out where the client was back when they created the packet.
Verify input values with a maximum error of 100 milliseconds. If a value is wrong, set the value to the transformation history value

This is better because:

1. Transformation history lookup is perfectly accurate
2. I can use a tight clamp because of this accuracy, so I don’t need to check for going through walls, since the timestamp is too low to ever go through one anyway.
3. Faster with no raytrace.
4. Performance is always good to other clients, no matter how bad the sender is.

However, it does give worse feel to the sender if they are very slow or lagged. They will warp around occasionally as the server corrects them. The warp is interpolated, but still noticeable.

I couldn’t figure out how to get the quaternion representing the rotation from A to B. Laugh if you want but I don’t use Quaternions enough to remember and have to reinvent the wheel every time.

20 minutes later of looking at Real-Time rendering

// start * delta = final
// start^-1 * start * delta = start^-1 * final
// delta = start^-1 * final

The inverse of a quaternion q is conjugate(q) / length(q)^2

For a unit quaternion, the length is 1.

For the conjugate, flip the sign of x,y, and z.

The first 3 years of my programming career I was a telecommuter. At that time I was entirely in favor of telecommuting for all information based jobs. In my opinion, the only reason companies didn’t allow telecommuters was because of anal managers grasping for control. Managers that didn’t trust people to do their work and foolishly thought that having you physically there made any difference. It was an outdated and pointless business model, and smarter more progressive people would excel in the marketplace over these dinosaurs.

The few times I applied to jobs and asked for telecommuting, I was told they didn’t allow it because of a lack of communication. I considered this to be a lame cop-out. Simply an excuse to justify their own anal behavior and lack of experience.

When I finally did start a non-telecommuting job, my opinion was only reinforced. I was twice as productive per unit time at home than in the office. Not only that, but at the office the computers were slower, there were a lot of distractions, I had to waste time driving to work, and I was more likely to work fixed hours than at all hours of the day as I do now. Overall, the company probably only got 1/3rd of their value for the money by forcing me to come into an office.

When I started this company my intention and initial design was to be 100% telecommuting. It was far cheaper for me to run the company, everyone would get those massive productivity games, I could hire anywhere in the world, and since people love to telecommute I could steal away the best talent from other companies.

That was 8 months ago. Now that my project is winding up I have some perspective on both sides of the issue. The truth is that telecommuting works, and it works and delivers the massive gains I always claimed it did – but only for programmers and then only for superstars. Everyone else fails miserably. A superstar has to excel in every relevant area: self-motivation, intelligence, attention to detail, communication skills, belief in the project, and organization. Since 98% of programmers are not superstars, and its very hard to tell who is and who isn’t just from an interview, you’re going to end up wasting a lot of money with bad hires, and firing a lot of people, as I did.

Self-motivation: One guy I hired worked hard the first three days, sort-of-worked the next week, then slacked off the remaining month. Emails queries just got excuses, until even under the most generous conditions I couldn’t believe it was taking him a month to write one UI screen. It’s very hard to keep motivated when nobody is forcing you to go into an office each day.

Attention to detail: The Indians failed here because of literalism, I believe due to cultural attitude of subservience. They do exactly what they think they are told, no more, no less, and don’t expect to think for themselves on any issue. Even if what they thought they were told is obviously stupid, or doesn’t make sense, they won’t think about it or bring up issues. So you just pay for a week to get some obviously wrong and useless check-in.

Communication: One guy I hired from the Ukraine would never communicate. He would take a task, guess at parts he wasn’t sure of, and work for a week only to check in something fundamentally wrong and unusable. Unlike the Indians, he would go against the written specification when it didn’t make sense, but based on usually wrong guesses as to the correct solution. Email checkups were always answered with short sentences. Over a month and a half I tried to get him to communicate – first nicely, then direct orders, finally threats, until I had no choice but to fire him. This wouldn’t have happened in an office setting, since I would have just went by his desk.

Lack-of-care: The database programmer I hired was competent technically but just didn’t give a crap. So he didn’t check for user string to server buffer overruns even when its only one line of code, implemented things the easiest, most inefficient way possible, and ultimately abandoned the work and ran with the money. People act this way for the same reason they may be loud-mouthed jerks on the internet but nice guys in person. There’s no face to face interaction, so you have much less investment.

With one exception, none of the guys I hired were truly bad such that they would fail under any circumstances. It was just that 90% of them were not superstars and were not able to cut it working over the internet.

The net result is I’m actually worse off because of telecommuting, because I got nothing at all from the fired individuals, where in an office setting I would have at least had some code to show for my money. However, my failure wasn’t the principle of telecommuting, but that I didn’t appreciate just how hard it was to find good programmers, or how only superstars would be able to successfully telecommutes. If I could do things over again, I would still telecommute, but I would be much more careful about hiring. Start with small, milestone based contracts, and don’t offer a job until an individual has proven himself.

With only two weeks left of funding on this project it’s now clear that my discovery of and subsequent decision to hire an overseas art-team was a mixed blessing.

On the positive side they are extremely cheap for the size of the team I hired. They try to do a good job. By hiring through a company I don’t have to manage individuals on a day to day basis. On certain tasks, such as drawing textures, or modeling objects when there are no technical requirements things worked well.

On the negative side, all games have technical requirements for art assets, and mine more than most. Trying to communicate and enforce these requirements was a constant major time loss on both sides. About 50% of the total time on art development with this company was either lost completely on unusable assets, or spent redoing work. I don’t think they did things wrong out of a lack of care, or of intentional sloppiness. It’s more like artists are very visual, and it’s unrealistic to expect them to follow written instructions without messing up a few times first.

I had to go in and do probably 1/4 of the total art development myself. For example, I knew it was hopeless to try to get the artists to setup physics when after 6 months they still don’t know how to center models correctly, or to reset transforms.. I probably spent a month in total doing work inside Photoshop or the 3D modeling program. This is a good part of the reason why the programming is late. Things look OK, but not half as good as I originally envisioned.

In the end I think I got what I paid for. 1/4 of the value I would have gotten from artists on-site, but 1/4 of the cost too. If I could do things over again, I would have hired on-site artists, and used off-site artists only for gross work with no technical requirements, or requirements that are already visually represented (such as concepts).

I’m not unhappy about how things turned out, I just thought it could have been better.

I added asteroids to my game levels now.

Asteroids are huge objects, about 3000 meters in diameter, that you can fly into. The fighter itself is 18 meters in diameter. The asteroid is about 40,000 polys.

My first approach was to render the physics geometry in the radar, and the regular mesh on the screen. However, my performance wasn’t very good – 50 FPS or so, about half of what I usually get on complex levels. There are about 500 boxes and 50 physics spheres for the large asteroid. So I stopped rendering the physics objects, figured out how to cut off the top of the asteroid, and render that instead. This brought me up to 60 FPS.

The next thing was that those 550 or so physics objects, even though they never render (visibility set to false), might still be processed through Ogre. While Ogre has many good qualities, efficiency isn’t one of its strongest strengths. So I deleted those objects after processing the physics bounds. This freed up some memory and got me from 60 to 62 FPS.

My next guess was that if any part of the asteroid renders, the whole asteroid renders, when in fact only the part you are looking at needs to be drawn. You only see a diameter of about 500 meters on the screen, about 1/(6^2) of the total asteroid, so there’s a lot of pointless vertex culling.

I decided to break the asteroid up into a grid, each cell of which is about half of what you can see on the screen. This means that at any given time it will render 4 cells. However, I went a little bigger and made each cell 800/2 meters. This is because I am anticipating a lot of players may complain the max camera zoom distance is still too low. If I made it higher later I wouldn’t want to resplit all the objects. At 400 meters per cell, and 3000 meters in diameter, this is slightly less than 8 cells on an edge, or 64 cells total. If I can render only 4 / 64 cells, this is a great improvement.

It took me a while to figure out how to do it in the modeling program. I eventually made an 8×8 grid of helper planes and split along each of these planes. After this, and rerunning the game, I now got 75 FPS. So someone with a machine half as fast as mine should still get at least 30 FPS, which is acceptable. (Actually it will be higher, as I was running the server too).

The problem as usual is this technique is too technically complicated for my artists to do. I’ll tell them to do it, and maybe get lucky, but I’ll give 10:1 odds they will mess it up somehow: the splits won’t be exactly 400 meters, won’t be evenly spaced, won’t be centered at the origin, splits will be missing, and/or it will take days and days. So I’m going to have to do it myself for all the models, just as I spent the last 3 days painfully creating physics geometry for every level and every asteroid.

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.