6 replies to this topic

[Eielef]

Hi everyone! I'm programming a top down space shooter with Allegro 5 in C++, and in the game class I have two deques, one for the enemies and other for the weapons. I also have a function called HandleCollisions(), who takes the two deques, and check the collisions between them. Well, it doesn't work much, so I'm pretty sure I did something wrong accesing the lists. Here is the code for the function:

void GS_Juego::HandleCollisions() {
unsigned i=0,j=0;
//Manejar colisión con armas de la nave
while(i< EnemyQueue.size()) {
  while(j<WeaponsQueue.size()) {
   if(EnemyQueue[i]->CheckCollision(WeaponsQueue[j])) {
	//crear explosión en (GetX(),GetY())   <-----¡¡¡EXPLOSIóN AQUÍ!!!
	delete EnemyQueue[i];
	delete WeaponsQueue[j];
	EnemyQueue.erase(EnemyQueue.begin()+i);
	WeaponsQueue.erase(WeaponsQueue.begin()+j);
   }
   else {
	j++;
   }
  }
  i++;
}
i=0;
//Manejar colisión con nave
while(i<EnemyQueue.size()) {
  if(EnemyQueue[i]->CheckCollision(Player1)) {
   //crear explosión en (GetX(),GetY())   <-----¡¡¡EXPLOSIóN AQUÍ!!!
   EnemyQueue.erase(EnemyQueue.begin()+i);
   //Player1->addLives(-1);
   //DESTRUIR ENEMIGOS
   while(!EnemyQueue.empty()){
	//crear explosion en (Get(),GetY()) <<---¡¡AquÍ otra!!
	EnemyQueue.erase(EnemyQueue.begin());
   }
  }
  i++;
}
}

This is the header with the declaration of the function and the two deques in black:

#ifndef GAMESTATE_JUEGO
#define GAMESTATE_JUEGO
#include "c_gamestate.h"

#include <allegro5\allegro5.h>
#include <allegro5\allegro_native_dialog.h>
#include <allegro5\allegro_primitives.h>
#include <allegro5\allegro_font.h>
#include <allegro5\allegro_ttf.h>
#include <allegro5\allegro_image.h>
#include <allegro5\allegro_audio.h>
#include <allegro5\allegro_acodec.h>
#include "Constants.h"

#include "EnemyChaser.h"
#include "Player.h"
#include "WeaponLaser.h"

#include <deque>
using namespace std;

class GS_Juego :
	public C_GameState
{
public:
	void Init();
	void Run();
	void Shutdown();
	GS_Juego(ALLEGRO_DISPLAY *display);
private:
	void drawBackground();
	void HandleEvents();
	[b]void HandleCollisions();[/b]
	void UpdateElements();
	void RenderElements();
	void ShootWeapon();
	void SpawnEnemy(int EnemyType);
	int create_random_number(const int min, const int max );

	ALLEGRO_DISPLAY *display;
	ALLEGRO_BITMAP *b_background, *b_enemychaser, *b_enemychaser_mask, *b_player1, *b_rotationBuffer, *b_laser;
	ALLEGRO_SAMPLE *s_music;
	ALLEGRO_EVENT_QUEUE *event_queue;
	ALLEGRO_EVENT evento;
	ALLEGRO_TIMER *timer;
	//Background Effect
	int background_Y;
	//THINGS
	bool done;
	bool redraw;
	bool calculateLogic;
	bool keys[NUM_OF_KEYS];
	int tc_weaponsDelay;
	int SelectedWeapon;

[b]	deque<C_Enemy*> EnemyQueue;
	deque<C_Weapons*> WeaponsQueue;[/b]

	Player *Player1;
};
#endif

I'd really aprecciate any feedback at all, because as far as I know, it should work perfectly, and I'm hitting my head against the wall repeatedly trying to find a solution. I checked the function collision and it works fine. The problem is that when it detects a collision with a bullet that it's not the first in the queue the program crashes, and if there is more than one enemy in the screen, if it's not the first one in the queue and I try to hit it with a bullet, it doesn't detect the collision. I'm sure the solution it's super silly, but I just can't find it. Please help! :-S

[Reedbeta]

Well, one obvious problem is that in the first code sample, you're incrementing 'i' in your loops even if you've deleted the enemy. This will cause some enemies to be skipped, e.g. if you delete enemy 0, enemy 1 will become the new enemy 0, but then i = 1 in the next iteration so you will skip this enemy.

