2D Collision algorithm?

[Morgawr]

Hi guys..

I'm still a newbie with irrlicht engine and I don't know every single function out there, even though I browsed the API doc, I still couldn't find what I was looking for...

I'm looking for an algorithm that allows me to stop a 2D sprite by colliding into another sprite.. Like obstacles in a platform game or in every 2D game after all..

This is my CharMovement.h header, where I stored the CharMovement class that allows me to move my character on the screen (now it can move freely all over the screen, that's not a problem I'm just testing):

Code: Select all

#include <irrlicht.h>
using namespace irr;

class CharMovement : public IEventReceiver
{
    private:
    u32 charx;
    u32 chary;
    public:
    CharMovement(u32 char_x, u32 char_y)
    {
        charx = char_x;
        chary = char_y;
    }
    virtual bool OnEvent(SEvent event)
		{
            if (event.EventType == irr::EET_KEY_INPUT_EVENT&&
			!event.KeyInput.PressedDown)
            {
                switch(event.KeyInput.Key)
                {
                    case KEY_KEY_A:{
                     if(charx>=10)
                      charx-=10;
                     break;
                    }
                    case KEY_KEY_D:{
                     if(charx<=(790-90))
                      charx+=10;
                     break;
                    }
                    case KEY_KEY_S:{
                     if(chary<=(590-145))
                      chary+=10;
                     break;
                    }
                    case KEY_KEY_W:{
                     if(chary>=10)
                      chary-=10;
                     break;
                    }
                }
                return true;
            }
            return false;
		}
    u32 getX(){
        return charx;
    }

    u32 getY(){
        return chary;
    }
};

Do you know any tip to help me include in this class the collision check function? or how could I do it? I just want something that could work for every 2D sprite collision, not a particular case of collision.. I've been thinking about it but couldn't come up with anything... thanks for the help

[JP]

If moving sprite1 causes sprite1's collision box to intersect with the collision box of another sprite then don't move sprite1 to that position.

The collision box is just a 2D rectangle which encloses the sprite. You could make it even easier by using a collision circle instead so you just check the radius against other objects.

For code to test for intersections i'm sure you can find something by googling or maybe even searching this forum.

[Morgawr]

If moving sprite1 causes sprite1's collision box to intersect with the collision box of another sprite then don't move sprite1 to that position.

The collision box is just a 2D rectangle which encloses the sprite. You could make it even easier by using a collision circle instead so you just check the radius against other objects.

For code to test for intersections i'm sure you can find something by googling or maybe even searching this forum.

Mm yeah that was my same idea too but... if you see my CharMovement code, the sprite moves when KEY_KEY_<button> is pressed, so I have to check every other sprite I have on the screen inside every case of the switch?

Like, I have one char1 sprite, a monster1 and a monster2 sprites, then I have 4 box1,2,3,4 sprites that are obstacles.. and a floor sprite (which will be where my char stands on)... Do i have to check everytime if char1 sprite collides with monster1,monster2,box1,box2,box3,box4 and floor sprites? That's my dilemma... I wanted to make a general function that could work with any sprite, not having to count how many sprites I have on the screen/map at that moment...

[GameDude]

Wouldn't this be in the game programming section?

[Morgawr]

Wouldn't this be in the game programming section?

I don't know, I know this section is about 3D and 2D stuff so I thought it was ok to post this here, if it's not then pardon me, I'm really sorry and please move it where it belongs thanks


EDIT:

Ok sorry guys if this was the wrong section, I found my solution anyways...

Code: Select all

        core::rect<s32> one(getX(),getY(),getX()+textarea.getWidth(),getY()+textarea.getHeight());
        core::rect<s32> two(obj.getX(),obj.getY(),obj.getX()+obj.textarea.getWidth(),obj.getY()+obj.textarea.getHeight());
        if(one.isRectCollided(two))
         return true;
        return false;

this works awesome

[JP]

What you should have really is a base class for all your sprite types say CSprite. Then for each individual sprite type you subclass that base class so you can add additional functionality that they may require. In CSprite you have all the basic stuff like basic movement and collision detection and any other functions and variables that span across all types of sprite.

That way you can keep a CSprite array of all the sprites that you currently want to handle and then each time you do a collision detection test you can just pass in that array and test the collisions. That way you don't have to keep track of all the sprites in seperate ways.

But maybe you did it that way already!

[Morgawr]

What you should have really is a base class for all your sprite types say CSprite. Then for each individual sprite type you subclass that base class so you can add additional functionality that they may require. In CSprite you have all the basic stuff like basic movement and collision detection and any other functions and variables that span across all types of sprite.

