How to program a chess: a forum based tutorial

llvllatrix · 2005-04-02T02:01:34

Introductions (ie what the heck is this thread about): This thread was born when da_grat1 asked me about model loading. After a bit of discussion it turned out that he was trying to program a chess game and wondered if I had any advice. The result; a good excuse to talk design. Although this may seem off topic on this forum, I think nehe is best for several reasons. This forum has a wide variety of visitors, both advanced and beginner (you'll see why this is important later...keep reading :) ). I also dont have to go over OGL, which we will be using to do our graphics. Most of you have also already taken a look at some general demo design as well as loading and playing sound, which is a bonus. Also note that da_grat1 will be trying to implement this, so I'm going to try my best to keep us on topic and drive us through the end. k, so its obvious that i cant tell you that if you follow steps 1 - X you'll successfully complete your project, or game ect. (lol, its just not possible) Instead, what I want to do with this thread is to start a discussion about game design from start to where ever we take it. Consider this an online, dynamic tutorial with many authors. You guys should feel free to tell me that I'm wrong (giving a reason for your decisions is very important because we are all of different expertise in different areas). Remember that even if you feel you cannot contribute because you dont have the experience, asking questions is just as valuable (they determine where this discussion will go). Questions you guys ask will determine what issues get addressed and in what order. So sit back and get ready for what will hopefully be a long and productive discussion. I think the best place to start is at the beginning. You'd be surprised how many people dont start there. Imagine how terrible it would be if you hired a company to build you a corporate headquarters for your multi-million dollar game development studio and when you open the door, the thing crashes down on you. Then, when your in your hospital bed you find out that its because the guys who built the place didnt do any planning or draw any blue prints and just started building the place without thinking twice. The reason this kind of thing doesn't happen with building companies is because architects and engineers design and test the building long before anyone uses a hammer or saw. However, this happens all to often in software engineering; people just dont start at the beginning. They jump into projects and start coding without design documents. Remember your friend who said he would make an amazing game and ended up not finishing it? Its because when he was nailing some code together, the structure fell straight down on top of his head and he couldnt continue...anyway I tink I made my point...design twice, build once...so lets get to some code design...that and I ran out of building analogies ;) ... Programming is like chewing a pack of bubble gum. If you chew it all at once you're going to die. Its best if you divide the pack into pieces and chew each separately. There’s no guarantee you're not going to choke on a small piece but at least if you do you can probably spit it back up. So the first thing to do is establish exactly what we hope to accomplish and then keep breaking it down till we can implement it. To break it down on a business level, the "what are we going to do" is the project proposal. The "break down" is the design document/feasibility study and the implement it is "code till it works". Side trackin': In this quick paragraph I'm going to describe my tendencies when it comes to game programming. Most of the reasons for this stuff comes from code on the cob (http://www.gamedev.net/reference/list.asp?categoryid=45#115) and we'll hopefully see it used and justified further on in the discussion. Game programming (unlike word processors) are made using synthesis. We are going to take elements like graphics, audio ect and put them together to make a product. To do the synthesis I typically use function libraries as the glue that holds my program together (think OpenGL's interface). Classes and inheritance usually dont work for this kind of thing (think MFC). I'm not saying to totally abandon classes, I'm saying "use them to do a job behind a function library so that whatever uses the library doesn’t have to know about them". Keep your interfaces clean and whatever you build with them will look ok...irregardless of what is behind the interface. What are we going to do? So we're making a chess game. It will have 3d pieces that move accross the board (as apposed to appearing where ever you clicked), an animated camera, ai which you can play against (not good ai, but ai none the less), a console for testing (not as complex as you think, but it will just take a long time to implement), sound for coolness, and the ability to save your game. That sound good to everyone? How are we going to do this? Well, first step is decomposition, but what exactly does that mean? If you refer to my side track up there, why are we decomposing, shouldn’t we be synthesizing? In truth, there are actually two different phases here that use different techniques to get their jobs done. The first phase is the design phase where we decompose our problem into sub problems till we are satisfied we can tackle them. Then we go to the implementation phase where we take the easiest sub problems, solve them, and their solutions to solve larger problems till we have a final solution; our game (this is what i mean by synthesis). So what is this design thingy all about? Decomposition is the answer to the question, "how the hell am i supposed to do that?" Design is about making a decomposition that works both now and in the future (you'll see what i mean). Pop quiz: what did a software blue print look like back when king tut was writing security software for his sarcophagus (namely the 7 Egyptian curses of death)? Ans: Same as they look today ; a pyramid. On the top of the pyramid is our goal (namely, a game) and on the very bottom is stuff we know we have to use to achieve our goal (our requirements). I our case, we have stuff like OpenGL, Windows, and fmod on the bottom. At the top of our pyramid is our chess game. Let the designing begin: A quick way to start is by listing a bunch of stuff you're probably going to need. In any game, we're going to need a main screen (the thing people see when they start the game), a game screen(the game itself), a menu (drawn over the screen), a way to tell if the game is over, a way to tell what screen gets input, a way to get the input, a way to keep track of time, a way to draw objects as apposed to triangles, a way to easily play a sound, a way to load files, a way for the ai to think, a way to control the camera, and a whole bunch of other stuff. The next thing to tackle is to organize this stuff in a pyramid and then fill in the gaps where we need to. We then keep doing this (decomposing these subsystems) till we can implement each subsystem without having to decompose it. So the next thing to tackle is to rearrange the subsystems i've listed (as well as others you guys come up with) into the pyramid and this i'm going to leave to anyone with time on their hands (this is a good exercise to do) or to my next post (which ever comes first). will post later, - llvllatrix

NeHe Productions Affiliates

Started by llvllatrix December 23, 2004 11:09 PM

276 comments, last by da_grat1 19 years, 8 months ago

llvllatrix

Author

340

January 03, 2005 05:35 PM

Its time to make some time ;)

So what exactly is a clock and what is it for? Let me answer that with a question. Have you ever programmed a demo that you thought was flawless and then run it on a faster computer only to have your jaw drop? This is because the duration between frames in a program (in our case the time it takes for our main while loop to repeat itself) is different from pc to pc. It can also change drastically while the program is running (ie when you break the program for debug). The clock we design will hopefully solve our update problems by providing a constant time reference for every frame.

If your familiar with nehe's basecode you'll notice that time is kept in an update function by a millisecond counter. Why change? A few reasons. The clock subsystem should address these issues, and once done you should be able to reuse the clock for any further project you do...exceptional cases like mmorpgs outstanding...

The structure of a clocking subsystem is fairly simple. There is one main counter for the entire game called the game clock. You then create timer classes that use the game clock's values to update their own counters. I usually stick with two types of timers, the forward timer and the count down timer. Why do we need timers when we can use the game clock for everything? Two reasons. First reason: timers reduce code duplication. There are going to be situations when you are going to want to know (or only care about) the time from or to a given point in time. Solution: the forward and count down timers. Second reason: independent time control. This way you can pause certain parts of your game without affecting others. For example, you can pause the animation in the chess game and still have your camera animate freely.

At any point in the game you can run into an incredibly long frame. This can be caused by a number of reasons like disk access or breaking the execution of the game. You are going to want to intercept these artifacts in the game clock. The simplest solution is to put a cap on how long a given frame can last. A good cap is 200-300 ms, which is about 3-5 frames per second.

The last issue to deal with when designing a clock is precision. Nehe's basecode uses integers to store the number of milliseconds that have elapsed between frames. While this is handy for demos, games tend to need more precision. Heres why:
- at 60 frames per second one frame lasts 16.66667 milliseconds,
which cant be represented by integers
- its hard to use ints when dealing with physics and animation
- ints can only store about 50 days worth of updates
While floats seem like the obvious choice, they tend to loose prevision very quickly (because you are continuously adding to them). After about five hours, they become less precise than ints. The only scalable solution is a double.

Implementation details:
Game clock:
- I recommend using a set of functions.
- The clock needs initialization, de-initialization, and update functions.
- When you call the update function (at the start of every frame), the
game clock queries the operating system for the current time.
- The only other function the game clock should have is one that lets you
query for the current time in a frame.
- Search the MSDN (msdn.microsoft.com) for details on using a precision
timer.
- You may not want to expose the game clock globally. Not doing so enforces
the use of your timer classes.
Forward timer:
- I recommend using a class
- The forward timer keeps track of time from a given point
- That point which can either be supplied by the creator or grabbed from
the game clock at the time of creation.
Count-down timer:
- I recommend using a class
- The count down timer accepts a duration from which to start counting.
- You should be able to query the timer for the remaining time.
- You should also be able to query the timer for a bool indicating if the
time is up.

...and that’s it :) Now you should be ready to implement a full blown timing subsystem of your own. Next we will start chipping away at our resource manager. In particular, we will tackle a sound wrapper that uses fmod (www.fmod.org)...unless you guys want to use OpenAL?

Will post later,
- llvllatrix

da_grat1

122

January 04, 2005 05:58 AM

Quote: The last issue to deal with when designing a clock is precision. Nehe's basecode uses integers to store the number of milliseconds that have elapsed between frames. While this is handy for demos, games tend to need more precision. Heres why:
- at 60 frames per second one frame lasts 16.66667 milliseconds,
which cant be represented by integers
- its hard to use ints when dealing with physics and animation
- ints can only store about 50 days worth of updates
While floats seem like the obvious choice, they tend to loose prevision very quickly (because you are continuously adding to them). After about five hours, they become less precise than ints. The only scalable solution is a double.

Wow I learn many things here... I am such a newbie.. :)

llvllatrix

Author

340

January 04, 2005 10:04 AM

Hey guys,

I decided to implement the subsystems we've been discussing. It would be neat if we did a series of tutorials where we used our engine to do more and more complex games...just and idea :) Anyway, heres my implementation of the context manager:

cntx_man_context_manager.h

#ifndef __CNTX_MAN_CONTEXT_MANAGER_H__#define __CNTX_MAN_CONTEXT_MANAGER_H__//----------------------------------------------------------------------------////cntx_man_context_manager.h////Copyright © Rishi Ramraj, 2004// A context can be either the main screen, the game screen, the menu or the // console. When no contexts exist on the context stack the game is over.//----------------------------------------------------------------------------//··········································································////    header :: Inclusions//··········································································////··········································································////    header :: Definitions//··········································································////··········································································////    header :: Structures//··········································································////··········································································////    header :: Class Defs//··········································································////··········································································////    header :: Function Defs//··········································································//// cntx_man_is_context_on_stack// Returns true if there are any contexts on the context stack, false otherwise.// When no contexts exist on the context stack the game is over.bool cntx_man_contexts_are_on_stack();// cntx_man_push_context// Creates a new context and adds it to the top of the context stack. Returns a // unique id (thanks shadowwz :) ), cntx_id, of the context added.int  cntx_man_push_context();// cntx_man_pop_context// Pops the context specified by cntx_id off the context stack and returns true// on success. If the context specified is not on the top of the stack then it // is not popped and false is returned.bool cntx_man_pop_context(int cntx_id);// cntx_man_is_context_in_focus// Returns true if the specified context is on the top of the context stack,// false otherwise.bool cntx_man_is_context_in_focus(int cntx_id);//----------------------------------------------------------------------------//cntx_man_context_manager.h//Copyright © Rishi Ramraj, 2004//----------------------------------------------------------------------------#endif //__CNTX_MAN_CONTEXT_MANAGER_H__

cntx_man_context_manager.cpp

//----------------------------------------------------------------------------////cntx_man_context_manager.cpp////Copyright © Rishi Ramraj, 2004//----------------------------------------------------------------------------//··········································································////    Source :: Inclusions//··········································································//#include <vector>using namespace std;#include "cntx_man_context_manager.h"//··········································································////    Source :: Definitions//··········································································//typedef vector<int> context_vector;typedef context_vector::iterator context_iterator;//··········································································////    Source :: Structures//··········································································////··········································································////    Source :: Class Defs//··········································································////··········································································////    Source :: Private Function Defs//··········································································////··········································································////    Source :: Private Vars//··········································································//// uid = unique id// uids start counting from 1, not 0int context_uid_counter = 0;// The end of the stack maps to its topcontext_vector context_stack;//··········································································////    Source :: External Function Implementation//··········································································//// cntx_man_is_context_on_stack// Returns true if there are any contexts on the context stack, false otherwise.// When no contexts exist on the context stack the game is over.bool cntx_man_contexts_are_on_stack(){	//Returns true if the size of the stack is not zero	return !context_stack.empty();}// cntx_man_push_context// Creates a new context and adds it to the top of the context stack. Returns a // unique id (thanks shadowwz :) ), cntx_id, of the context added.int  cntx_man_push_context(){	// Increment the uid counter to get a new unique id	context_uid_counter++;	// Push the current context uid onto the stack	context_stack.push_back(context_uid_counter);	// Return the uid	return context_uid_counter;}// cntx_man_pop_context// Pops the context specified by cntx_id off the context stack and returns true// on success. If the context specified is not on the top of the stack then it // is not popped and false is returned.bool cntx_man_pop_context(int cntx_id){	// If the passed id is not in focus then the context cannot be popped	// because there are other contexts above it that need to be popped first.	if(!cntx_man_is_context_in_focus(cntx_id))		return false;	// pop the passed context off the end of the stack and return successfully.	context_stack.pop_back();	return true;}// cntx_man_is_context_in_focus// Returns true if the specified context is on the top of the context stack,// false otherwise.bool cntx_man_is_context_in_focus(int cntx_id){	// If the last entry in the stack equals the specified id then return true.	return context_stack[context_stack.size() - 1] == cntx_id;}//··········································································////    Source :: External Class Implementation//··········································································////··········································································////    Source :: Internal Function Implementation//··········································································////··········································································////    Source :: Internal Class Implementation//··········································································////----------------------------------------------------------------------------//cntx_man_context_manager.cpp//Copyright © Rishi Ramraj, 2004//----------------------------------------------------------------------------

lol, I decided to change the abbreviation of the subsystem as per Enigma's suggestion :) I did a bit of testing and things seem to be functioning properly, but if you have any free time a quick unit test would be awesome :D (Its always best to catch bugs asap). If you have any questions, concerns, comments or querys feel free to post. Next, I'll implement our clock and get things ready for our sound loading module.

Will post later,
- llvllatrix

Enigma

1,410

January 04, 2005 11:19 AM

Quote: Original post by llvllatrix

int context_uid_counter = 0;// ...int  cntx_man_push_context(){	// Increment the uid counter to get a new unique id	context_uid_counter++;	// Push the current context uid onto the stack	context_stack.push_back(context_uid_counter);	// Return the uid	return context_uid_counter;}

If the context_uid_counter is only supposed to be used by one function it would probably be better to encapsulate it within that function:

int cntx_man_push_context(){	static int context_uid_counter = 0;	// Increment the uid counter to get a new unique id	context_uid_counter++;	if (context_uid_counter < 0)	{		throw std::overflow_error("context_uid_counter");	}	// Push the current context uid onto the stack	context_stack.push_back(context_uid_counter);	// Return the uid	return context_uid_counter;}

I also added a check for overflow.

Quote:

bool cntx_man_is_context_in_focus(int cntx_id){	// If the last entry in the stack equals the specified id then return true.	return context_stack[context_stack.size() - 1] == cntx_id;}

Consider what would happen if you tried to pop the last context twice.

bool cntx_man_is_context_in_focus(int cntx_id){	// If the last entry in the stack equals the specified id then return true.	return cntx_man_contexts_are_on_stack() && context_stack.back() == cntx_id;}

Enigma

llvllatrix

Author

340

January 04, 2005 03:22 PM

// The end of the stack maps to its topcontext_vector context_stack;

...should be...

// The end of the stack maps to its topstatic context_vector context_stack;

Quote:
Consider what would happen if you tried to pop the last context twice.

Never thought of that...thx Enigma :) Do you know if most systems support performance timers?

da_grat1

122

January 05, 2005 07:52 AM

llvllatrix...

Is it possible to run the code already...
when i tried to build it, this error came out..

Linking...
LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main
Debug/cntx_man_context_manager.exe : fatal error LNK1120: 1 unresolved externals
Error executing link.exe.

What should I do...what should i do >_<

llvllatrix

Author

340

January 05, 2005 11:08 AM

Hey Guys,

Busy at the moment but I should have time for a short post.

If you've never seen a declaration like vector<int> then your missing out on a fairly big part of c++, namely templates. I recommend researching the STL or Standard Template Library. This library provides you with a bunch of useful programming structures like linked lists (called vectors) all the way up to databasing structures. If you like what you see in the STL you can also research templates to create your own (kinda like containers for your classes).

While programming the clock I discovered two subsystems that we should probably have in our engine. First is the inc_ or inclusion subsystem. This subsystems lets us include things like opengl, windows, and fmod. Why not just include them in our cpp files? In the case of opengl and fmod, we want to link to .lib files when compiling. Having the preprocessor declarations in a centralized header means that everything else that uses this header will naturally use the right declarations (same principle behind using a const). The reason we have windows.h in its own header is exposure. Someone else may want to port our code, and having windows exposed in inc_os_system_sdk.h makes is very easy to find and subsequently change every where else.

The second subsystem I discovered is an error reporting subsystem. If anything wrong happens, we're going to want to report it to either the user or the developer. There are several ways of reporting an error, depending on its severity. If, for example, you cant load a particular sound then the game can continue and all you really need to do is use the games menu system to report the error. On the other hand if the error occurs early in the initialization then we're going to have to use windows to report the errors because our display system has not been loaded. Errors like this usually mean that something very wrong has happened and the game cant run (ie no performance timer). This is the kind of error we're going to have to deal with now because we are currently developing the lower level systems.

There are a few issues to work around when dealing with errors at this level. lol, in my first engine I made the mistake of thinking that it was as simple as calling a message box when an error occurred. While this is fine before you start OpenGL, it can be cumbersome afterwards to say the least. For example, say you have already switched to full screen and an error occurred, what would happen if you called a message box and then tried to de-initialize? Your program would be minimized to let the message box display and then your system would try to destroy the window. In the best case scenario things would be ok or your desktops properties would be messed up. In the worst scenario you may end up crashing windows. So we have to de-initialize first and then tell the user that something wrong happened.

The way this is typically done is by passing the error to higher and higher layers of execution. For example, if a function init called init_clock and init_clock failed it would tell init what the error was and hopefully init would do something about it (and tell the user). Unfortunately, this style of system has several problems:

1. A lower level system never has any guarantee that the higher level system
will do anything about the error.
2. Multiple occurrences of the same error could be reported. For example, say an
error occurs with init_clock and it posts an error to the user. The init
function also notices that init_clock fails and reports this to the user.
Then the start_game function notes that init fails and reports this error as
well. 3 errors are reported when we really only want one.
3. The higher the error gets passed the more general the report becomes. For
example, if the init function from the previous example was called by a
function called start_game then the following might occur. init_clock fails,
which causes init to fail. init reports its failure to start_game but
start_game cannot tell that it was the init_clock part of init that failed.
start_game's functionality really only cares that init failed.
4. A subsequent problem of the previous is that errors are not reported where
they occur. This is important feature when you debug your program because
the closer the error report is to the problem, the easier it is to search
your code for the failure.

I propose a system that will let us post our errors where they occur and store them until it is safe to display the errors to the user. The main problem this approach solves is #3 and by extension #4. We can easily get detailed information and if we design the system correctly we can also produce debug and release error messages (so that we can display a general message to the user and a technical one to the developer). This still does not solve #1 or #2 but it does help. For problem 2, we can state that as a general policy, errors should be reported only where they occur at the bottom level and no where else. This way the only error we get reported is the one that caused the crashed. #1 is a tricky problem to solve because there is no way around having the higher level post the error. The higher levels of a program are responsible for reacting to a failure. That said, they must first de-initialize the system and then post the errors (as we discussed). The advantage that our error posting subsystem affords us is that it centralizes our error posts to one function (as apposed to a distribution of error posts throughout the program). This sort of error posting system does have its drawbacks however. There may be situations, for example, where you are going to have to call our error posting function more than once in different parts of our program. I think we will be able to deal with these problems as they occur. That said, I think this system is worth a shot. Can you guys think of any other problems with this system? (I love this thread; its like having one massive code review session :) )

Anyway, I'm off to implement this system and then the clock. I'll also try to get the sound loading subsystem up and running for the next post.

Will post later,
- llvllatrix

llvllatrix

Author

340

January 05, 2005 11:11 AM

Quote:
llvllatrix...

Is it possible to run the code already...
when i tried to build it, this error came out..

Linking...
LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main
Debug/cntx_man_context_manager.exe : fatal error LNK1120: 1 unresolved externals
Error executing link.exe.

What should I do...what should i do >_<

Not yet. You can include the files in your console basecode, however, and do unit tests on it to make sure it can run. I'll post my source tree to let you take a look at what a unit test looks like :)

The error you get means that there is no int main(void) function.