Techniques for making a 2D game world.

[bilygates]

Hello. This is my first attempt at making a game and I will appreciate any help you can give me.

I want to make a 2D game where you control a tiny ship in a cave of some sort. This cave will be created automatically (random levels) and will look like this:
.

Suppose I already have the points of the polygon of the inside of the cave (the white part). How should I render this shape on the screen and use it for collision detection? From what I've read around different forums, I should use a triangulation algorithm to make meshes of the walls of the cave (the black part) using the polygon of the inside of the cave (the white part). Then, I can also use these meshes for collision detection. Is this really the best way to do it? Does Irrlicht have some built-in functions that can help me?

Furthermore, how can I "smoothen" the walls of the cave? I will generate a rough polygon, but a smoother one would look more pleasant.

Thanks in advance!

[pippy3]

If you want to use triangles, you'd have to build it from a custom scene node with a array of vertex points and indexes. This would require a lot of thought and be very difficult to achieve. for collision, ISceneCollisionManager has a function getSceneNodeAndCollisionPointFromRay which would work well with it. The mesh would have to be in 3d, but if you have an orthographic view you wouldn't see the edges.

What you want to do seems it would be best in 2d; Irrlicht is mostly a 3d engine. Using 3d would be nice as you could show off depth in the background/forground. Also you'd save on having to draw hundreds of frames, but realisiticly you'd be more likely to get the job done with an engine like pygame.

EDIT: alternatively you could use an array of triangle3ds and use getIntersectionOfPlaneWithLine for collisions.

[Brainsaw]

A game like this is also on my schedule. I already created a class that makes a 3D model (for the cave) out of an Image. Gotta check my archives at home. I originally wanted to use the box2d physics engine, but I had some problems getting it up and running, so I came back to ODE (which I already knew). The model I'm creating looks quite crappy, I think I'll search for my early version, port it to a newer version of Irrlicht and put it online (if I find enough time this weekend).

[bilygates]

@pippy3: I know it would be easier to use a 2d engine like PyGame, Allegro, SFML, etc., but I'm willing to take the challenge.

@brainsaw: It would be great if you could share that project of yours, even if it runs with an older version of Irrlicht. Although I won't be generating an image for the cave, I'm sure there are bits of code I will find useful.

Any other thoughts on this?

[Ulf]

Since it is only 2D and if you are really up to the challenge, then you might want to create your own collision detection algorithms using the Separating Axis theorem. That's what I have done since I want to start with 2D as well.
I could have chosen some physics engine, but I wanted to learn the underlying physics of it. I'm a stickler for punishing myself!
It takes time though, even on a simple level.
I can find collisions with convex or concave polygons.

You set up the collision checking to first test for bounding box collision. If the bounding boxes don't collide, then there is no collision. If the bounds boxes collide, then you test with SA theorem, then you do the full check at the end to get the point of intersection, normal etc. so you can respond to the collision.

Then you can make your map thing in various ways.

One basic method is to make the boundaries (black parts) into sections of convex polygons. Put them all in an array and as your objects travel around the map, they check for collisions against those boundary polygons.
Doing it that way can reduce your overhead. You can basically just check the polygons that are in your vicinity if you keep the map polygons ordered by x and y position in the array.

I created a static class of functions to perform collision testing between 2 objects. (Headers below) Then I made a collision manager which uses these static functions and keeps track of objects.

Code: Select all

struct SPolygonCollisionResult 
{
public:
	//! Empty Constructor
	SPolygonCollisionResult()
	: pPolygon1((ICollisionObject *)NULL),
	  pPolygon2((ICollisionObject *)NULL),
	  vIntersect(bkNullVectorf),
	  vNormal(bkNullVectorf),
	  fDepth(0.0)
	{}

	//! Constructor
	SPolygonCollisionResult(ICollisionObject const * const p1,
							ICollisionObject const * const p2)
	: pPolygon1(const_cast<ICollisionObject *>(p1)),
	  pPolygon2(const_cast<ICollisionObject *>(p2)),
	  vIntersect(bkNullVectorf),
	  vNormal(bkNullVectorf),
	  fDepth(0.0)
	{}

	//! Constructor
	SPolygonCollisionResult(ICollisionObject const * const p1,
							ICollisionObject const * const p2,
							irr::core::vector2df const & intersect,
							irr::core::vector2df const & normal,
							irr::f32 depth)
	: pPolygon1(const_cast<ICollisionObject *>(p1)),
	  pPolygon2(const_cast<ICollisionObject *>(p2)),
	  vIntersect(intersect),
	  vNormal(normal),
	  fDepth(depth)
	{}

	//! First polygon
	ICollisionObject * pPolygon1;

	//! Second polygon
	ICollisionObject * pPolygon2;

	//! Intersection point
	irr::core::vector2df vIntersect;

	//! Normal to polygon 2
	irr::core::vector2df vNormal;

	//! Amount of penetration
	irr::f32 fDepth;

}; // end struct SPolygonCollisionResult


class CCollision
{
// ---------------------------------------------------------------
// Methods
// ---------------------------------------------------------------
public:
//! Check for collision between a point and a rectangle.
/** \param ptTestPoint: point (position) to test collision with.
\param rcBox: box (rectangle) to test collision with.
\return: Returns true if ptTestPoint has collision with rcBox. */
static bool isPointInsideBox(irr::core::vector2di const & ptTestPoint, irr::core::recti const & rcBox)
{
	return rcBox.isPointInside(ptTestPoint);
}
static bool isPointInsideBox(irr::core::vector2df const & ptTestPoint, irr::core::rectf const & rcBox)
{
	return rcBox.isPointInside(ptTestPoint);
}
static bool isPointInsideBox(irr::core::vector2di const & ptTestPoint, irr::core::rectf const & rcBox)
{
	return rcBox.isPointInside(irr::core::vector2df((irr::f32)ptTestPoint.X, (irr::f32)ptTestPoint.Y));
}
static bool isPointInsideBox(irr::core::vector2df const & ptTestPoint, irr::core::recti const & rcBox)
{
	irr::core::rectf const box((irr::f32)rcBox.UpperLeftCorner.X, (irr::f32)rcBox.UpperLeftCorner.Y,
							   (irr::f32)rcBox.LowerRightCorner.X, (irr::f32)rcBox.LowerRightCorner.Y);

	return box.isPointInside(ptTestPoint);
}


//! Check for collision between 2 rectangles.
/** Note: The rect function isRectCollided only needs to test 1 way to find an overlap.
\param rcTestRect: Rectangle 1 to test collision with.
\param rcBox: Rectangle 2 to test collision with.
\return: Returns true if rcTestRect has overlapped rcBox, or vice versa. */
static bool isRectCollision(irr::core::recti const & rcTestRect, irr::core::recti const & rcBox)
{
	return rcTestRect.isRectCollided(rcBox);
}
static bool isRectCollision(irr::core::rectf const & rcTestRect, irr::core::rectf const & rcBox)
{
	return rcTestRect.isRectCollided(rcBox);
}
static bool isRectCollision(irr::core::recti const & rcTestRect, irr::core::rectf const & rcBox)
{
	irr::core::rectf const testRect((irr::f32)rcTestRect.UpperLeftCorner.X, (irr::f32)rcTestRect.UpperLeftCorner.Y,
									(irr::f32)rcTestRect.LowerRightCorner.X, (irr::f32)rcTestRect.LowerRightCorner.Y );

	return testRect.isRectCollided(rcBox);
}
static bool isRectCollision(irr::core::rectf const & rcTestRect, irr::core::recti const & rcBox)
{
	irr::core::rectf const box((irr::f32)rcBox.UpperLeftCorner.X, (irr::f32)rcBox.UpperLeftCorner.Y,
							   (irr::f32)rcBox.LowerRightCorner.X, (irr::f32)rcBox.LowerRightCorner.Y );

	return rcTestRect.isRectCollided(box);
}


//! Check if a rectangle is fully inside another bounding rectangle (not on border either).
/** \param rcTestRect: Rectangle to test.
\param rcBox: Boundary rectangle.
\return: Returns true if rcTestRect is fully inside rcBox. */
static bool isRectInsideBox(irr::core::recti const & rcTestRect, irr::core::recti const & rcBox)
{
	return (rcTestRect.UpperLeftCorner.X > rcBox.UpperLeftCorner.X && rcTestRect.UpperLeftCorner.Y > rcBox.UpperLeftCorner.Y &&
			rcTestRect.LowerRightCorner.X < rcBox.LowerRightCorner.X && rcTestRect.LowerRightCorner.Y < rcBox.LowerRightCorner.Y);
}
static bool isRectInsideBox(irr::core::rectf const & rcTestRect, irr::core::rectf const & rcBox)
{
	return (rcTestRect.UpperLeftCorner.X > rcBox.UpperLeftCorner.X && rcTestRect.UpperLeftCorner.Y > rcBox.UpperLeftCorner.Y &&
			rcTestRect.LowerRightCorner.X < rcBox.LowerRightCorner.X && rcTestRect.LowerRightCorner.Y < rcBox.LowerRightCorner.Y);
}
static bool isRectInsideBox(irr::core::recti const & rcTestRect, irr::core::rectf const & rcBox)
{
	irr::core::rectf const testRect((irr::f32)rcTestRect.UpperLeftCorner.X, (irr::f32)rcTestRect.UpperLeftCorner.Y,
									(irr::f32)rcTestRect.LowerRightCorner.X, (irr::f32)rcTestRect.LowerRightCorner.Y);

	return (testRect.UpperLeftCorner.X > rcBox.UpperLeftCorner.X && testRect.UpperLeftCorner.Y > rcBox.UpperLeftCorner.Y &&
			testRect.LowerRightCorner.X < rcBox.LowerRightCorner.X && testRect.LowerRightCorner.Y < rcBox.LowerRightCorner.Y);
}
static bool isRectInsideBox(irr::core::rectf const & rcTestRect, irr::core::recti const & rcBox)
{
	irr::core::rectf const box((irr::f32)rcBox.UpperLeftCorner.X, (irr::f32)rcBox.UpperLeftCorner.Y,
							   (irr::f32)rcBox.LowerRightCorner.X, (irr::f32)rcBox.LowerRightCorner.Y);

	return (rcTestRect.UpperLeftCorner.X > box.UpperLeftCorner.X && rcTestRect.UpperLeftCorner.Y > box.UpperLeftCorner.Y &&
			rcTestRect.LowerRightCorner.X < box.LowerRightCorner.X && rcTestRect.LowerRightCorner.Y < box.LowerRightCorner.Y);
}


//! Performs a collision test for two collision items. Check both ways.
/** Note: This only needs to be done when a bounding box overlap has occured. So do that test first.
Note: Uses the SA and VE test to check for collision. Does not keep any stats.
\param pPolygonA: The first polygon.
\param pPolygonB: The second polygon.
\param sCollisionResult: Return parameter. 
\return: Returns true if there is a penetrating vertex.
\pre: the polygons are assumed to be valid. */
static bool isPolygonCollision(ICollisionObject const * const pPolygonA,
							   ICollisionObject const * const pPolygonB,
							   SPolygonCollisionResult & sCollisionResult);


//! Performs a collision test for two collision items. Check both ways.
/** Note: This only needs to be done when a bounding box overlap has occured. So do that test first.
Note: Uses the SA and VE test to check for collision. Does not keep any stats.
\param pPolygonA: The first polygon.
\param pPolygonB: The second polygon.
\param arVertexCollisionA: The address of the array of boolean values representing each vertex of pPolygonA, and whether each vertex collides with pPolygonB.
\param arVertexCollisionB: The address of the array of boolean values representing each vertex of pPolygonB, and whether each vertex collides with pPolygonA.
\param sCollisionResult: Return parameter. 
\return: Returns true if there is a penetrating vertex.
\pre: the polygons are assumed to be valid. */
static bool isPolygonCollision(ICollisionObject const * const pPolygonA,
							   ICollisionObject const * const pPolygonB,
							   irr::core::array<bool> & arVertexCollisionA,
							   irr::core::array<bool> & arVertexCollisionB,
							   SPolygonCollisionResult & sCollisionResult);


//! Check if polygon A is going to collide with polygon B.
/** Note: Does not keep any stats. Only check one way.
Uses the separating axis theorem to test for collision. 
Checks every vetex of PolygonA against every edge of polygonB for collision.
If one of the edges of polygon B is a separator line, we can return false.
To find a collision we must check every edge of polygon B.
\param pPolygonA: The first polygon that may collide with pPolygonB.
\param pPolygonB: The second polygon that may be impacted by pPolygonA.
\return: Returns false if there is an edge that separates the two polygons.
True simply means potential for an overlap.
\pre: the polygons are assumed to be valid. */
static bool SACollisionTest(ICollisionObject const * const pPolygonA, ICollisionObject const * const pPolygonB);


//! Test of all vertices in pPolygonA against all edges in pPolygonB. 
/** Note: Does not keep any stats. Only check one way.
This is looking for a vertex in pPolygonA that is inside pPolygonB, a symmetrical problem to the above tests.
Note: This function returns the best collision result for the 2 polygons.
m_sBestCollide can be used to repair the collision when it happens.
\param pPolygonA: The first polygon that may collide with pPolygonB.
\param pPolygonB: The second polygon that may be impacted by pPolygonA.
\param sCollisionResult: Return parameter. 
(Will be modified in this function to reflect the best collision found, else will be set to zero.)
\return: Returns true if there is a penetrating vertex.
\pre: the polygons pPolygonA and pPolygonB are assumed to be valid. 
\post: The collision result, sCollisionResult has its two polygons set to the two polygon parameters, pPolygonA and pPolygonB. */
static bool VECollisionTest(ICollisionObject const * const pPolygonA,
							ICollisionObject const * const pPolygonB,
							SPolygonCollisionResult & sCollisionResult);


//! Check if a any points of a polygon are inside a non-convex or convex polygon.
/** Note: Does not keep any stats. Only check one way. 
This is a parallel test to testSA, which first check if there is a collision, before finding the exact intersection.
FAST VERSION, but does NOT set an array of boolean values indicating which vertices had collisions. 
Returns once a collision is found. If using the SLOW version (below), the return parameter, arVertexCollision, 
can be passed back into the function VEConcaveCollisionTest(). Which allows VEConcaveCollisionTest() to
perform more quickly by skipping all non-colliding vertices. It only needs to check the vertices that were
found to be colliding to find the deepest collision.
\param pPolygon: The polygon that may collide with pConcavePolygon.
\param pConcavePolygon: The polygon that may be impacted by pPolygon.
\return: Returns true if the polygon is inside the concave polygon, else false. 
\pre: the polygons are assumed to be valid. */
static bool SAConcaveCollisionTest(ICollisionObject const * const pPolygon, ICollisionObject const * const pConcavePolygon);


//! Check if a any points of a polygon are inside a non-convex or convex polygon.
/** Note: Does not keep any stats. Only check one way.
This is a parallel test to testSA, which first check if there is a collision, before finding the exact intersection.
Note: SLOW but PROPER VERSION. Sets an array of boolean values indicating which vertices had collisions. 
The return parameter, arVertexCollision, can be passed back into the function VEConcaveCollisionTest(). 
This allows VEConcaveCollisionTest to perform more quickly by skipping all non-colliding vertices.
VEConcaveCollisionTest won't work correctly otherwise, as it doesn't know which side of each edge is inside the polygon. 
So it would simply find the vertex that is closest to any edge, inside or outside the polygon.
That is why we must use the version of SAConcaveCollisionTest function that has the array parameter arVertexCollision.
This function sets the array with boolean values indicating if each vertex is inside or outside the polygon.
We can then pass this array into the VEConcaveCollisionTest function.
There are 2 versions of SAConcaveCollisionTest because we may want to find a collision without finding collision results.
But there is only one version of VEConcaveCollisionTest which uses the array because trying to find the exact collision result
without first knowing which vertices are inside the polygon, is useless. Gives unreliable and incorrect results.
\param pPolygon: The polygon that may collide with pConcavePolygon.
\param pConcavePolygon: The polygon that may be impacted by pPolygon.
\param arVertexCollision: The address of the array of boolean values representing each vertex of pPolygon, and whether each vertex collides with pConcavePolygon.
Note: The boolean values must be set in this function.
\return: Returns true if the polygon is inside the concave polygon, else false. 
\pre: the polygons are assumed to be valid. */
static bool SAConcaveCollisionTest(ICollisionObject const * const pPolygon,
								   ICollisionObject const * const pConcavePolygon,
								   irr::core::array<bool> & arVertexCollision);


//! Test of all vertices in pPolygon against all edges in pConcavePolygon. 
/** Note: Does not keep any stats. Only check one way.
FAST VERSION, does use an array of boolean values indicating which vertices had collisions. Thus, can skip non-collising vertices.
This is looking for a vertex in pPolygon that is INSIDE pConcavePolygon.
This function sets the member vavriable, m_sBestCollide.
m_sBestCollide can be used to repair the collision when it happens.
\param pPolygon: The polygon that may collide with pConcavePolygon.
\param pConcavePolygon: The polygon that may be impacted by pPolygon.
\param arVertexCollision: The address of the array of boolean values representing each vertex of pPolygon, and whether each vertex collides with pConcavePolygon.
Note: The values cannot be changed in this function. This array must be calculated previously. The function SAConcaveCollisionTest sets these values.
\param sCollisionResult: Return parameter. 
(Will be modified in this function to reflect the best collision found, else will be set to zero.)
\return: Returns true if there is a penetrating vertex.
\pre: the polygons are assumed to be valid.
\post: The collision result, sCollisionResult has its two polygons set to the two polygon parameters, pPolygon and pConcavePolygon. */
static bool VEConcaveCollisionTest(ICollisionObject const * const pPolygon,
								   ICollisionObject const * const pConcavePolygon,
								   irr::core::array<bool> const & arVertexCollision,
								   SPolygonCollisionResult & sCollisionResult);


//! Performs a boundary collision test for a polygon and a boundary polygon. Does not keep any stats.
/** Note: This is a symmetrical problem to the polygon collision tests which
check if any vertices of one polygon penetrate (ENTER) any edge of another polygon.
This function checks if any vertices of pPolygon EXIT the boundary of polygon pBoundary.
\param pPolygonA: The polygon that may collide with boundary pBoundary.
\param pPolygonB: The boundary polygon.
\param sCollisionResult: Return parameter. 
(Will be modified in this function to reflect the best collision found, else will be set to zero.)
\return: Returns true if there is a penetrating vertex.
\pre: the polygon and boundary are assumed to be valid. */
static bool isBoundaryCollision(ICollisionObject const * const pPolygon,
								ICollisionObject const * const pBoundary,
								SPolygonCollisionResult & sCollisionResult);


//! Check if polygon is going to collide with boundary polygon.
/** Note: Does not keep any stats. Only needs to check one way.
Note: Uses a modified (reversed) implementation of the separating axis theorem to test for collision.
Checks every vetex of PolygonA against every edge of polygonB for collision.
If one of the edges of polygon B is not a separator line, we have found a collision and can return true.
To prove that there is no collision we must unfortunately check every edge of polygon B.
\param pPolygon: The polygon that may collide with pBoundary..
\param pBoundary: The boundary polygon.
\return: Returns true if there may be a collision. 
\pre: the polygon and boundary are assumed to be valid. */
static bool SABoundaryCollisionTest(ICollisionObject const * const pPolygon,
									ICollisionObject const * const pBoundary);


//! Test of all vertices in pPolygon against all edges in pBoundary.
/** Note: Does not keep any stats. Only needs to check one way.
This is looking for a vertex in pPolygon that is OUTSIDE pBoundary.
This function sets the collision result parameter variable, m_sBestBoundaryCollide.
m_sBestBoundaryCollide can be used to repair the collision when it happens.
\param pPolygon: The polygon that may collide with pBoundary.
\param pBoundary: The boundary polygon.
\param sCollisionResult: Return parameter. 
(Will be modified in this function to reflect the best collision found, else will be set to zero.)
\return: Returns true if there is a penetrating vertex.
\pre: the polygon and boundary are assumed to be valid. 
\post: The collision result, sCollisionResult has its two polygons set to the two polygon parameters, pPolygon and pBoundary. */
static bool VEBoundaryCollisionTest(ICollisionObject const * const pPolygon,
								    ICollisionObject const * const pBoundary,
								    SPolygonCollisionResult & sCollisionResult);
}; // end class CCollision

