Gamedev tip #2 : Divide and conquer

Image via Wikipedia

Even today, I am overwhelmed by the difficulty in creating a video game. Since the first years I learned how to program it seemed like a relatively easy task. Ok. I could draw a teapot on the screen. I could play sounds and music. It was ridiculously easy to see what keys was the user pressing, to read a file from disk and what not.

It’s not about the lines of code

So why is making a game more difficult than the sum of all these? This is something I found out the hard way! The relationship between the size of a project and its difficulty is not linear. Games today are usually large projects with a magnitude of tens to hundreds thousands lines of code. Thus, creating an average game today presents a challenge that requires taking a very different approach than someone is used to when dealing with small scale projects.

When a project grows, its difficulty grows not with the lines of code, but with the number of interactions that exist between the various parts of the code. These interactions must be taken into account all the time. Let us define a fully unstructured project as one in which every part of the code is able to interact with every other part. In that case these interactions are not proportional to the project’s size, but to its square.

Someone with background on algorithms can easily see where this is going… When a project is not structured, it becomes increasingly difficult to manage, until it eventually reaches a point where any addition or change becomes prohibitively troublesome.

Fortunately there exists a solution, but it requires a somehow different mindset than the one we are used to when working with small projects.

High level design

Apologizing in advance to all the people who have devoted their lives to software development and have read and written dozens of books on the subject, I am just going to say here what in my opinion is most important with respect to our context:

High level design is all about separating a large project into logical parts which are mostly independent from each other. Ideally this way we can treat every part (or module) as a small program. The keyword here is “independent”, and represents the change in mindset I was talking about earlier.

When working on a small project, we are most concerned about writing the least amount of code possible  in order to achieve our goal. As a result we focus more on reusability and we try to reuse pieces of code regardless of where in the code they exist. In essence there is no distinction between parts of code. Everything belongs to a single entity, our program, which we can manage as long as it stays small.

On the other hand, when we design something bigger, our first concern is different. We must focus on making sure that the project ever gets completed. And to achieve this we have to find a way to fight its tendency to become harder as it grows. We saw that this tendency springs from the interactions between code rather than the size of the code itself.

Preparing for a large project

So how do we deal with these interactions? Its simple: Forbid them! This is what high level design is all about. Forbiding interactions (or dependencies) between modules. The first step is to divide our code to logical parts our program will consist of. For example: graphics, sound, math, input, game logic.

We then document which modules will be allowed to depend on each other. For instance it must be obvious that graphics must not depend on sound. But there are more subtle cases. Does the sound module need to depend on math? Modern games feature 3d sound with various sound sources placed in different positions in the game world. Setting their position and velocity using a vector class might seem like an attractive idea:

sound_source->SetPosition(Vector3 pos);

How elegant is that. However is that enough to support the addition of one more dependency? The answer is no. Every dependency between modules must justify its existence beyond any doubt. We could have easily avoided the dependency like this:

sound_source->SetPosition(float x, float y, float z);

Maybe not as appealing as the former, but its not so much more troublesome either, and its enough to get rid of a dependency which is our very first priority here.

There will certainly be situations where its difficult to decide if a dependency is justified or not. I have a rule of thumb for these: “When in doubt, forbid!“, and here is why:

• Dependencies are evil! Believe a man who has suffered!
• If you are in doubt, you are probably already thinking about a way around the dependency. If that way was not easily implementable, you would not have been in doubt in the first place.
• Even if you took a wrong decision, adding a new dependency is always easier than removing an already existing one.

So to summarize:

In order to give a large project a hope of ever being completed, we must divide it into small entities and forbid as many dependencies between them as possible.

I intended to add more here about my own frightening experiences, in order to show how troublesome can underestimating dependencies be, but this post already exceeded the size of a “tip”. So I will be postponing the terror for my next tip about unit testing which is somewhat related anyway.

Set your modules free!

Related Articles

• Redundancy vs dependencies: which is worse? (yosefk.com)

Using custom I/O callbacks with ffmpeg

Image via Wikipedia

Video playback in Conspiracies 2 is based on ffmpeg, which is a very fast and easy to use library. I got better results than using DirectShow with less effort and not to mention my video playback code is going to compile everywhere!

Following this tutorial got me started immediately. After an afternoon of coding I had a decent video player running. This tutorial shows you how to play videos from a file in the filesystem. What I needed was a little bit different though. All the assets of the game (including videos) exist in a “virtual file system” in archives. So I need to provide my own I/O functions for reading them. ffmpeg provides this functionality but it is a little bit tricky to figure out, so I thought I’d write this guide here for future reference. Thanks to the kind people at libav-user mailing list who helped me sort this out!

Implementing the I/O routines.

There are 3 routines you need to impement:

int ReadFunc(void *opaque, uint8_t *buf, int buf_size);

This function must read “buf_size” number of bytes from your file handle (which is the “opaque” parameter) and store the data into “buf”. The return value is the number of bytes actually read from your file handle. If the function fails you must return <0.

int WriteFunc(void *opaque, uint8_t *buf, int buf_size);

This is optional and behaves like the ReadFunc.

int64_t SeekFunc(void *opaque, int64_t offset, int whence) ;

This function is like the fseek() C stdio function. “whence” can be either one of the standard C values (SEEK_SET, SEEK_CUR, SEEK_END) or one more value: AVSEEK_SIZE.

When “whence” has this value, your seek function must not seek but return the size of your file handle in bytes. This is also optional and if you don’t implement it you must return <0.

Otherwise you must return the current position of your stream  in bytes (that is, after the seeking is performed). If the seek has failed you must return <0.

Opening your custom stream.

So when you need to open a custom stream for reading you must do the following:

• Allocate a buffer for I/O operations with your custom stream. The buffer’s size must be (n + FF_INPUT_BUFFER_PADDING_SIZE), where n is the actual useful buffer size.

• Allocate a new ByteIOContext object and initialize it by calling init_put_byte():
  

  int init_put_byte	(	ByteIOContext *	s,
  		unsigned char *	buffer,
  		int	buffer_size,
  		int	write_flag,
  		void *	opaque,
  		int(*)(void *opaque, uint8_t *buf, int buf_size)	read_packet,
  		int(*)(void *opaque, uint8_t *buf, int buf_size)	write_packet,
  		int64_t(*)(void *opaque, int64_t offset, int whence)	seek
  	)

  s is a pointer to your ByteIOContext object.
  buffer is a pointer to your allocated buffer
  buffer_size is “n” (the useful portion of your allocated buffer)
  write_flag must be zero if your stream does not support writing
  opaque is a pointer to your custom file stream. This is going to be passed to your custom routines.
  read_packet, write_packet and seek are pointers to your custom routines. write_packet is optional (it can be NULL)

• Use av_open_input_stream() instead of av_open_input_file() to open your stream:
  

  int av_open_input_stream	(	AVFormatContext **	ic_ptr,
  		ByteIOContext *	pb,
  		const char *	filename,
  		AVInputFormat *	fmt,
  		AVFormatParameters *	ap
  	)

  ic_ptr, filename, fmt and ap are the same parameters you use with av_open_input_file().
  pb is your initialized ByteIOContext object.

Closing your custom stream.

• When you are done with the stream call av_close_input_stream() instead of av_close input_file().
• Deallocate your ByteIOContext object.
• Deallocate your buffer.

That’s it! Everything else is the same as with av_open_input_file().

Edit: Actually there is more to it.  av_open_input_file automatically probes the input format. With av_open_input_stream you must do this yourself and pass av_open_input_stream a valid AVInputFormat pointer.  Probing the input format is easy: You just fill a buffer with some bytes from the beginning of your stream and you pass it to av_probe_input_format() which hopefully recognizes the input format and returns the pointer needed. Here is my probing code:

AVProbeData probe_data;

probe_data.filename = filename;

probe_data.buf_size = 4096; // av_open_input_file tries this many times with progressively larger buffers each time, but this must be enough

// allocate memory to read the first bytes

probe_data.buf = (unsigned char *) malloc(probe_data.buf_size);

// read first 4096 bytes into buffer

// …

// probe

AVInputFormat *ret = av_probe_input_format(&probe_data, 1);

// cleanup

free(probe_data.buf);

probe_data.buf = NULL;

return ret;