Allegro.cc - Online Community

Allegro.cc Forums » Game Design & Concepts » Useful class

This thread is locked; no one can reply to it. rss feed Print
Useful class
The Master
Member #4,498
April 2004
avatar

Hi all,
I thought I'd mention a useful class I've put together. Basically it's a class that can find the roots of any polynomial up to 4th degree. You can use this to solve problems such as circle-circle and ellipse-ellipse intersection for collision detection and such.
Link here.
Enjoy/

We can only do what we feel is right each moment as we live it.

Gideon Weems
Member #3,925
October 2003

You can use this to solve problems such as circle-circle and ellipse-ellipse intersection for collision detection and such.

... Really? This is actually next up in my learn-how-to-do-this queue.

Well, ellipse-ellipse is. Circle-circle would just be a distance check, after all. Thanks for sharing!

pkrcel
Member #14,001
February 2012

Well, ellipse-ellipse is. Circle-circle would just be a distance check, after all. Thanks for sharing!

The look up for polimonial terms shoudl aid in finding the intersection of the two ellipses/circles....not only the eventual distance based collision check.

At least this is what I remember.

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

The Master
Member #4,498
April 2004
avatar

It's really useful when doing collision detection to know the points of intersection - especially if you're trying to simulate objects moving across each other.

To be helpful, here's how you get the intersection points for circle-circle intersection. You have two circles, given by the equations
<math>x^2+y^2=R_1^2</math>
<math>(x-X)^2+(y-Y)^2=R_2^2</math>
The second equation is written in terms of the origin of the first. Thus you can get (X,Y) in the second equation by subtracting the origin of the first circle from the second.

Subtract the second equation from the first, expand, and solve for x. Substitute that solution into the first equation, then solve for y. You get a quartic equation with coefficients A, B, C, D, and E given by

<math>A=\frac{1}{X^2}</math>
<math>B=-\frac{2Y}{X^2}</math>
<math>C=2+\frac{2Y^2+R_1^2-R_2^2}{X^2}</math>
<math>D=-Y\left( 1+\frac{Y^2+R_1^2-R_2^2}{X^2} \right)</math>
<math>E={{Y^4+\left(2\,X^2-2\,{\it R_2}^2+2\,{\it R_1}^2\right)\,Y^2+X^4+
 \left(-2\,{\it R_2}^2-2\,{\it R_1}^2\right)\,X^2+{\it R_2}^4-2\,
 {\it R_1}^2\,{\it R_2}^2+{\it R_1}^4}\over{4\,X^2}}</math>

The last one looks really complicated, I know. Once you have the coefficients, use the Quartic polynomial class to get the roots. If there are no real roots, then the circles don't intersect. If they are real, you solve the first equation for x and put the roots into y. And there you have it, intersection points of two circles.

Once you have the intersection points, you can get a tangent vector, and project any movement of the circles along it. Or you can use it to compute trajectories post-collision.

It's a bit more versatile than just distance calculation.

We can only do what we feel is right each moment as we live it.

Gideon Weems
Member #3,925
October 2003

That is really cool. I can't wait to wrap my head around this. Your explanation is really helpful. :)

I hope to eventually interface primitives of arbitrary types, so that the intersection point(s) of, say, an ellipse and a triangle could be calculated. Even a cursory understanding should help in figuring out how to abstract things... I'm just sad that by the time I get that understanding, this topic will already have been archived.

Thank you!

Raidho36
Member #14,628
October 2012
avatar

There's quite a lot of calculations is going on there just to find a couple of coordinates. So basically there's a lot of simplier functions to find those coordinates for practical purpose.

Can you describe more tasks solvable by this class?

----

And it's written in C++... if you targeted allegro users you probably should've written it in C.

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

LennyLen
Member #5,313
December 2004
avatar

Raidho36 said:

And it's written in C++... if you targeted allegro users you probably should've written it in C.

Allegro itself is written in C, but most people who use Allegro are fluent in both C and C++.

The only "negative" thing I can say about it is that everything is in the header file! :o

Raidho36
Member #14,628
October 2012
avatar

