Collision problem. Projectile colliding with invisible diagonal barrier.
piskypom

Git Repo (dev branch)

I know it's alot of code to look at. And honestly this is just a long shot to see if anybody has spare time to look at it.

The problem is when you click your mouse to shoot the projectile out of the end of the line (aimer), the projectile will hit this invisible barrier that runs diagonally across the screen from the bottom left to top right. Probably not a coincidence it crosses the target too. It's like the math I use stretches the target shape and "skews" and stretches it across the screen.

I have an entities_collided() function that is making me pull my hair out. The relevant functions are

1bool Game::entities_collided() 2bool Entity::operator>(const Entity &rhs) const 3void Entity::set_sides(Entity &_ent, Coords _origin, Dimension _dimension)

The structure is confusing, so I'll break it down:

First I take the top left coordinates of an entity and determine it's top, bottom, left, and right side values. It's not their lengths. I use square collision using the four points. I add like this:

1// 10x10 square 2pA(0,0) // Top left 3pB(10,0) // Top right 4pC(0,10) // Bottom left 5pD(10,10)// Bottom right 6 7Obj objA.top = pA.x + pB.x + pA.y + pB.y; 8Obj objA.bot = pC.x + pD.x + pC.y + pD.y; 9Obj objA.left = pA.x + pC.x + pA.y + pC.y; 10Obj objA.right = pB.x + pD.x + pB.y + pD.y;

Then I just compare the values of each side of each object. It actually works nicely.

I do this math for both the projectile and the target. The formula for square collision is:

1if (objA.left < objB.right && 2 objA.right > objB.left && 3 objA.top < objB.bot && 4 objA.bot > objB.top)

I'm sure you veterans know this formula by heart. Just recapping for the rest of us.

I created an operator overload of > so that I can just take any object and say objA > objB. The function takes care of all the math.

Perhaps I made this all too convoluted and thus confusing to debug. I'll eventually simplify things and make them easier to understand.

Thanks for your time.

NiteHackr

The way I do simple box collision is instead of checking for collisions, I reject instances where collisions are impossible.

In some older code I have something like this, it's quite simple...

```// If the bottom of one is less than the top of another, than they cannot be colliding...
if(bottomA < topB) return false;

// if the top of one, is greater than the bottom of another, no collision possible...
if(topA > bottomB) return false;

// If the right of one is less than the left of another, impossible to be colliding...
if(rightA < leftB) return false;

// If the left of one is greater than the right of another, impossible to be colliding...
if(leftA > rightB) return false;
```

This makes it super simple. And if all four of these tests fail, you absolutely have a collision.

Later on, I ended up changing this code so that it did circular collision which is simple as well. You check if the distance between the two objects is less than the sum of their two radius', if so, they are colliding.

piskypom

OK, right on Neil. I'll give it a shot. Though I'm convinced it's not my collision logic. I have this sad feeling I'll have to abandon this and start over. It's a bit of a can of worms for me eyes. I'll split up things into different classes to make it easier for me to debug.

Also, I'll do collision checking before I do any other code. That way I know it works and when something goes wrong, it's not the collision.

By chance, did you happen to glance at handle_events()? Just curious if I'm utilizing the even system properly.

Anyway, I'm off to go try your suggestion. And you're right, it is a much simpler way. Why not put them in if/else form that way it doesn't check each if implicitly? You know, if it's false it doesn't have to go through those precious cpu cycles to ge to the next condition?

*Edit: It was a good idea, but the invisible barrier is still there. So weird. I don't know where it's coming from. Back to the drawing board.

*Edit2: I apologize. My math was wrong. It's shameful. I now have the fix. So lesson is don't do this:

