Hi to everyone. The first thing i'd like to do is to introduce myself in this forum. I'm a new user and a game programming beginner i'm glad to find this forum wich i'm sure it'll help me a lot on this complex and amazing science i'll start to learn. I'm developing a simple pacman game, keeping it very basic. I'm using vb.net, but of course i'm planning to move out to c++ later on. I check collision seeing if rectangular shapes wich enclosed sprites intersects each other. But there's something on it that i don't like because i think it carries poor performance. Here's the simplified version of my code: Dim ghostsVector() As Sprite 'These are sprite vectors Dim wallsVector() As Sprite Dim pacman As Sprite 'Pacman sprite ... While (true) update() 'Update characters position, z-order, etc checkGhostsCollision() checkWallsCollision() screen.refresh() 'Repaints the screen so all changes are shown End While Sub checkGhostsCollision() Dim i For i = 0 To ghostsVectorcount - 1 pacman.collide(ghostsVector(i)) Next End Sub Sub checkWallsCollision() Dim i For i = 0 To wallsVectorscount - 1 pacman.collide(wallsVector(i)) Next End Sub pacman.collide is defined as follow: Sub collide(ByVal spr As Sprite) If pacman.intersectsWith(spr.Rectangle) Then 'Here I basically see wich type of sprite it's and do actions 'relatevely to it End If End Sub The first thing I see that it's wrong with this algorithm is that I need to check collision on every sprite on the screen, and i think that it's not really necessary, because if pacman is in position (40, 40), there's no need to check if it has collided with a sprite wich is in position (300, 200) or (200, 400). I mean I want to contemplate the context of the sprite first to check (or not) if it has collided. But if the function to check the context of a sprite is slower than pacman.intersectsWith() method (wich is provided by .Net) then checking the context has drawbacks instead of improve performance. So, what do you suggest? how is it done in a 2D game? Regards.

Instead of keeping an array of wall segments, each with precise position and size, why not simply store a two-dimensional array of tile numbers. That way you test for collisions against the background simply by checking the single tile which the player/ghost is trying to move to.
Similarly instead you can let edible 'dots' and fruit be represented by special tile numbers rather than as separate objects with full positions.

As for collisions between moving objects, that is between Pac-man himself and the ghosts, I wouldn't worry about four tests per frame. VB.Net can handle many thousands of these per frame without breaking a sweat.

In more complicated 2D games you've often got one set of actors (player bullets, say) which can collide with another another set (enemies). This scales badly as each bullet needs to be tested against each enemy, so with only a hundred of each you've already got ten thousand tests to perform. This is usually optimized by first sorting the lists on either the x or y axis and then walking through both lists in tandem, easily rejecting entries in the opposite list which are to far away.

Quote:Original post by mariano_donati
I'm using vb.net, but of course i'm planning to move out to c++ later on.

Why?

First of all, welcome to GDNet :)

Quote: I'm using vb.net, but of course i'm planning to move out to c++ later on.

That doesn't necessarily have to be an 'of course'. Depending on what sort of games you want to make, it may be that some other language (or languages) would be a better choice.

As for the collision detection issue you mention, what you're looking for is generally referred to as 'broad-phase culling'. The idea (as you described yourself) is to cull pairs that cannot possibly intersect before applying a narrow-phase (i.e. 'exact') algorithm.

There are many different broad-phase algorithms, each with its own strengths and weaknesses. One thing you might consider for your 'Pac Man' game is that (typically) the walls and dots align to a grid of some sort. With a uniform grid, you could easily determine which grid cells the player is overlapping, thereby quickly determining which walls/dots the player might collide with.

As for ghost-player interaction, you can probably just get away with brute force (assuming that, as in the original game, the ghosts don't collide with each other).

There are more sophisticated methods you could apply here, but a uniform grid would probably be adequate, and would be relatively easy to implement.

After saying anything I want to thank you both for your answers, now I know what to do. In response to your questions, I must say that i'm a beginner now so I don't want to deal with more complicated languages like C o C++. I need to focus in game programming to learn the essence of it and not to mess around with aa more complex syntax, pointers, dynamic memory allocation, etc. Also, I've only done console networking client/server applications in these languages, so I really don't know how to draw images, how to repaint the screen in every game loop or make a GUI, etc. But I'm aware that if I want to get really involved with game development, I need to change to another language. I said C/C++ just because I'm familiar with its syntax and I have more knowledge compare with another languages. Then I want to move over to languages that allow me to do more sophisticated things and have a better performance regarding to game applications.
Thanks again!.

hmm, VB.NET that sounds familiar. I participated in a competition:
Scroll to the bottom.
It was coded in a few hours, but if you finish your version and want to compare it to something else then there it is. If I remember correctly iterating through all the pellets works flawlessly.

The actual map can just be a tile map.