mein Battletree-Algo funktioniert nicht so wie er soll...

[yankee]

Hi @ll,

ich bin gerade dabei ein Programm zu schreiben, welches einen Battletree generiert. Also sowas:

Code:

Spieler1 \ Sieger1
          >---\
Spieler2 /     \
                \ Endsieger
                 ------
                /
Spieler3 \     /
          >---/
Spieler4 / Sieger2

Ich hoffe man kann aus der Grafik erkennen, was ich will. Weil das ziemlich viel zum posten wäre, habe ich einfach mal alles in den Anhang geschmissen. Das ist das volle Programm, welches ihr kompilieren könnt. Dann geht ihr auf "edit players", gibt in die Memo untereinander 2,4,8,16 (oder eine andere 2er-Potenz) Namen ein und klickt dann auf "generate basic tree". Dann schließt ihr das Fenster und befindet euch wieder im Hauptfenster, wo ihr auf "gen battletree" klickt. Dann wird der Battletree gezeichnet. Das sollte so aussehen, dass gaanz links (in meiner kleinen Grafik Spieler1,2,3,4) in der Reihenfolge angezeigt bekommt, wie ihr sei eingegeben habt. (Zur Sicherheit, falls ihr nicht kompilieren könnt/wollt ist auch ein Screenshot davon im Anhang). Das klappt aber nicht. Es kommt eine andere Reihenfolge. Ich bin jetzt meinen Algo ganz oft durchgegangen (Umain.pas: Button1Click und PaintPart), aber ich kann den Fehler einfach nicht finden.
Übrigens wird beim starten des Programms in dem Ordner, wo das Programm ist liegt ein Ordner "data" erstellt, in dem beim beenden der Baum als XML gespeichert wird. Bei starten wird diese Datei automatisch wieder geladen, so dass ihr nur einmal bei "edit players" was eingeben müsst, dann ist es drin und ihr könnt direkt auf "gen battletree" klicken.

Achso, ist alles in englisch, weil ich gerade in Amerika auf Schüleraustausch bin und das hier verwenden möchte.

EDIT: Code-Tags gesetzt, meine Grafik war vollkommen zerstört :-)

[tigerman33]

Hmm,

den Fehler konnte ich leider nicht finden, da ich keine Jedis hab. Aber was mir aufgefallen ist:
Warum benutzt du anstatt von FindExponent nicht einfach den Logarithmus? :gruebel:
x = ln(cnt)/ln(2)

[Der_Unwissende]

Hi,

Zitat:

Warum benutzt du anstatt von FindExponent nicht einfach den Logarithmus?
x = ln(cnt)/ln(2)

Oder einfach

Delphi-Quellcode:

x = log2(cnt)

(Unit Math)

Ansonsten liegt dein Fehler ganz einfach in der Rekursion. Spinn die mal auf einem Blatt Papier mit nicht all zu großem Baum (4 Elemente) durch, dann siehst du schon wo der Fehler kommt.
Kann dir echt nur raten das ganze Iterativ zu lösen. Rekursion scheint häufig einfacher, aber wenn du nicht gerade eine Funktionale Sprache benutzt zahlt sie sich so gut wie nie aus. Also definitiv nicht hier :wink:
Wenn du sehen möchtest was du tolles mit Rekursion erreichen kannst, leg mal den Baum ohne Eingabe von einem Namen an, aber auch ein genügend großer Baum würde deinen Stack recht schnell füllen.

Also versuch mal den Algorithmus mit while zu realisieren,
Viel Spaß

Gruß Der Unwissende

[yankee]

tja, warum ich kein log. verwendet habe hat einen ziemlich plausiblen Grund: Ich habe mich zwar daran erinnert, das man sowas errechnen kann, aber ich hatte nichtmehr erinnert wie und log habe ich vollkommen verdrängt. Ich habe also im Internet gesucht und ein paar Leute in meinem Umkreis gefragt, aber keiner wusste das. Nur im Internet habe ich jemand gefunden, der es per Trial and Error vorgeschlagen hatte und dann habe ich mir eben einfach gesagt "was soll's". Also danke für den Hinweis.

Ich habe übrigens als aller erstes versucht das ganze iterativ zu lösen. Ich bin damit aber nicht sonderlich weit gekommen und dann habe ich mir gesagt "was solls, es gibt warscheinlich kein besseres Beispiel für einen Rekursiven Algo, mach's einfach neu". Und man hat schließlich nur log2(spieleranzahl) Rekursionslevel. Also selbst bei 1024 Spielern (und das könnte kein Ottonormalverbraucherbildschirm mehr anzeigen) nur 10 Rekursionslevel und das sollte den Stack hoffentlich nicht überlasten (*an ein paar Programme denk', die rekursiv die ganze Dateistruktur einer Platte durchsuchen*). Wie groß ist der Stack denn btw?

Ich habe übrigens das Problem gefunden. Aber eine Lösung habe ich immrnoch nicht. Und zwar habe ich ein loggingfeature eingefügt. Das ist die Logdatei von 8 Spielern:

Code:

[20:48:21, 2] generate Battletree
[20:48:21, 3] using parameters: cnt=8 exponent=3 vchange=120 hchange=180 newx=576 newy=250
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=120 hchange=180 newx=540 newy=130 level=2
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=60 hchange=180 newx=360 newy=70 level=1
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=30 hchange=180 newx=180 newy=40 level=0
[20:48:21, 3] Spieler1
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=-30 hchange=180 newx=180 newy=100 level=0
[20:48:21, 3] Spieler2
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=-60 hchange=180 newx=360 newy=190 level=1
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=-30 hchange=180 newx=180 newy=220 level=0
[20:48:21, 3] Spieler3
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=30 hchange=180 newx=180 newy=160 level=0
[20:48:21, 3] Spieler4
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=-120 hchange=180 newx=540 newy=370 level=2
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=-60 hchange=180 newx=360 newy=430 level=1
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=-30 hchange=180 newx=180 newy=460 level=0
[20:48:21, 3] Spieler5
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=30 hchange=180 newx=180 newy=400 level=0
[20:48:21, 3] Spieler6
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=60 hchange=180 newx=360 newy=310 level=1
[20:48:21, 3] PaintPart running with parameters: direction=topround vchange=30 hchange=180 newx=180 newy=280 level=0
[20:48:21, 3] Spieler7
[20:48:21, 3] PaintPart running with parameters: direction=bottomround vchange=-30 hchange=180 newx=180 newy=340 level=0
[20:48:21, 3] Spieler8

Der gibt jedes mal, wenn PaintPart aufgerufen wird (die erste Zeile ist aus Button1Click), aus, ob er nach unten oder oben zeichnen soll und die Parameter mit denen er aufgerufen wurde. Dann schiebt er noch schnell die Beschriftung, die er ausgeben soll hinterher, wenn er eine erstellen soll. Als erstes ist mir aufgefallen, dann die Reihenfolge richtig ist... Ganz schön verzwickt. Beim näheren überlegen habe ich mir überlegt, dass jede topround einen positiven vchange-Wert haben sollte und jede bottomround einen netagtiven. Das ist aber genau der Fehler.
.... mh, wo ich gerade so tippe, fällt mir eine mögliche Lösung ein. Moment, das teste ich gerade mal, ich editiere gleich...

EDIT:
Ha, tatsächlich. Ich habe jetzt in PaintPart den Rekursionsaufruf folgendermaßen abgeändert und es funzt!:

Delphi-Quellcode:

PaintPart(xml.Items.ItemNamed['topround'],newx, newy, hchange, abs(vchange div 2), level -1); //draw lines to the top...
        PaintPart(xml.Items.ItemNamed['bottomround'],newx, newy, hchange, abs(vchange div 2)*-1, level -1); //..and to the bottom

also das mit dem abs() ist neu.

Danke für eure Denkanregungen und den Hinweis auf log!!
:-D