Here is some progress on my game learning/development! Asteroids type "game" with 9 bullet streams, turns up over 1,000 bullets. Did it to see if I could. No noticeable performance loss!
Posted Sep 26, 2011, 1:48 AM UTC
2322
cool, dude. keep up the good work.
2
Somebody was having a lot of fun. :D
2
Now tell us how :)
2
In Java. Made an object pool with a stack, generating all the needed bullets (for this, 1200) before the program runs and throwing them into the stack, and then popped bullet objects into a linked list to make them active, then when the bullets expire they simply go back into the stack to be recycled. Works much better than constantly creating and deleting objects.
2
Keep in mind that javas LinkedList creates an object on every insert
3
I would be surprised if your object pool performs better than the GC, and I wouldn't be surprised if it was worse. Generally you only need to pool objects that have a significant cost other than memory allocation (threads, database connections).
1
What do you mean by GC?
1
The garbage collector. Sun's GC is state-of-the-art, so trying to work around it with your own memory management will almost always be for naught, or worse. If profiling shows you that memory is being a problem, you're probably much better off reworking that part of your program to better help the GC do its job.
1
After a few years of programming C, I decided to try out python a few days ago and recently wrote some particles which worked in a similar way, except without the stack. A few hundred particles are added to a list when the particle generator is initialised, and as soon as a particle dies it is reset as a new particle.
Why didn't you choose to keep all the bullets in a linked list and just give them an active / inactive state instead of adding and removing them?
1
This is what I consider to be my first data structure test. I tested doing the same thing but with an ArrayList and the ArrayList was 100 times slower. Basically, I theorized that this would be faster because if I chose to have the active/inactive states inside of a linked list, then 1) for every loop it would have to traverse the entire list, and 2) when adding/activating new bullets, it would have to traverse the list until it finds an inactive bullet. For 1), my method only has to loop through already active bullets and if they have been turned to inactive then they will be removed on the spot and 2), this is avoided entirely by simply popping from the stack and throwing it in, therefore avoiding performing another traversal. I'll have to make a stress test with both methods to find out the real truth as to which way is faster; this is already on the plate.
1
http://www.youtube.com/watch?v=Qy9v3g48LKA Same game but with only 1 bullet stream.
1
The color effect near your ship reminds me of when old CRTs would get magnetized
1
Judging by the blending on the ship, this is OpenGL.
Just so you know, Geforce 8600 cards (2006 technology) push around 136 million triangles per second.
Where you are going to start running into performance problems with this sort of game is going to be in collision detection, if you want all objects to be collidable with all other objects. So for 1000 objects onscreen, you'd be looking at ~1 million collision calculations per tick. In my experience, "naive" collision detection starts running into problems at around 300 objects.
So then you get into different sorts of ways to whittle down the collision number, including "binning" or dividing the screen up into N squares, ideally somewhat larger than the individual object's collision box. However, even if you just divide it up into quadrants, that will usually work just fine for any type of sane collision algorithm. There are edge conditions on the borders of the boxes but they are just not noticeable.
Here's a really simple way of binning. Give each object a quadrant, zero through three. When the object moves, its screen quadrant gets updated. On collision check, check first if the two objects' screen quadrants are the same. If not, don't bother doing the collision check. In one way, this seems inefficient because you're only cutting the problem up in four. If you use more bins, you will be able to push more collisions, but then the binning code gets a fair bit more complicated. The advantage the quadrants have is that you have fine-grained collisions the vast majority of the time.
A piece of advice: game development isn't necessarily like other forms of programming. It's sort of a beast unto itself, and since it's for entertainment, it doesn't need to impress Stanford University computer science professors with its elegance. If you can't think of an elegant way to do something, just do it brute force. If it causes speed problems, worry about it later.
An example would be having a different set of lists for each object type, and then a different list altogether for particles, instead of having them all thrown into one big list. It might not seem like the most elegant way of doing things but it might simplify things for one reason or another, and it will get the job done and you will be able to ship the product.
Also, here is a fun little asteroids game you could learn from:
Hyperoid
This includes the source. You're not going to be able to get it to compile, most likely, so just look at it and learn from it. It is probably not even particularly good learning code but it's simple.
Here's some more-- I didn't write this or even run it.
Geometry Wars clone
136 million triangles per second, if you manage to feed the card those triangles in exactly the way it wants them.
This is actually where you are going to run into trouble if you want lots of triangles in a game like this: If you try to feed them to the card through immediate mode, or if you try to switch textures each time you draw a new triangle, you are going to cut that rate down by orders of magnitude.
What you need to do is collect as many triangles as you an into buffers, and then draw them all in big batches without switching texture or other state. This is not always trivial in a 2d engine, and how to do it depends on your exact requirements, but if you think you'll need it, then you need to plan from it right from the start, because it will put limitations on your engine.
Once you do, though, you can draw many tens of thousands of sprites on the screen with no slowdown, easily.
Of course, that then leaves the rest of your engine, like the collision detection and such to optimize too.
This begs the question of why someone would ever want 136 million TPS in a top-down shooter, but that's neither here nor there. The bottleneck in this sort of thing is always going to be in collision detection-- also AI. Because those aren't on hardware, typically.
Even the naive approach can do crazy shit these days.
Maybe, but not so crazy that you can't run out of performance fairly easily, especially when you start doing things like building your levels out of lots of composited bitmaps. Things like texture switches are incredibly expensive. You really run out of time very quickly if you're not careful.
What about the method of putting lots of bitmaps onto one texture and changing coordinates?
[deleted]
Very interesting, thank you. This is all new stuff to me. I'll look into it when I have the time.
Your Hyperoid link is borked. I think they're doing silent (403 instead of "derp, wrong referrer") referrer checking.
Try the top-level game page instead.
Wow, thank you for this post. I'm making a game where I need lots of bullets on the screen at once and I managed to make it go up to ~300 bullets without much performance drop. So reading what you said sort of made me happy because I was trying to get it up to 1000 bullets but I can't find anymore optimizations. That binning method you mentioned makes a lot of sense and I'll try to implement it to see if it makes everything better! Thanks a lot!
I used a strange space partitioning container, where the objects are stored in a matrix which contains entity-linkedlist, each square is an arbitrary sized square.
It is very simple to calculate an object's position in the matrix from it's position to decide where it has to be stored.
When an object has to detect collisions, it queries the nearest X partitions, and only handles collisions to these objects. If the speed of objects is slow enough (as in, not pass through the query range in one tick) this will cause no errors. Now my game can handle a thousand brownian-motion-like "bats" colliding in dumb bounce physics without any slowdown.
This also gave a nice method for updating object only relatively close to the player, because then I need just a higher X for querying.