Well, I use C, so I'd had to rewrite entire thing if I wanted to use it.

LennyLen said:

everything is in the header file

That's is negative thing actually. Placing executable code into header makes it being recompiled every time you recompile a file that use it and it will create it's own object code for every file.

Speaking of C++ part. Vector2D class doesn't need to be a class. Essentially it's simply a struct, it doesn't have anything that makes it reasonable to use classes. That's one of the thing that's wrong with modern OOP languages: they teach programmers to use classes for everything. Like there's no other approach exists. Java and C# are especially guilty for that. While what modern OOP languages offer is not even real OOP as it defined, just a bunch of syntax sugar on top of plain imperative programming. And as for C++, it's not even good at making the sugar sweet.

C++ may not be the worst programming language ever created, but without a doubt it's the worst ever to be taken seriously.

Also it uses #pramga once for some reason, even though including the file into code file couldn't case multiple inclusions, while including it from different files doesn't save from being included in all of them, which makes include guarding meaningless as every file would need the whole header, not just one of them. It would only make sense if you include this file in both header and code file, which doesn't make sense in the first place. There is reasons why function definitions don't go to header files. Luckily, all it takes to fix it is cut-pasting function definitions to the code file.

I see lack of meaningful comments. Most of them are Captain Obvious-style descriptions, few others are branching roadsigns. Saves that the whole thing doesn't need any comments anyway, so that's not really negative thing.

count
Member #5,401
January 2005

Raidho36 said:

Well, I use C, so I'd had to rewrite entire thing if I wanted to use it.

Well, he did this in his free time and I guess it was allot of work. He gives it to others for free. And he can use the language that he wants.
Nobody forces you to use this. If you want to use it with a language that his work isn't compatible with you have to rewrite it yourself.
Your post sounds like he put a burden on you because he didn't code in the language of your choosing. You don't have to use it. Write your own useful class.

And just because you don't like C++ and you found people on the internet that don't like it as well does not mean that nobody is allowed to use it.

It comes across very impolite and not constructive. More so because it sounds like you don't even want to use it. You just complain that you couldn't.

The feedback about the header files is constructive though.

Raidho36
Member #14,628
October 2012
avatar

And he can use the language that he wants.

And he could've posted windows batch script that does this.

I don't see how blaming OOP for obvious crimes a little is impolite. It may be not constructive though, but it comes as a spot-on for the case. Still, there were no reason to make a stress on it that much.

You also sounded like one of those C++ fanboys who sincerely can't see any flaws in their language of worshipping and treat any pointing out of such as a personal insult. Even though I didn't even pointed at anything, just made a statement in a general direction on a narrow topic.

count
Member #5,401
January 2005

I do sound like a C++ fanboy?
I don't even use C++. And I didn't say one positive thing about C++ and I didn't even mention OOP (and btw: I can see flaws in OOP but that's content for another thread :)).

The only thing I mentioned is that the OP can use whatever language he likes and that the way you present your opinion sounds impolite.

How you still were able to read C++ Fanboism into my post eludes me.

I didn't even relate to your C++/OOP statements but just to the part I quoted.
The part I quoted did sound like just because you want to use C everyone has to use C. Because otherwise you would have to do work when you want to use stuff that other people do in their free time.

If I misunderstood you then I apologize.
As said it wasn't related to you c++/oop statement in the rest of the post.

SiegeLord
Member #7,827
October 2006
avatar

The only one who is impolite here is you, Christopher Bludau. There is nothing in Raidho36's post that warranted your idiotic rant.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

count
Member #5,401
January 2005

Didn't meant to be. I apologize.

Gideon Weems
Member #3,925
October 2003

... And clean your room while you're at it, mister!

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Raidho36 said:

Well, I use C, so I'd had to rewrite entire thing if I wanted to use it.

This statement makes no sense. Your compiler is perfectly capable of compiling C++ as well as C. All you would have to do is change from gcc to g++ if on MinGW/gcc. I will never understand C elitism. :P

pkrcel
Member #14,001
February 2012

Uhu? but of heìs writing in C, how would he interface the darn thing? ???

