Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Vector questions

Credits go to Archon, gillius, and Kris Asick for helping out!
This thread is locked; no one can reply to it. rss feed Print
Vector questions
Ceagon Xylas
Member #5,495
February 2005
avatar

Okay, this one's pretty simple. I'm going to reduce this example to a very minor part of my project.

In my game I have a bullet struct followed by a vector with that struct as it's elements. (See code below) The problem occurs after I push_back around 8,000 elements of this vector. Things run great until then, but at somewhere around this point in the application it hangs up (only graphically it would seem.) Once the bullets hit something and tell the vector to remove themselves, everything resumes.

Not sure if this is a code problem or I just don't understand something about vectors. Here's the code I have for this problem:

1struct bullets{
2 float x,y;
3 float velX,velY;
4};
5vector<bullets>bullet;
6 
7void update_bullets() {
8 for(int i=0; i<bullet.size(); i++)
9 if(bullet.at(i)) { //check to see if it's there
10 bullet<i>.x+=bullet<i>.velX;
11 bullet<i>.y+=bullet<i>.velY;
12 if(collided_with_object)
13 bullet.erase(bullet.begin()+i);
14 }
15}
16 
17void draw_bullets() {
18 for(int i=0; i<bullet.size(); i++)
19 if(bullet.at(i)) //check to see if it's there
20 putpixel(buffer,bullet<i>.x,bullet<i>.y,3);
21}
22 
23main() {
24 while(game_loop) {
25 //in the real application I have the timer setup correctly =P
26 if(key[KEY_SPACE]) {
27 bullets b={0,0,10,0};
28 bullet.push_back(b);
29 }
30 update_bullets();
31 draw_bullets();
32 //buffer the screen
33 }
34}

Archon
Member #4,195
January 2004
avatar

It might be better to use a pointer to the struct, like so:
vector<bullets*>bullet;
Because a vector would need to keep copying that struct over when it needs to resize - instead, a vector of pointers would be smaller and quicker to organise.

Quote:

for(int i=0; i<bullet.size(); i++)

You should use an iterator, I think that it's like (someone should correct this):

for (vector<bullets>::iterator i = bullet.start(); i != bullet.end(); /*nothing here*/)

and when you erase a bullet, it's like

    if(collided_with_object)
    {
        bullet.erase(*(&i));
        i = bullet.delete(i);
    }
    else
    {
        i++;
    }

Something like that ^.

Kris Asick
Member #1,424
July 2001

Add your timer and screen buffering to the code you provided. There could be a problem there.

Also, something to keep in mind here is that vectors are not efficient for deleting elements in the middle of them, only for pushing and popping. I recommend you change your bullet.erase() line with the following:

if(collided_with_object) {
  if (i == bullet.size() - 1)
    bullet.pop_back();
  else {
    memcpy(&bullet<i>,&bullet.back(),sizeof(bullets));
    bullet.pop_back();
}

Granted, this is not an OOP compliant solution, but if you want to keep using vector objects, it's a fast way to speed up the erasing of your bullets.

When you have 8000 objects in your vector and you delete, say, the 5th one, there's about 7994 reallocations of memory which must occur. (If I understand how vectors work.)

It's a lot more efficient to set a limit, allocate the memory ahead of time, then work within that limit so you're not constantly allocating and deallocating memory.

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Archon
Member #4,195
January 2004
avatar

Quote:

I recommend you change your bullet.erase() line with the following

If you don't know what he's doing, he's swapping the last vector item with a 'dead' one in the middle so that the vector doesn't need to shift down all of the items towards the end. ;)

But you still need to delete the item at the end...

Ceagon Xylas
Member #5,495
February 2005
avatar

Okay thanks a lot, guys. This is helping a lot. ;D

I have a question concerning Kris's snippet. Were you declaring i as an int or vector<bullets*>::iterator?

