2D Game Theory w/ SFML

[Lox]

Hey,

I'm developing a sort of framework for my 2D games with SFML .NET.  I would like it to be more of a generic framework.  I am, however, running into a few performance issues.  Here are some methods I am using which I am concerned with:

Collisions: Every frame I loop through each object to see if it collides with any other object in the scene (2 loops) and I do a bounding-box-type test (and then enter into pixel-perfect).  Recently I implemented a "hascollisions" property that filters out all objects in the first loop that don't have anything to do when they collide with something, which has greatly improved my performance.  Is there another way?

Drawing:
Every new object has its own image (stores its own sprite).  This gets complicated when i have 100+ objects on screen.  Would it make more sense to have 1 sprite and move it around to each object's position, load in the object's image, and draw it instead of drawing individual sprites?

I also try to implement a sort of "culling".  If objects are outside of the screen, they are not drawn.  However, I feel like the way I am doing it may be inefficient:

Code: [Select]

drawSpr = (Sprite)objList[i].resources["imgmain"];
                        collider = new SFML.Graphics.FloatRect((float)drawSpr.Position.X, (float)drawSpr.Position.Y, (float)drawSpr.Position.X + (float)drawSpr.Width, (float)drawSpr.Position.Y + (float)drawSpr.Height);
                        if (SFML_WINDOW.GetView().Viewport.Intersects(collider))
                        {
                            SFML_WINDOW.Draw(drawSpr);
                        }

^This runs every frame.  I am not very familiar with SFML so I don't know if there is a better way.

These are a few of my main concerns.

Are there any articles or projects that you would recommend I take a look at in order to better-aquatint myself with common practice?

Thanks,

Lox

[Nexus]

Collisions: Every frame I loop through each object to see if it collides with any other object in the scene (2 loops) and I do a bounding-box-type test (and then enter into pixel-perfect).  Recently I implemented a "hascollisions" property that filters out all objects in the first loop that don't have anything to do when they collide with something, which has greatly improved my performance.  Is there another way?

Don't check every object with every other object, this has quadratic complexity. And especially don't do it twice (two cascaded for loops running each from 0 to #elements-1 do that). You can use some sort of graph/quadtree/map/... to group elements that are close to each other. Then you only check collisions inside a group and between its immediate neighbors, but not between distant groups.

Drawing:
Every new object has its own image (stores its own sprite).  This gets complicated when i have 100+ objects on screen.  Would it make more sense to have 1 sprite and move it around to each object's position, load in the object's image, and draw it instead of drawing individual sprites?

Sprites are cheap to process, images are heavy. Do you really need a distinct image for each object, or can you share images?

I also try to implement a sort of "culling". If objects are outside of the screen, they are not drawn. However, I feel like the way I am doing it may be inefficient

Maybe you could apply some ideas of the first paragraph to this problem, too. If an object enters the screen, store it in a special group; if it leaves, remove it. Only draw objects in the screen group. To avoid checking every object, you could filter candidates that are close to the window border and that are likely to enter/leave the window soon.

But you should measure time (with SFML or a profiler) to make sure you are optimizing the right parts.

[Lox]

Thank you very much.  This is an interesting post.  How would you recommended I approach this "grouping" method?  Images will be of varying sizes as well as varying distances to each other.

I looked up "quadtree" and found some very interesting results.  I found a great article on codeproject.  The DLL provided supports a sort of "quadtree query", which I can use by querying the bounds of the object's image as well as selecting the viewport.  I hope that I can query for specific quadtrees as well. Do you have any other recommended references?

In terms of the culling system, I am moving the view around meaning every time the view moves (and depending on the library if an object moves), I would have to recalculate the to-draw list.  Do you think that will affect the performance? I imagine the benefits will scale with more objects.  I guess my main question is if querying the quadtree is really cheap.

Thanks for that great post, it's really opened my eyes to some new ideas.

EDIT: What happens when an object moves out of the quadtree?

[Groogy]

Do you have any other recommended references?

Me . No but the technique is called Spatial Partitioning and a simple google should find what you need. Though I think most techniques are ment for 3D but it's fairly simple to remove one dimension so it works for 2D instead.

You also have to remember that some of these techniques only work for static environment(kD-tree, BSP-tree and so on) but using a simple Grid or Quadtree should work very well to a dynamic environment.

In terms of the culling system, I am moving the view around meaning every time the view moves (and depending on the library if an object moves), I would have to recalculate the to-draw list.  Do you think that will affect the performance? I imagine the benefits will scale with more objects.  I guess my main question is if querying the quadtree is really cheap.

Depends on how the quad tree is made. I'll reference my Octree(Quadtree for 3D) I've made for my engine. Doing a Frustum query for that one is very cheap even in worst case scenarios and the query returns an array of pointers to all objects that were inside the frustum.

EDIT: What happens when an object moves out of the quadtree?

Depends on the implementation but most probably it will assert or place it in the top-node(I.E no optimization is done).
My Octree expands the tree in order to make sure that it fits. Kind of like a growing array

UPDATE: Did a fast check on the tree you are using. It probably works but is not properly done. For instance it has a max capacity for each node and only works with that and the position of the nodes. A Quadtree should NOT have a max capacity in nodes, it should have a minimum capacity before splitting and then go after the size of objects put into the node to make sure that each object are inside the node. If I had time I could remake my octree to become a proper Quadtree for you instead.

In english: the insertion of his Quadtree is not well made.

Damn I spoke too soon XD I kept reading and it looks like everything is done right.

[Lox]

That's gonna be a problem.  I was wondering if there could be like an expandable quadtree.