DISCLAMER: seriously asking, I am not expert enuff to know by myself...

It is unlikely that Google shares your distaste for capitalism. - Derezo
If one had the eternity of time, one would do things later. - Johan Halmén

Jeff Bernard
Member #6,698
December 2005
avatar

pkrcel said:

Uhu? but of heìs writing in C, how would he interface the darn thing?

By pretending the classes are structs? He just wouldn't have to go through the hassle of setting up all the "function pointers" himself, and the syntax for calling them will be nicer too since he won't need to pass in the "struct" or any members. As for the use of templates, just pretend they aren't there and only use the typedefs in the header?

--
I thought I was wrong once, but I was mistaken.

SiegeLord
Member #7,827
October 2006
avatar

pkrcel said:

Uhu? but of heìs writing in C, how would he interface the darn thing? ???

That is a perfectly fine question and I don't get what the other two are talking about. Surely they are not suggesting to compile C as C++, which doesn't work in general.

You cannot use C++ libraries (like the one in OP) with C without writing a C API wrapper for it, period. You won't need to rewrite the whole thing, but you will need to wrap the C++ API with a C one. Although, glancing at the code your time will be better spent rewriting it in C anyway.

I glanced at the code itself and I take issue with the way operator() is implemented. It really should use Horner's method. Also, I don't see the point of the Vector2D class. There is already std::complex which you should have used. N.B. if somebody does want it in C, you'd use _Complex from C99.

EDIT: Also... GPL'd header-only library? Surely you must be joking ;). I'd suggest using template specialization to make it a header + cpp file (and switch to LGPL maybe) so you can at least use it without needing to relicense the whole project as GPL... not that there's anything wrong with that ;).

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Gideon Weems
Member #3,925
October 2003

I tend to use C++, though I certainly understand the differences between the two styles and find myself programming C-style modules in C++ more often than not.

Last night, though, I realized I had made an entire module in C++ using absolutely no C++ specific features. I decided to change it to C--and lo and behold, the compiler blows my mind: Apparently, C doesn't have the bool type. I could have sworn bools were backported at some point (ala C++ style comments).

So I guess I use C++ mostly for the bools. :-*

SiegeLord
Member #7,827
October 2006
avatar

I could have sworn bools were backported at some point (ala C++ style comments).

They are both in C99.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Gideon Weems
Member #3,925
October 2003

:) Well, at least I'm not going crazy in that particular area of the brain. Thank you.

I did a quick check before changing the file back to C++ and found this IBM document listing all reserved words. It doesn't list "bool," though it does include "_Bool," which is kind of lame.

On second glance, the IBM document pertains specifically to their implementation and should be taken with a grain of salt--but that still doesn't explain why gcc 4.7.2 wouldn't handle a bool...

But wait. Apparently, I didn't know about this command-line option:

--std=c99

Oh, silly GNU and your old-man ways... You'd think that 14 years would have been enough time to adopt a standard by now.

SiegeLord
Member #7,827
October 2006
avatar

It doesn't list "bool," though it does include "_Bool," which is kind of lame.

To get bool (and true and false) you need to #include <stdbool.h>. They kind of had to do that so that old code wouldn't get broken.

Incidentally, Allegro5 provides a cross-compiler definition of bool for the non-C99 compilers, so it's nice in that sense. You still don't get the C++ comments that way though...

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

l j
Member #10,584
January 2009
avatar

Oh, silly GNU and your old-man ways [stackoverflow.com]... You'd think that 14 years would have been enough time to adopt a standard by now.

We're already at c11 and Microsoft hasn't even bothered implementing c99 in their own compiler. At least it's possible to use c99 with gcc.

Raidho36
Member #14,628
October 2012
avatar

Well, (with x86) the smallest possible data size a program can fetch without using bithacks is 8 bit, a char, so in ANSI C you #define bool char #define true 1 #define false 0 if you need booleans that much. Or you typedef enum bool { false, true } which makes more sense. Otherwise you simply use char and 0 for false with anything else for true.

...with typedef you can also typedef enum bool { false, true, uncertain }... yeah...

Go to: