Welcome, Guest. Please Login or Register.  • Help
SMF Underground
+ SHMUP-DEV » SHMUP DEV FORUMS » Assistance
|-+ Common Programmer Algorithems (motion,graphic,computation)

Pages: [1]   Go Down
0 Members and 1 Guest are viewing this topic. Topic Tools  
Read May 20, 2006, 05:04:00 PM #0
Pixel_Outlaw

Common Programmer Algorithems (motion,graphic,computation)

I think that we as a community should start a compilation of usefull formulas/algorithems. I'm think some along the lines of basic movement and computation. Many formulas can be used in any programming language so I would sudgest posting them in psudo-code.

Ok well I would be an idiot if I made this thread and didn't contribute.

Point Distance formula: Gives length between point a snd b
Uses: AI,circular collision detection
______________________________________________________________
x1= first x
y1= first y
x2= second x
y2= second y

point_distance(x1,y1,x2,y2)

// get the x difference
x_distance=Abs(x1-x2)

// get the y difference
y_distance=Abs(y1-y2)

// find the difference using pythagroin therom
distance=sqr((x_distance*x_distance)+(y_distance*y_distance))

Return distance


_________________________________________________________



Point Angle: Gives angle between two points
Uses: AI, Homing missles, Chasing behaviors
_________________________________________________________

point_direction(x1,y1,x2,y2)
      
angle= ATan2(y2-y1,x2-x1)
If angle<0
angle:+ 360
End If
      
Return angle

      
   
« Last Edit: May 20, 2006, 05:17:46 PM by Pixel_Outlaw »


Aviator sunglasses are pretty much the shmups of the sunglasses world.
Offline  
Read May 21, 2006, 12:54:42 AM #1
oNyx

Re: Common Programmer Algorithems (motion,graphic,computation)

Uhm... sqrt is a pretty expensive operation. For circle-circle collision detection you arent interested in the exact distance. You only need to know if the squared distance is bigger than the sum of the radii squared. You also dont need something like abs, because after squaring it it will be positive either way.

public boolean intersects(Sphere s){
   return (r+s.r)*(r+s.r)>(x-s.x)*(x-s.x)+(y-s.y)*(y-s.y);
}
(Dont start a discussion that one should use ">=" instead. Its a question of which definition you use. For me an intersection is if there is one point which is inside of both circles. Feel free to disagree. In a game it doesnt make a visible differene anyways.)
« Last Edit: May 21, 2006, 12:56:34 AM by oNyx »

Offline  
Read May 21, 2006, 01:04:30 AM #2
Pixel_Outlaw

Re: Common Programmer Algorithems (motion,graphic,computation)

Oh you're right! I didn't remember that abs would not be necessary. I failed my highschool trig/alg2 class. So I had to write these myself. Thanks!

Anyone  else have any good algorithems?



Aviator sunglasses are pretty much the shmups of the sunglasses world.
Offline  
Read May 21, 2006, 01:19:42 AM #3
RedKnight

Re: Common Programmer Algorithems (motion,graphic,computation)

Basic Bullet class.

Double  X, Y, Spd, Dir;

then you run your bullet like this.


void OBJECT::Move(void)
{
 double sSpeed   = (Interval * Spd);
 double rDir     = DegreeToRadiant(Dir);

 X += (sSpeed * sin(rDir));
 Y += (sSpeed * cos(rDir));
}





It should be more easier to code.
if you can wrapped it up in vector.




vector<BULLET> Bullets.

void AddBullet( double x, double y, double spd, double dir)
{
 Bullets.push_back( BULLET( x, y, spd, dir));
}



and all of these idea.
I got it from reverse enginering Kenta cho BulletML.

 Grin

 



These convert Radiants into Degree and vice versa.

inline float RadiantToDegree(float rRadiant)
{
 return( rRadiant * ( 180 / PI));
}


inline float DegreeToRadiant( float rDegree)
{
 return( rDegree / ( 57.295776));
}




Distance between two 3d vectors.
You can remove the Z to make it 2d.

inline float                   Distance(VECTOR3D VecX, VECTOR3D VecY)
{
 double tDistance = sqrt((VecX.Vec[0] - VecY.Vec[0]) * (VecX.Vec[0] - VecY.Vec[0]) +
                         (VecX.Vec[1] - VecY.Vec[1]) * (VecX.Vec[1] - VecY.Vec[1]) +
                         (VecX.Vec[2] - VecY.Vec[2]) * (VecX.Vec[2] - VecY.Vec[2]));

 return tDistance;
}

sqrt slowwww??
My badd.
I've been working with quake 3 bsp mapping and is quite fast.
 but remember to use "inline"
 and importantly use "C/C++"



Check this function

bool __declspec( dllexport) InsidePolygon(VECTOR3D vIntersection, VECTOR3D Poly[], long verticeCount)
{
 const double MATCH_FACTOR = 0.9999;
       double Angle        = 0.0;
 VECTOR3D     vA;
 VECTOR3D     vB;

 for (int i = 0; i < verticeCount; i++)
 {
  vA = Poly - vIntersection;

  vB = Poly[(i + 1) % verticeCount] - vIntersection;

  Angle += AngleBetweenVectors(vA, vB);
 }

 if(Angle >= (MATCH_FACTOR * (2.0 * PI)) )
 return true;

 return false;
}



VECTOR3D vIntersection  => is the 2d vector.... just say this is our "bullet"
VECTOR3D Poly[]            => the collection of our 4 point square

This test if the vIntersection is in the poly box by checking all the angle together.
since all together our angle should come up about 360 degree.









Be Attitude for Gains
Offline  
Read May 21, 2006, 04:19:26 AM #4
pixelizr

Re: Common Programmer Algorithems (motion,graphic,computation)

Regarding the distance formula, I do know that in C++, there is a function called hypot(). You could use that to directly compute the distance between points. Does anyone know if hypot() is slower than two multiplications?

I personally don't use vectors for bullets. I use lists. From what I know, it takes a long time to remove and insert elements in the middle of vectors; while it takes just constant time in lists to do the same operation. I imagine this to be important when you need to delete bullets, since deletion can happen anywhere in the list. The advantage of vectors is constant time random access, though I don't think you need that if you iterate across all bullets; an iterator will work just fine.

I also don't use a function similar to AddBullet() as you have mentioned, since it only contains a single push_back call. I just directly call the push_back function rather than wrapping it inside a function.
Offline  
Read May 21, 2006, 05:10:40 AM #5
oNyx

Re: Common Programmer Algorithems (motion,graphic,computation)

>sqrt slowwww??

Relatively. If its called 2k times per frame it can surely make a difference of a few frames. Well, that is if its cpu bound.

---

When in doubt compare the performance for yourself.

In java you have ArrayList and LinkedList for example. Inserting/removing elements from an ArrayList is slower, but iterating over it is faster (and random access is *way* faster). Fast enough to offset the add/remove difference even if you would add/remove the same amount bullets you're iterating over. I was acutally quite surprised by that.

Under usual (game) circumstances you add/remove way less than you iterate. So, an ArrayList is certainly the better choice.
Offline  
Read May 21, 2006, 04:31:45 PM #6
RedKnight

Re: Common Programmer Algorithems (motion,graphic,computation)

Quote
Relatively. If its called 2k times per frame it can surely make a difference of a few frames. Well, that is if its cpu bound.

Well that happens when you called it 2k times. ( is that 2000 times )  Grin
there's also another alternative solution
and that is

double tDistance = (VecX.Vec[0] - VecY.Vec[0]) * (VecX.Vec[0] - VecY.Vec[0]) +
                          (VecX.Vec[1] - VecY.Vec[1]) * (VecX.Vec[1] - VecY.Vec[1]) +
                          (VecX.Vec[2] - VecY.Vec[2]) * (VecX.Vec[2] - VecY.Vec[2]);

without the square root.

and there's also a "Manhattan" distance

Dist = abs( V1.X-V2.X) + abs( V1.Y-V2.Y) + abs( V1.Z, V2.Z)






Quote
I also don't use a function similar to AddBullet() as you have mentioned, since it only contains a single push_back call. I just directly call the push_back function rather than wrapping it inside a function.

Well I have made everything dumb down to simple.
maybe it is my who like to organize my codes to classic C style perfection.
 Grin


int AddBullet( lua_State * State)
{
 if( lua_gettop( State) > 0)
 {
  AddBullet( lua_tonumber( State, 1),
                lua_tonumber( State, 2),
                lua_tonumber( State, 3),
                lua_tonumber( State, 4));
 }

 return 0;
}
 

you see,This is the same function.
for lua.


I have also plan to ported everything in the main game loop over the Lua.
So I can easilly change it contents to my liking.






Be Attitude for Gains
Offline  
Read July 16, 2006, 02:39:07 PM #7
Landon_Fox

Re: Common Programmer Algorithems (motion,graphic,computation)

Sqrt is actually VERY slow.  Not only does it work in doubles and not floats, it computes out accuracy to every significant digit stored in the number.  No only are you hit for conversion, you only really need two or three significant digits to make it look good on a display.

So just do what I did and make your own sqrt function using lookup tables!  This speedup as enough to let me dump 4000 particles on the screen before I had slowdown.

Code:
// Initialization
for (i=0; i<10000; i++) {
SqrtTableLow[i] = (float)sqrt( (float)i/100.f );
SqrtTableMedium[i] = (float)sqrt( (float)i );
SqrtTableHigh[i] = (float)sqrt( (float)i*100.f );
}

// The functions
float FASTMATH::Sqrt(int Value) {
if (Value < 0) {
Value *= -1;
if (Value < 10000)
return -1 * SqrtTableMedium[Value];
else if (Value < 1000000)
return -1 * SqrtTableHigh[Value/100];
else
return -1 * SqrtTableHigh[9999];
}
else if (Value < 10000)
return SqrtTableMedium[Value];
else if (Value < 1000000)
return SqrtTableHigh[Value/100];
else
return SqrtTableHigh[9999];

}

// Alternate function
float FASTMATH::Sqrt(float Value) {
if (Value < 0) {
Value *= -1;
if (Value < 100)
return -1 * SqrtTableLow[(int)(Value*100.0f)];
else if (Value < 10000)
return -1 * SqrtTableMedium[(int)Value];
else if (Value < 1000000)
return -1 * SqrtTableHigh[(int)(Value/100.0f)];
else
return -1 * SqrtTableHigh[9999];
}
else if (Value < 100)
return SqrtTableLow[(int)(Value*100.0f)];
else if (Value < 10000)
return SqrtTableMedium[(int)Value];
else if (Value < 1000000)
return SqrtTableHigh[(int)(Value/100.0f)];
else
return SqrtTableHigh[9999];
}
Offline  
Read July 17, 2006, 02:02:40 AM #8
relsoft

Re: Common Programmer Algorithems (motion,graphic,computation)

Some 2d collision helper functions. Code is in Freebasic.

Get a a 2d normal of a line segment.

Code:
private sub get_2dnormal (seg as segment_type, s as integer)
   
    if s then
    seg.normal.x = -(seg.y2-seg.y1)  'negate to get the other normal
    seg.normal.y = (seg.x2-seg.x1) 'erase negatio here if you want the other
                                    'normal
    else
    seg.normal.x = (seg.y2-seg.y1)  'negate to get the other normal
    seg.normal.y = -(seg.x2-seg.x1) 'erase negatio here if you want the other
                                    'normal
    end if
    normalize (seg.normal)
end sub

Get the midpoint of a line:

Code:
private function midpoint (seg as segment_type) as point_type
   
    dim leng as single
    dim v as vector2d
    dim half_leng as integer
    dim p as point_type
    leng = get_length ( seg )
    v.x = seg.x2 - seg.x1
    v.y = seg.y2 - seg.y1
    normalize (v)
    half_leng = leng / 2
    p.x = seg.x1 + ( v.x * half_leng)
    p.y = seg.y1 + ( v.y * half_leng)
   
    return p
   
end function


To check if a point is inside a convex poly...
Pseudocode......

Code:
    dim as integer sameside = 1
for every  point in the polygon...
        'check if point is inside the poly
        dim as single dota
        dim as vector2d v
        v.x = any_point_in_line.x - mypoint.x
        v.y = any_point_in_line.y - mypoint.y
        dota = dot(v, line.normal)       
        dim as integer p_side = 0
        if dota >=0 then p_side = 1       
        sameside = sameside and p_side       
loop

Now it would be just a matter of checking whether sameside <> 0.

Ive attached demo which uses the above and some additions. Like bouncing on an arbitrary line. :*)
Move the mouse inside the rotating poly to check for the function.  I'm open for questions regarding the bounce method. :*)

Demo includes the source.


[attachment lost, please re-upload]


Hello
Offline  
Read July 30, 2006, 09:59:59 AM #9
ELLioT

Re: Common Programmer Algorithems (motion,graphic,computation)

Some helpful 2D function I often used. It can be used in vector games ( but not only ) to check collision between entities boundaries or with bullets trajectories.

Code:
;-------------------------------------------------------------------------------
; Check 2 Segments intersection
; in :
;    a0x, a0y, a1x, a1y : coords of 1st segment
;    a2x, a2y, a3x, a3y : coords of 2nd segment
; out :
;    -
; return : True if segments intersect, else False
;-------------------------------------------------------------------------------
Function SegIntersect(a0x%, a0y%, a1x%, a1y%, a2x%, a2y%, a3x%, a3y%)

    v0x% = -(a1y - a0y)
    v0y% = +(a1x - a0x)

    s1% = ((a2x - a0x) * v0x + (a2y - a0y) * v0y) >= 0
    s2% = ((a3x - a0x) * v0x + (a3y - a0y) * v0y) >= 0

    If Not(s1 Xor s2) Then
        Return False
    EndIf

    v0x% = -(a3y - a2y)
    v0y% = +(a3x - a2x)

    s1% = ((a0x - a2x) * v0x + (a0y - a2y) * v0y) >= 0
    s2% = ((a1x - a2x) * v0x + (a1y - a2y) * v0y) >= 0

    If s1 Xor s2 Then
        Return True
    EndIf

    Return False

End Function ; SegIntersect()
Offline  
Read October 04, 2006, 09:48:49 AM #10
motorherp

Re: Common Programmer Algorithems (motion,graphic,computation)

I personally don't use vectors for bullets. I use lists. From what I know, it takes a long time to remove and insert elements in the middle of vectors; while it takes just constant time in lists to do the same operation. I imagine this to be important when you need to delete bullets, since deletion can happen anywhere in the list. The advantage of vectors is constant time random access, though I don't think you need that if you iterate across all bullets; an iterator will work just fine.

Using a list will also give you poor performance for a bullet system were you're dealing with large quantities of small objects with minimal processing on each.  In fact I'd venture as far to say that your performance with a list is going to be worse than a vector for these circumstances.  There's several reasons for this.  You'll be very frequently creating a destroying lots of very small objects.  For a start all these memory allocations and deallocations will directly impact on your performance but this will also fragment your memory something rotten reducing performance in the longer term.  Its also a poor use of memory since the sizes you are allocating dont significantly outweigh the size of the header which gets created with an allocation meaning that you'll be chewing up more memory this way.  More importantly though is the impact a list has when you wish to iterate through all your bullets to update and render them.  To go from one bullet to the next not only requires a dereference but also means thrashing your cache since they're going to be scattered all over the place in memory.  Since you've got a lot of bullets and each one only requires minimal processing, this will easily become the dominant usage of your time here which can be saved by using a vector instead.

You're quite right about deletions and insertions being slow in a vector but you really dont want all these allocations and de-allocations going on all the time anyway so the trick is to create your own management system which side steps this need.  Therefore here's my code snippet for efficient bullet management which gets the best of both worlds (written in lazy c++):

Code:
class Bullet
{
   float  m_x, m_y;
   float  m_vx, m_vy;
   bool  m_alive;

   void  Update();
}

class Battery
{
   vector<Bullet>   m_bullets;
   vector<int>   m_freeBullets;

   int   AddBullet();
   void   FreeBullet();
   Bullet&   GetBullet(int id);
   void   UpdateBullets();
}


