Optimization using Allegro in C++

What's up /prog/,
I'm currently trying to write an rts/ shooter using C++ and allegro. By shooter/rts, I mean shooter in the terms of ikuraga, and rts in that you will be switching control of units as well as being able to "freeze" the area around the ship you are currently controlling and que some command for the flotilla you are commanding.
Seeing as I have this in mind, I need to be able to have at least 90 units in the game without visible slowdown, so if you have some suggestions, I'm open to anything.

Thanks!

Don't do any optimization until you need to.

Have you dont any benchmarking/profiling to determine the areas of slowdown? Have you even started coding this thing? Don't optimize until you have visible slowdown.

I guess, but any ideas on efficient ways to, say figure out which bullets to check for a hit, how to handle large groups well, etc. would help; I would like to be in the right state of mind while writing the code, to make it easier later on.

I don't have benchmarking, however I have started coding. Currently, I have allegro loading the png's that I use as sprites, full user control of a basic ship, spawning of enemies, and the ability to fire bullets. My algorithm for firing bullets places them in an array (the bullet type is a class) in the ship class, and whenever a bullet leaves the screen, I re-init it, and push it to the back of the array, then order the array from smallest to greatest. I do this because I plan to use the quickfind trick, where when I check where if a fighter has been hit, I first find the bullets within range of the fighter, allowing me to only check a few bullets, instead of the whole array.

Oh, and I also have slowdown at 90 units, as well as tearing and unpleasant graphical ghosting/ etc.

How big is the array? How often are you sorting it? What sorting algorithm are you using? Anyway, I would profile your code first to see where the most time is spent.

Here's my code for updating bullets. It runs every time the game loop runs through. Also, how would I be able to find out where the most time is being spent? This is my first time in C++; everything else was in VB.net.
//The bullets are more complicated; need to be updated, then drawn
        for (int counter = 0; counter < NumOfBullets; counter++) used[counter] = false; //init used at false
       
        for (counter = 0; counter < TempNumOfBull; counter++) 
        { //Find the units that have left the screen.
            if (bullets[counter].lowerRightY <= 0 && bullets[counter].fired == true)
            {
                used[counter] = true;
                bullets[counter].bullet_init(); //refresh the bullet
                --NumOfBullets; // there's one less bullet on screen
            }                              
        }
       
        for (counter = 0; counter < (counter < TempNumOfBull2); counter++)
        { //put all the used bullets at the end of the array
            if (used[counter] == true) //if the bullet is gone
            { //perform les swap, and order the bullets from greatest to least
                for (counter2 = 0; counter2 < TempNumOfBull; counter2++)
                {
                    swap(bullets[counter2], bullets[counter2 + 1]);
                    swap(used[counter], used[counter + 1]);
                }
                --TempNumOfBull;
            }
        }
        //Now that the bullets are ordered, create the new ones, and update
        //their positions.
//        cout << NumOfBullets << endl;       
        for (counter = 0; counter < (NumOfBullets +1); counter++)
        {
            if (bullets[counter].fired == false)
            { // if the bullet hasn't been init, but has been fired
                bullets[counter].fired = true;
                bullets[counter].sprite = load_png( "bullet4.png" , NULL);
                if (leftright == true) //shoots the bullet from the left side
                {
                    leftright = false; //switch the side to fire from next
                    bullets[counter].x = x + 55;
                } 
                else //shoots the bullet from the right side
                {
                    leftright = true; //switch the side to fire from next
                    bullets[counter].x = x + 90;
                }
                bullets[counter].y = y;
            }
        bullets[counter].y = bullets[counter].y - 15;
        draw_trans_sprite(offscreen, bullets[counter].sprite, bullets[counter].x, bullets[counter].y);
        bullets[counter].lowerRightX = (bullets[counter].x + bullets[counter].sprite->w);
        bullets[counter].lowerRightY = (bullets[counter].y + bullets[counter].sprite->h);
        }

Check your compiler's manual for enabling performance instrumentation. Just looking at this, I see a couple of things:
* You are using a bubble sort for sorting your bullet array.
* You are storing object instances inside the array. This is causing objects to be needlessly copied on every swap.
* I'm a bit wary of that load_png call. Is this actually reading from disk, or are you caching the image in memory? An analogy I read somewhere about caching is that, accessing something from memory is like walking from your 12 story office to the lobby to pickup a parcel. Accessing something from hard disk is like walking across the equater.

Thanks for the help, I'll keep this in mind. I'm using GCC as my compiler (switched to linux a few years ago).
Load_png is indeed loading from HD, I'll see what I can do about that; trying to think of an easy way to reference them from memory.

I looked into bubble sort, but seeing as only "rabbits" are being sorted, so don't see too much of a problem with it, unless there are better suggestions. Also, I thought swap() in c++ was just switching the pointers to the objects, which I assume would be faster - is there any way I could do that instead?

I'm going to take this time to hump some quicksort. Quicksort is your friend and is probably less complicated logically than most of the others other than bubble sort.

When you use objects, pass by reference even if the object isn't modified. That way, it won't copy the object every time. Also, if you don't want it to be modified, just make it a const reference.

I doubt swap() exchanges the pointers. Even if it did, there's really no reason to use it when you can write much better sorting routines that are custom-tailored to your needs.

I suggest that you also keep future expansion in mind when you design your code. There's nothing worse than having to refactor. It drags you down by the balls.

