Results 1 to 9 of 9

Thread: Game Programming Issues

  1. #1
    Registered User
    Join Date
    Jun 2003
    Location
    Zuid-Holland
    Posts
    6

    Exclamation Game Programming Issues

    Simple collision detection and transparency, by Erwin Haantjes
    DelphiApplicationDiscussion@hotmail.com
    --------------------------------------------------------------


    It's not uncommon that collision detection in games is one of the most called functions. There are several ways of doing collision detection and this article describes a method for 2D games using bounding boxes (rectangles).

    Perfect collision detection down to the pixel is of course what (theoretically) is the best. However, checking each pixel against each other for all objects every frame in a game is slow, very slow. So a simplier way is needed, this is where bounding boxes comes in.

    Imagine that you draw a rectangle, like a frame, around an object (the player spaceship for examle). Then do the same thing for all the other objects in the game. Now calculate if these rectangles intercept each other to determine a collision, instead of checking each pixels. This method is much faster, not as precise, but usually exact enough.

    +------------+
    | XX |
    | XXXXXX |
    |XXXXXXXXXXXX|
    | XXXXXX+-|----------+
    | XX |X|XX XXXX|
    +------------+ XX XX |
    | XXXX |
    | XX XX |
    |XXXX XXXX|
    +------------+

    A problem is that sometimes a collision is detected when visually it seems like the object didn't touch. This usually occurs when any of the objects is shaped like a sphere. To compensate this we use an offset when checking if the bounding boxes intercept. By making the bounding boxes slightly smaller than the object itself, detection usually seems accurate enough. As mentioned before, we sacrifice precision for speed, but this is a way to compensate the precision to make it "feel" more exact.

    Here is the function which does the real collision detection of two objects. In this example the player's coordinates are R1, while the enemy's coordinates are R2. You can use an offset for the X and Y coordinates to precize the detection (especially when you using shaped objects).


    Code:
    function CheckBoundryCollision( R1, R2 : TRect; pR : PRect = nil; OffSetY : LongInt = 0; OffSetX : LongInt = 0): boolean; {overload;}
    // Simple collision test based on rectangles.
    
    begin
    // Rectangle R1 can be the rectangle of the character (player)
    // Rectangle R2 can be the rectangle of the enemy
    if( pR <> nil ) then
    begin
    // Simple collision test based on rectangles. We use here the
    // API function IntersectRect() which returns the intersection rectangle.
    with( R1 ) do
    R1:=Rect( Left+OffSetX, Top+OffSetY, Right-(OffSetX * 2), Bottom-(OffSetY * 2));
    with( R2 ) do
    R2:=Rect( Left+OffSetX, Top+OffSetY, Right-(OffSetX * 2), Bottom-(OffSetY * 2));
    
    Result:=IntersectRect( pR^, R1, R2 );
    end
    else begin
    // Simple collision test based on rectangles. We can also use the
    // API function IntersectRect() but i believe this is much faster.
    Result:=( NOT ((R1.Bottom - (OffSetY * 2) < R2.Top + OffSetY)
    or(R1.Top + OffSetY > R2.Bottom - (OffSetY * 2))
    or( R1.Right - (OffSetX * 2) < R2.Left + OffSetX)
    or( R1.Left + OffSetX > R2.Right - (OffSetX * 2))));
    end;
    end;

    Also you can make an overloaded function with the same name based on handles (to make it easier).

    Code:
    function CheckBoundryCollision( h1, h2 : Hwnd; pR : PRect = nil; OffSetY : LongInt = 0; OffSetX : LongInt = 0): boolean; {overload;}
    var
     R1 : TRect;
     R2 : TRect;
    
    begin
     FillChar( R1, SizeOf( R1 ), 0 );
     FillChar( R2, SizeOf( R2 ), 0 );
    
      // Note: You will get here the REAL screen coordinates.
      // It doesn't matter if a control is placed inside a panel or something.
     GetWindowRect( h1, R1 );
     GetWindowRect( h2, R2 );
    
     Result:=CheckBoundryCollision( R1, R2, pR, OffsetY, OffSetX );
    end;

    As an example, the above function may be used in a (threated timer) loop like this to check the player against multiple enemies:

    Code:
      for i := 0 to Length( Enemies ) - 1 do 
       if( CheckCollision( Player.Handle, Enemies[i].Handle, nil, 4, 4 )) then 
        GameOver;

    Bottom line is that usually it's enough if it "looks" real, and less important that it "is" real. It's a balance between how exact we want it, and how fast we need it to perform.

    I have used this methods in a simple game and it just works fine. Let's talk about transparency. You can use Regions to create special shaped Wincontrols. For example: A TPanel with a TImage on it (Panel1 and Image1). You can shape the panel to the image using the following examples:

    Code:
    function  CreateRegion( Bitmap : TBitmap; Rect : TRect; TransColor : TColor ) : hRgn;
    var
     i1, Count   : LongInt;
     x,y         : LongInt;
     c1          : Cardinal;
     c,t         : TColor;
     Msg         : TMsg;
    
    begin
    
     Result:=0;
    
     if( NOT Assigned( Bitmap )) then
      Exit;
    
     Count :=0;
    
     {if( TransColor = clAutomatic ) then
      }t:=Bitmap.Canvas.Pixels[ Rect.Left, Rect.Top ]
     {else t:=TransColor};
    
     with( Bitmap.canvas ) do
      for y := Rect.Top to Rect.Bottom do
        begin
          // Sort of the same like Application.ProcessMessages but doesn't require
          // the bulky Forms unit.
         PeekMessage( Msg, 0, 0, 0, PM_REMOVE );
    
         x:=Rect.Left;
    
         while( x <= Rect.Right ) do
          begin
           C:=Pixels[ x, y ];
    
           if( C <> t ) then
            begin
             i1 := x;
    
              while( C <> t ) do
               begin
                Inc(i1);
    
                C:=Pixels[ i1, y ];
    
                if( i1 >= Rect.Right ) then
                 Break;
               end;
    
              c1:=CreateRectRgn( x-Rect.Left,y-Rect.Top, i1-Rect.Left, (y-Rect.Top) + 1 );
    
              if( count = 0 ) then
               Result:=c1
              else begin
                    CombineRgn( Result, Result, c1, RGN_OR );
                    DeleteObject( c1 );
                   end;
    
           Inc( Count );
           x := i1;
           Continue;
          end;
    
          Inc(x);
        end;
      end;
    
     if( Count = 0 ) and ( Result > 0 ) then
      begin
       DeleteObject( Result );
       Result:=0;
      end;
    end;
    
     // Put this somewhere in your code (for example in the FormCreate event)
     begin
      Image1.Left:=0;
      Image1.Top:=0;
      Image1.AutoSize:=TRUE;
      Panel1.BevelInner:=bvNone;
      Panel1.BevelOuter:=bvNone;
      Panel1.Width:=Image1.Width;
      Panel1.Height:=Image1.Height; 
    
       // Create a region of the bitmap that is inside the image and set the region for the window.
       // Note: In this example the transparent color is black. Make sure the transparent (background) color is
       //       black! To be sure that you using the right color, you can also try this: Image1.Picture.Bitmap.Pixels[ 0, 0 ]       
      with( Panel1 ) do
       SetWindowRgn( Handle, CreateRegion( Image1.Picture.Bitmap, Rect( 1, 1, Width, Height ), clBlack ));
     end;
    Note: When you move the panel it is possible that the bitmap starts to flicker. You can create an
    Message handler for the message WN_EREASEBKGND to avoid the flicker. See the help of Delphi how to
    create new components and/or message handlers if do not know. Here is an example:

    Code:
          procedure TMyPanel.WMEraseBkgnd(var Message: TWmEraseBkgnd);
          begin
           if( csDesigning in ComponentState ) then
            inherited
           else Message.Result:=1; // Fake erase
          end;

    NOTE: Absolutly no warranty to this code. This is just an example. It is possible that you need to make some
    improvements to the code to give it a more proffesional behaviour.

    This article was aimed towards beginners wanting get into game programming, I'll hope it was helpful.

    Regards and good luck,
    Erwin Haantjes.

    Last edited by Richard; 12-Jun-03 at 01:53.

  2. #2
    Ziet er leuk uit. Een paar kleine vraagjes/opmerkingen?

    Allereerst over het uiterlijk
    - Waarom niet in het Nederlands?
    - Zou je je plaatje tussen [code] tags willen zetten. Dan wordt het goed uitgelijnd.
    - Zou je de code door de PascalConverter willen halen. Het is dan ingesprongen en in kleur, wat e.e.a. veel leesbaarder maakt.

    En natuurlijk ook nog wat inhoudelijk commentaar.
    - Ik heb wel vaker de keuze gezien tussen een exacte match en de zgn Bounding Box. Maar waarom wordt er nooit gebruik gemaakt van meerdere bounding boxes? Stel: Ik heb een vliegtuigje:
    Code:
        
        XXX 
        XXX
    XXXXXXXXXXXX
    XXXXXXXXXXXX
        XxX
        XXX
        XXX
       XXXXX
    Als ik naar dit plaatje kijk, dan zie ik eigenlijk globaal twee rechthoeken. Als ik deze sprite dus twee bounding boxes zou geven, dan ben ik nog steeds redelijk optimaal bezig, maar toch heb ik vrijwel volledig de contouren van het object te pakken. Ik denk dat de meeste game sprites in twee of drie boxes behoorlijk nauwkeurig te vatten zijn.
    Dit is niet om je artikel af te vallen, maar ik heb regelmatig artikels gelezen waar de keuze werd gesteld tussen de bounding box of de pixel benadering, maar deze combinatie schijnt niet aan de orde te zijn. Het schoot ook net pas in mijn hoofd toen ik je artikel las, dus misschien is er iets chronisch mis met mijn denkwijze...

    - Het WM_EraseBackgrnd verhaal is wel interessant.
    Er zijn in het verleden veel vragen gesteld over knipperingen die ontstaan bij het bewegen van sprites. Meestal wordt aangeraden om de sprites op een buffer te tekenen en deze dan in één keer te tonen. (Double buffering.) Ik begrijp dat je gebruik maakt van TImage afgeleiden om je sprites te vormen en dat je met het afvangen van deze message deze toch tamelijk knipperloos kunt tekenen.

    - Misschien is dit artikel ook wel geschikt voor bij de overige artikelen? Marcel?
    1+1=b

  3. #3
    Wat mij betreft: graag! Maar dan wel in het Nederlands natuurlijk.
    Marcel

  4. #4
    Registered User
    Join Date
    Jun 2003
    Location
    Zuid-Holland
    Posts
    6
    Pfff, hoe werkt dat dan met dat PasConvert. Nog steeds niet leesbaar!
    Erwin Haantjes

  5. #5
    Registered User
    Join Date
    Jun 2003
    Location
    Zuid-Holland
    Posts
    6
    <PRE>
    [code]

    Hallo Jongens, het is in het engels omdat ik het artikel voor een engelse delphi site heb geschreven als reactie op iemand met een collision probleem. Hij vroeg of er iemand was die een algemene oplossing voor dit probleem had. Ik heb op het internet mij ook blauw gezocht naar een oplossing in flexibele code. Nope, niet gevonden dus vandaar dat ik dit artikel geschreven heb. Helaas heb ik geen tijd het artikel te vertalen en ik denk dat het ook niet zozeer nodig is omdat Delphi nou eenmaal in het Engels is nietwaar? Natuurlijk, ik begrijp het, dit is een nederlandse site. Misschien is er iemand die vertalen erg leuk vind?

    Hier nogmaals de tekening:
    +------------+
    | XX |
    | XXXXXX |
    |XXXXXXXXXXXX|
    | XXXXXX+-|----------+
    | XX |X|XX XXXX|
    +------------+ XX XX |
    | XXXX |
    | XX XX |
    |XXXX XXXX|
    +------------+

    Om antwoord te geven op GolezTrol:
    Het is mogelijk een betere check uit te voeren na een collisiontest met de functie CheckBoundryCollision(). Zoals ik al eerder geschreven heb hou ik van flexibele oplossingen. Als je bij de parameter pR een variable invul dan krijg je de overlappende rectangle terug (zoals in de tekening te zien is als deze leesbaar is), tenminste als ik de API Help moet geloven. Voorbeeld:

    var
    R : TRect;

    begin
    if( CheckBoundryCollision( Player.Handle, Enemy.Handle, @R )) then
    begin
    // Doe hier een verdere controle m.b.v. var R
    end;
    end;

    Met deze rectange kun je dan testen of er echt pixels zijn die elkaar 'raken'. Als twee objecten elkaar raken dan moet op zijn minst 1 pixel in beide bitmaps ongelijk zijn aan de transparante kleur en zich precies op dezelfde positie bevinden. Als dit klopt dan zou er pas sprake zijn van een 'collision' (ontmoeting). Klinkt eenvoudig en zal best met wat moeite voor elkaar te krijgen zijn. Realiseer je alleen dat de collision test heel vaak wordt uitgevoerd en als de overlapping groot is dan treedt er (ernstige) vertraging op. Nu vraag ik mij af hoe ze dat doen in professionele games. Ik ben er wel van overtuigd dat er eerst een simpele collision test wordt gedfaan. Maar de rest, daar zou ik graag een antwoord op willen hebben en dan graag in transparante code. Wie o wie?

    Momenteel heb ik zelf een game engine geschreven (die overigens nog niet geheel foutloos werkt). De engine werkt op basis van regions zoals boven is beschreven. Het Regions systeem werkt heel goed alleen is soms nog niet 'smooth' genoeg, vooral als de sprite (bewegende afbeelding) heeel snel over het scherm flitst. Daarvoor leent 'double buffering' zich goed maar dit gaat niet op voor regions en kost bovendien meer geheugen. Mijn vorige engine werkte op basis van 'double buffering' en dit ziet er gelikt uit alleen onstaat er een probleem wanneer twee objecten elkaar overlappen, dan moet allerlei ingewikkelde kaprioolen (schrijf ik dat goed zo?) gaan uithalen. Met regions heb je daar dus geen last van. De nieuwe engine kent bovendien vele voordelen zoals: geen problemen bij overlappen, collision check op basis van handles, verschillen tussen sprites (images) en objecten (die zorgen voor de eigenschappen) = geheugen besparing, Regions vereisen geen AND bitmap = geheugen besparing, slimmer geheugen gebruik = geheugen besparing en tot slot gebaseerd op threads (objecten kunnen zich afzonderlijk op een bepaalde manier gedragen).
    Ondanks dat de engine op 2D gebaseerd is moet er eigenlijk ook nog een Z-order functionaliteit in komen. Iemand die daar tips over heeft, graag! Naast dat ook nog vele effecten zoals: transparantie, flikkeren (als speler is geraakt), bewegende achtergronden, explosies, health status, score etc. PS: De engine is volledig gebaseerd op de windows API (en toch nog zo snel WOW) en dus niet op DelphiX of OpenGL.

    Reacties altijd welkom, mvgr,
    Erwin.
    [code]
    </PRE>
    Erwin Haantjes

  6. #6
    Registered User
    Join Date
    Jun 2003
    Location
    Zuid-Holland
    Posts
    6
    Nog een antwoord op GolezTrol:
    Volgens mij is het niet verstandig meerdere bounding boxes toe te passen aangezien op al deze bounding boxes controle moet worden uitgevoerd!
    Erwin Haantjes

  7. #7
    5th member of nldelphi
    Join Date
    Mar 2001
    Location
    Alkmaar
    Posts
    2,127
    OkkieBokkie,

    Hoe werkt de pasconverter ?
    mischien dat je middels deze thread er uit komt zo niet geef dan even een brul
    http://www.nldelphi.com/Forum/showth...&threadid=2170

    Richard

    ps. ik heb de 2 code post gedelete welke niet door de pasconverter heen is gegaan.
    RLD

  8. #8
    Senior Member PsychoMark's Avatar
    Join Date
    Nov 2001
    Location
    Raamsdonksveer
    Posts
    10,269
    GolezTrol's idee is zeker niet slecht, helemaal niet als je 't combineert. Ik weet natuurlijk niet exact hoe profi games 't doen (alhoewel ik hier wel de source van een heb liggen (lang leve commerciele games die open-source gaan), maar da's flink wat C++ code ), maar ik kan me wel een voorstelling maken...

    Allereerst zullen waarschijnlijk alle games de bounding box als eerste controleren, dit is snel en efficient. Daarna is pixel-detection een optie (waarbij je 't liefst alleen de "colliding rectangle" gebruikt, waar de twee bounding boxes elkaar dus overlappen). Tot zover veranderd er dus weinig, maar laten we dat eens vergelijken met GolezTrol's aanpak in het geval van het vliegtuigje: de eerste bounding-box-check is snel, maar zodra het tweede vliegtuig rechts onder de ander komt is deze bounding box "betreden" en gaat de pixel collision detection in werking. Relatief gezien duurt het vrij lang voordat ze elkaar echt raken, wat een hoop onnodige pixel-checks betekent. Stel dat deze open ruimte slechts 50x100 pixels is, dan zijn dat wel 5000 checks per frame... niet bepaald efficient .

    In GolezTrol's geval controleren we 2 rectangles voordat we op pixel-detection over gaan. Dat scheelt 4998 checks per frame. Lijkt me toch een aardige optimalisatie . Als je object uit meerdere rectangles (of eventueel andere vormen zoals cirkels) bestaat kan je er nog voor kiezen om de bounding-box check eerst te doen.

    In het uiterste geval betekent dat dus een bounding-box check, dan een rectangles-check (om 't zo maar even te noemen) en daarna pixel-detection. Inderdaad, dat zijn dus overbodige stappen, maar reken eens uit hoeveel je ermee bespaart zodra de rectangles elkaar niet raken. Bij collision wordt er toch vaak gestopt met bewegen of storten vliegtuigen neer, dus zo'n impact hebben die extra checks niet .
    Qui custodiet ipsos custodes

  9. #9
    En je hoeft natuurlijk alleen maar een rectangles check uit te voeren als er inderdaad rectangles zijn. Een object dat zelf vrijwel rechthoekig is zal alleen de bounding box nodig hebben.
    1+1=b

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Scores voor Game en Gameprogrameren
    By Anton Sr. in forum Koffiehoek
    Replies: 8
    Last Post: 17-Feb-04, 20:58
  2. Delphi COM Programming
    By GolezTrol in forum Boekhoek
    Replies: 8
    Last Post: 02-Sep-03, 17:09
  3. E-Book: Graphics Programming Black Book
    By Christiaan in forum Boekhoek
    Replies: 1
    Last Post: 25-May-03, 03:20

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •