Giygas learns the art of C++

you should still be more concerned about speed efficiency than memory efficiency in this case; collision detection is a potentially very expensive operation and chances are cpu cycles will be more valuable than ram when you have hundreds of objects

also i'm going to spoil some of the fun and mention that there more data structures than justs lists and vectors and a few of them are a hell of a lot more efficient for CD than either of those

I know, I just thought Memory usage could also be an issue, especially on older computers. Clock Cycles are definitely important, and Lists tend to be very fast for checking if there is a collision with any of the objects in a set of objects. Most people only use precise CD with things like slopes and 3D. When they don't use precise, it's either BBox(very common and efficient), BCube(very efficient 3D), or distance(semi-efficient). There are tons of efficient techniques that don't require pixel-perfect precision, but can still be pretty precise.

This post has been edited by OniLink10 on Oct 23 2009, 04:39 PM

Not sure I want to mess around with lists right now unless I have a decent example to go by... I still want to figure it out myself ( For learning purposes ) but I don't wanna start from scratch, so i'll move onto uh... Colissions.

it doesn't matter much how fast list checking is if your collision detections end up being O(n²), which is what they'll be if you do the straightforward check-each-object-against-every-other-object-for-a-collision path

by the time you have 100 objects you'd be performing 10,000 checks every time you run the CD algorithm (which could be as often as your framerate, or more)

use a certain data structure and you could drop that to O(log n)

Could you explain which data structure this is? It could be very useful.

quadtree

That is genius.
If you are confused, it just divides the screen into 4 parts and places each object into one of the 4 parts. For collision detection, it only checks for collisions between two objects if they are in the same quadrant. I might be a little off, but that seems to be the general idea.
http://en.wikipedia.org/wiki/Quadtree

This post has been edited by OniLink10 on Oct 23 2009, 06:39 PM

well actually it can subdivide as well

mainly it can let you reduce your search space by quite a lot (since you can leave most objects out of the test entirely); basically you just figure out which cell a given object is in (information you'll probably have immediately), and search within the current cell, expanding outward if you need to

This post has been edited by Xgoff on Oct 23 2009, 06:49 PM

Xgoff, you are amazing. C++ Game Designers on MFGG should be worshiping you right now.

i dunno rii saved my ass by telling me about them a few weeks ago or something so worship him

and lifning

do you know what you're doing? 100 isn't the worst case in the situation I gave at all.
100 of these Objects in a vector would take (128*9)=1152 Bytes.

1000 Objects in a list would then take (1000*(9+4)) = 13000 Bytes
while 1000 Objects in a vector would be (1024*9) = 9216 bytes

etc.. the only time-based overhead in the vector is the reallocation of array space and the only space-based overhead is the difference between size and allocated capacity.

Giygas does not understand this conversation
:(

Okay, now I see what you meant. I didn't know how vectors expand.
Right now I have a level with 109 Objects. Each one uses about 24 Bytes. Let's see the memory usage.
List: 109*(24+4)=3052B(Approx 2.98KB)
Vector: 128*24=3072B(3KB)

Me and Lightning are discussing how much of your RAM different numbers of objects with different size will take up when stored in either a vector or a list. Lightning is teaching me so I understand. Xgoff was pointing out better ways to do Collision detection, mainly the Quadtree technique, which you can find on wikipedia.

For 99%+ of the use cases, the difference is not important.

yeah that's what I'm tryin' to get at

Which is why we moved on to Clock Cycle Efficiency and Quadtrees.

Okay, almost finished with this.

I just turned it into a little Minigame, because I don't want to spend to much time on this when I have other things to learn~

So, uh... Straight from the instruction booklet/manuel, here is it!

So uh... Yeah. Almost done with the project.

\o/

Looking nice, but did you forget to turn off Image Smoothing?