if(collided_with_object) {
  if (i == bullet.size() - 1)

Kris Asick said:

but if you want to keep using vector objects, it's a fast way to speed up the erasing of your bullets.

Is there a better way? I'm definitely up to changing my code completely at this point. Is it better to go with a predelcared size so that you're not resizing a ton every game cycle?

Here's the code for my timer, though it's not easily readable and I can't imagine it being very helpful.

1main() {
2 //blah blah all this junk.
3 //I've already declared the variable and function of course
4 LOCK_VARIABLE(speed_counter);
5 LOCK_FUNCTION(increment_speed_counter);
6 install_int_ex(increment_speed_counter,BPS_TO_TIMER(60));
7 
8 while(!exit_now) {
9 while(speed_counter>0) {
10 game_logic.update(); //all the logic
11 speed_counter--;
12 }
13 game_logic.draw(); //all the drawing
14 game_logic.buff(); //buffer it (see below)
15 yield_timeslice();
16 }
17}
18 
19void game_logic::buff() {
20 acquire_screen();
21 vsync();
22 stretch_blit(buffer,screen,0,0,buffer->w,buffer->h,0,0,SCREEN_W,SCREEN_H);
23
24 if(draw_mouse)
25 draw_sprite(screen,mouse_sprite,mouse_x,mouse_y);
26
27 release_screen();
28 clear_to_color(buffer,makecol(0,0,0));
29}

[edit] Gosh I edit a lot

gillius
Member #119
April 2000

EDIT: I am only commenting on what people were saying on how to structure the list and not the main issue with the graphics freezing -- I didn't see anything wrong with the posted code.

---

I see conversations head this way all of the time, so for the bullet idea I will bring back what I did research on in the past with particles (bullets are the same thing practically). copy-on-death with a vector is the fastest way if bullets are small (yours are). You don't need to memcpy, you can just use assignment.

http://www.gillius.org/articles/partmem.htm -- VectorAlgor is what I'm referring to -- and there is code.

Most people (and I used to all the time) use lists of pointers, but lists of pointers can be 4-5x slower than vectors with copy-on-death with 36 bytes. As the object size goes down the vector gets faster; your size is 16. As the object size increases, eventually pointer list and vector will match speed. In terms of memory usage, the vector version uses less as the object peak, but if you use it intelligently it will increase to the peak and stay there while the list version goes up and down, but at the peak the list uses more memory, therefore the vector solution has a lower upper-bound.

Gillius
Gillius's Programming -- http://gillius.org/

Kris Asick
Member #1,424
July 2001

Get vsync() out of the area between acquire and release!

That could be the source of all your problems. Calling vsync() while a video bitmap is locked with the acquire commands can cause bad things to happen!

On my computer, that action would cause a program lock-up within the first split second of operation.

I also noticed I forgot a } in the code I posted, and I also noticed a way to improve it:

if(collided_with_object) {
  if (i < bullet.size() - 1)
    memcpy(&bullet<i>,&bullet.back(),sizeof(bullets));
  bullet.pop_back();
}

;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Ceagon Xylas
Member #5,495
February 2005
avatar

Okee doke. vsync() before acquire_screen() then? If so, that didn't solve anything for me, but it's nice to know for later projects. ;)

HoHo
Member #4,534
April 2004
avatar

I'd draw mouse to buffer, not to screen.
Also, have you tried to drop the aquire_screen and/or vsync completely?

I haven't done any windows development for quite a few years but I don't remember not having any problems when not using them.

[edit]

Doh, you are using stretching. You might want to ignore this post. I haven't got enough sleep :-X

__________
In theory, there is no difference between theory and practice. But, in practice, there is - Jan L.A. van de Snepscheut
MMORPG's...Many Men Online Role Playing Girls - Radagar
"Is Java REALLY slower? Does STL really bloat your exes? Find out with your friendly host, HoHo, and his benchmarking machine!" - Jakub Wasilewski

Ceagon Xylas
Member #5,495
February 2005
avatar

Well, using iterators may have sped it up a little. The biggest help was Kris Asick's code. Thanks :) I can handle around 40,000 instances now, which is a huge step up from 8,000!

I'll have to spend some extra time reading up on the link you provided, gillius.

Kris Asick
Member #1,424
July 2001

Ok, I think we can assume something here...

Your code was working fine before, up until about 8,000 bullets, then died.

Now it works up to about 40,000 then dies.

Either way, it still dies, but improving the bullet removing code improved how many you could handle.

This suggests that the problem is in the way you are handling framerates below the target framerate. I would look at how you handle lower than normal framerates and see if that's the problem.

EDIT: I figured the problem out. If your timer increments while the game logic is still being processed, it never runs the drawing code.

Try this...

1main() {
2 int speed_counter_copy;
3 //blah blah all this junk.
4 //I've already declared the variable and function of course
5 LOCK_VARIABLE(speed_counter);
6 LOCK_FUNCTION(increment_speed_counter);
7 install_int_ex(increment_speed_counter,BPS_TO_TIMER(60));
8 
9 while(!exit_now) {
10 speed_counter_copy = speed_counter;
11 while(speed_counter_copy>0) {
12 game_logic.update(); //all the logic
13 speed_counter_copy--;
14 }
15 game_logic.draw(); //all the drawing
16 game_logic.buff(); //buffer it (see below)
17 yield_timeslice();
18 }
19}

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Ceagon Xylas
Member #5,495
February 2005
avatar

My program doesn't really die either way. Like there's no errors or forcing the closing of the program. Pretty much just becomes a extremely laggy (like, up to 20 seconds of no visible updates... Just hard number crunching) at around 40,000 bullets.

About your counter code. It doesn't work, and I don't see why it would. What was it you were trying to do?

Kris Asick
Member #1,424
July 2001

You're right, the code I provided doesn't work... the problem is almost the same with it.

Here's what's happening with your original code. Your variable "speed_counter" is incremented by your 60 FPS timer, right? And you've designed your second while loop to run while speed_counter is greater than 0.

So what happens when you're processing so much data that speed_counter increments while in the middle of processing logic? The while loop continues for another logic pass, which again takes so long that speed_counter increments, so it processes even more logic, and this whole time, ends up skipping your drawing routine which is outside the while loop.

My code, which I thought would work, doesn't because each time it processes the logic, it ends up with more of it to process each new frame and just stockpiles exponentially when the framerate drops.

I don't actually understand proper frame dropping techniques because I switched to doing realtime programming before I learned any, but that's what you need to look up because your frame dropping technique is where the problem is. Though frame dropping is usually for handling when rendering takes too long. If it's the game logic that's taking too long, you need to do something to decrease how much logic is processed.

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

HardTranceFan
Member #7,317
June 2006
avatar

Kris,

Would you code work if you add the following?

1main() {
2 int speed_counter_copy;
3 //blah blah all this junk.
4 //I've already declared the variable and function of course
5 LOCK_VARIABLE(speed_counter);
6 LOCK_FUNCTION(increment_speed_counter);
7 install_int_ex(increment_speed_counter,BPS_TO_TIMER(60));
8 
9 while(!exit_now) {
10 speed_counter_copy = speed_counter;
11 speed_counter = 0; // <<<----------------Line added
12 while(speed_counter_copy>0) {
13 game_logic.update(); //all the logic
14 speed_counter_copy--;
15 }
16 game_logic.draw(); //all the drawing
17 game_logic.buff(); //buffer it (see below)
18 yield_timeslice();
19 }
20}

--
"Shame your mind don't shine like your possessions do" - Faithless (I want more part 1)

gillius
Member #119
April 2000

Yes, Kris is right frame dropping only works if the logic loop runs fast enough that the computer can keep up with logic alone. Since rendering takes a long time (especially with Allegro games), usually this assumption is that the logic is much less demanding than graphics.

If the logic loop can't keep up then you have problems because if rendering takes a lot more effort, then your game is going to run too slow.

The only solution if your game is fixed-rate logic is to have a maximum frame skip and run your game slower than real-time -- the computer just can't keep up with your game.

What HardTranceFan showed does something similar except that it isn't predictable. What will happen is that the frames will get farther and farther spaced out because every time it runs, speed_counter and therefore speed_counter_copy will get higher.

I've published on here and also mentioned in several posts something to deal with it if you have dynamic rate logic, that had several ranges (dt being the logic frame duration for a single step)

  1. If dt > maxDt, dt = maxDt (run less than real-time)

  2. If dt > frameSkipDt (frame skipping)

  3. If dt > minDt (1:1 frame drawing, dynamic dt rate)

  4. else, dt is < minDt (1:1 frame drawing, fixed dt rate, CPU sleeping to reduce CPU usage

EDIT: BTW, having code to run less than real-time is especially important even for fast computers and fast games -- if your process is temporarily suspended because your user switched away from your app (alt-tab), suspended/slept/hibernated PC, a process like virus scan or firewall paused your PC, or a heavy disk app like defrag paused you, you don't want the game to go into super-fast zoom mode when it returns from the pause... you want it to stop, pause, and resume where it left off. If it's a network game, you can't do this, though.

Gillius
Gillius's Programming -- http://gillius.org/

Kris Asick
Member #1,424
July 2001

Quote:

What HardTranceFan showed does something similar except that it isn't predictable. What will happen is that the frames will get farther and farther spaced out because every time it runs, speed_counter and therefore speed_counter_copy will get higher.

No, my code does that. HardTraceFan's code fixes the bug in mine, but the problem persists if the logic is overloaded. ;)

--- Kris Asick (Gemini)
--- http://www.pixelships.com

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Ceagon Xylas
Member #5,495
February 2005
avatar

Well, it helped! 8-)

gillius
Member #119
April 2000

Ha sorry Kris I get mixed up who posted what sometimes ;)

Gillius
Gillius's Programming -- http://gillius.org/

Go to: