[JS] Psuedorandom noise genereren

[Verwijderd]

Allereerst: Ik weet dat javascript in Webdesign thuishoort, maar dit is meer een programmeer/algoritme vraag dan iets javascript-specifieks. De reden dat ik het vermeld is omdat ik dus ook geen toegang heb tot een ingebouwde seeded generator.

Ik ben bezig om een Perlin Noise functie te maken om procedureel textures te genereren voor een game. Deze site legt alle stappen zeer duidelijk uit, en de uiteindelijk code is niet zo heel moeilijk. Ik loop echter vast bij de functie die noise genereert.

Ik heb nu zelf de volgende javascript functie geschreven om aan de hand van de input een getal tussen de 0.0 en 1.0 te returnen (aangepast van de site om ipv [-1.0..1.0] [0.0..1.0] terug te geven):

JavaScript:

function Noise(n)
{
    n = (n << 13) ^ n;
    return ((n * (n * n * 15731 + 789221) + 1376312589) & 0x7fffffff) / 2147483648;
}

Als ik de resultaten op een grafiek plot krijg ik dit resultaat:


De getallen zijn goed verdeeld tot aan n = 600. Hierna worden de nummers onzin, allemaal herhalingen.

Nu kan ik wel de input beperken met n %= 600, maar bij ook maar een beetje grote plaatjes zie je meteen patronen verschijnen. Ik snap de random functie niet goed genoeg om te zien hoe ik een groter bereik kan krijgen. Hoe kan ik een random reeks van bijvoorbeeld minstens 3000 getallen genereren?

Bovendien wil ik later meerdere reeksen kunnen creëeren. De site waar ik de informatie vandaan heb heeft het over de priem getallen variëeren, maar dan moet ik toch wel priem getallen uitzoeken van ongeveer dezelfde grootheid?

Ik heb al wat gezocht naar alternatieve bronnen, maar de meeste gaan uit van ingebouwde generators in andere talen of zijn volledige papers van wiskunde professoren die mij boven de pet gaan.

[chem]

Wat is er mis met Math.random() ?

[.oisyn]

Ten eerste het feit dat het reproduceerbaar moet zijn (ergo, je moet een seed kunnen instellen - bij Math.random() kan dat niet), ten tweede dat hij z'n textures waarschijnljik niet in javascript wilt genereren

[NMe]

.oisyn schreef op zondag 26 september 2010 @ 15:47:
Ten eerste het feit dat het reproduceerbaar moet zijn (ergo, je moet een seed kunnen instellen - bij Math.random() kan dat niet), ten tweede dat hij z'n textures waarschijnljik niet in javascript wilt genereren

Beetje lullig/vreemd dat JS niet voorziet in een functie die een seed accepteert. Maar goed, er zijn toch wel wat kant en klare functies te vinden. Lijkt me makkelijk genoeg om aan te passen zodat je je eigen seed gebruikt?

[.oisyn]

Niet zo'n seed. Eentje waarbij je in O(1) tijd het N'de random nummer op kan vragen.

[.oisyn]

Het ligt trouwens denk ik aan javascript, want als ik het door een C++ compiler gooi dan krijg er zeker tot 5000 goede getallen uit (verder heb ik 'm niet laten lopen)

[ Voor 104% gewijzigd door .oisyn op 26-09-2010 16:23 ]

[Verwijderd]

Haha, bedankt .oisyn voor het in de goede richting houden van het topic . En voor het testen in C++, zelf nog niet aan gedacht .
Ik wil inderdaad een functie die bij een bepaalde input een bepaalde output geeft, en niet eentje die bij elke aanroep een nieuw nummer geeft.
Vreemd dat het in javascript fout gaat. Ik heb het na je test in C++ ook maar eens in een Opera (ipv Firefox) getest en die komt zelfs al na 10 iteraties met enkel 0en.

[.oisyn]

Het komt omdat het doubles gebruikt voor de berekening, terwijl hij is toegespitst op een int. Probeer dit eens:

JavaScript:

function IntMul(a, b)
{
    return (a * b) & 0xffffffff;
}

function Noise(n) 
{ 
    n = (n << 13) ^ n; 
    return ((IntMul(n, IntMul(IntMul(n, n), 15731) + 789221) + 1376312589) & 0x7fffffff) / 2147483648;
}

Verklaring: bij ints hebben de bits een vaste waarde. Doubles werken daarentegen met een vast aantal bits en een exponent. Door heel veel te vermenigvuldigen wordt het getal heel groot. Bij ints betekent dat dat er bits aan de bovenkant verloren gaan. Bij doubles daarentegen schuift de exponent op, zodat het getal tot een bepaalde precisie blijft kloppen. Die precisie is vervolgens het probleem - uiteindelijk doe je een AND om de onderste bits eruit te krijgen, maar die bestaan dan al niet meer.

Een voorbeeld met decimale digits, stel een int bestaat uit 4 digits, en een double heeft er 6 en een exponent. De invoer is 1001.

1001*1001*1001 = 1003003001
Als int komt daar dus simpelweg 3001 uit (de onderste 4 digits). Een double encodeert het als 100300 * 10⁴. Je ziet, de minst significante digits zijn weggegooid, maar die zijn juist zo belangrijk omdat je juist daarin geinteresseerd bent. Een modulo met 10000 (vergelijkbaar met AND 0xffffffff) geeft dan gewoon 0 terug.

[ Voor 59% gewijzigd door .oisyn op 26-09-2010 16:31 ]

[Verwijderd]

.oisyn schreef op zondag 26 september 2010 @ 16:23:
Het komt omdat het doubles gebruikt voor de berekening, terwijl hij is toegespitst op een int. Probeer dit eens:

JavaScript:

function IntMul(a, b)
{
    return (a * b) & 0xffffffff;
}

function Noise(n) 
{ 
    n = (n << 13) ^ n; 
    return ((IntMul(n, IntMul(IntMul(n, n), 15731) + 789221) + 1376312589) & 0x7fffffff) / 2147483648;
}

Geweldig! Nu werkt het in zowel Firefox als Opera en IE (al kan IE het natuurlijk niet plotten vanwege het ontbreken van het Canvas element).
Dank je, dit soort dingen zijn zonder een stevige low-level achtergrond altijd wel erg lastig te vinden.

[Soultaker]

Verwijderd schreef op zondag 26 september 2010 @ 15:29:
Ik ben bezig om een Perlin Noise functie te maken om procedureel textures te genereren voor een game. Deze site legt alle stappen zeer duidelijk uit, en de uiteindelijk code is niet zo heel moeilijk.

Niet dat het concreet veel uitmaakt, maar wat op die site wordt uitgelegd is geen Perlin noise.

[Verwijderd]

Soultaker schreef op zondag 26 september 2010 @ 16:49:
[...]

Niet dat het concreet veel uitmaakt, maar wat op die site wordt uitgelegd is geen Perlin noise.

Ah, na wat lezen op wikipedia zie ik dat je gelijk hebt. De site legt blijkbaar Value Noise uit, al weet ik niet precies wat het verschil is. Maakt voor het gewenste resultaat idd niet uit volgens mij.