Sierpinski-Teppich als Bildschirmschoner

Code-Stücke können hier veröffentlicht werden.
Antworten
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Hallo mal wieder :D ,
ich habe einen Sierpinski-Teppich (https://de.wikipedia.org/wiki/Sierpinski-Teppich), dem man beim Rendern zusehen kann und mit zufälligen Einflüssen mit Tkinter und Python3 geschrieben. Viel Spaß damit, Kritik ist erwünscht.

Code: Alles auswählen

import tkinter as tk
from itertools import product
from random import choice, randint, shuffle
from time import sleep

def random_farbe():
    return "#"+"".join(choice("123456789ABCDEF") for _ in range(6))

fenster = tk.Tk()
min_rechteck_groesse = 10
tiefe = 4
fenster_groesse = min_rechteck_groesse * 3**tiefe
canvas = tk.Canvas(master=fenster, width=fenster_groesse, height=fenster_groesse)

def teppich(groesse=fenster_groesse, verschiebung_x=0, verschiebung_y=0):
    fenster.update()
    sleep(.001)
    if groesse<min_rechteck_groesse: return
    canvas.create_rectangle(verschiebung_x+groesse/3,#+randint(-10,10),
                            verschiebung_y+groesse/3,#+randint(-10,10),
                            verschiebung_x+2/3*groesse,#+randint(-10,10),
                            verschiebung_y+2/3*groesse,#+randint(-10,10),
                            fill=random_farbe(),
                            width=0)
    unterbereiche = list(product((0, groesse/3, 2/3*groesse),(0, groesse/3, 2/3*groesse)))
    shuffle(unterbereiche)
    for vx, vy in unterbereiche:
        if not vx==vy==groesse/3:
            teppich(groesse/3, verschiebung_x+vx, verschiebung_y+vy)

canvas.pack()
while True:
    canvas["bg"] = random_farbe()
    canvas.delete("all")
    teppich()
    sleep(3)
E: z.B.
Bild
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: `sleep()` verwenden und keine `mainloop()` aufrufen ist halt unsauber. Das könnte man mit einer rekursiven Generatorfunktion lösen, die die Koordinaten liefert und `after()`/`after_idle()` um dann von der GUI-Hauptschleife aus die Koordinaten zu holen und anzuzeigen. Dann wäre die Logik auch von der GUI getrennt und man könnte die gleiche Generatorfunktion auch für andere GUI-Rahmenwerke, oder vielleicht sogar für `curses` verwenden.
BlackJack

Mal eine Variante mit `mainloop()` und Geschäftslogik (generieren der Quadrat-Daten) und Zeichnen getrennt:

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
import Tkinter as tk
from itertools import product
from random import choice, shuffle

MIN_SQUARE_SIZE = 10
DEPTH = 4
CANVAS_SIZE = MIN_SQUARE_SIZE * 3**DEPTH


def random_colour():
    return '#' + ''.join(choice('0123456789ABCDEF') for _ in range(6))


def iter_sierpinsky_carpet_squares(size=CANVAS_SIZE, x_offset=0, y_offset=0):
    if size >= MIN_SQUARE_SIZE:
        one_third = size / 3
        two_thirds = 2 * one_third
        yield x_offset + one_third, y_offset + one_third, one_third
        coordinates = list(product((0, one_third, two_thirds), repeat=2))
        shuffle(coordinates)
        for x, y in coordinates:
            if not x == y == one_third:
                for square in iter_sierpinsky_carpet_squares(
                    one_third, x_offset + x, y_offset + y
                ):
                    yield square


def draw_square(canvas, squares):
    try:
        x, y, size = next(squares)
    except StopIteration:
        canvas.after(3000, draw_sierpinsky_carpet, canvas)
    else:
        canvas.create_rectangle(
            x, y, x + size, y + size,
            fill=random_colour(),
            width=0,
        )
        canvas.after(10, draw_square, canvas, squares)


def draw_sierpinsky_carpet(canvas):
    canvas['background'] = random_colour()
    canvas.delete(tk.ALL)
    canvas.after_idle(draw_square, canvas, iter_sierpinsky_carpet_squares())


def main():
    root = tk.Tk()
    root.title('Sierpinski Carpet')
    canvas = tk.Canvas(root, width=CANVAS_SIZE, height=CANVAS_SIZE)
    canvas.pack()
    draw_sierpinsky_carpet(canvas)
    root.mainloop()


if __name__ == '__main__':
    main()
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Da fällt mir grade ein winziger "Fehler" in random_farbe auf. Da kann kein Schwarz generiert werden, weil in dem String die 0 fehlt. In diesem Fall ist das aber wohl nicht tragisch, weil es ohne dunkle Farben vermutlich besser aussieht.
PS: Die angebotene Summe ist beachtlich.
BlackJack

Ups :oops:, den Fehler hatte ich doch glatt übernommen. Und dann habe ich gleich mal das Assembler-Programm (für DOS) überprüft das ich gerade schreibe, ob das schwarz kann (→ ja). Es malt grundsätzlich schon mal das Teppichmuster und bricht ab wenn der Benutzer eine Taste drückt. Allerdings ist noch keine Pause drin wenn das Muster komplett ist.
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Code: Alles auswählen

from itertools import product
VERSCHIEBUNGEN = [(vx,vy) for vx,vy in product([0,1/3,2/3], repeat=2) if not vx==vy==1/3]
def erzeuge_teppich(tiefe):
    "Erzeugt Sierpinski-Teppich als Iterator von Rechtecken (x1, y1, x2, y2)"
    yield (1/3, 1/3, 2/3, 2/3)
    if tiefe > 1:
        unterteppich = [[koord/3 for koord in rechteck] for rechteck in erzeuge_teppich(tiefe-1)]
        for vx, vy in VERSCHIEBUNGEN:
            for x1, y1, x2, y2 in unterteppich:
                yield (x1+vx, y1+vy, x2+vx, y2+vy)
print list(erzeuge_teppich(2))
PS: Die angebotene Summe ist beachtlich.
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

@Blackjack: Assembler? Dir ist arg langweilig am Wochenende, was? :mrgreen:
Ich mag übrigens, dass du die Quadrate als (x1, y1, groesse) speicherst, auf die Idee war ich nicht gekommen.
Wenn man die Berechnung der Quadrate des Teppichs schon von der Gui entkoppelt, muss man den Offset auch nicht mehr als Parameter übergeben und kann stattdessen immer nur 1 rekursiven Aufruf machen und das Ergebnis dann an 8 verschiedene Stellen verschieben.

Code: Alles auswählen

from itertools import product
VERSCHIEBUNGEN = [(vx,vy) for vx,vy in product([0,1/3,2/3], repeat=2) if not vx==vy==1/3]
def erzeuge_teppich(tiefe):
    "Erzeugt Sierpinski-Teppich als Iterator von Quadraten (x1, y1, groesse)"
    yield (1/3, 1/3, 1/3)
    if tiefe > 1:
        unterteppich = [[koord/3 for koord in rechteck] for rechteck in erzeuge_teppich(tiefe-1)]
        for vx, vy in VERSCHIEBUNGEN:
            for x1, y1, groesse in unterteppich:
                yield (x1+vx, y1+vy, groesse)
print len(list(erzeuge_teppich(3)))
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: Langeweile? Dann erzähle ich lieber nicht womit ich mich dieses Wochenende noch so beschäftigt habe. :-)

