Game Development

Finite state machines and why Perforce sucks

At work, we use Perforce for source control. Perforce is the most popular source control system that I know of. There are some reasons for this: it is fast, it has a lot of features, and it has good support.

Before Perforce we used Visual Source Safe. VSS has many failings. The database sometimes gets corrupted. It’s slow. It lacks features. It’s why we went shopping for a new source control system. But one thing good about it is that once you get it working and you backup your database you can mostly focus on your work. Artists can use it and programmers can use it and you don’t need someone full-time supporting it.

Perforce fixes two of the problems with VSS: it’s fast and it has a lot of features. But it brings with it its own set of problems. Before where we didn’t have anyone supporting source control, we now have a technical director supporting Perforce nearly full-time. Support drags other people, including myself, into issues. For example, I had to sit through 15 minutes of a meeting yesterday listening to a proposal for a script on how to update artists from Perforce correctly. I’ve been here two hours today and have already overheard two conversations concerning recovering from Perforce related problems. Because of usability issues I’ve stopped checking checking in more than once a month. It’s an issue often enough that when people say “Perforce fucked up” they always add an “again” to the end of that sentence. Now in all fairness 90% of the time problem is human error. But that’s part of my point – that’s 9X more problems than should be occuring. Why are there so many usability problems and why are people making so many mistakes when using Perforce? Because Perforce is fundamentally flawed in how they update their repository finite state machine.

According to Wikipedia, a finite state machine is a model of behavior composed of states, transitions and actions. A state stores information about the past, i.e. it reflects the input changes from the system start to the present moment. A transition indicates a state change and is described by a condition that would need to be fulfilled to enable the transition. An action is a description of an activity that is to be performed at a given moment.

How do you determine the conditions that must be fulfilled to enable the transition? There are two ways to do this: event driven and through polling. With event based updates, you find every situation where the event happens and trigger the condition. With polling, the state itself (or possibly the condition) will check all other relevant states to see if it should update. If so, it triggers the condition to change the state.

This is much simpler than it sounds. Let takes a hypothetical game where the player has a health value and a death animation. There is a rule where if the player’s health reaches 0, the player plays a death animation.

With event based systems, you would find every place in the code that modifies the player’s health (barrel falling on you, bullet hitting you, falling off a cliff). If, after that event, your health is 0, you play the death animation. This system is efficient but has an important problem. If a new scenario is introduced (spike trap), and the programmer forgets to trigger the death animation, your system now has inconsistent states. In this case you’d have a bug in your game where the player is able to run about, perhaps invulnerable, after falling on a spike trap. This is an especially common problem in network programming where new remotely triggered events are introduced for most actions in the game.

With polling systems, you have the destination state check its own transition triggers. So in the scenario above, once per cycle you would have the character check his own health. If, for any reason his health becomes 0 then he changes to the death animation. This is nice because now you can add as many health modifications you want and never have to worry about the player running around invulnerable. But it too has an important problem: it’s inefficient. Even when your player is inside an insane asylum, with padded walls, no bullets, no barrels, and no cliffs, you are still checking to see if his health reaches 0.

If you think about it, most computer and many non-computer systems can be envisioned as states, with corresponding event-based or polling checks. Menu systems often use event-based transitions (OnMouseClick) while AI often uses polling (Is there an enemy in front of me?). In baseball, the umpire calling “Strike!” is an event based transition while watching an instant replay to check the results uses polling to break the ball updates into discrete frames and to check each frame (Slow-motion replay) for the transitional condition.

The Perforce update system is also a finite state machine, and is event-based. Perforce, being event based, is fast but error prone. It defines a specific set of conditions to update the database. The primary condition is that you check out a file, update it, and check it in. If you deviate from this model then you get inconsistent states. For example, if you update a file locally and later update that file from source control you lose your work. If you add a file locally but forget to check it in, nobody can build the project. If you delete a file locally and later update the file is back again. There’s no way to say “Just use what is on my harddrive!” Perforce is complicated and there are many ways to get inconsistent states. If you know exactly what you are doing and never forget what you’ve done between updates you are OK. If that isn’t true (which is to say you are a human and make human errors) then you are in trouble because you are going to have problems ranging from lost time to lost work.

