Keskustelu: Yleinen keskustelu: Random-funktio

User137 [12.03.2009 18:31:27]

Tekeillä tuota rts-peliä varten (toisessa topiikissa) pieni random funktio joka ei turvautuis liukulukuihin mitenkään. Kokeilin periaatetta että lasketaan ensin ihan normaalein keinoin 2048 valmiiksi arvottua lukua väliltä 0-255 ja laitetaan ne tiedostoon. Jokainen luku esiintyy yhtä monta kertaa mutta Delphin omalla randomilla sekoitettuna.

Nyt sitten tulee pientä ongelmaa kun tuota taulukkoa yrittää ottaa käyttöön. Tarkotuksena on että noiden 2048 sekaisin olevan luvun avulla voi arpoa minkä tahansa (positiivisen) kokonaisluvun.
Kun kutsun arpojaa rnd(101) niin saapi tällasta hajontaa:
http://i39.tinypic.com/2cxzf7.png
Huomaa että osa tietyn välein esiintyy selvästi useammin kun muut. Pikasesti testattuna väli rnd(0)..rnd(16) toimii oikein eli tasanen hajonta eikä yksikään luku tee piikkiä ylös tai alas.

Jos jottain vinkkiä tai huomattavaa tulee mieleen? :)

// Funktio
function Rnd(const n: integer): integer;
var i,sum: integer;
begin
  result:=0;
  if n<2 then exit;
  rnd_seed:=rnd_seed mod 2048;
  sum:=0;
  repeat
    result:=result+_rnd[rnd_seed];
    sum:=sum+255;
    rnd_seed:=(rnd_seed+1) mod 2048;
  until sum>=n;
  result:=result*n div (sum+1);
end;

// _rnd[] taulukon Generointi
  randomize;
  for i:=0 to 2047 do _rnd[i]:=i mod 256;
  for k:=1 to 3 do // Sekoitetaan 3 kertaa
    for i:=0 to 2047 do begin
      j:=random(2048);
      temp:=_rnd[i]; _rnd[i]:=_rnd[j]; _rnd[j]:=temp;
    end;

Lebe80 [13.03.2009 11:36:51]

Miksei se saa käyttää liukulukuja? Pyöristät vaan arvotun summan alaspäin lähimpään kokonaislukuun.

User137 [13.03.2009 16:32:30]

Alkup. viesti oli siis Tuolla.

Kävi ilmi että eri prosessorit laskee liukuluvuilla eri tavalla. Olen melko varma että kielien yleiset randomit turvaa liukulukuihin jollain tapaa.

Erilaisia variaatioita on tullu myös kokeiltua ja funktio kirjotettu uudestaan tyhjästä melko tuloksetta. 200 luvulla voi jo saada aikaan jonkunlaisen "sahanterän" mutta 3000 on jo karua katseltavaa. Pitäskö mun vaan käyttää suosiolla suurempia lukuja taulukossa tai enemmän lukuja? Jotenkin vaan luulen että se on ns. purkkaratkaisu joka kostautuu kun taas etsii 10 kertaa suurempia satunnaislukuja.

Objektien koordinaatit itse on helppo esittää kokonaisluvuilla. 4 tavuun (sama kuin tyyppi single) mahtuu luku jonka koko on 4 miljardia eikä tuon pelin karttakoko tule olemaan muutamaa tuhatta suurempi. Saan siis rauhassa kertoa koordinaatit 0.001:llä piirtovaiheessa ja olettaa että 1000 kokonaislukuna vastaa lukua 1 desimaaleina.

os [13.03.2009 17:48:23]

User137 kirjoitti:

Olen melko varma että kielien yleiset randomit turvaa liukulukuihin jollain tapaa.

Ööö... ei? Yksinkertaisimmat toimivat näin

http://en.wikipedia.org/wiki/Linear_congruential_generator

Ainakin voit koodata oman random-funktion samalla tavalla, jos epäilyttää.
Onhan käsite siemenluku tuttu?

http://www.delphibasics.co.uk/RTL.asp?Name=RandSeed
http://www.cplusplus.com/reference/clibrary/cstdlib/srand.html

User137 [13.03.2009 19:20:40]