Mir fiel bei dem Teppich nur auf, das ich auf dem PC noch nie was rekursives in Assembler geschrieben habe. Das war eine Lücke die ich unbedingt füllen musste. :-) In reinem Assembler verwende ich normalerweise auch nicht den Stack zur Parameterübergabe oder für lokale Variablen. Zu langsam und zu kompliziert. ;-)

Das mit den ”relativen” Grössen ist eine gute Idee, lässt sich aber nicht so leicht auf die Assembler-Lösung übertragen weil ich da mit ganzen Zahlen operiere. Dafür habe ich keine Tiefe bei den aufrufen. Abbruchbedingung ist das die Grösse kleiner als ein Pixel wird — dann macht das zeichnen keinen Sinn mehr. :-)

Jetzt wo das Programm an sich fertig ist und gerade mal knapp unter 300 Bytes gross ist, überlege ich ob da nicht noch irgendwas fehlt. Noch ein Effekt oder zumindest ein bisschen Grafik/ein Logo. Bei 320×200 Pixeln ist der Teppich 200 Pixel breit, also sind links und rechts 60 Pixel breite schwarze Streifen.
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Leg doch noch fallende Schneeflocken darüber :3

Das hat zwar gar nichts mit dem Sierpinskiteppich zu tun, sieht aber sicher gut aus.
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: Hm, ich hatte auch schon an ein ”star field” gedacht, aber Schnee ist ja um Grunde der gleiche Effekt bloss um 90° gedreht. Allerdings müsste ich dann die Grafik puffern, denn ich weiss nicht ob die Rechenzeit ausreicht um das sonst ohne flackern hin zu bekommen. Irgendwas innerhalb des grossen, mittigen Quadrats und/oder an den Seiten und/oder etwas was nicht über den gesamten Bildschirm geht, wäre wahrscheinlich leichter umzusetzen. :-)
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Code: Alles auswählen