Store pointers to objects in your array. Do comparisons using the object references. This will be faster since this time, you're only swapping pointers (ie. 32-bit integers) inside your array. Currently, the swap function is taking the address of the two objects in your array, and copying entire objects. This involves copying A to temporary store, a copy from B to A, then a copy from temp. store to B. Depending on what goes on inside the constructor and destructor of your class, this can be very costly indeed, especially if you're doing this inside a tight loop.

I also just noticed counter < (counter < TempNumOfBull2) inside that second for loop. Are you aware that (counter < TempNumOfBull2) will only be 0 or 1? Was this the intent?

Thanks a ton, guys, you're a big help. I tried passing by reference using swap (swap( &bullet1, &bullet2), but the compiler complained. I'm sure I'll figure it out. I'm still a frosh in college with only my high school VB and one semester of college C++ on me, hence why I used bubblesort - I didn't even know what I was, it was just the only alg I came up with. You guys rock.

>>13
Holy shit, I never saw that! Well, when I take out the first counter, the game speeds up considerably, but my bubble sort fails to sort correctly - bullets that leave the screen pop back to wherever the ship is. Say I fire 3 bullets, the first one goes off screen, then pops back to my ship. However, it doesn't go infinitely - the bullets disappear one by one, just not when I want them too. I think it has to do with my sentinel value, or TempNumOfBull2.

Fixed it! This:
for (counter = 0; counter < (counter < TempNumOfBull2); counter++)
        { //put all the used bullets at the end of the array
            if (used[counter] == true) //if the bullet is gone
            { //perform les swap, and order the bullets from greatest to least
                for (counter2 = 0; counter2 < TempNumOfBull; counter2++)
                {
                    swap(bullets[counter2], bullets[counter2 + 1]);
                    swap(used[counter], used[counter + 1]);
                }
                --TempNumOfBull;
            }
        }
Should have been this:
for (counter = 0; (counter < TempNumOfBull2); counter++)
        { //put all the used bullets at the end of the array
            if (used[counter] == true) //if the bullet is gone
            { //perform les swap, and order the bullets from greatest to least
                for (counter2 = 0; counter2 < TempNumOfBull2; counter2++)
                {
                    swap(bullets[counter2], bullets[counter2 + 1]);
                }
                --TempNumOfBull2;
            }
        }
removed the   swap(used[counter], used[counter + 1]);, and changed TempNumOfBull to TempNumOfBull2.
If I haven't said it enough, you guys rock.

The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. If it's known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.<sup>[1]

1</sup>: http://en.wikipedia.org/wiki/Quicksort

my bubble sort
What the fuck.

Reasonably fast collision detection algorithm:
http://www.shmup-dev.com/forum/index.php?action=printpage;topic=1636.0

Also note that only fixed frame rate is acceptable in shooting games, which means you'll have to use the graphics card as the timing source (vsync).  Please support both 60Hz and 120Hz for future compatibility, as people can't keep ignoring the obvious advantages of 120Hz displays forever.

I also recommend making your game deterministic, for easy replay saving/playback.

What's your Ikaruga score?  How many other shooting games have you 1CCed?  If you can't play these games well then you have no chance of making a good one.  But if this is just a learning exercise then don't worry about it.

What's your Ikaruga score?  How many other shooting games have you 1CCed
wat

>>19
But if this is just a learning exercise then don't worry about it.
You're an idiot.

>>19
I also recommend making your game deterministic, for easy replay saving/playback.
More info about this please.

>>22
http://www.gamasutra.com/view/feature/3057/instant_replay_building_a_game_.php?print=1

>>23
Random() considered harmful.

>>18
Obviously it's mine if it fails to sort correctly.
>>19,23
Thanks for the collision detection help, with everything I've gotten from here I think I'll be good for the next two weeks working stuff in. I'm planning on making it somewhat deterministic (certain enemies follow same patterns, etc.), as I want part of the game to be you "training" units to follow patterns you want them to use while attacking enemies, which means I need to be able to record player input. Although I've played a good amount of shooters, at this point the best I can say is that I've beaten Ikuraga with a C++. Then again, this game will be a mix of shooter/rts, so it will be bursts of reaction-dodging mixed with quickly queuing commands, and as it's an rts as well, the battle can go multiple ways, which means I can't be fully deterministic - and also means you can't just memorize where the enemies are coming from through multiple play-throughs, like the best ikuraga players do. I'm hoping the mix of shooter action and commanding troops should be what gives it its fun.

Barack Obama wouldn't use bubble sort.

>>26
[Citation needed]

>>27 http://www.youtube.com/watch?v=k4RRi_ntQc8

USE QUADTREES FAGGOT

Allegro and SDL are slow as fuck except for screen sizes 320*240 and below. Use opengl or directx instead.

>>29
*googles quadtrees*
wat?
>>30
Seriously? Well, I'm in linux, so directx is out of the question. Anyone have experience with Opengl? Recommend it? Or is this guy full of bs?

You can emulate directx w/ opengl

>>32
That's great, but this is a 2d game. Even just looking into opengl, it seems like everything thing is for 3-d. I saw a few Sdl howto's, but apparently that's as bad as allegro. I might just have to stick with allegro, unless there's something to help out in the 2-d department in opengl, and an online tutorial that can show me it.

>>31
SDL/Allegro's 2d functions are fine for 2d games. Examples include Liquidwar, and the games by Parallel Realities. SDL can be used together with OpenGL

>>33
For 2d in OpenGL you just draw everything flat.