No joo, näyttäis että Borland on käyttäny just tuota linearia vanhoista TP ajoista Delphi 7 asti ainakin (ei ihan virallisesta lähteestä). Homma jatkuu kumminkin sillä...

Käsittääkseni jos tuota omaa ideaa olis jatkanu ja päästä helpolla niin niiden lukujen olis tullu olla vähintään yhtä suuria kuin suurin luku mitä sillä generoidaan ja jottei samankaltaisuutta ole liikaa niin useampia jaksoja. Toisinsanoen olis vieny muistia liikaa. Olis kasvattanu seediä aina yhdellä ja skaalannu sillä kohtaa esiintyvän taulukon luvun halutulla arvolla. Toisaalta jos haluaa rajoittaa muistin käyttöä niin käyttäis pienempiä lukuja sillä menetyksellä että osa luvuista jää esiintymättä kun kysytty arvo on suurempi (mikä ei välttämättä haittaa).

jalski [13.03.2009 21:21:53]

Miten kävisi multiply-with-carry (MWC) random-funktio toteutus?

Alla on Micho Durdevichin OS/2 PM-ohjelmointi esimerkistä kopioitu assembly toteutus:

mov eax, 0x4019CF16
mul random_var
add eax, random_var[4]
mov random_var, eax
adc edx, 0
mov random_var[4], edx

Metabolix [13.03.2009 21:52:20]

Kehuvat hyväksi ja nopeaksi sellaista kuin Mersenne twister. Sivun lopussa on myös pseudokoodi, joka vääntyy Pascaliksi aika näppärästi.

koo [13.03.2009 23:14:57]

Complimentary-Multiply-With-Carry on aika paljon yksinkertaisempi ja nopeampi kuin Mersenne Twister, mutta silti riittävän satunnainen ja erittäin pitkäjaksoinen.

Ikiomaa algoritmia ei oikein kannata ruveta väsäämään, ellei ole hallussa aikas paljon teoriaa ja tutkimusta. Omaan peliin riittää varmasti kirjaston perus-random. Nettipokerissa tai jossain Monte Carlo -laskennassa on parasta siirtyä käyttämään jotakin ihan totisesti oikeata algoritmitoteutusta, joka on myös testattu oikein.

jalski [17.03.2009 19:33:42]

Alla esimerkkinä aikaisemmin mainitsemani MWC random-funktio OpenWatcom C-kutsuttavana assembler toteutuksena.

rand1.asm

.386p

 _DATA SEGMENT DWORD PUBLIC USE32 'DATA'
        public _random_var1
        public _random_var2
        _random_var1    dd 8
        _random_var2    dd 5


 _DATA ENDS

 DGROUP GROUP _DATA


_TEXT SEGMENT PARA PUBLIC USE32 'CODE'
ASSUME CS:_TEXT, DS:_DATA

public Randomize_
Randomize_ proc near
        push ebx
        push edx

        cmp       eax, 0
        jz @random_exit

        cmp eax, 0xFFFFFFFF
        jz @random_exit

        mov ebx, eax

        mov eax, 0x4019CF16
        mul _random_var1
        add eax, _random_var1[4]
        mov _random_var1, eax
        adc edx, 0
        mov _random_var1[4], edx

        xor edx, edx
        inc ebx
        div  ebx
        xchg edx, eax

@random_exit:
        pop edx
        pop ebx

        ret

Randomize_ endp


        _TEXT ends
                end

Jos haluat testata, niin tee uusi projekti. Määritä alustaksi 32-bittinen DOS (Causeway -tai dos4gw-extender) ja liitä ylläolevan tiedoston lisäksi projektiin allaolevat tiedostot:

buftoscr.asm

.386p


    extrn _Screen:dword
    extrn _ScreenBuffer:dword



_TEXT SEGMENT PARA PUBLIC USE32 'CODE'
ASSUME CS:_TEXT, DS:_DATA

public BufferToScreen_
BufferToScreen_ proc near
    push esi
    push edi

;  Kopioi näyttöpuskurin sisällön näyttömuistiin 32 bittiä kerrallaan!!!
;
    cld
    mov edi, _Screen                ; osoitin videomuistiin
    mov esi, _ScreenBuffer          ; osoitin puskuriin

    mov cx,((320*200)/4)            ; kopioitavan määrä

    mov dx,3dah                     ; VGA portti ja indeksi (Input Status Register)