import tkinter as tk
from itertools import product
from time import sleep
from random import choice, shuffle

VERSCHIEBUNGEN = [(vx,vy) for vx,vy in product([0,1/3,2/3], repeat=2) if not vx==vy==1/3]
FENSTER_GROESSE = 900

def erzeuge_teppich(tiefe):
    "Erzeugt Sierpinski-Teppich als Iterator von Quadraten (x1, y1, groesse)"
    yield (1/3, 1/3, 1/3)
    if tiefe > 1:
        unterteppich = [[koord/3 for koord in rechteck] for rechteck in erzeuge_teppich(tiefe-1)]
        for vx, vy in VERSCHIEBUNGEN:
            for x1, y1, groesse in unterteppich:
                yield (x1+vx, y1+vy, groesse)

def random_farbe():
    return "#"+"".join(choice("123456789ABCDEF") for _ in range(6))

teppich = list(erzeuge_teppich(5))

if __name__ == "__main__":
    fenster = tk.Tk()
    fenster.title("LSD-Sierpinski-Teppich")
    canvas = tk.Canvas(master=fenster, width=FENSTER_GROESSE, height=FENSTER_GROESSE)
    canvas.pack()
    while True:
        canvas["bg"] = random_farbe()
        canvas.delete("all")
        shuffle(teppich)
        for x1, y1, groesse in teppich:
            canvas.create_rectangle(x1*FENSTER_GROESSE, y1*FENSTER_GROESSE, (x1+groesse)*FENSTER_GROESSE, (y1+groesse)*FENSTER_GROESSE,
                                    width=0, fill=random_farbe())
            fenster.update()
            sleep(.001)
        sleep(3)
Der Teppich wird jetzt einmal errechnet und danach immer wieder gezeichnet.

Sichtbare Änderung: Jetzt werden die Quadrate in wirklich zufälliger Reihenfolge gezeichnet, also nicht jeder Bereich einzeln .. falls man ferstet was ich meine :mrgreen:

Ich bin bei sleep und update geblieben, weil ich das mit after nicht gut finde. Wenn ich alles aus einer Liste zeichnen soll, ist ne Schleife die offensichtlichste Lösung, und ich will mich nicht von Tkinter in die Rekursion zwingen lassen, oder gehts auch irgendwie anders?

Lg
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: `after()` ist keine Rekursion! `sleep()` und `update()` sind halt technisch die schlechtere Lösung weil Du die GUI-Hauptschleife an Dich reisst. Das kann nur einer machen, und Du bestimmst ausserdem, dass alle anderen Beteiligten immer Deine `sleep()`-Zeiten abwarten müssen. Also zum Beispiel auch der Benutzer eine jedes mal für drei Sekunden einfrierende GUI hat wenn ein Teppich fertig ist. In der Zeit wird potentiell die Anzeige nicht neu gezeichnet wenn man das Fenster mal aus dem sichtbaren Bereich und zurück verschiebt und die Anwendung reagiert erst nach Ablauf der drei Sekunden auf Aktionen wie das Schliessen des Fensters.
BlackJack

Hier wäre meine Assemblerlösung für DOS die sich mit NASM übersetzen lässt (``nasm -fbin -o scarpet.com scarpet.asm``):
[codebox=asm file=Unbenannt.asm] cpu 386
org 0x0100
[map all]
;-------------------------------------------------------------------------

SCREEN_WIDTH equ 320
CARPET_SIZE equ 200

segment .bss
key_pressed:
resb 1

segment .text

start:
xor ax, ax
mov [key_pressed], al
int 0x1a ; Return the BIOS tick count in CX:DX.
mov [random.random_state], dx

mov ax, 0x0013 ; MCGA mode 320x200 256 colors.
int 0x10

mov ax, 0xa000 ; ES = video memory segment.
mov es, ax

.mainloop:
call random_color ; Fill carpet area with random color.
mov cl, al
xor ax, ax
xor di, di
mov bx, CARPET_SIZE
call draw_square

mov ax, CARPET_SIZE ; draw_carpet(CARPET_SIZE, 0, 0)
push ax
xor ax, ax
push ax
push ax
call draw_carpet

mov cx, 250 ; Wait some frames and then start over.
.waitloop:
call wait_for_retrace_and_keypress
cmp byte [key_pressed], 0
jne .exit_mainloop
loop .waitloop

jmp .mainloop

.exit_mainloop:
mov ah, 0 ; Remove pressed key from buffer.
int 0x16