It’s easy to say “Just don’t deviate from that model, stupid!” and in fact some people do say that to the artists. But it’s something that shouldn’t need saying because the flaw is not in the artists but in the system.

The logical system for updates is:

  1. You have completed work on your harddrive
  2. You upload the state of your harddrive to source control.
  3. You do work
  4. Go to 1.

You don’t want to and shouldn’t have to think about source control while you are working – you only want to think about it while you are updating. The fact that you do have to is because Perforce is event-based, and event-based in such a way that if you don’t work following a certain methodology Perforce won’t update correctly. Is this the fault of the person working, or a design flaw with the source control system? I believe that it’s the latter. As I work at a game company there are many artists. Artists care about conceptual models – they don’t care about leaky abstractions such as what version control system you are using. They just want to do their art and want the game to work. As the company gets bigger and there are more artists you get more errors. Eventually you reach the point to where every day I hear coworkers complaining about problems related to Perforce and someone has to work nearly full time just supporting a tool In my opinion this shouldn’t be necessary and why I think that Perforce sucks.

For my game network library RakNet I use Sourcegear Vault. While not perfect, it supports both ways of updating (event-based and polling). With polling, it takes a second longer to scan my harddrive but

  1. I’ve never missed checking in a file
  2. I’ve never overwritten work I did locally
  3. I can do work on another computer, copy it over, and still upload and update from the repository
  4. I’ve never had to spend a lot of time recovering from a problem caused by source control

None of these things are true for Perforce and all of these things are true for Sourcegear Vault. As you get more users, Perforce gets worse because if each user has a p percentile chance of making a mistake per day, then the odds you will go a day without mistakes is (1-p)^n where n is the number of users. At p=1% and n=100 you only have a 33% chance per day of going a day without someone losing work or breaking the build directly because of Perforce.

Which is why Perforce is not suitable for large projects.


Why you shouldn’t partner in business

Some people ask me why I’m working on something as big as an MMOG by myself. Here’s a list of reasons why you shouldn’t partner with someone in a business:

A partnership is a marriage
My neighbor runs the biggest Mailboxes Etc. in Newport Beach and complains about this topic every time I bring up the issue. When you have a partner no longer can you do what is best for the business. On all major points you now need to consult your partner. You’re going to spend most of your waking hours with your partner, more than your girlfriend or wife. If you don’t get along a ‘divorce’ is going to be just as expensive as a real divorce, and possibly kill the business you put the years of your life into. You wouldn’t marry someone unless you knew them well first and only 1 person in 1000 is worthy marrying. How many people do you know that well at all, much less are worth partnering with?

Your reasons for finding a partner is probably short-term but the partnership is long-term
When starting a business there’s a lot to do and a lot of difficulties that can be most easily and effectively solved by someone else. In my case, I need art for my game and I don’t have much money to pay for it. One solution is to partner with an artist. So lets say I were to grab a friend who I know well, get along with, and who does a good job at art. If the business is successful, 10 years from now I gave up half the business so I could save 30K on artwork. Stupid.

It’s like those idiots who get venture capital from Y Combinator. They give up some percentage of their startup for a measly $6000 per founder. If you are so hard up you can’t scrape together $6000 you don’t have the connections, work experience, or qualifications to run a business.

Your payoff is p/n, where n goes up by 1 for each partner
That’s profit / number of partners. Of course p may go up too, and if p goes up by more than the inverse of (n+1) then it’s worth it. But that’s unlikely unless you partner with a superstar. At n=1 you’d have to double your profit to make up for it. It’s easy to envision two people doubling income but I didn’t say that. I said two partners doubling profit. Would a partner, vs. an employee, make that much more? Keep in mind a partner, unless they work for free, is going to draw a salary from your income too, thus reducing profit.

Do you need a partner, or an employee?
Following from my previous message, do you really need a partner, as opposed to an employee? You have to ask yourself “Am I partnering for someone to do a specific job?” Because if you are, hire an employee instead. If you can’t afford an employee… this is one reason to find a partner. They can bring the money you need where otherwise it would be impossible to make your business succeed (I’m talking hundreds of thousands, not $6000). Another reason is if your partner is such a superstar and they are so critical to the business that you would never be able to hire them otherwise. That’s rarely the case.

Most people aren’t cut out to run a business
Not everyone is a superstar. If they were, we wouldn’t call them superstars anymore. We’d call them average. Most people are average by the very definition of the word, with half the people below average and half above average. How many superstars do you know at work? Probably 1 or 2 right? So they can program, or do art, or whatever. How are their social skills? Their business sense? Do they bring capital with them that they are willing to part with? Are they good at managing people? Are they a superstar at every one of these things, or enough of them to compliment yourself? You have a 1 / p^n chance of finding such a person. So the odds are, whoever you are thinking of partnering with might help you today but won’t be carrying their weight tomorrow.

Some people can’t hold long-term interests
A business isn’t a 9-5 job. It’s a 9-9 job, and will be for some number of years, if not the rest of your life. Can your potential partner stick with things this long? If not, it’s going to cost you a lot of stress and money down the road when they decide they work too hard and should stick to management.

Back when I was in Alaska there was a good opportunity to start a computer store. There was only one other computer store in the city and they overcharged, were rude, and had a poor selection. At the time the internet was still growing so there was no real way to order over the internet either. At the time I didn’t have much business sense so I partnered with my cousin to start such a store. I wrote up some business proposals to send to family to try to get money to get the initial batch of parts and open the storefront. I called and looked around to try to find a suitable location. I worked out the math on the finances and contacted a vendor who I could order from. My cousin… well he was excited to talk about what to name the store. After a week of my bitching at him to help, he said “Why should I do anything when you’re doing it all?”

As it turns out I was right. About 2 years later a Computer City opened there. They went out of business, but then CompUSA opened a year later and has been there since. With a 2 year lead into the market I could have potentially done very well for myself.

Don’t partner with someone just because it’s exciting to do so, or you need a short-term employee. Partnerships only make sense if you

  • Know someone incredibly talented in a wide variety of fields
  • Will make you far more money than not partnering with them
  • Is mission critical
  • You have no other way to get what you need

Political compass test

Political compass test

I got:

Economic Left/Right: -0.25
Social Libertarian/Authoritarian: -2.92

The maximum is 10 on the scale, so I’m right in the middle for the economy and more towards Anarchism than goverment control. I think this is because of the current goverment oppression I’m strongly against any goverment control.

Game Development

MMOG update – found artists

I spoke to the guy running this site yesterday. The art looks good, the guy sounds professional and intelligent, his English is fine, and their rates are good. So assuming nothing goes amiss in the meantime I’ll be hiring them to do the art for my MMOG.

An added plus is we are using the same game engine so they know exactly what format I need and can test stuff before sending it to me. They also have some programming talent so I probably won’t have to spend time explaining technical requirements.

Assuming they are able to do the work (and I have no reason to believe otherwise) this solves two problems:
1. How do I find my artists
2. How do I pay for them (in this case I can pay outright or do some programming work for them).

I have a pretty clear plan in front of me now:
Finish autopatcher and miscellaneous 2.x features on RakNet [1 week]
Load balancing and clustering plugin [1 week]
RakNet 3.0 features [1 week]
Rip out the netcode from the Reality Engine and put in my MMOG framework [4 weeks]
Work on the actual game code [6 months?]
Testing and tuning [??? months]

I have no idea how long testing will take. I’ll ship it when the game reaches critical mass. A good metric is customer retention rate. When you have customers who are still playing the game after 2-3 months and your traffic is not only increasing but accelerating then it’s a good time to ship.


Am I in the wrong line of business?

As a programmer I make a decent living. But it seems like I make a pittance compared to certain kinds of labor that you don’t even need a high-school education to perform.

