HTML5 Canvas Game

[Jordan]

Dec 19, 2010 10:58:10 GMT prads said:

From the samples given in the SDK and a book by Frank D. Luna, those help me learn the DirectX. Though I haven't learn pixel shading yet.

I figured you read a book since 3D programming is much more complicated. I need to do the same thing, and if you ever make your code open source let me know.

Dec 19, 2010 10:58:10 GMT prads said:

In my game, collision is done by calling simple bounding box overlap checking and if it returns true, another algorithm derived from Separating Axis Theorem is called. That is enough since cars usually have rectangular concave shape.

Did you have to write them yourself or were they already implemented? I am using bounding boxes as well, actually circles, but I just check to see if they overlap.

Dec 19, 2010 10:58:10 GMT prads said:

I don't have deep knowledge on Spatial Subdivision. I believe it's like dividing space into smaller parts and then doing a checking (Bounding Box checking?) so that only the objects near each other are checked for collision. That is done for speed right? Since checking collision against every objects is redundant.

You got it completely. Basically I have an objects array which holds pointers to all the objects which are derived from an Object class, and then after I call obj.move() on an object, I store a copy of the object's pointer in a subplane array according to where it is on the screen so only objects that are near to each other get checked for overlapping. I then call my collision detection algorithm on the sub arrays. Right now I only split the screen into 2 sections, but I plan on splitting it up to 4 or 8 sections to make it more efficient.

[prads]

Dec 20, 2010 0:29:31 GMT Jordan said:

I figured you read a book since 3D programming is much more complicated. I need to do the same thing, and if you ever make your code open source let me know.

Code will be open source, but will be hard to read. But I will try to write a separate documentation so other's can read the mess I wrote. lol

Dec 20, 2010 0:29:31 GMT Jordan said:

Did you have to write them yourself or were they already implemented? I am using bounding boxes as well, actually circles, but I just check to see if they overlap.

I read about the algorithm here: www.gamedev.net/reference/programming/features/2dRotatedRectCollision/
And then wrote it myself. Here's the code:

Simple bounding box collision check done in each frame:

bool d3dCollide::checkCollision(D3DXVECTOR3 AMinP, D3DXVECTOR3 AMaxP, D3DXVECTOR3 BMinP, D3DXVECTOR3 BMaxP) {
if (AMaxP.x < BMinP.x || AMaxP.z < BMinP.z)
return false;
else if (AMinP.x > BMaxP.x || AMinP.z > BMaxP.z)
return false;
else
return true;
}


Now the vector projection code. Formula for vector projection is:
Projection(a,p) = (p.a / ||a||^2) * a (where a = Axis and p = Point)
Code:
void d3dCollide::vecProjection(D3DXVECTOR3 *vOut, D3DXVECTOR3 axis, D3DXVECTOR3 point) {
vOut->x = (D3DXVec3Dot(&point, &axis) / (axis.x * axis.x + axis.z * axis.z)) * axis.x;
vOut->y = 0;
vOut->z = (D3DXVec3Dot(&point, &axis) / (axis.x * axis.x + axis.z * axis.z)) * axis.z;
}


And my implementation of Separating Axis Theorem Algorithm:
bool d3dCollide::SATCTest(D3DXVECTOR3 (&objA)[4], D3DXVECTOR3 (&objB)[4]) {
D3DXVECTOR3 vecAxis[4], projPoints;
float MinA, MaxA, MinB, MaxB, dotProduct;

vecAxis[0] = objA[0] - objA[2]; vecAxis[0].y = 0;
vecAxis[1] = objA[1] - objA[2]; vecAxis[1].y = 0;
vecAxis[2] = objB[0] - objB[2]; vecAxis[2].y = 0;
vecAxis[3] = objB[1] - objB[2]; vecAxis[3].y = 0;

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
vecProjection(&projPoints, vecAxis[i], objA[j]);
dotProduct = D3DXVec3Dot(&projPoints, &vecAxis[i]);
if (!j)
MinA = MaxA = dotProduct;
else if (MinA > dotProduct)
MinA = dotProduct;
else if (MaxA < dotProduct)
MaxA = dotProduct;

vecProjection(&projPoints, vecAxis[i], objB[j]);
dotProduct = D3DXVec3Dot(&projPoints, &vecAxis[i]);
if (!j)
MinB = MaxB = dotProduct;
else if (MinB > dotProduct)
MinB = dotProduct;
else if (MaxB < dotProduct)
MaxB = dotProduct;
}
if (MinB <= MaxA && MaxB >= MinA) continue; else return false;
}
return true;
}


Dec 20, 2010 0:29:31 GMT Jordan said:

You got it completely. Basically I have an objects array which holds pointers to all the objects which are derived from an Object class, and then after I call obj.move() on an object, I store a copy of the object's pointer in a subplane array according to where it is on the screen so only objects that are near to each other get checked for overlapping. I then call my collision detection algorithm on the sub arrays. Right now I only split the screen into 2 sections, but I plan on splitting it up to 4 or 8 sections to make it more efficient.

Yeah I think it needs to be more than two, would be more efficient that way.

[Jordan]

Dec 20, 2010 9:24:05 GMT prads said:

Code will be open source, but will be hard to read. But I will try to write a separate documentation so other's can read the mess I wrote. lol

Awesome.

Dec 20, 2010 9:24:05 GMT prads said:

I read about the algorithm here: www.gamedev.net/reference/programming/features/2dRotatedRectCollision/
And then wrote it myself. Here's the code:

Simple bounding box collision check done in each frame:

bool d3dCollide::checkCollision(D3DXVECTOR3 AMinP, D3DXVECTOR3 AMaxP, D3DXVECTOR3 BMinP, D3DXVECTOR3 BMaxP) {
if (AMaxP.x < BMinP.x || AMaxP.z < BMinP.z)
return false;
else if (AMinP.x > BMaxP.x || AMinP.z > BMaxP.z)
return false;
else
return true;
}


Now the vector projection code. Formula for vector projection is:
Projection(a,p) = (p.a / ||a||^2) * a (where a = Axis and p = Point)
Code:
void d3dCollide::vecProjection(D3DXVECTOR3 *vOut, D3DXVECTOR3 axis, D3DXVECTOR3 point) {
vOut->x = (D3DXVec3Dot(&point, &axis) / (axis.x * axis.x + axis.z * axis.z)) * axis.x;
vOut->y = 0;
vOut->z = (D3DXVec3Dot(&point, &axis) / (axis.x * axis.x + axis.z * axis.z)) * axis.z;
}


And my implementation of Separating Axis Theorem Algorithm:
bool d3dCollide::SATCTest(D3DXVECTOR3 (&objA)[4], D3DXVECTOR3 (&objB)[4]) {
D3DXVECTOR3 vecAxis[4], projPoints;
float MinA, MaxA, MinB, MaxB, dotProduct;

vecAxis[0] = objA[0] - objA[2]; vecAxis[0].y = 0;
vecAxis[1] = objA[1] - objA[2]; vecAxis[1].y = 0;
vecAxis[2] = objB[0] - objB[2]; vecAxis[2].y = 0;
vecAxis[3] = objB[1] - objB[2]; vecAxis[3].y = 0;

for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
vecProjection(&projPoints, vecAxis[i], objA[j]);
dotProduct = D3DXVec3Dot(&projPoints, &vecAxis[i]);
if (!j)
MinA = MaxA = dotProduct;
else if (MinA > dotProduct)
MinA = dotProduct;
else if (MaxA < dotProduct)
MaxA = dotProduct;

vecProjection(&projPoints, vecAxis[i], objB[j]);
dotProduct = D3DXVec3Dot(&projPoints, &vecAxis[i]);
if (!j)
MinB = MaxB = dotProduct;
else if (MinB > dotProduct)
MinB = dotProduct;
else if (MaxB < dotProduct)
MaxB = dotProduct;
}
if (MinB <= MaxA && MaxB >= MinA) continue; else return false;
}
return true;
}


Thanks for the link and code, that helps a lot. That algorithm is better than what I am using since it works with any polygon. I read through the article and I didn't quite understand it all, but I have a question about the projection formula which may help me with a problem I have right now.

I'm dealing with a classic 2D detection problem, and that is objects moving at high velocities passing through each other. In my Centipede game which is extremely inefficient, I just moved the coordinates by a small amount of pixels for fast moving objects and a fraction of a pixel for slow moving objects and just looped the physics function many times between calling draw(). I don't want to do this again and so I read that I need to draw a line/vector out in front of the object and see if it intersects with any other lines/vectors from any other objects nearby to see if they will collide in between frames. Could I use that projection formula to do that or not?

[prads]

Dec 21, 2010 5:35:21 GMT Jordan said:

Thanks for the link and code, that helps a lot. That algorithm is better than what I am using since it works with any polygon. I read through the article and I didn't quite understand it all, but I have a question about the projection formula which may help me with a problem I have right now.

I'm dealing with a classic 2D detection problem, and that is objects moving at high velocities passing through each other. In my Centipede game which is extremely inefficient, I just moved the coordinates by a small amount of pixels for fast moving objects and a fraction of a pixel for slow moving objects and just looped the physics function many times between calling draw(). I don't want to do this again and so I read that I need to draw a line/vector out in front of the object and see if it intersects with any other lines/vectors from any other objects nearby to see if they will collide in between frames. Could I use that projection formula to do that or not?

No, you cannot. Let say you have a point P1 and axis A (a vector). What the above vector projection formula will give you is the another point P2 such that line formed joining P1 and P2 is perpendicular to the axis A.

Ok, about you problem, you need to find the intersection of two lines. So, I think this formula should help: en.wikipedia.org/wiki/Line-line_intersection

[Jordan]

Dec 21, 2010 17:08:36 GMT prads said:

Dec 21, 2010 5:35:21 GMT Jordan said:

Thanks for the link and code, that helps a lot. That algorithm is better than what I am using since it works with any polygon. I read through the article and I didn't quite understand it all, but I have a question about the projection formula which may help me with a problem I have right now.

I'm dealing with a classic 2D detection problem, and that is objects moving at high velocities passing through each other. In my Centipede game which is extremely inefficient, I just moved the coordinates by a small amount of pixels for fast moving objects and a fraction of a pixel for slow moving objects and just looped the physics function many times between calling draw(). I don't want to do this again and so I read that I need to draw a line/vector out in front of the object and see if it intersects with any other lines/vectors from any other objects nearby to see if they will collide in between frames. Could I use that projection formula to do that or not?

No, you cannot. Let say you have a point P1 and axis A (a vector). What the above vector projection formula will give you is the another point P2 such that line formed joining P1 and P2 is perpendicular to the axis A.

Ok, about you problem, you need to find the intersection of two lines. So, I think this formula should help: en.wikipedia.org/wiki/Line-line_intersection

Ah, thanks, that's exactly what I needed.

I have another question for you, though.

How do you decide which objects should be compared with each other? Do you keep a grid of some sort and then just loop through the grid pieces around the piece? I'm just wondering since there's got to be a better way than the Spatial Subdivision algorithm I'm using.

[prads]

In my game, I don't check collision for each and every objects, instead big bounding boxes are used. For example, a straight drag racing track has no more than 4 Bounding Boxes (Front, Back, Left and Right). Now if I want to put a corner, 2 more bounding box needs to be added, if 2 corners, total bounding boxes are 8 and so on. And drag racing tracks don't have many corners so, maybe 16 to 18 bounding boxes maximum.
So, what I do is loop through those bounding box and make a bounding box overlap checks and if that returns true, only then I call the SAT Collision Check. That way, only the bounding boxes that are near player's car is checked with SAT. One of the track I made contains only 4 bounding boxes, so it would have been useless to do Spatial Subdivision.

[Jordan]

Ah, so basically if I understand this correctly, you have a hierarchy of bounding boxes? Basically a large one, then maybe one or two smaller ones within it, and then smaller ones inside those etc?

[prads]

Not really. I will try to make this clear using pictures.

1st Picture:



2nd Picture:



Black = Track
Blue = Objects like houses, trees, bushes etc.
Red = Bounding Boxes

In the first picture, there are 4 bounding boxes, BB1, BB2, BB3 and BB4. And in the middle of those Bounding Boxes, there is a straight track.

In the second picture, there is a corner between "start" and "end" and there are 2 more Bounding Boxes than in the previous track/picture. Now you may ask, "why can't we make BB3 big enough so that it cover BB5? There would be no need for BB5 then." Well, every Bounding Box has a vector, which is used to calculate the angle by which the car is to be rotated if it collides with the Bounding Box. So, vector for BB3 (-1,0,0) won't be same for vector for BB5 (0, 0, 1).
Angle is calculated by finding the angle between player's car look vector and Bounding Box vector. Formula is:
A = cos^-1(CL.BB) / (|CL||BB|) (where A = Angle, CL = Car's look vector and BB = Bounding Box vector).

[Cam]

You should post a tutorial!

[Jordan]

Thanks for all those pictures, I see what you mean now. The bounding boxes are basically just used for static objects, right? If you had other cars then you would then have to loop through each car and see if any overlap unless you divided the racetrack into sections and just checked the cars that are in the same section with each other.

[prads]

Yep, only for static. But the race will have only two opponents so no need to divide the track.