mov ax, 0x0003 ; Textmode.
int 0x10

mov ax, 0x4c00 ; AL = exit code.
int 0x21


;-------------------------------------------------------------------------
; Recursively draw the sierpinsky carpet.
;
; Return when all squares are printed or the user pressed a key.
;
; stack input:
; size:word size of the square
; x_offset:word x coordinate of upper left corner
; y_offset:word y coordinate of upper left corner
;
; out:
; key_pressed:byte set to 1 if the user pressed a key. The key
; info is not removed from the keyboard buffer!
;-------------------------------------------------------------------------
draw_carpet:

%define size bp+8
%define x_offset bp+6
%define y_offset bp+4

%define one_third bp-2 ; 1/3 of the size (word)
%define two_thirds bp-4 ; 2/3 of the size (word)
%define zero bp-6 ; a zero (word)
; These local values are also used as an array that is looped over with
; two nested loops to determine the sizes and offsets of the recursively
; drawn squares at each step.

%define locals_size 6

push bp
mov bp, sp
sub sp, locals_size

xor ax, ax ; zero := 0
mov [zero], ax

mov ax, [size] ; one_third := size / 3
mov dx, 3
div dl
or al, al
jz .finished
xor ah, ah
mov [one_third], ax

shl ax, 1 ; two_thirds := one_third * 2
mov [two_thirds], ax

; Check for keyboard, wait for retrace, and return early if a key was
; pressed.
;
; TODO A really fast exit via restoring the stack pointer from before
; the first call to the recursive function would be nice.
;
call wait_for_retrace_and_keypress
cmp byte [key_pressed], 0
jne .finished

call random_color ; Get a random color and draw the current square.
mov cl, al
mov bx, [one_third]
mov di, [x_offset]
add di, bx
mov ax, [y_offset]
add ax, bx
call draw_square

mov di, 4 ; Nested loop with DI and SI as loop variables
.outer: ; and offsets into the local array starting at
mov si, 4 ; variable 'zero'.
.inner:
cmp di, si ; If both offsets are equal and adressing the
jne .not_equal ; last array element 'one_third', it is the
cmp di, 4 ; middle square, which doesn't need a recursion.
je .middle_square
.not_equal:

push di ; draw_carpet(one_third, word zero[DI], word zero[SI])
push si

mov ax, [one_third]
push ax
mov ax, [x_offset]
add ax, [zero+di]
push ax
mov ax, [y_offset]
add ax, [zero+si]
push ax
call draw_carpet

pop si
pop di
.middle_square:
sub si, 2
jnc .inner
sub di, 2
jnc .outer

.finished:
mov sp, bp
pop bp
ret locals_size


;-------------------------------------------------------------------------
; Wait for the VGA card to start a new frame and check for a key press
; from the user.
;
; in: -
; out: key_pressed:byte set to 1 if a key was pressed. The key info
; is *not* removed from the keyboard buffer!
;-------------------------------------------------------------------------
wait_for_retrace_and_keypress:
mov ah, 0x01 ; Peek keyboard buffer.
int 0x16
jz .skip_to_retrace
mov byte [key_pressed], 1

.skip_to_retrace
mov dx, 0x3da ; Wait for retrace.
.L1:
in al, dx
test al, 0x08
jnz .L1
.L2:
in al, dx
test al, 0x08
jz .L2
ret


;-------------------------------------------------------------------------
; Draw a square with a given color.
;
; in: AX y
; DI x
; BX side length
; CL color
; ES segment of the video memory
; uses: AX BX CX SI DI
;-------------------------------------------------------------------------
draw_square:
mov dx, SCREEN_WIDTH ; DX = offset from the end of a line to the start
sub dx, bx ; of the next.
push dx

mov dx, SCREEN_WIDTH ; DI = offset of first pixel to draw.
mul dx
add di, ax
add di, (SCREEN_WIDTH - CARPET_SIZE) / 2

mov al, cl ; Draw the box line by line.
mov si, bx
pop dx
.line_loop:
mov cx, si
rep stosb
add di, dx
dec bx
jnz .line_loop
ret


;-------------------------------------------------------------------------
; Return a random color from the VGA standard palette's "rainbow" section.
; That is a value from 32..248 (=216 colors.).
;
; in: -
; out: AL result
; uses: AX, DL
;-------------------------------------------------------------------------
random_color:
call random
and ah, 0x7f
mov dl, 216
div dl
mov al, ah
add al, 32
ret


;-------------------------------------------------------------------------
; Return a pseudo-random number between 0 and 0xffff.
;
; in: -
; out: AX result
; uses: EAX
;-------------------------------------------------------------------------
random:

segment .data
.random_state:
dd 1
db 0

segment .text
mov eax, [.random_state]
add eax, [.random_state+1]
add eax, 0x31415927
mov [.random_state], eax
shr eax, 8
ret[/code]
Üpsilon
User
Beiträge: 222
Registriert: Samstag 15. September 2012, 19:23

Boah :O

Aber um mal auf das Ding mit after zurückzukommen: Ja, mir ist auch schon aufgefallen, dass das Programm in den 3 Sekunden ein bisschen rumspastet. Kann man aber doch sicher umgehen:

Code: Alles auswählen

for _ in range(30):
    sleep(.1)
    fenster.update()
:mrgreen: :mrgreen: :mrgreen:
Wenn man after nutzt, macht man eine Funktion, die sich am Ende selbst aufruft. So wie ich das gelernt habe, nennt man das Rekursion. Mag sein, dass das auf technischer Ebene kein normaler Funktionsaufruf ist, aber es sieht aus wie einer ... ist ja auch wurscht. Gibts evtl noch ne andere Möglichkeit, bei der man "die Hauptschleife nicht an sich reißt"?
PS: Die angebotene Summe ist beachtlich.
BlackJack

@Üpsilon: Bei `after()` ruft sich die Funktion nicht selbst auf sondern sagt ihrem Aufrufer sie möge doch bitte später von ihm erneut aufgerufen werden. Das ist IMHO keine Rekursion weil der Funktionsaufruf ja zurückkehrt bevor der nächste kommt. Bei einer Rekursion ruft sich eine Funktion direkt, oder auch indirekt, mehrfach zur gleichen Zeit auf, das heisst es sind immer noch Aufrufe aktiv und noch nicht zu ende abgearbeitet wenn sie erneut aufgerufen wird.
Pygoscelis papua
User
Beiträge: 206
Registriert: Freitag 13. März 2015, 18:36

@BlackJack Ich hatte mich auch schon mal nur so ganz wenig mit Assembler beschäftigt.
Hast du einen Tipp wo und wie ich das am besten lernen kann?
32bit oder 64bit??
Ich hatte aus irgendeinem Grund immer Probleme mit 64bit.

Ich hoffe meine Frage hat jetzt nicht zu sehr den Rahmen gesprengt.
import this
hidden python features

JAVA = Just Another Vulnerability Announcement :D
BlackJack

@Pygoscelis papua: Ich kann jetzt keine spezielle Quelle nennen, aber das Netz ist voll von Einführungen zu allen möglichen Prozessoren.

Warum willst Du es denn lernen? Ich denke wenn man aus tatsächlich praktischen Gründen für aktuelle PCs Assembler lernen will, dann muss man schon *sehr* tief in die Materie einsteigen. Also nicht nur der Befehlssatz selber sondern auch alle möglichen Hardwareeigenheiten des Systems und des jeweiligen Prozessors. Denn wenn man nicht deutlich besser als ein guter Compiler ist, macht es nicht wirklich Sinn auf diese Ebene runter zu gehen. Das war zu Turbo/Borland Pascal-Zeiten noch einfach besseren Assemblercode als der Compiler zu schreiben (also zumindest bei Turbo/Borland Pascal).

Wenn es nur darum geht mal einen Prozessor nahezu direkt zu programmieren, ist das mit den Bits ja fast egal. Da kann man sich auch einen 8-Bit-Prozessor wie den 6502 (oder einen kompatiblen) oder einen Z80 hernehmen. Oder x86-16-Bit-Programme für DOS zu schreiben, wie das was ich weiter oben gemacht habe. Diese Varianten haben den Vorteil das die Prozessoren/Systeme/Betriebssysteme noch relativ einfach sind und auch sehr gut dokumentiert, weil da schon Generationen von Programmierern dran gesessen haben. Und auch ganze Programme ausschliesslich in Assembler dafür programmiert haben. Das lässt sich dann mittels Emulatoren und Cross-Assemblern auch recht einfach auf aktuellen Systemen programmieren und austesten.
Pygoscelis papua
User
Beiträge: 206
Registriert: Freitag 13. März 2015, 18:36

BlackJack hat geschrieben: Warum willst Du es denn lernen?
Eigentlich eher nur zum Spaß, aber auch um es zu verstehen also aus Neugierde. Ich möchte zwar evtl. technische Informatik Studieren, aber ich bezweifle dass man dort wirklich oft Assembler einsetzt.

Ich werde mal mit Emulatoren etc. schauen.
import this
hidden python features

JAVA = Just Another Vulnerability Announcement :D
Antworten