Case 1:
I went to get a haircut today. The first place I went to charged $17. So I walked across the street to this place with “Salon” in the name, as if that made it any different from any place that cut your hair. They charged

  • $28 for a junior haircutter
  • $35 for an experienced haircutter
  • $40 for a senior haircutter

Plus tip of course.

Lets give them the benefit of the doubt and say that a haircut takes half an hour. The senior haircutter then makes $80 an hour (plus tip). A 15% tip adds $12 to that. Lets say that the store takes half of that $80. That’s still $40 + $12 = $52 an hour which is pretty damn good considering you don’t even need a high school education to be a barber.
Hourly Wage: $52

Case 2:
I took my wife to a fancy restaurant for our annivesary. The meal came out to be about $150 and we didn’t order wine. We took about 45 minutes but to make the math easy make it an hour (for cleaning the table and crap). There were 8 people total serviced from this waiter, including us. Assuming the average customer spends $75 on food, that’s $600 an hour on food. The wine there was between $50 and $200 per person. We didn’t order wine but the other 6 did. Assuming they each spent $75 on average on wine that’s 6 * 75 = $450. So the restaurant takes in $1050 an hour per waiter. If the waiter gets 15% of that as tip that’s $157.5 untaxed income, plus whatever their usual salary is!
Hourly Wage: $157.50 + salary.

Case 3:
Rental agents
When I was in Germany my wife and I were looking for apartments. We had a rental agent (the company got her) with us who did the following:

  • Unlock the door
  • Tell us about the apartment
  • Stand there for 15 minutes while we looked around

The apartment seemed OK. When asked the price, the agent responded something to the effect of “$800 a month, utilities included. [Pause] Plus my fee.”
Me: “Um… Fee? How much is the fee?”
Her: “2 months rent.”
Me: “So you mean $1600???”
Her: “Yes.”

Counting everything everything we spent about 40 minutes there. But to make the math easy lets make it an hour to count for incidental time incurred.
Hourly Wage: $1600

Case 4:
Real Estate Agent
This one isn’t by the hour so much as it is by the house – usually 6% of the selling price. Around here the average selling price is $750,000. That’s $45,000! I’ve read that they sometimes lower the commision rate after the first $100,000. So to give them the benefit of the doubt, lets make it $30,000. Lets say you are a discriminating client and look at 50 houses before buying one. Each house takes 1 hour to show around.
Hourly Wage: $600

Lawyers and recruiters are also overpaid according to the work they do but at least you need an education for that. These are all uneducated semi-skilled jobs, which shouldn’t pay more than $20 an hour at most.

Game Development

Sourcegear Vault is the best version control system I’ve used

I’ve said this before and I’ll say it again: The more I use Sourcegear Vault the more I like it. Nifty features I’ve been using are a right click context menu “Detect new files to add”, the ability to search file by status (such as modified), and the ability to specify difference detection by CRC or by date checked out.

Why the other source control systems I’ve used are worse:
Perforce – Doesn’t have detect new files to add. You can’t search by status through the GUI (if at all?), and differences are determined only by date checked out with the exception of undo checkout of unchanged files. Also hard to use.
Evolution – Doesn’t have a merge tool so I stopped looking.
VSS – Harder to use, although much easier than Perforce. Doesn’t support any of the features I just listed.
CVS and Subversion – Create hidden directories of crap on your harddrive. I believe this is done to avoid CRC checking and to avoid having the per-user data on the server. Whatever the reason, this is unacceptable.

I like that Vault uses a real database to store its data.

The only thing I seriously don’t like is the Microsoft tie-in. Why use Microsoft’s database rather than PostgreSQL which is free? And why depend on IIS? I still don’t understand that one. IIS is for webservers and there is no reason I can think of that you couldn’t program source control without it. Because they use a Microsoft database rather than PostgreSQL and IIS Linux isn’t supported.


The pursuit of self-interest in goverment

The reason why Capitalism works is that it is based on the pursuit of self-interest in such a way that it benefits society. All people are naturally inclined to pursue their own interests. Therefore, Capitalism works because it is based (among other things) on the natural motivations of people.