That way you can keep a CSprite array of all the sprites that you currently want to handle and then each time you do a collision detection test you can just pass in that array and test the collisions. That way you don't have to keep track of all the sprites in seperate ways.

But maybe you did it that way already!

Yeah, that's what I'm doing now... I have this Object2D base class...

Code: Select all

class Object2D
{
    private:
    u32 posX;
    u32 posY;
    video::ITexture *texture;
    bool isMobile;
    core::rect<s32> textarea;

    public:

    Object2D(u32 x, u32 y,c8* textname,bool mob,video::IVideoDriver *drive, core::rect<s32> sel_area)
    {
        if(x<0)
         posX=0;
        else
         posX=x;

        if(y<0)
         posY=0;
        else
         posY=y;

        texture = drive->getTexture(textname);

        isMobile = mob;
        textarea = sel_area;
    }

    u32 getX()
    {
        return posX;
    }

    u32 getY()
    {
        return posY;
    }

    bool isMob()
    {
        return isMobile;
    }

    video::ITexture* getText()
    {
        return texture;
    }

    void setCoords(u32 x, u32 y)
    {
        if(x<0)
         posX=0;
        else
         posX=x;

        if(y<0)
         posY=0;
        else
         posY=y;
    }

    core::rect<s32> getTextArea()
    {
        return textarea;
    }

    bool isColliding(Object2D obj)
    {
        core::rect<s32> one(getX(),getY(),getX()+textarea.getWidth(),getY()+textarea.getHeight());
        core::rect<s32> two(obj.getX(),obj.getY(),obj.getX()+obj.textarea.getWidth(),obj.getY()+obj.textarea.getHeight());
        if(one.isRectCollided(two))
         return true;
        return false;
    }

};

the code might be a little harsh since I'm still learning and this is just a test after all, still trying to learn to use irrlicht ^^

[TheMiss]

Try this... I had written it for my 2d game.
But it is currently abandoned now

CSprite.h

Code: Select all

#ifndef __C_SPRITE_H_INCLUDED__
#define __C_SPRITE_H_INCLUDED__

#include "CStuff.h"

using namespace irr;

class CSprite : public CStuff
{
public:

	//! Constructor.
	CSprite(IrrlichtDevice *device);

	//! Destructor.
	~CSprite();

	//! Create sprite from filename which automatically calculate size.
	virtual void create(const c8* filename, s32 divX = 1, s32 dixY = 1);

	//! Create sprite from ITexture which automatically calculate size.
	virtual void create(video::ITexture *texture, s32 divX = 1, s32 divY = 1);

	//! Make color key from upper left corner sprite.
	virtual void makeColorKey();

	//! Set positon X axis on screen.
	virtual void setPosX(const s32 &posX);

	//! Set position Y axis on screen.
	virtual void setPosY(const s32 &posY);

	//! Set position X,Y axis on screen.
	virtual void setPos(const s32 &posX, const s32 &posY);

	//! Set position X,Y axis on screen.
	virtual void setPos(const core::position2di &pos);

	//! Set current frame.
	virtual void setFrame(const s32 &frame);

	//! Get height of sprite.
	virtual s32 getHeight();

	//! Get width of sprite.
	virtual s32 getWidth();
	
	//! Get position X axis on screen.
	virtual s32 getPosX();

	//! Get position Y axis on screen.
	virtual s32 getPosY();

	//! Get position X,Y axis on screen.
	virtual void getPos(s32 &outPosX, s32 &outPosY); 

	//! Get postion X,Y axis on screen.
	virtual core::position2di getPos();

	//! Get current frame.
	virtual s32 getFrame();

	//! return true if the sprite collides with another sprite.
	virtual bool isCollided(CSprite *other);

	//! Draw prite.
	virtual void draw();

	//! Draw prite on coordinate of the map.
	virtual void draw(core::position2di &posMap);

	//! Draw sprite with alpha channel.
	virtual void drawAlpha();

	//! Draw sprite with alpha channel on coordinate of the map.
	virtual void drawAlpha(core::position2di &posMap);


protected:

	video::ITexture *Texture;
	core::array<core::rect<s32>> Frame;
	core::position2di Position;
	s32 CurrentFrame;

	s32 Height;
	s32 Width;

};

#endif //__C_SPRITE_H_INCLUDED__

CSprite.cpp

Code: Select all

#include "CSprite.h"

CSprite::CSprite(IrrlichtDevice *device) : CStuff(device)
{
	Texture = NULL;
	Position = core::position2di(0,0);

	CurrentFrame = 0;

	Height = 0;
	Width = 0;
}

CSprite::~CSprite()
{
}

void CSprite::create(const c8 *filename, s32 divX, s32 divY)
{
	//! \param filename get a filename of srpite.
	//! \param divX number of sprites along colum(X).
	//! \param divY number of sprites along row(Y).
	Texture = Driver->getTexture(filename);

	core::dimension2di spriteSize = Texture->getSize();
	Width = spriteSize.Width / divX;
	Height = spriteSize.Height / divY;

	Frame.set_used(divX * divY);

	s32 n = 0;

	for( s32 j = 0; j < divY; ++j )
	{
		for( s32 i = 0; i < divX; ++i)
		{
			Frame[n] = core::rect<s32>(Width * i, Height * j,//Upper Left Corner
				Width * (i+1),Height * (j+1));//Lower Right Corner

			++n;
		}
	}
	CurrentFrame = 0;
}

void CSprite::create(video::ITexture *texture, s32 divX, s32 divY)
{
	//! \param texture get a texture(Sprite) which contrains in video card
	//! \param divX number of sprites along colum(X).
	//! \param divY number of sprites along row(Y).
	Texture = texture;

	core::dimension2di spriteSize = Texture->getSize();
	Width = spriteSize.Width / divX;
	Height = spriteSize.Height / divY;

	Frame.set_used(divX * divY);

	s32 n = 0;

	for( s32 j = 0; j < divY; ++j )
	{
		for( s32 i = 0; i < divX; ++i)
		{
			Frame[n] = core::rect<s32>(Width * i,Height * j,//Upper Left Corner
				Width * (i+1),Height * (j+1));//Lower Right Corner

			++n;
		}
	}
	CurrentFrame = 0;
}

void CSprite::makeColorKey()
{
	Driver->makeColorKeyTexture(Texture,core::position2di(0,0));
}

void CSprite::setPosX(const s32 &posX)
{
	Position.X = posX;
}

void CSprite::setPosY(const s32 &posY)
{
	Position.Y = posY;
}

void CSprite::setPos(const s32 &posX, const s32 &posY)
{
	Position.X = posX;
	Position.Y = posY;
}

void CSprite::setPos(const core::position2di &pos)
{
	Position = pos;
}

void CSprite::setFrame(const s32 &frame)
{
	CurrentFrame = frame;

	if( CurrentFrame > (s32)Frame.size() - 1 )
		CurrentFrame = Frame.size() - 1;
	else if( CurrentFrame < 0 )
		CurrentFrame = 0;
}

s32 CSprite::getHeight()
{
	return Height;
}

s32 CSprite::getWidth()
{
	return Width;
}

s32 CSprite::getPosX()
{
	return Position.X;
}

s32 CSprite::getPosY()
{
	return Position.Y;
}

void CSprite::getPos(s32 &outPosX, s32 &outPosY)
{
	outPosX = Position.X;
	outPosY = Position.Y;
}

core::position2di CSprite::getPos()
{
	return Position;
}
	
s32 CSprite::getFrame()
{
	return CurrentFrame;
}


bool CSprite::isCollided(CSprite *other)
{
	// \param other sprite which you want to check collision.
	core::rect<s32> rect1(Position,//Upper Left
		core::position2di(Position.X + Width, Position.Y + Height));//Lower Right
	core::rect<s32> rect2(other->getPos(),//UL
		core::position2di(other->getPos().X + other->getWidth(), other->getPos().Y + other->getHeight()));//LR

	return rect1.isRectCollided(rect2);
}

void CSprite::draw()
{
	Driver->draw2DImage(Texture,Position,Frame[CurrentFrame],0,video::SColor(255,255,255,255),false);
}

void CSprite::draw(core::position2di &posMap)
{
	// \param posMap position of the map.
	Driver->draw2DImage(Texture,Position,Frame[CurrentFrame],0,video::SColor(255,255,255,255),false);
}

void CSprite::drawAlpha()
{
	Driver->draw2DImage(Texture,Position,Frame[CurrentFrame],0,video::SColor(255,255,255,255),true);
}

void CSprite::drawAlpha(core::position2di &posMap)
{
	// \param posMap position of the map.
	Driver->draw2DImage(Texture,Position - posMap,Frame[CurrentFrame],0,video::SColor(255,255,255,255),true);
}

You can add some methods which lack from the class.

I feel shy to share my noob class

because I'm the beginner,too

Good Luck!

[rogerborg]

Checking every sprite against every other sprite is an O(n^2) order problem.

Instead, consider storing the sprites sorted by (e.g.) X co-ordinate, then you only have to test them against the sprites on either side until you reach one that they can't possibly collide with (based on the size of the largest sprite). That brings it down to O(n).