Just a note: I also made some "reverse" SA tests to do boundary collision checking. Normal SA test checks if the polygon is entered, whereas proper boundary collision checks if you exit.

But as I was explaining before all the code above, you can just make polygons from the boundary and test for collision using the standard SA test.

If you want my collision manager code, plus the static functions above, I'm not quite happy to release it yet. It's not fully tested yet. I just did some static tests.

[Brainsaw]

OK, I found my old project in my archives. All it does is take an image and create 3d models out of it to show the world. The program also features an ugly spaceship I created . When starting the program you have a fps camera, the actual object is on the right side below you (in case you can't find it). The program can be downloaded at

dustbin-online.de/gravitation.zip

here are two images to show what it actually does:

1: the input image


2: a screenshot of the result


edit: I have used 3 colors for the image:

- white is empty space
- gray is rock
- black is rock that will create collision triangles

[Ulf]

@Brainsaw
That's pretty cool.

So does he view it orthogonally and do the collision checking against the boundary mesh?

[Adler1337]

@Brainsaw
That's pretty cool.

I agree, that's amazing

[Brainsaw]

Thanks a lot. I spent some time doing this, but it has now been resting for one and a half years. I still want to make a game using this, but not before the current project is finished.

[pippy3]

I had an idea: why not use ITerrainSceneNode, flip it on it's side, and then remove (or hide via alpha transparency) the triangles that are under a certain value.

Doing it this way would save a lot of code, and give you an option of having depth. Also zooming would be a lot smoother too because it's a mesh.

[bilygates]

Hey folks. Thanks for all your help, I really appreciate it. Here's what I've come up with:



In the second image you can also see the polygons (red and green) used to generate the cave. The blue ones are used for collision detection (check the rounded corners, especially).

I've managed to do this with 3 libraries besides Irrlicht: GPC for clipping polygons (union, difference, etc), Poly2tri for triangulation and Box2D for collision detection.

Now I have another question for you. As you can see, each triangle has an image of a red dot painted on it. How can I paint something like a wall texture uniformly on the meshes (the unconnected walls in the middle are different meshes)? Do I have to change the texture coordinates of each vertex or is there another way?

LE: Never mind, I've just discovered makePlanarTextureMapping.

Thanks!