Systems fail when they do not follow the natural motivations of people. For example, government. People in government (politicians) are inclined to pursue their own interest. In theory, this corresponds to the interests of the electorate, but in practice it’s a leaky abstraction. The interests of people in government is to make laws and systems that benefit themselves and give the appearance of benefitting their constituency so that they get reelected. In practice, this is not one and the same. For example, Digital Rights Management benefits politicians, who get compensation from special interests for passing these laws, while DRM does not benefit the electorate. Therefore, DRM passes, which hurts the populace but benefits the politician. But it passes because to the uninformed it gives the appearance of helping the industry. We can’t really blame the politician because he is following his own self-interest, anymore than we can blame the lion for killing the idiot who jumped in the zoo. It’s the system that is broken.

The reason why the Judicial branch works better than the Executive or Legislative branches is because, for a judge, there is less power and thus less self-interest involved. A judge theorectically doesn’t have the power to make laws, only to interpret existing laws. So a judge has less at stake, meaning that it is harder to bribe him or her and you don’t necessarily know which judge will take your case, and even if you bribe one the judge that gets the appeal may not accept your bribe. More people involved in a process tend to give better results than fewer people and people who have different levels of self-interest tend to form a more fair group that one that doesn’t.

Since we only have two effective political parties there are only two sets of self-interested parties. Also, by definition it’s in your own interest to get into Congress (so you can benefit yourself) and it’s easier to get into Congress by being dishonest than by being honest simply because lying works better than telling the truth as long as you don’t get caught. Since only liars win elections it’s no surprise that Congress is full of liars.

So what’s the solution? I think a system of government that would work is one that works best when people follow their own interests, as long as there is transparency of information. Because as soon as you start lying self-interest doesn’t work the same way Capitalism doesn’t work when people lie and cheat.

I’m proposing nearly a true democracy. Eliminate the legislative branch entirely. Instead, ALL laws are drafted and passed through a simple majority vote by those parties that have an interest in the matter. So state laws by state and federal laws by the country. In order to prevent lying, there needs to be a simple framework:

1. Each law up for vote needs to be fully described in the voting pamphlet in a factual and neutral way (think Wikipedia), including how much it will cost you, the long term effects, who it will benefit, who supports the law, etc.
2. There can’t be any voter fraud. This means keeping out qualified voters, cheating at the polls, allowing illegal aliens to vote, etc, a lot of which people claim happened for the Presidential election for G.B. 2nd term.

The judicial system can be kept intact to review and interpret laws that are passed to make sure they are fair and non-contradictory.

The executive branch should be severely curtailed to be solely a figurehead position to represent the country. The populace should be able to kick out the President at any time with a majority vote.

Game Development

Loose coupling & tight cohesion

About 3 years ago I read “Code Complete.” One of the programming tips in the book is to make your functions with loose coupling and tight cohesion.

Loose coupling means the input and output to your function are of types that are more generic, rather than more specific. For example, an int is more generic than a UINT which is more generic than MyIntClass. A function which takes an XML file is more generic than one that takes your custom proprietary format, but is less generic than a pointer to the data in the XML file.

Tight cohesion means your function does one thing, rather than many things. Joel on Software refers to this as leaky abstractions, although he was talking about API code, it’s the same principle. A function which sends a file between two systems has tight cohesion. A function which sends data between two systems has even tighter cohesion.

Architecture design, which is what loose coupling and tight cohesion is a guiding principle of, is something you learn programming architecture. Most programmers don’t know how to design architecture – not because they are bad programmers but because most programmers don’t get to write architecture and the only way you learn is by doing. You have to be in the position of writing large programs that evolve over time and have complex parts that have interrelations and work together. This is not something you learn by simply writing a large program. It’s something you learn when your large program doesn’t extend well, or you have to rewrite systems that, or your users complain about bugs and 6 months later you can’t figure out what you wrote the first time.