It seems you are handling this with 'j' in the inner loop, only incrementing it when you didn't delete the weapon. You just need to do the same thing with the enemies. Also, at the "DESTRUIR ENEMIGOS" section you should probably break out of the while loop, since you have just emptied the enemy list.

BTW, it is easier to code this sort of thing if you iterate backward over the lists. That way, when you delete something you will not change any of the indices. Or, in your collision logic do not actually delete anything but just mark them as "dead" (add flags to the Enemy and Weapon classes for this), then in a later step you can do another loop and remove the dead ones. Or just leave them there and re-use them when new enemies and weapons are created.

Incidentally...why did you choose std::deque for this? It is an odd choice. I think most people would simply use std::vector or std::list.

[Eielef]

Thank you for the help, I don't know how I didn't see it. I changed the code a little bit now:

void GS_Juego::HandleCollisions() {
for(int i=EnemyQueue.size()-1;i>=0;i--) {
  for(int j=WeaponsQueue.size()-1;j>=0;j--) {
   if(EnemyQueue[i]->CheckCollision(WeaponsQueue[j])) {
	delete EnemyQueue[i];
	delete WeaponsQueue[j];
	EnemyQueue.erase(EnemyQueue.begin()+i);
	WeaponsQueue.erase(WeaponsQueue.begin()+j);
   }
  }
}
for(int i=0;i<EnemyQueue.size();i++) {
  if(EnemyQueue[i]->CheckCollision(Player1)) {
   EnemyQueue.erase(EnemyQueue.begin()+i);
   while(!EnemyQueue.empty()){
	EnemyQueue.erase(EnemyQueue.begin());
   }
  }
}
}

Still, if I shoot several times and I hit an enemy with the first bullet before the rest dissapears, the program crashes and says "deque subscript out of range".

Actually, I didn't use flags because I didn't want to check the list twice, one for checking collisions and one more for deleting, but I just realised I have to check it again when I update all the objects, so I'll change the implementation, since I'm thinking it'll be better for handling destroying animations and all that.

About using the deque list... well, I looked up all of them in the internet, trying to figure it out which one was better to use. I'm not sure yet what's the main difference between std::vector and std::deque, and I don't remember why I'm using std::deque in that code. Do you think it's better to use std::list or std::vector instead?

Thanks again!

[Reedbeta]

I would prefer std::vector unless there's a specific reason to use something else. It's not *bad* to use std::deque, but it's not necessary either, as std::deque is designed specifically to be fast for adding/removing stuff at either the beginning or the end of the list, but you're not really using that capability, as far as I can tell.

As for the program crashing, do you know how to use the debugger? You should run it in the debugger and then when it crashes, you'll be able to see where it was and the values of nearby variables. You can also step through the code line by line and see how the crash happens.

[Eielef]

Hmmm, well, I think both have the same functions, so I guess it'll be easy to change to std::vector.

About the debbuger, I actually don't. I guess I should have learned how to use it by now :

Btw, the "DESTRUIR ENEMIGOS" section was there so, if one of the enemies hits the player, then every enemy on game is deleted, so the player can have a break. But since I'm thinking about implementing flags now, Instead of emptying the list, I'll just change the state of the enemies.

Thanks for the advices!

[Reedbeta]

Oddly enough, just a couple days after this thread, I saw this article posted on Twitter: C++ benchmark – std::vector VS std::list VS std::deque

The results are interesting. In theory, std::list has an advantage when you must insert/erase in the middle of the list. However it seems that advantage is only realized with a sufficiently large element type (128 bytes or more) or if the data is non-POD. For small POD types the vector is actually faster there.

[TheNut]

I think that's to be expected when you're using value types. It basically comes down to how fast can you iterate over a list to reach your target vs how fast you can reallocate and copy swaths of data from resizing a vector. In most cases, you're going to use pointer types (or smart pointers) when working with large data sets, so resizing the heap is likely to contribute more to the performance cost than simply iterating and copying pointers. If you're smart about your storage and you prealloc, then that's one less performance metric to worry about. As his tests show (specifically the 8-byte tests, 64 bit apps), the vector is a solid choice overall.

IMO, vectors are very good general purpose containers, but there's the old saying. Use the right tool for the job, be it vectors, lists, hash tables, or trees.