As another answer stated, the problem you re seeing is called "tunneling" It s the "bullet through paper" problem, the bullet is moving fast, the paper is thin, how do you know that a collision happened?

It s easy if your world boundaries are simple. E.g. in Tetris, the blocks are only allowed to move left and right until they hit the sides, and it s easy to test if the bottom-most coordinate is hitting the "ground." These tests are simple because you can do one axis at a time, and collisions against the sides means something different than collisions against the bottom of the pit. If you have a rectangular room, just "stop" the moving object if its movement has put it outside the room by clamping its coordinates. I.e. if the room width is from -3 to +3, and your object has an X of 5, just change it to 3 and you re done.

If you want to handle more complicated worlds, it s a bit trickier. You ll want to read up on "swept" geometry collision. Basically, if you have a circle, you need to do collision tests with a capsule instead, the shape that would be made by "sweeping" the circle from its start point to its end point. It ll be like a rectangle with semicircles on either end. The math is surprisingly straight forward (IMHO), but it can be tricky to get it right and to truly understand what s going on. It s worth it though!

Edit: On the thread issue- no need to complicate things. One thread is fine. Skipping update frames can get messy too, and is pretty advanced since you actually need to figure out "the future" and then do interpolation of all interesting values up to that point. I don t call it the "render" loop, myself, as the render loop is just one part of the process.

def GameLoop():
   while True:
      ReadInputs()
      FigureOutWhatStuffDoes()
      DrawItAll()

Edit 2: This seems like an interesting discussion: http://www.gamedev.net/community/forums/topic.asp?topic_id=482397

If you create a separate thread for this you also create a lot of complexity that you might not want to deal with. It s easy to handle with one thread and one loop.

Basically what you want to do is have a loop that does both logic and rendering, but not necessarily in every iteration. See this pseudo-code:

while(true) {
   oldTime = currentTime;
   currentTime = systemTime();
   timeStep = currentTime - oldTime;

   // Only do logic x times / second
   if( currentTime > lastLogicTime + logicRefreshTime ){
      doGameLogic( currentTime - lastLogicTime );
      lastLogicTime = currentTime;
   }

   // Extrapolate all movements using timeStep
   renderGraphics( timeStep );

   wait( screenRefreshTime );
}

void doGameLogic( timeStep ) {
   // Update all objects
   for each( gameObject obj )
     obj.move( timeStep );
}

Let all solid movable objects inherit the class SolidObject. When you call SolidObject.move(timeStep) that method checks to see how far the object can be moved within the given timeStep. If there is a wall before this point then the object should stop, bounce and change direction, die or whatever you like.

Edit:

If two objects move you might want to check if and where they collide. Lots of games don t do this very well, but here s how you do it:

First calculate the line of movement between the oldTime and the currentTime for every object that moves. Then compare the lines to see if two lines intersect. Note, you need to take the objects size into account. The intersection point is where the objects collide. Using this method you can accurately detect collisions of moving objects.

It is possible to have a separate update-thread and a drawing-thread, but it isn t easy! Usually you ll need to do a lot of mutex checking to prevent multithreaded access to the same variables so this isn t really viable (plus you don t want to handle with half-updated states). For a correct implementation you indeed need to have some form of snapshot of the last render state. If you don t mind the difficulty involved, there is a good implementation that van be found here:

http://blog.slapware.eu/game-engine/programming/multithreaded-renderloop-part1/

http://blog.slapware.eu/game-engine/programming/multithreaded-renderloop-part2/

Don t let naysayers discourage you. It is possible, it is viable and efficient. The only downside is that it is very difficult to implement and therefore probably not worth your time (unless you have a very CPU-heavy game).

Don t thread it -- you ll cause more problems than you ll solve. You can thread things and separate logic updates and rendering, but it s tricky to get right and large portions of game loops are inherently single-threaded.

Instead, look into advancing your game loop using a delta time to scale things so that the logic update is largely independent of the machine s ability to chomp through the frames.