This is why when I read “Code Complete” 3 years ago I understood the words and the reasoning behind loose coupling and tight cohesion but I wasn’t able to put it into practice. Even though I had been programming for years already, including some small games, I had never written a large enough system to practice these skills. RakNet is finally getting large enough (60K lines of code, excluding comments and dependencies) to where I’m learning real architecture and have some comments on this principle.

The first is that it’s easy to see when you do it wrong. When your coupling is too tight, this means your function (or class) can take one type of data, where it should be able to take another type of data that is otherwise perfectly valid. Or it takes several types of data and performs conversions between them. For example, I want to use the compression of bzip2 and the binary deltas of bsdiff. Compression and binary deltas should just take an array of bytes and a length, along with some optional parameters. However, the implementations of these tools assume your data is on a file on disk. Furthermore, they are written such that they are tightly coupled to running from a main() function, rather than implemented as a set of functions that take a structure of data and happen to run from main. So now I have several hours of headache in front of me to figure out how to decouple these tools from main and from assuming they work on disk files. I’ll have to write C++ wrapper to do this and a test-bed to make sure I got it right and so forth. A big waste of time.

An example of poor cohesion was the last autopatcher I wrote, which is part of the reason why I’m rewriting it now. The last autopatcher I wrote did quite a few things:
1. Binary diff on a set of files on one computer
2. Transfer that diff in a message representing a set of diffs for a set of files to another computer
3. Process that set and find the differences on the local computer
4. Generate a list of files based on those differences
5. Compress those files
6. Transfer those files back to the requester
7. Unpack and write those files to disk, creating directories when needed.

It did all these things, but the problem was all this functionality was contained in one class. So later on, when I just wanted to transfer a set of files and write them to disk on another computer, I basically had to do it by hand. Another time, when I wanted to compress a set of files, again I had to do it by hand. Sure, I could have looked at the code I had and copy / pasted to make things faster, but it wasn’t like I had a nice function I could just pull out (the functionality was too tightly coupled).

An architecture with good cohesion, which happens to be the way I’m rewriting it, finds the the set of minimal functional units that comprise an activity. One functional unit is generating a list of files. Another is writing a list of files to disk, taking a list of files as input. Another is transmitting that list of files over the network. Another is compressing that list of files. And so on. So that later on, when I want to use a list of files for a different purpose, I have the code already there and it didn’t matter that I originally wrote it for an autopatcher.

How do you know if you’re writing good architecture? If you didn’t have to spend some serious time thinking about the architecture, coming up with solutions, and discarding those solutions for better solutions, then you probably aren’t. Designing good architecture is hard because you are programming (in your head) in general and solving unknown problems. If you spend an hour changing the functions around for header files you are probably working on architecture. If you are writing code, you are probably not.

A good indicator of when you are using good architecture is that you are able to build up on previous successes and so accomplish a lot with much less work than if you were to write your solution from scratch. A trivial example is where you wanted to display an ordered list of names. One way to do it is to allocate an array, sort this array, and print out the names. Another way to do it is to use a previously written ordered list class that takes a template for your type, then iterate through that list. Another way is to use the same ordered list class, but extend it with a print function, and then just call that.

If you ever encounter the scenario where you have a huge problem to solve and do so with surprising ease because of something you wrote in the past you are benefiting from good architecture.

Design Patterns is a good reference to read about this subject.


Why Religion Must End

There’s an excellent article “Why Religion Must End” at this site. The author proposes that religion is the cause of a great deal of hate and strife, which seems to me to be true. The middle east has been at war for thousands of years. Right now they are killing us while yelling “God is Great” Just recently some cartoons depicting Mohammed resulted in violence and the torching of an embassy, although ironically only when we post them. The same cartoons were posted in Muslim newspapers without a peep. My neighbor moved from Egypt because of religious persecution (Muslims again). Just so I’m not picking on Muslims, the Crusades was a war driven by Christianity.

As the article points out, some of what religion proposes is good – such as the parts that propose generosity. When I was poor in Alaska my neighbor was a Mormom and he let me stay with his family for a couple of months until I found an apartment. However, rational thinking has the same effect and comes without the bad parts such as intolerance.