int Battery::AddBullet()
{
   int id = -1;

   if(m_freeBullets.size())
   {
      id = m_freeBullets.back();
      m_freeBullets.pop_back();
   }
   else
   {
      id = m_bullets.size();
      Bullet newBullet;
      m_bullets.push_back(newBullet);
   }
   
   m_bullets[id].m_active = true;
   return id;
}


void Battery::FreeBullet(int id)
{
   m_bullets[id].m_active = false;
   m_freeBullets.push_back(id);
}


Bullet& Batter::GetBullet(int id)
{
   return m_bullets[id];
}


void Battery::UpdateBullets()
{
   for(int i = 0; i < m_bullets.size(); ++i)
   {
      if(m_bullets[i].m_active)   { m_bullets[i].Update(); }
   }
}

If you're going to implement this for yourself I'd recommend reserving a good size qauntity in both vectors during Battery creation and also put in debug error checking since such a system could go badly wrong if used incorrectly.


« Last Edit: October 04, 2006, 09:52:57 AM by motorherp »

Offline  
Read February 05, 2007, 03:15:20 PM #11
Techbear

Re: Common Programmer Algorithems (motion,graphic,computation)

These two functions convert between rgb values and hsv values.  If you want your ships to be different, but blightly colored, or of you want a background that color-cycles smoothly, use these.

Code:
//*************************************************************************
void HSVtoRGB(float h, float s, float v, float &r, float &g, float &b)
{
    int i;
    float f, p, q, t,hTemp;
 
    if( s == 0.0 || h == -1.0) // s==0? Totally unsaturated = grey so R,G and B all equal value
    {
      r = g = b = v;
      return;
    }
    hTemp = h/60.0f;
    i = (int)floor( hTemp );                 // which sector
    f = hTemp - i;                      // how far through sector
    p = v * ( 1 - s );
    q = v * ( 1 - s * f );
    t = v * ( 1 - s * ( 1 - f ) );
 
    switch( i ) 
    {
    case 0:{r = v;g = t;b = p;break;}
    case 1:{r = q;g = v;b = p;break;}
    case 2:{r = p;g = v;b = t;break;}
    case 3:{r = p;g = q;b = v;break;} 
    case 4:{r = t;g = p;b = v;break;}
    case 5:{r = v;g = p;b = q;break;}
    }
}
 
//*************************************************************************
void RGBtoHSV(float r, float g, float b, float &h, float &s, float &v)
 {
    float mn=r,mx=r;
    int maxVal=0;
 
    if (g > mx){ mx=g;maxVal=1;}
    if (b > mx){ mx=b;maxVal=2;} 
    if (g < mn) mn=g;
    if (b < mn) mn=b; 
    float  delta = mx - mn;
 
    v = mx; 
    if( mx != 0 )
      s = delta / mx; 
    else 
    {
      s = 0;
      h = 0;
      return;
    }
    if (s==0.0f)
    {
      h=-1;
      return;
    }
    else
    { 
      switch (maxVal)
      {
      case 0:{h = ( g - b ) / delta;break;}         // yel < h < mag
      case 1:{h = 2 + ( b - r ) / delta;break;}     // cyan < h < yel
      case 2:{h = 4 + ( r - g ) / delta;break;}     // mag < h < cyan
      }
    }
 
    h *= 60;
    if( h < 0 ) h += 360;
}

Offline  
Read February 05, 2007, 03:20:52 PM #12
Techbear

Re: Common Programmer Algorithems (motion,graphic,computation)

This piece of code is a Catmull-Rom spline.  I love it because 1) the curved line it describes passes thru the control points, unlike a b-spline, and 2) if you use it for enemy ship paths, it results in nice curves with smooth velocity changes.

It takes four points, and the value t is 0.0 - 1.0, and represents how far you are between the middle two points.

Code:
//*************************************************************************
void PointOnCurve(TPoint &out, float t, TPoint p0, TPoint p1, TPoint p2, TPoint p3)
{
float t2 = t * t;
float t3 = t2 * t;
out.x = 0.5f * ( ( 2.0f * p1.x ) +
( -p0.x + p2.x ) * t +
( 2.0f * p0.x - 5.0f * p1.x + 4 * p2.x - p3.x ) * t2 +
( -p0.x + 3.0f * p1.x - 3.0f * p2.x + p3.x ) * t3 );
out.y = 0.5f * ( ( 2.0f * p1.y ) +
( -p0.y + p2.y ) * t +
( 2.0f * p0.y - 5.0f * p1.y + 4 * p2.y - p3.y ) * t2 +
( -p0.y + 3.0f * p1.y - 3.0f * p2.y + p3.y ) * t3 );
}


Offline  
Read February 05, 2007, 04:36:43 PM #13
the2bears

Re: Common Programmer Algorithems (motion,graphic,computation)

These two functions convert between rgb values and hsv values.  If you want your ships to be different, but blightly colored, or of you want a background that color-cycles smoothly, use these.

I was just thinking about looking for this very conversion Smiley   Thanks!

Bill


the2bears - the indie shmup blog
Offline  
Read February 05, 2007, 08:20:00 PM #14
Pixel_Outlaw

Re: Common Programmer Algorithems (motion,graphic,computation)

Really, this thread should be a core thread. Lots and lots of good snippets here.

RGB and HSV conversion is VERY helpfull. HSV is what we use in real live but RGB is the programming standard. I would argue that if we used the HSV model in compilers as a standard some hommade games would have better color paletts. Colors would probably share light or value and saturation and just vary in hue. That's why there is so many saturated pure colors in games such as RGB(255,0,0). It's like the compiler writers wanted to burn out retnas because saturation and light were not easly found.

How I do rant sometimes...
« Last Edit: February 05, 2007, 08:22:05 PM by Pixel_Outlaw »


Aviator sunglasses are pretty much the shmups of the sunglasses world.
Offline  
Read May 07, 2009, 09:14:16 PM #15
Slackluster

Re: Common Programmer Algorithems (motion,graphic,computation)

Good stuff so far!  I have a few contributions.  Some of these functions call each other so you are going to need to make them static member functions of your Vector2 class or declare them at the top of the header file.

Code:
// 2d line segment intersection test
// returns true and sets the point of intersection if segments intersect
inline bool LineSegmentIntersection
(
    const Vector2& segment1a, const Vector2& segment1b,
    const Vector2& segment2a, const Vector2& segment2b,
    Vector2& intersectionPoint
)
{
    const Vector2 delta1 = segment1b - segment1a;
    const Vector2 delta2 = segment2b - segment2a;
    const Vector2 delta3 = segment1a - segment2a;
    const float d = delta1.Cross(delta2);
    const float ud1 = delta2.Cross(delta3);

    if (d > 0)
    {
        if (ud1 < 0 || ud1 > d)
            return false; // outside bounds of segment 1

        const float ud2 = delta1.Cross(delta3);
        if (ud2 < 0 || ud2 > d)
            return false; // outside bounds of segment 2
    }
    else if (d < 0)
    {
        if (ud1 > 0 || ud1 < d)
            return false; // outside bounds of segment 1

        const float ud2 = delta1.Cross(delta3);
        if (ud2 > 0 || ud2 < d)
            return false; // outside bounds of segment 2
    }
    else // d == 0
        return false; // segments are parallel

    // compute intersection point
    intersectionPoint = segment1a + (ud1/d) * delta1;
    return true;
}

// 2d point distance from line segment test
// returns the distance between line segment and point
inline float DistanceFromLineSegement
(
    const Vector2& lineStart, const Vector2& lineEnd,
    const Vector2& point
)
{
    const Vector2 deltaPos(lineEnd - lineStart);
    const float deltaPosMagSquared = deltaPos.MagnitudeSquared();
    const Vector2 deltaStart(point - lineStart);
    const float dp = deltaStart.DotProduct(deltaPos);

    if (dp >= deltaPosMagSquared)
        return (point - lineEnd).Magnitude();
    else if (dp <= 0)
        return (point - lineStart).Magnitude();
    else
    {
        const Vector2 pointNearest(lineStart + deltaPos * (dp / deltaPosMagSquared));
        return (point - pointNearest).Magnitude();
    }
}

// 2d line segment intersection test
// faster then the full line segment test if you don’t need the intersection point
// returns true if finite line segments intersect
inline bool LineSegmentIntersection
(
    const Vector2& segment1a, const Vector2& segment1b,
    const Vector2& segment2a, const Vector2& segment2b
)
{
    const Vector2 d1a1b = segment1a - segment1b;
    const Vector2 d1b2a = segment1b - segment2a;
    const Vector2 d1b2b = segment1b - segment2b;

    if (IsClockwise(d1a1b, d1b2a) == IsClockwise(d1a1b, d1b2b))
        return false;

    const Vector2 d1a2a = segment1a - segment2a;
    const Vector2 d2a2b = segment2a - segment2b;

    return (IsClockwise(d1a2a, d2a2b) != IsClockwise(d1b2a, d2a2b));
}

// 2d point inside polygon test
// returns true if point is inside clockwise winding polygon
inline bool InsidePolygon
(
    const Vector2* vertexList,
    int vertexCount,
    const Vector2& point
)
{
    for (int i = 0; i < vertexCount - 1; ++i)
    {
        if (!IsClockwise(vertexList[i], vertexList[i+1], point))
            return false;
    }

    return IsClockwise(vertexList[vertexCount - 1], vertexList[0], point);
}

// 2d clockwise winding test
// returns true if verts form clockwise triangle
inline bool IsClockwise
(
    const Vector2& v1,
    const Vector2& v2,
    const Vector2& v3
)
{
    const Vector2 d1 = v1 - v2;
    const Vector2 d2 = v2 - v3;
    return IsClockwise(d1, d2);
}

// 2d clockwise winding test
// returns true if directions are winding clockwise
inline bool IsClockwise(const Vector2& d1, const Vector2& d2)
{
    return (d1.y*d2.x > d2.y*d1.x);
}
Offline  
Read April 22, 2010, 09:44:04 PM #16
OMNICYPHER

Re: Common Programmer Algorithems (motion,graphic,computation)

heres some homing missile code using dot product:
Code:

//make vector pointing from missile to target

targetDir.x = (targetPos.x - missilePos.x);
targetDir.y = (targetPos.y - missilePos.y);

//rotate missile 90 deg from (x,y) to (y,-x)
//then if the dot product says its perpendicular, it actually means its parallel
//if the line from missile to target is parallel with the angle of the missile,
//the missile is pointing at the target//

if ( missileVelocity.y * targetDir.x - missileVelocity.x * targetDir.y > 0 )     
missileAngle -= TURN_SPEED;
else
missileAngle += TURN_SPEED;

//polar to cartesian conversion

missileVelocity.x = missileSpeed * cos(missileAngle); 
missileVelocity.y = missileSpeed * sin(missileAngle);

//update missiles cartesian position

missilePos.x += missileVelocity.x;
missilePos.y += missileVelocity.y;



Good gameplay is when Pace is inversely proportional to mental effort
Offline  
Read January 18, 2011, 04:19:26 AM #17
trap15

Re: Common Programmer Algorithems (motion,graphic,computation)

A quick one that always gives me headaches to work out. It's a simple collision detection between 2 rectangles.
*0* are top-left coordinates.
*1* are bottom-right coordinates.
s** and o** are points of the 2 rectangles.

Code:
int collision_check(float s0x, float s0y, float s1x, float s1y, float o0x, float o0y, float o1x, float o1y)
{
if((s0x <= o1x) && (s1x >= o0x) && (s0y <= o1y) && (s1y >= o0y))
return 1;
return 0;
}

If you want to check if an object is within another, change all the o0* to o1* and vice versa, then change <='s to >='s and vice versa. o** will be the rectangle that must be within s**.
Offline  
Read January 21, 2011, 08:12:18 AM #18
motorherp

Re: Common Programmer Algorithems (motion,graphic,computation)

A quick one that always gives me headaches to work out. It's a simple collision detection between 2 rectangles.
*0* are top-left coordinates.
*1* are bottom-right coordinates.
s** and o** are points of the 2 rectangles.

Code:
int collision_check(float s0x, float s0y, float s1x, float s1y, float o0x, float o0y, float o1x, float o1y)
{
if((s0x <= o1x) && (s1x >= o0x) && (s0y <= o1y) && (s1y >= o0y))
return 1;
return 0;
}

If you want to check if an object is within another, change all the o0* to o1* and vice versa, then change <='s to >='s and vice versa. o** will be the rectangle that must be within s**.




EDIT:  Please ignore the following ravings of a mad-man, it makes no sense unless you happen to live inside my version of reality with all the other loons Smiley:

Quote
For reference, the above rectangle collision algorithm can be optimised by doing the following:

Code:
int collision_check(float s0x, float s0y, float s1x, float s1y, float o0x, float o0y, float o1x, float o1y)
{
if((s0x > o1x) || (s1x < o0x) || (s0y > o1y) || (s1y < o0y))
return 0;
return 1;
}

Logically its equivalent but when described this way the code is allowed to drop out of the function early if it detects that these two rectangles cant collide.  This is because when using the OR operator the code will only continue to evaluate each term until one is true at which point it can skip the remaining evaluations since it knows which branch to take regardless of the result of the rest of the terms.  When using the AND operator however then the code has to evaluate every term every time to determine which branch to take due to the way the logic works.  Therefore in the case of intersecting rectangles both versions will perform the same number of operations, but in the non intersecting rectangle case then the OR version will likely drop out faster than the AND version and thus be quicker.

As a further aside, if you have specific knowledge about your game which could mean that rectangles are more likely to be spread out along one axis than the other (for example if your play area is long and thin) then by putting your evaluations in the order in which they are most likely to drop out you can on avergae get the algorithm to go even faster still.  For more information check out the 'Art of Collision part 1' tutorial I wrote over in the tutorials section of the forum which talks about this kind of stuff.
« Last Edit: January 21, 2011, 09:44:45 AM by motorherp »

Offline  
Read January 21, 2011, 09:27:30 AM #19
Hornet600S

Re: Common Programmer Algorithems (motion,graphic,computation)

@motorherp

Either it's my flu or you are wrong Smiley .
Both variants are absolutely identical regarding early drop behaviour.

The AND version drops early if the first FALSE condition is calculated.
The OR version is satisfied early if the first TRUE condition is calculated.
And since the comparisms are identical, only "mirrored" (<= vs. >), there is exactly zero difference between the two.

Asume s0x = 60 and o1x = 50
Then:

The AND version does 1 comparism, 60<=50, is FALSE, therefore early break, returns 0.
The OR version does 1 comparism, 60>50, is TRUE, therefore or-condition satisfied, returns 0.


"When the Amiga came out, everyone at Apple was scared as hell."
(Jean-Louis Gassée - Head of Macintosh development at Apple)
Offline  
Read January 21, 2011, 09:39:50 AM #20
motorherp

Re: Common Programmer Algorithems (motion,graphic,computation)

@motorherp

Either it's my flu or you are wrong Smiley .
Both variants are absolutely identical regarding early drop behaviour.

The AND version drops early if the first FALSE condition is calculated.
The OR version is satisfied early if the first TRUE condition is calculated.
And since the comparisms are identical, only "mirrored" (<= vs. >), there is exactly zero difference between the two.

Asume s0x = 60 and o1x = 50
Then:

The AND version does 1 comparism, 60<=50, is FALSE, therefore early break, returns 0.
The OR version does 1 comparism, 60>50, is TRUE, therefore or-condition satisfied, returns 0.


Heh, yeh you're absolutely right, got knows what I was thinking.  Probably fixating too much on the conditions of getting into the branch and missed the bigger picture.  Clearly I've not had enough tea yet this morning  Wink.  Cheers for pointing that out, sometimes I seriously doubt myself hehe Tongue

PS:  I've edited my OP to point out what a buffoon I am and so no-one else gets confused Smiley.
« Last Edit: January 21, 2011, 09:45:52 AM by motorherp »

Offline  
Pages: [1]   Go Up
Jump to:  

Page created in 0.43 seconds with 17 queries.