@retrace:
    in al,dx                        ; lue VGA portti
    and al,8                        ; selvitä tahdistuksen tila
    jz @retrace                     ; odota näytön tahdistusta

    rep movsd                       ; kopioi 32-bittiä kerrallaan

    pop edi
    pop esi
    ret
BufferToScreen_ endp


public ClearBuffer_
ClearBuffer_ proc near
    push edi

    cld
    mov edi, _ScreenBuffer

    mov eax,0                       ; täyttöväri
    mov cx,((320*200)/4)            ; kopioitavan määrä
    rep stosd                       ; kopioi 32-bittiä kerrallaan

    pop edi
    ret
ClearBuffer_  endp

        _TEXT ends
                end

main.c

//
// OpenWatcom versio spritekääntäjästä
//
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <dos.h>


#define SCREEN_WIDTH 320
#define SCREEN_HEIGHT 200

#define SPRITE_WIDTH 24
#define SPRITE_HEIGHT 16


    typedef unsigned char uchar;

    typedef void near (*CompiledSprite)(uchar *,int,int);
    CompiledSprite CompileSprite(uchar *pBitmap, int width, int height);



CompiledSprite CompileSprite(uchar *pBitmap, int width, int height)
{

    int row, column;
    int b1, b2, b3, b4;
    int dwords=0, words=0, bytes=0;

    unsigned int Offset, BufferSize, Index=0;
    uchar *CodeBuffer;

    // Selvitetään kuinka monta tavua kerrallaan voidaan kopioida
    for(row=0; row < height; row++) {
        Offset = row * width;
        for(column=0; column < width; column++)  {


            b1 = (pBitmap[Offset+column] != 0 ) ? 1 : 0;

            if((column+1) < width)   {
                b2 = (pBitmap[Offset+column+1] != 0 ) ? 1 : 0;


            if((column+2) < width)   {
                b3 = (pBitmap[Offset+column+2] != 0 ) ? 1 : 0;

            if((column+3) < width)   {
                b4 = (pBitmap[Offset+column+3] != 0 ) ? 1 : 0;

            }
            else b4 = 0;
                    }
                     else b3 = 0;
                            }
                             else b2 = 0;


            if(b1) {
                    if(b2) {
                            if(b3) {
                                    if(b4) {

                                        dwords++;
                                        column+=3;
                                }


                                else {
                                        words++;
                                        bytes++;
                                        column+=2;

                                }
                        }

                        else {
                                words++;
                                column++;
                        }
                }

                else {

                        bytes++;
                }

           }


        } // Lopeta sarake looppi

     }  // Lopeta rivi looppi


     // Lasketaan tarvittava puskurin koko
    BufferSize = (10 * dwords) + (9 * words) + (7 * bytes) + 15;

    // Varataan tilaa koodipuskurille
    CodeBuffer = (uchar *) malloc(BufferSize);
    if(!CodeBuffer) return (CompiledSprite)CodeBuffer;


    // Käydään kuvatieto läpi uudestaan ja kirjoitetaan puskuriin
    //  konekielinen piirtorutiini

        // Parametrit rekistereistä
        CodeBuffer[Index++] = 0x89; // mov ecx,ebx
        CodeBuffer[Index++] = 0xd9;

        CodeBuffer[Index++] = 0xc1; // shl ebx,08h
        CodeBuffer[Index++] = 0xe3;
        CodeBuffer[Index++] = 0x08;

        CodeBuffer[Index++] = 0xc1; // shl ecx,06h
        CodeBuffer[Index++] = 0xe1;
        CodeBuffer[Index++] = 0x06;

        CodeBuffer[Index++] = 0x01; // add eax,ebx
        CodeBuffer[Index++] = 0xd8;

        CodeBuffer[Index++] = 0x01; // add eax,ecx
        CodeBuffer[Index++] = 0xc8;

        CodeBuffer[Index++] = 0x01; // add eax,edx
        CodeBuffer[Index++] = 0xd0;


    // Kuvatieto
    for(row=0; row < height; row++) {
            Offset = row * width;
            for(column=0; column < width; column++)  {


             b1 = (pBitmap[Offset+column] != 0 ) ? 1 : 0;

        if((column+1) < width)   {
                b2 = (pBitmap[Offset+column+1] != 0 ) ? 1 : 0;


        if((column+2) < width)   {
                b3 = (pBitmap[Offset+column+2] != 0 ) ? 1 : 0;

        if((column+3) < width)   {
                b4 = (pBitmap[Offset+column+3] != 0 ) ? 1 : 0;

        }
         else b4 = 0;
                }
                 else b3 = 0;
                        }
                         else b2 = 0;


        if(b1) {
                if(b2) {
                        if(b3) {
                                if(b4) {
                                        // mov dword ptr [eax+offset32],xxxxxxxx
                                        CodeBuffer[Index++] = 0xc7;
                                        CodeBuffer[Index++] = 0x80;
                                        // 32-bit offset
                                        CodeBuffer[Index++] = ((row * 320 + column) & 0x00FF);
                                        CodeBuffer[Index++] = ((row * 320 + column) >> 8);
                                        CodeBuffer[Index++] = 0x00;
                                        CodeBuffer[Index++] = 0x00;
                                        // pixel data
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column];
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+1];
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+2];
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+3];

                                        column+=3;
                                }


                                else {
                                        // mov word ptr [eax+offset32],xxxx
                                        CodeBuffer[Index++] = 0x66;
                                        CodeBuffer[Index++] = 0xc7;
                                        CodeBuffer[Index++] = 0x80;
                                        // 32-bit offset
                                        CodeBuffer[Index++] = ((row * 320 + column) & 0x00FF);
                                        CodeBuffer[Index++] = ((row * 320 + column) >> 8);
                                        CodeBuffer[Index++] = 0x00;
                                        CodeBuffer[Index++] = 0x00;
                                        // pixel data
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column];
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+1];

                                        // mov byte ptr [eax+offset32],xx
                                        CodeBuffer[Index++] = 0xc6;
                                        CodeBuffer[Index++] = 0x80;
                                        // 32-bit offset
                                        CodeBuffer[Index++] = ((row * 320 + column) & 0x00FF);
                                        CodeBuffer[Index++] = ((row * 320 + column) >> 8);
                                        CodeBuffer[Index++] = 0x00;
                                        CodeBuffer[Index++] = 0x00;
                                        // pixel data
                                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+2];

                                        column+=2;

                                }
                        }

                        else {
                                // mov word ptr [eax+offset32],xxxx
                                CodeBuffer[Index++] = 0x66;
                                CodeBuffer[Index++] = 0xc7;
                                CodeBuffer[Index++] = 0x80;
                                // 32-bit offset
                                CodeBuffer[Index++] = ((row * 320 + column) & 0x00FF);
                                CodeBuffer[Index++] = ((row * 320 + column) >> 8);
                                CodeBuffer[Index++] = 0x00;
                                CodeBuffer[Index++] = 0x00;
                                // pixel data
                                CodeBuffer[Index++] = (uchar) pBitmap[Offset + column];
                                CodeBuffer[Index++] = (uchar) pBitmap[Offset + column+1];

                                column++;
                        }
                }

                else {
                        // mov byte ptr [eax+offset32],xx
                        CodeBuffer[Index++] = 0xc6;
                        CodeBuffer[Index++] = 0x80;
                        // 32-bit offset
                        CodeBuffer[Index++] = ((row * 320 + column) & 0x00FF);
                        CodeBuffer[Index++] = ((row * 320 + column) >> 8);
                        CodeBuffer[Index++] = 0x00;
                        CodeBuffer[Index++] = 0x00;
                        // pixel data
                        CodeBuffer[Index++] = (uchar) pBitmap[Offset + column];
                }

            }


        } // Lopeta sarake looppi

     }  // Lopeta rivi looppi

        // paluu
        CodeBuffer[Index++] = 0xc3; // retn


    return (CompiledSprite)CodeBuffer;
}


/////////////////////////////////////////////////////////////////////////////////////////////////
// Seuraava on vain testiä varten ...
/////////////////////////////////////////////////////////////////////////////////////////////////


    void SetMode13h(void);
    #pragma aux SetMode13h = \
    "     mov ax,13h       " \
    "     int 10h          " \
    modify [ax];


    void SetMode03h(void);
    #pragma aux SetMode03h = \
    "     mov ax,03h       " \
    "     int 10h          " \
    modify [ax];



    extern int Randomize(int);
    extern void ClearBuffer(void);
    extern void BufferToScreen(void);

    extern int random_var1;
    extern int random_var2;

    struct dostime_t time;


    uchar *Screen;
    uchar *ScreenBuffer;

    CompiledSprite testi;


    uchar Sprite_data[] = {
                             00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,
                             00,00,00,00,00,00,16,16,16,16,16,16,16,16,16,16,16,16,16,00,00,00,00,00,
                             00,00,00,00,16,16,16,14,14,14,14,14,14,14,14,14,14,14,16,16,16,00,00,00,
                             00,00,00,16,16,14,14,14,16,14,14,14,14,14,14,16,14,14,14,14,16,16,00,00,
                             00,16,16,16,14,14,14,16,16,16,14,14,14,14,16,16,16,14,14,14,14,16,16,00,
                             00,16,14,14,14,14,14,16,16,16,14,14,14,14,16,16,16,14,14,14,14,14,16,00,
                             00,16,14,14,14,14,14,14,16,14,14,14,14,14,14,16,14,14,14,14,14,14,16,00,
                             00,16,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,16,00,
                             00,16,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,16,00,
                             00,16,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,16,00,
                             00,16,14,14,14,16,14,14,14,14,14,14,14,14,14,14,14,14,16,14,14,14,16,00,
                             00,16,14,14,14,14,16,14,14,14,14,14,14,14,14,14,14,16,14,14,14,14,16,00,
                             00,16,16,16,14,14,14,16,16,16,16,16,16,16,16,16,16,14,14,14,16,16,16,00,
                             00,00,00,16,16,14,14,14,14,14,14,14,14,14,14,14,14,14,14,16,16,00,00,00,
                             00,00,00,00,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,00,00,00,00,
                             00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00 };




int main(void)
{

    _dos_gettime( &time );
    random_var1 = time.second;
    random_var2 = time.minute;


    testi=(CompiledSprite)CompileSprite(Sprite_data, SPRITE_WIDTH, SPRITE_HEIGHT);

    ScreenBuffer=malloc(SCREEN_WIDTH*SCREEN_HEIGHT);
    if(!ScreenBuffer)
    {
        printf("Ei tarpeeksi muistia näyttöpuskurille\n");
        exit(1);
    }

    ClearBuffer();

    Screen = (uchar *) 0xA0000;    // osoitin videomuistiin

    SetMode13h();

    while(!kbhit()) {
        testi(ScreenBuffer, Randomize(SCREEN_WIDTH - SPRITE_WIDTH), Randomize(SCREEN_HEIGHT - SPRITE_HEIGHT));
        testi(ScreenBuffer, Randomize(SCREEN_WIDTH - SPRITE_WIDTH), Randomize(SCREEN_HEIGHT - SPRITE_HEIGHT));
        testi(ScreenBuffer, Randomize(SCREEN_WIDTH - SPRITE_WIDTH), Randomize(SCREEN_HEIGHT - SPRITE_HEIGHT));
        testi(ScreenBuffer, Randomize(SCREEN_WIDTH - SPRITE_WIDTH), Randomize(SCREEN_HEIGHT - SPRITE_HEIGHT));
        testi(ScreenBuffer, Randomize(SCREEN_WIDTH - SPRITE_WIDTH), Randomize(SCREEN_HEIGHT - SPRITE_HEIGHT));

        BufferToScreen();
    }

    free(ScreenBuffer);

    SetMode03h();

    return 0;

}

Ohjelman pitäisi piirtää melko vauhdikkaasti hymynaamoja ruudulle satunnaisille paikoille. Ai niin... kyseessä ei sitten ole mikään esimerkki hyvännäköisestä C-ohjelmointi tavasta.

Lebe80 [18.03.2009 08:37:36]

ja alla dailywtf:sta

function random(){
  return 4; // luku on valittu täysin satunnaisesti
}

Sivun alkuun

Vastaus

Aihe on jo aika vanha, joten et voi enää vastata siihen.

Kirjautuminen

Haku

Tehtävät

Kilpailu