[ALG] Teveel if-statements

[Verwijderd]

Hey, ik ben op het moment een spelletje aan het maken. Dit spelletje is een ouwe bekende, weet alleen niet meer hoe hij heet. Maar het idee is om mbv een links rechts bewegend plankje een stuiterend balletje tegen te houden, die weer blokjes moet raken om het veld leeg te maken.
Met dit spel moet er bij botsingen gekeken worden in welke richting het balletje gaat en op welke muur hij stuiterd, waardoor deze van richting moet veranderen. Zoals ik het op dit moment heb geprogrammeert zijn er bij de check op botsingen heel veel if-else statements. En ik vroeg me af of daar geen mooiere oplossing voor is, om dit kleiner te maken en overzichtelijker.

code:

if(  linkermuur wordt geraakt ){
        if(   balletje gaat omhoog )//bla
        else if(  balletje gaat omlaag )//bla
else if( rechtermuur )

etc etc

[clevy]

stukken voor linker en rechter muur ieder in een functie zetten ?

[Zoijar]

Verwijderd schreef op zaterdag 23 april 2005 @ 17:25:
Hey, ik ben op het moment een spelletje aan het maken. Dit spelletje is een ouwe bekende, weet alleen niet meer hoe hij heet. Maar het idee is om mbv een links rechts bewegend plankje een stuiterend balletje tegen te houden, die weer blokjes moet raken om het veld leeg te maken.
Met dit spel moet er bij botsingen gekeken worden in welke richting het balletje gaat en op welke muur hij stuiterd, waardoor deze van richting moet veranderen. Zoals ik het op dit moment heb geprogrammeert zijn er bij de check op botsingen heel veel if-else statements. En ik vroeg me af of daar geen mooiere oplossing voor is, om dit kleiner te maken en overzichtelijker.

code:

if(  linkermuur wordt geraakt ){
        if(   balletje gaat omhoog )//bla
        else if(  balletje gaat omlaag )//bla
else if( rechtermuur )

etc etc

Arkanoid?

Je kan een call tabel maken. Je maakt dan eerst een aantal event functies, bv onLeftWall() onUp() etc. en een tabel met functie pointers hiernaartoe, geindexeerd bij de state van de bal... of een OO structuur. Maar zoveel if's zijn het niet volgens mij.

[Verwijderd]

Arakaniod ja wist de naam effe nie

[ Voor 99% gewijzigd door Verwijderd op 23-04-2005 18:01 ]

[Soultaker]

Dat heet dus Arkanoid.

Voor horizontale en verticale muren is het makkelijk; je hoeft dan alleen maar de horizontale of de verticale snelheid van teken te verwiselen. Bv:

C:

float x = 10, y = 10;  // beginpositie
float vx = 1, vy = 1;  // schuin naar onder

while( .. ) {

    if(x + vx < 0 || x + vx > breedte))
        vx = -vx;    // horizontale muur

    if(y + vy < 0 || y + vy > hoogte))
        vy = -vy;    // verticale muur

    // Positie bijwerken
    x += vx; y += vy;

}

Het algemene geval (met willekeurige muren) is lastiger, maar dat heb je voor een Arkanoid-clone niet nodig.

edit:
Deze code werkt trouwens ook niet helemaal perfect, maar als je genoeg frames per second doet valt dat niet zo op.

[ Voor 11% gewijzigd door Soultaker op 23-04-2005 17:38 ]

[Verwijderd]

hehe ja zo kan het natuurlijk ook, tnx. Alleen vind ik mijn stukkie wel leesbaarder. Maarik denk wel dat jouw manier een stuk korter en mooier is ja

[Janoz]

code:

              if( downright ){ 
                setX( x+dx ); 
                setY( y+dy ); 
              }else if( upright ){ 
                setX( x+dx ); 
                setY( y-dy ); 
              }else if(downleft){ 
                setX( x-dx ); 
                setY( y+dy ); 
              }else if(upleft){ 
                setX( x-dx ); 
                setY( y-dy ); 
              }

Dit stukje vind ik een beetje vreemd. Wanneer dx en dy negatief kunnen zijn heb je dit hele stuk niet nodig. Gebruik je gewoon alleen een dx en dy dan wordt je intersectie algoritme ook een stuk simpeller.

[Zoijar]

Je kan ook, als je per se wilt, if's vermijden op deze manier...ooit eens gedaan voor snelheids winst; maar het is nutteloos als er geen 80% oid in die functie zit.

C++:

    signed int dx = p.x() - c.x();
    signed int dy = p.y() - c.y();
    int off = (std::abs(dy)+std::abs(dx)) >> 1;

    // calculate without branching. This is much faster than if/else on modern architectures.
    static const char lut[] = {-1,  0, -1, +1,  0, +1,
                               -1, -1, -1, -1, +1, +1,
                                0, -1, +1, -1, +1,  0};
    
    int signx = ((dx != 0) | (dx >> (sizeof(int) * 8 - 1))) + 1;  // 0, 1 or 2
    int signy = ((dy != 0) | (dy >> (sizeof(int) * 8 - 1))) + 1;  // 0, 1 or 2

    return Index(c.x() + lut[(signy*2)+(6*signx)]*off, c.y() + lut[(signy*2)+(6*signx)+1]*off);

[Soultaker]

Ik kan me niet voorstellen dat dat sneller is dan wat assembly code met een conditionele move (die ook niet branched en ook geen look-up table in de cache hoeft te houden), of gewone code met goede branch predictability (alleen een stall als je een muur raakt, bijvoorbeeld).

[ Voor 24% gewijzigd door Soultaker op 23-04-2005 22:51 ]

[JoetjeF]

Ik zou er ook meteen mee rekening houden dat je de collision per pixel berekent. Stel dat het balletje een snelheid van meer dan 1 pixel heeft, dan is het mogenlijk dat het balletje tussen twee diagonaal tegen elkaar aanliggende blokken door stuitert.

Ik ga er hier even vanuit dat je het balletje een 2x2 collision domain geeft, anders kan je natuurlijk ook grotere stappen nemen.

[MSalters]

Zoijar schreef op zaterdag 23 april 2005 @ 21:32:
Je kan ook, als je per se wilt, if's vermijden op deze manier...ooit eens gedaan voor snelheids winst; maar het is nutteloos als er geen 80% oid in die functie zit.

C++:

    signed int dx = p.x() - c.x();
    signed int dy = p.y() - c.y();
    int off = (std::abs(dy)+std::abs(dx)) >> 1;

    // calculate without branching. This is much faster than if/else on modern architectures.
    static const char lut[] = {-1,  0, -1, +1,  0, +1,
                               -1, -1, -1, -1, +1, +1,
                                0, -1, +1, -1, +1,  0};
    
    int signx = ((dx != 0) | (dx >> (sizeof(int) * 8 - 1))) + 1;  // 0, 1 or 2
    int signy = ((dy != 0) | (dy >> (sizeof(int) * 8 - 1))) + 1;  // 0, 1 or 2

    return Index(c.x() + lut[(signy*2)+(6*signx)]*off, c.y() + lut[(signy*2)+(6*signx)+1]*off);

Onder wat aannames, geen int padding, CHAR_BIT==8, en een snelle 8-bit load. Bovendien heb ik wat twijfels over de registerdruk (voor x86). Eigenlijk wil je de register loads van lut[6x+2y] en lut[6x+2y=1] combineren. Dan zou je vervolgens AL/AH kunnen gebruiken, cq. een 8-bits mask in een register kunnen doen. Als off<256 (of<65536) dan zou je de multiply met off ook in parallel kunnen doen.

Aan de andere kant: wat is de kans dat dit uitmaakt?

[Zoijar]

Voor een wild varierende functie, ie. branch prediction bakt er hier weinig tot niets van, kan het iets helpen. Ja, tuurlijk, als je alles nog handmatig in assembler schrijf zal je er nog wel wat snelheid uit kunnen persen. Het ging sowieso om het idee, ik gaf ook al aan dat het bij arkanoid weinig nut zou hebben. De TS vraagt toch echt hoe je onder if's uit kan komen Ik neem ook aan dat je compiler een index met 2 multiplies (waarvan eentje met 2) en een som, wel optimized naar een enkel instructie en wat bifshift. Geneste if's optimized een compiler iha niet naar branchloze code.