1Rectangle rec1(x,y) 2Rectangle rec2(x,y) 3 4rec1.top = rec1.x + rec2.x + rec1.y + rec2.y; 5 6/* 7 * Comparing sides with the above math is not correct. 8 * It does in fact draw an invisible diagonal. 9 * Solution is to do it properly: 10 */ 11 12rec1.top = rec.y; 13rec1.bot = rec.y + rec.height; 14rec1.left = rec.x; 15rec1.right = rec.x + width;

A really simple fix. Thanks for letting me trouble you guys.

NiteHackr

The reason why I have separate checks is if any one of them fails (which will be most of the time), it returns right away.

As far as CPU cycles go, well, if you have several tests in a single check, it STILL has to check each test until one fails before it exits. So there's really no difference. I prefer the separate if's to keep it more "human readable".

And yeah, you should have your collision check in it's own function. Here's my full box collision function I used to use in my Deluxe Pacman 2 game...

1// Bounding box collision detection 2bool dp2_collision(PACMAN *p, GHOST *g) 3{ 4 #define BUFFER 10 5 6 int leftp, leftg; 7 int rightp, rightg; 8 int topp, topg; 9 int bottomp, bottomg; 10 11 // if the ghost is dead, there can be no collision 12 if(g->dead) return false; 13 14 // set the top, bottom, left and right boundries for each bitmap 15 leftp = p->x - 25 + BUFFER; 16 leftg = g->x - 9 + BUFFER; 17 rightp = p->x + 24 - BUFFER; 18 rightg = g->x + 40 - BUFFER; 19 topp = p->y - 25 + BUFFER; 20 topg = g->y - 9 + BUFFER; 21 bottomp = p->y + 24 - BUFFER; 22 bottomg = g->y + 40 - BUFFER; 23 24 // In this code we're not checking to see if the sprites overlap, 25 // but the opposite, we're checking to see if they do NOT overlap! 26 // If any of these tests are true, an overlap is impossible and so 27 // we can safely return false, or no collision. 28 // I think each test is fairly self explanitory. 29 if(bottomp < topg) return false; 30 if(topp > bottomg) return false; 31 32 if(rightp < leftg) return false; 33 if(leftp > rightg) return false; 34 35 // the bitmaps are definitely overlapping so flag a collision 36 return true; 37}

I eventually replaced it with a circle collision check and added a radius to my main player and the ghosts.

1// Circular collision detection 2bool dp2_collision(PACMAN *p, GHOST *g) 3{ 4 // If the ghost is already dead, there is no collision 5 if(g->dead) return false; 6 7 double gx = (double)g->x + 16.0; // ghost.x is based on tile size (32), so half that is 16. 8 double gy = (double)g->y + 16.0; // ghost.y is based on tile size (32), so half that is 16. 9 double px = (double)p->x; 10 double py = (double)p->y; 11 double dist_x = px - gx; 12 double dist_y = py - gy; 13 double gr = g->r; 14 double rt = abs(p->r + gr); 15 16 if(abs(dist_x) > rt) return false; 17 else if(abs(dist_y) > rt) return false; 18 19 double dist = sqrt((dist_x * dist_x) + (dist_y * dist_y)); // The distance of the vector between the two 20 21 // is the distance less than or equal to the absolute sum of the two radius'? 22 return dist <= rt; 23}

piskypom

Oh that's brilliant. The circle collision, I love it! Don't mind if snag these into my stash o' scripts?

I've downloaded both pacman. I want to try them out. I love seeing other peoples creations. I haven't made a game yet. But I intend to do something this time. Just like I said last time. And the time before ...

Eric Johnson

I don't have anything meaningful to add, but I wanted to say this...

@Neil: That's a neat trick. I haven't considered checking if two objects are NOT colliding before. I typically do something like this for AABB collision:

1// pseudo-code for check collision between two rectangles. 2isColliding(x1, y1, w1, h1, x2, y2, w2, h2) { 3 4 return abs(x1 - x2) < w1 + w2 && abs(y1 - y2) < h1 + h2; 5}

I'll start using your method though. It's a few more lines of code, but it's much simpler and easier to read compared to my method. Plus, your way doesn't have to check the rest of the conditions to return false! Thanks for sharing!

Edgar Reynaldo

whether you do it with and or or the logic is all the same and i bet you will produce the same code. The first AND check to fail will halt the testing. Likewise with OR it stops as soon as the first positive is found and returns. Same logic.

Audric

Neil, note that you can do without the sqrt(), using a multiplication of the other term instead :

```   double dist_squared = (dist_x * dist_x) + (dist_y * dist_y);
return dist_squared <= rt * rt;
```

piskypom

@Audic: Is there a benefit to using multiplication over sqrt()? I can't remember what I was told, but a friend explained that there is a particular math that the cpu handles faster than others. Is this the same principle? For example, does the cpu handle multiplication better/or faster than division?

@Edgar: I know for me, it does wind up being the same code, in that the same principles are applied for checking whether something is or isn't colliding. Thanks to Neil, I will use the method for checking if something is not collding.

@Eric: You're right. I prefer code that is easier to read than lengthy one liner formulas (or longer!). My problem with long formulas is that I'm slow at math. So it helps when things are broken down for me. I don't care if it takes using more variables or several shorter lines, I just need to understand what's going on. It's also a plus for sharing your code because fresh eyes looking at the formula may not understand what it's doing or why without detailed notes. Which probably ends up causing you to expend more finger taps on the keyboard thus going counter to writing shorter code with the intent of not having to type as much.

Edit: (I do these a lot) Formulas that use single char variables really frustrate me. Something more meaningful with be: origin_x < destination_x or similar to what Bjarne and Herb wrote about here.

Edit2: (I can't help myself) Additionally, meaningful/descriptive variables saves me time from having to trace the code back to where the var came from and what it's purpose is.

Edgar Reynaldo

Trust me you will get tired of long variable names when you have to write them over and over and over again.

It's cheaper to compare distance squared than the square root of it.

Eric's way of comparing overlap is quite nice and elegant. I would prefer it above all else.

piskypom

Of course this is all a matter of taste!

Even if some got lengthy, the text editor has autocomplete

Edgar Reynaldo

Why use autocomplete? It's an extra couple keys when all I need to do is press one.

Take for example this code :

```   ALLEGRO_DISPLAY* d = al_create_display(800,600);
ALLEGRO_EVENT_QUEUE* q = al_create_event_queue();
ALLEGRO_TIMER* t = al_create_timer(1.0/60.0);
ALLEGRO_FONT* f = al_load_ttf_font("Verdana.ttf" , -20 , 0);

if (!f || !d || !t || !q) {
return -2;
}
```

In this case, there's no need to write out "display", "queue", "timer", and "font" when one letter is enough. They're clearly declared there, and they make code elsewhere much simpler and shorter.

LennyLen

In this case, there's no need to write out "display", "queue", "timer", and "font" when one letter is enough. They're clearly declared there, and they make code elsewhere much simpler and shorter.

It depends on how good/poor your memory is. Mine is terrible. If I looked at that if statement more than 5 minutes after I wrote it, I'd have to search for the declaration of the variables to know what they mean. And then sometimes by the time I've worked out what the q represents, I've forgotten what the f was again.

For people like me, descriptive names save a hell of a lot of time compared to that wasted typing a few extra keystrokes.

piskypom

In this case, there's no need to write out "display", "queue", "timer", and "font" when one letter is enough. They're clearly declared there, and they make code elsewhere much simpler and shorter.

It's all a matter of preference. I'm glad it works for you

NiteHackr
piskypom said:

Don't mind if snag these into my stash o' scripts?

Feel free.

My main thoughts were that most of the time collision checks will fail, so why not check for failure conditions first.

Most of the other collision algorithms all work well, it's more a matter of taste I suppose. My code is just more in line with how I think and how I like to read my code. We're all different.

Audric said:

Neil, note that you can do without the sqrt(), using a multiplication of the other term instead :

double dist_squared = (dist_x * dist_x) + (dist_y * dist_y);
return dist_squared <= rt * rt;

Yeah, I think I discovered that I didn't need the sqrt() in another project, a 3D one actually (City3D, one of my many 3D experiments), when thinking about how to speed it up it occurred to me if I could eliminate the sqrt, which is expensive, that might help, and it did. It was a similar calculation as I recall. I never even thought to also update my DP2 game, but it's only 2D and much simpler. I'll probably add that in, thanks.

piskypom said:

Is there a benefit to using multiplication over sqrt()?

sqrt() is very expensive, if you can avoid it, you should. His suggestion is a very nice one and will be faster.

I'm no math whiz either, I tend to think in non-mathematical ways and if I can solve a problem without it, all the better, though in recent years I have studied math more in depth when working in 3D (you have to) and have learned to love it.

Edit: in my circular collision, in case you haven't already guessed, g->r and p->r are the ghost and pacman radius (in pixels), that is, the distance from their centre. And the function basically checks to see if their radius overlaps or touches. You can reduce the radius a little so that they actually have to overlap a little, or increase it so that they barely touch, it's up to you, and it's easy to adjust rather than resizing a box.

Additionally, you could combine the two so that you have a box collision test, reject any collision if they are not close to each other like in the first test, and then if they are within a certain boundry, you could then do a circle collision or something else to fine tune it.

Often games do like Eric mentioned, AABB tests (Axis Aligned Bounding Boxes) to see if objects are close enough to even qualify for a more in depth collision, then you can go even more in depth if that is true for pixel perfect collision etc if need be, though for most 2D games, it is now.

I switched to circle collision for obvious reasons, my Pacman is round, and most of the ghosts are round as well, so it was a no brainer.

piskypom
Neil Roy said:

I'm no math whiz either, I tend to think in non-mathematical ways and if I can solve a problem without it, all the better, though in recent years I have studied math more in depth when working in 3D (you have to) and have learned to love it.

Yes. You just described me, quite honestly. I'm not talented with math. I tend to avoid it if I can because, like you, I don't think in mathematical ways. But I still manage to get the job done.

I've found myself learning about vectors and triangles and I have to agree, I'm starting to like it myself. The more I understand the better it makes me feel and more confident in the code I write. I can't wait to try some 3D one day!

NiteHackr

My first 3D project with collision, I actually cheated and used 2D collision for it, as the game is mostly on a grid anyhow. So you can do 3D and still avoid math for a little while... though not for long.

piskypom

As far as I can tell, all I need to do is add another comma to my 2d vector class (at least that's what I've been told). I'll be sure to check in with you once I cross that bridge, that is if you're available

NiteHackr

If only it were that simple. It's funny how going from two dimensions to three dimensions increases the difficulty exponentially.

Displaying 3D is easy (well, easy when using the old fixed pipeline way, more involved the modern way with shaders). Detecting collisions is another matter.

In 2D, you can check below your position, usually a grid, to see what is below you and if you're over lapping. But in 3D, define "below you"? Which way is up? Which way is down? You NEED more complex math for all of this, where as in 2D, it's all fairly simple.

piskypom

I'll be taking my time. No hurry. But glad that you cleared up the misconception I had about 3D. I'd rather go in thinking it will be difficult than easy.

Could somebody please explain Audric's alternative to sqrt() function? I'd like to use it but have no idea how. No idea what it's doing.

LennyLen
piskypom said:

Could somebody please explain Audric's alternative to sqrt() function? I'd like to use it but have no idea how. No idea what it's doing.

Instead of taking the square root of one side of the equation and comparing the results, you leave that side as it was and square the other side instead. Mathematically both equations are equivalent, but the compiler now only needs to do a multiplication, which is one basic assembly instruction, instead of performing a square root, which is more complicated.

Thread #617311. Printed from Allegro.cc