Halton Sequence

[I am Lord]

Halton Sequence jest to w skrócie metoda rozmieszczania punktów w taki sposób by miały małą rozbieżność.

Zrobiłem prosty generator takich punktów na podstawie artykułu na wikipedii: http://en.wikipedia.org/wiki/Halton_sequence

 

Wynik generowania wygląda następująco:

 

Funkcja halton_point zwraca liczbę z przedziału <0, 1> na podstawie podanego indexu ( jakiejś całkowitej dodatniej liczby ) i liczby pierwszej.

Na oś x i y przypadają 2 różne liczby pierwsze, ja losuję je z przedziału <2, 7> czyli po wywaleniu powtarzającej się liczby powstaje 12 różnych kombinacji.

 

Gdyby przyjąć większy przedział losowania liczby pierwszej np <2, 73> to różnorodność "patternów" się zwiększa ale w końcu możemy trafić na sekwencję która wygląda mniej więcej tak:

 

Co jest oczywiście niepożądane. Ale w małych przedziałach to się nie zdarza nigdy. Dlatego ja wybrałem <2, 7>. Przedział <2, 11> jest też ok ale powoli już można się dopatrzeć prostych linii. Jest parę metod które ten błąd naprawiają ale ja ich tutaj nie zaimlementowałem bo nie wiem jak działają.

 

Jednakże żeby stworzyć pozór większej różnorodności przy tylko 12 dostępnych patternów postanowiłem że przemieszczę punkty jeszcze przez losowy offset.

Całość daje niezłe wrażenie losowości.

 

Zastosowania:

Halton sequence najczęściej jest stosowany do symulowania deszczu. Ale spotyka się go także przy generatorach map, ja właśnie planuję wykorzystać halton sequence do generowania wysep.

 

Updated:

Download: HaltonSequenceV2

[Jakim]

No i cóżeś uczynił. Teraz będę nocami olewał moje obowiązki i szukał optymalnych stałych dla tego skryptu, dla którego wariancja jest największa przy stałej gęstości na stałą jednostkę obszaru :/.

 

A tak na serio: bez zaglądania do skryptu propsy.

 

PS Proste lokalne transformacje izometryczne pozwalają uniknąć efektu linearyzacji.

[I am Lord]

Ja jestem za słabym matematykiem żeby to rozbudować także jak potrafisz coś z tym zrobić to śmiało.

[Jakim]

Z przyjemnością, ale muszę trzymać się własnych priorytetów, bo za łatwo zbaczam z własnych torów ;).

[I am Lord]

Wpadłem na drobne udoskonalenie.

Można jeszcze dodać losowy startowy index do pętli która tworzy punkty

GML

// losowy startowy offset indexów

offI = irandom( 100000 );

GML

gNodeX = gMapW * halton_point( offI+i, xH );

gNodeY = gMapH * halton_point( offI+i, yH );

 

No i teraz mamy unikalny układ za każdym razem :D

[Threef]

No i teraz mamy unikalny układ za każdym razem :D

To wciąż tylko 100000 unikalnych układów! :twisted:

Ale cały pomysł ciekawy i spróbuję go użyć.

[I am Lord]

To wciąż tylko 100000 unikalnych układów! :twisted:

Ale cały pomysł ciekawy i spróbuję go użyć.

 

Nie bo 100000 * 12 * 640 * 480 :P

 

Tym ładnie można rozsiewać roślinność.

[Amaterasu]

Chytra rzecz!

Co się stanie, jeśli zamiast losować normalną liczbę, wylosujesz liczbę na podstawie rozkładu Gaussa?

[I am Lord]

Chytra rzecz!

Co się stanie, jeśli zamiast losować normalną liczbę, wylosujesz liczbę na podstawie rozkładu Gaussa?

Nie powinno być różnicy jako że liczba jest losowana tylko raz. Raz na przesunięcie w osi X raz w Y i raz na przesunięcie indexów.

 

Ale ciekawe rzeczy powstają gdy funkcji halton_point( i, p ) nie poda się liczby pierwszej a zwyczajną na którąś z osi.

[Jakim]

 

Generator pól do Farmer Frana? :D

 

Nie ma bata, trzeba zrobić demo z tego.