News

News

I am adding and subtracting

LovePosted by Eskil Steenberg Sat, April 18, 2009 10:56:47
I get a fair amount of E-mails asking how to get started in game development, about my programming style and what tools and algorithms I use. With limited time to answer all questions (Some of you may remember I have this fairly large game project I'm working on) I thought I would write something here for all to read and link to. (Obviously I realize that this will come off as a an open invitation to send me more mail and and ask even more questions, but what the hell...) If you are not interested in learning about game development skip this one.

Language

First of all get yourself a book on ANSI C. When hunting for computer books the main rule is to avoid any book that is thick, because that usually tells you that whoever wrote it got payed per page so there is going to be a lot of yadi-yadi in them. O'Reilly is considerd good, so is "C Programming Language", I got started with "A book on C" and if you search around the net im sure you can find some free stuff too. People will tell you that C is old and hard to program, but that is sort of the point. Your goal shouldn't be to make something quick but rather to learn the basics. C is a small but incredibly powerful language that you will never grow out of, so learn it well rather then constantly try to find a different language that is easier. Programming is very little about the syntax, and all about what you do with it. C has a tiny syntax so you can learn it very quickly and get on with learning to do stuff with it. Some people will tell you you need C++ because it is newer and has more stuff, but in my opinion it just complicates things and tries to force you to program a specific way, rather then using the best practice for the problem at hand. Anyhow C++ is a super set of C so you will need to learn C to learn C++ anyway. I would strongly suggest not trying to learn an "easy" higher level language like C#, java, Pyhon, PHP or VB, they are bigger more complicated and they obfuscate how a computer really works and that is what you need to learn. All games are written in low level a languages like C/C++ so why not learn that? It is far easier to become a good high level programmer by learning low level programing first, then trying to becoming a good low level programmer after you have learned to program high level languages. (If anyone wants to have an argument about what language to use, please take it somewhere else, People have asked what I recommend, so I answer).

When you get started you don't really need to learn the entire language at once, just the basics. Things like macros, bitwise operations, function pointers, and goto you can leave for now.

What you need

You need to get yourself a development environment. Go with gcc on linux, X-Code on OSX or VisualStudio on Windows (I use VS6). All these are free or have free versions. If someone tells you that you need a specific editor, version, tool, hardware, or something else, they are lying and are probably not great programmers. A great programmer needs skills and that's about it, so go get some skills. Yes, your 10 year old computer running win95 will do the trick. Don't upgrade until you have written something that needs more power and even then try to optimize it first to see if it can run on your old computer anyway. having less memory and CPU actually makes you a better programmer, because it teaches you to conserve resources.

Guessing that you want to do something with graphics, I would recommend learning OpenGL; its free, its multi platform, and there is lots of documentation online that can help you. I would recommend going through some of Ne-He´s tutorials to get you started. Download some sample code, compile it, and start modifying it. This will help you understand what different things do and will let you experiment a bit. I will probably post something longer about OpenGL coding in the future.

My advice is to try to use as few libraries as possible, and try to choose libraries that are are portable. For opening windows and reading input I would recommend SDL or GLUT and for networking just use Sockets. For timing I use "gettimeofday" on UNIX platforms and the performance counter under windows. Other then that I just use the standard libraries. When you start using any library the first thing you should do is abstract it so that you can change it in the future and remain portable. I have created a module called "betray" for system specific things like input and display, that can be built against glut, SDL, or X, Win32, OSX native. It can be downloaded as part of the source to my apps in the file section.

Style


As you start programing you will notice that you need to solve a bunch of common problems, and this is where you start developing your own coding style. So let me give you some insight to my personal coding style and that I use:

I almost never use linked lists (I think there is one place in all of LOVE), and instead I try to use arrays, they are faster, smaller and more cash coherent. I avoid jumping around using pointers a lot to minimize cash misses. Many people think that this is premature optimization, buy by making it my coding style it becomes easy and natural to always write fast code. On occasion i use reallocate, reallocate has got a bad rep but it is actually very fast. If you make a big reallocate the MMU will actually make sure to avoid any big memory copies, and while it can be slow to preform it will be faster in the long run. Say you need to store 5000 integers that you need to process a lot. if you store them as a linked list, they will take up twice the amount memory due to the linked list, and they will be slow to process because of cash misses. If you need to add more more elements, an reallocation of an array may be slower, but if you over allocate so that you don't need to reallocate every time you add a single element this will be rare. Even if you over allocate quite a lot it will still be smaller then all the pointers in the linked list.

I never sort. My feeling is that if you store your data properly you almost never have to sort it. In graphics you often need to sort objects back-to-front and front-to-back and what i do is that i keep a sorted list of all objects and for each frame i do a single pass of bubble sort. I simply check is this object closer to the camera then the last, if they are i switch their places.

One trick that too few C programmers know about / use is that if you build a structure, a pointer to that structure is also a pointer to the first element of that structure. This means that you can have a pointer that points to two structures. This is very useful as you can create a header that is shared by multiple structures, that you can accessed using cast. For instance if you have 10 different types of structures describing objects in your world, they can all have the same header structure that can tell you what type of object they are and other common info like position. This is a very nice way of structuring a lot of code, and you can use it to do inheritance. I use it extensively.

I use very few comments, and while that is not something I should promote, I am promoting the idea that your code should be readable without them. I use long and descriptive function names, and try to use recurring variable names that always are used for similar things. "f" is a float, "i", "j" "k" are integer counters, "length" is the length of an array, "count" is the number of things stored in it and so on. I use what someone would call reverse notation in function names, to create a hierarchy of function names. Many people would name a function "destroy_character", where as i would name it "character_destroy". If you think about it the "destroy" is something that operated on "character" and therefor belongs to the "character" family of functions along with say "create", therefor you should first signify what family it is in and then become more precise about what you want to do with it. I use much fewer .h files then .c files and when you have a lot of functions named like this things become very easy to find, especially as your function names become longer and more descriptive as you add more prefixes. I prefix all functions with at least project, and module.

This:

void love_ai_character_create();
void love_ai_character_destroy();
void love_ai_character_update();
void love_ai_tool_create();
void love_ai_tool_destroy();
void love_ai_tool_update();

...is more stuctured then this:

void create_character();
void destroy_character();
void update_character();
void create_tool();
void destroy_tool();
void update_tool();

Math

When I was in school i wasn't a huge math person and I still I cant read any book on math. What I do have is a "feel" for it. If you do any type of graphics, you probably need to have a handle on dot products, normalization, Pythagorean theorem, cross products and simple matrices. None of this is very hard, and they are all very logical once you start experimenting with them in code. You don't really need to learn big formulas, but rather get a deeper understanding of the basic building blocks and you will be able to build your own formulas. Its important to learn the tricks, like how you can avoid the expensive square root in Pythagorean theorem if the length of the vector you are computing is only used for comparison to a value, and how simple splines can be used for animation.

Algorithms I use


In general I tend to reinvent a lot of things but some algorithms have repeatedly found themselves to be useful.

For random number generation i use the following code. Its small its fast and according to people who spend their time figuring things like this out it is a recommended algorithm.

i = (seed << 13) ^ seed;
rand = ((i * (i * i * 15731 + 789221) + 1376312589) & 0x7fffffff);

For triangle intersection I use my own version of Tomas Akenine-Möllers triangle intersection algorithem.


For pathfinding i use my own implementation of a*. You can find a good tutorial explaining a* here.

For simple image loading I use uncompressed targa files. You can implement a loader/saver in a matter of minutes.

Geometry

I do a fair bit of geometry manipulation and in order to store geometry I have devised a few things. This is all very personal but I have hardly ever found anyone who talks about this so I thought it may be interesting to give some details, at least as many other structures I have heard of are much less elegant in comparison. My geometry storage is very influenced by how verse manages geometry, but as verse mixes quads and triangles, and the data can contain holes and broken polygons, I differentiate between this data and geometry data that has been "cleaned". For verse data I store vertexes as an array, any hole in the array is signified by setting the vertex X value to MAX_FLOAT. The reference data is stored in an unsigned integer array where every group of four integers is one polygon. For a vertex reference to be valid it has to be less then the length of the vertex array times the size of the vertex and the vertex has to have a valid X value (one that isn't MAX_FLOAT). if all four reference values are valid that is a quad, if only the three first are, then its a triangle. So an reference array storing a quad and two triangles may look like this:

uint ref[4 * 3] = {/* a tri starts*/ 1, 4, 2, -1, /*a quad starts */ 0, 1, 2, 3,
/*an other tri*/, 4, 5, 2, -1};
uint poly_ref_count = 3;

Since this data can be cumbersome to manage, I create a clean version that guarantees that no reference value ever points to an illegal vertex. All quads (if quads are used) are stored first followed by all triangles. This means that you no longer have to store the illegal last reference in the triangles. A nice property with this structure is that you can feed it in to OpenGL directly and draw everything with two draw calls. A cleaned reference array for a quad and two triangles may look like this:

uint ref[4 * 1 + 3 * 2] = {0, 1, 2, 3,
/* quad ends, tris starts */ 1, 4, 2, 4, 5, 2};
uint quad_ref_count = 1;
uint tri_ref_count = 2;

This may be fine for basic poly soup storage but to be able to easily process the polygons you need to compute some data on how the geometry relates to its surroundings. There are many ways of doing this, most of them are based on complicated structures where vertices's points to the polygons that use it. I on the other hand just store one neighbour value per polygon edge, that relates to the edge it connected to. Each edge starts with a vertex, so I just reference that vertex. So the data for a quad a and a adjacent triangle becomes this:

uint ref[4 * 1 + 3 * 1] = {0, 1, 2, 3, 1, 4, 2};
uint quad_ref_count = 1;
uint tri_ref_count = 1;
uint neighbour[4 * 1 + 3 * 1] = {-1, 6, -1, -1, -1, -1, 1};

Note the symmetry how the neighbour[neighbour[1]] equals one and neighbour[neighbour[6]] equals six. Keeping the neighbour data separate is very nice since you can throw it away separately when you no longer need it. To generate the neighbour data i have invented (what i think) is a very clever algorithm you can download here. EDIT: this image may help you understand the data better:



Final thoughts


Thinking you can become a great game developer because you like games, is like thinking you are qualified to be an astronaut just because you like to travel. Astronauts spend 99% on the ground training and doing science, and if you don't have a passion for that you just wont make it. The 1% in space is really just the icing. If you don't love that act of developing games, it simply wont work. I don't advocate you trying to find the easiest way to make a game, because there is none, I instead think you should love the challenge of the hard parts of game development. Love the journey not the goal. Programming is a lot easier to love then you may think.

  • Comments(32)//news.quelsolaar.com/#post45