In simplified terms, if you use a delta to scale things, regardless of how long it takes to get through a frame, a ball moving from one side of a room to another will take the same amount of time to do it on a really fast PC and a slow one.

E.g. If a ball moves 10 units in one second and you can determine that 0.1 seconds has passed since the last update (use the high performance timer or whatever is available to you), you simply scale the movement by 0.1 and the ball moves 1 unit.

E.g.

private const float BallSpeedInMetresPerSecond = 10;

public void Update(float deltaTimeInSeconds)
{
    float adjustedSpeed = deltaTimeInSeconds * BallSpeedInMetresPerSecond;
    // set ball s speed / move it etc. using adjusted speed
}

This won t entirely solve your problem (if something is really fast, it s going to get stuck in walls regardless!), but it is a simple and effective way to keep things predictable and consistent until you get into more complicated problems.

If you get that working and then want to solve a more complicated problem, as dash-tom-bang said, look into swept collision detection.

I was thinking that I should have a separated thread for the game logic and in the render loop, I should just "take a snapshot" of the current game logic and display that, no?

There is no way that is simple, safe, and fast to take a snapshot of a massive lump of game state. You can double-buffer it, which is probably the next best thing. But it doesn t fix the problem anyway, so no, you wouldn t do this, at least not for this purpose.

Let s say I have a ball with X=0, and a wall in X=10 and in a slow machine, the first loop places the ball in X=7 and in a second loop, it places the ball in X=14. It would just crash the game!

Threading the two wouldn t solve this, unless you could guarantee that every single computer you used would always be fast enough to check X=1, X=2, X=3... X=10. You can t make this guarantee. And even if you could, it s rare to use integer numbers for positions. Can you iteratively check X=0.0000001, X=0.0000002, X=0.0000003 ... X=0.9999999, X=10.00000 ? Nope.

How do you guys, experienced game developers work around this?

We typically still have one loop. input, update, render, repeat. Collision problems as you mention are solved by using a collision detection method that calculates the area that the object would pass through, eg. resolving for X=[0 to 17]. On a really slow machine it might be X=[0-50] and on a fast machine it might be X=[0-5] followed by X=[5-10], but each will work as expected.

From my limited experience in game design and AI I would say to have a logical loop and a display loop (much like XNA sets up). The logical loop (Update method in XNA) will basically handle updating positions and what not, while the display loop (Draw method in XNA) will draw everything to the screen. As for collision detection, I would personally localize that to your ball. When it moves have it look for collision and react appropriately.

Threading is another topic, but in my opinion I would say not to seperate the update and draw. It just seems intrinsically wrong to me to potentially have 2 draws for 1 update or vice versa. Why draw if nothing has updated... or why update multiple times before showing the user what is happening.

Just my opinions, hope I m not way off base.

If logic updates are usually cheap, and rendering is occasionally expensive, the easiest thing to do is decide to have N logic updates per second. N=60 is common -- but you should just pick the smallest value that lets the game work well, pick a value and tweak the game until it works at that rate, or (more likely) some combination of the two.

At runtime, keep track of time actually elapsed, keep track of how much time has logically elapsed (in terms of updates performed), and when there s more than 1.0/N seconds of discrepancy (because the rendering is taking too long) perform extra updates to catch up. This is better than than trying perform an arbitrary period of time s-worth of updates in one go, because it s more predictable. (Should the reader disagree, they are welcome to find this out the hard way.)

The disadvantage of this system is that if the rendering becomes particularly time-consuming, and the logic has to perform too many updates because of this, the two can get a bit out of sync, and the logic will never catch up. If you re targetting a fixed system, this just indicates that you re trying to do to much, and you ll have to somehow do less, or (if this situation is likely to be rare) just dump the whole idea and do a 1:1 render:update. If you re targetting something variable like a Windows PC, you ll just have to clamp the number of catch-up logic updates, and hope that this will let things get back in line.

(If the logic is more expensive, this approach isn t appropriate; I ve never worked on a game where this was a problem, though.)