| neue Message hinzufügen |

Kombination rusty 2010-12-29 17:26:33
Kürzen und Cache lassen sich ja auch kombinieren, dann werden halt weniger Einträge für die "Nachguck"-Tabelle gebraucht.

Übrigens kann man bei der Kürzungstechnik auch erst bei den seltenen grösseren Zugvektoren sparen.
bis [5,5] gibt es genau 6 kürzbare Vektoren
bis [10,10] sind es 37
bis [20,20] dann 145
Trivialfälle mit [x,0] oder [0,x] ausgenommen

Dafür holt man sich den "Overhead" der ggt-Berechnung, des Aneinanderlegens und muss weiterhin die Streckenverläufe errechnen. Überzeugt nicht so wirklich.
Davon abgesehen kann ich nicht erkennen was genau an vorberechneten Schritten unschön sein soll? Das wird doch allenthalben gemacht, von Rainbow-Tables bis zu vorberechneten Kosinustabellen in Spielen.

mfG Andreas

Oder abkuerzen kili 2010-12-29 11:44:49
Unabhaengig davon, ob man nun jedesmal rechnet, oder das Zeugs einmal im Voraus berechnet (finde ich etwas unelegant), kann man natuerlich das ganze noch etwas abkuerzen, in dem man den Vektor `kuerzt', also dx und dy durch den ggt(dx, dy) teilt. Die Deltas fuer die beruerhten Kaestchen wiederholt man dann ggt(dx, dy) mal. Ob's wirklich was bringt, habe ich nicht ausprobiert.

ps: mit ggt meine ich den groesten gemeinsamen Teiler, also

ggt(a, b) = a, wenn b = 0
ggt(a, b) = ggt(b, a),, wenn a < b
ggt(a, b) = ggt(b, a mod b) sonst

cache quabla 2010-12-29 11:16:15
macht Botrix natuerlich auch so.

Cache rusty 2010-12-29 10:45:18
Tag auch,

Ist vielleicht etwas spät, denn ich lese hier nicht mehr so wahnsinnig häufig im Forum. Aber, warum muss denn der Zugvektor überhaupt jedesmal berechnet werden? Ich würde die einmal berechnen, womit auch immer, irgendwo cachen und immer nur noch von da herholen.
Ich bin mir sogar sicher das damals bei meinem eigenen Bot auch so gemacht zu haben, zumindest alle Zugvarianten von [0,0] bis [20,20]. Alles andere kommt sowieso nicht vor, bzw. kann in den abstrusen Fällen dann mal algorithmisch berechnet werden. Aber sonst ist es doch sinnlos zig-hundertfach immer das Gleiche neu zu berechnen.

mfG Andreas

Alter Code... ultimate 2010-11-29 10:22:20
... habe den Code wie gesagt seit ca. 4 Jahren nicht mehr angefasst... Kann gut sein, dass sich da ein paar Probleme ergeben
Schön aber, dass ihr eine Lösung gefunden habt, die auch noch performant ist...

Aus dem Off Madeleine 2010-11-29 09:58:40
Die Berechnungen durchdringe ich eher nicht (müsste ich mich 'nen Tag lang dransetzen, schätze ich), aber ich find's klasse, wie hier mal produktive Zusammenarbeit demonstriert wird!

Der olle Bresenham Didi 2010-11-28 10:37:50

Sieh mal einer an... so ein 50 Jahre alter ALgorithmus kommt daher und gewinnt das Rennen...

Timing on 5000 loops, vector range (-100,100):

DIDI: 101.63142490387
QUABLA: 11.590938806534
QUABLA2: 11.903616905212
BRESENHAM: 5.9029719829559

Dass meine Implementierung voll abstinkt - nu, so isses...
Aber schön, dass sich alle immerhin mit dem Ergebnis einig sind!

Dann kann ich ja jetzt mal beruhigt weitermachen und den ollen Bresenham mit quablanischen Erweiterungen benutzen.

Danke an alle für die diversenen Implementierungen. Auf github hab ich die letzte Version hochgeladen, die ein bisschen übersichtlicher ist.

@Ultimate: Sieht hübsch aus, das Ding - wirft bei mir unter Win7 und aktuellem Java nur leider mit Exceptions um sich und funktioniert nicht wirklch. Schade

:)idi

Nachricht mit Code... ultimate 2010-11-26 22:16:35
... hast du meine Variante eigentlich bekommen Didi???

is ja ganz einfach mit dem github... quabla 2010-11-26 22:08:21
https://gist.github.com/717207

Rekordumständlich Calypso 2010-11-26 20:13:42
ist die folgende von mir in Visual Basic gefertigte Lösung:

' Zugzulässigkeit ermitteln
    'Gehe zu Startposition
    'Stop
    Range("A1").Select
    ActiveCell.Offset(py - 1, px - 1).Range("A1").Select
    ' Zug flach legen, daraus ergibt sich lange Richtung + kurze Richtung
    If Abs(vx) < Abs(vy) Then GoTo 90
    ' flach - lange Richtungen x und y
    lrx = vx / Abs(vx)
    lry = 0
    krx = 0
    ' waagrecht dann kry = 0
    If vy <> 0 Then kry = vy / Abs(vy) Else kry = 0
    GoTo 95

90
    ' Steil also vertauschen
    lry = vy / Abs(vy)
    lrx = 0
    kry = 0
    ' senkrecht dann krx = 0
    If vx <> 0 Then krx = vx / Abs(vx) Else krx = 0
    
95

    ' Superschleife
    ' Holla, keine max-Funktion in VBA und Steigung berechnen
    If Abs(vx) > Abs(vy) Then GoTo 110
    zl = Abs(vy)
    stg = Abs(vx) / Abs(vy)
    GoTo 120
110
    zl = Abs(vx)
    stg = Abs(vy) / Abs(vx)
120
    ' zwi 1/2 vor berechnen
    zwi = 0.5 + (0.5 * stg)
    
    For z = 1 To zl
    
    ' Rundungsfehler ausgleichen
    If Abs(1 - zwi) < 0.0001 And zwi <> 1 Then zwi = 1
    If zwi < 1 Then GoTo 150
    
    ' gehe steil
    ActiveCell.Offset(kry, krx).Range("A1").Select
    zwi = zwi - 1
    If zwi = 0 Then GoTo 150
    
    ' prüfe ob grün
    If ActiveCell.Interior.ColorIndex = 43 Then Stop
    
150
    ' gehe flach
    ActiveCell.Offset(lry, lrx).Range("A1").Select
    ' prüfe ob grün
    If ActiveCell.Interior.ColorIndex = 43 Then Stop
    
    ' zwi neu berechnen (Summierung zum alten Wert)
    zwi = zwi + stg
    Next z
' **** ende des Teils ****** ende des Teils ****** ende des Teils ******


Aber für einen Nicht-Programmierer doch auch nicht soo schlecht, oder?

modified Bresenham quabla 2010-11-26 15:58:13
Also zunaechst mal: Didi, dass sich die Ergebnisse unterscheiden, hast du selber reingebastelt - aus irgendeinem Grund laesst du meine Version ja nur 100 Zyklen machen. Is klar, dass das dann bei grossen Beispielen zu frueh abbricht, oder?
Wenn man die Beschraenkung rausnimmt, sind wir beide uns aber einig. Ist doch auch mal schoen :-)

Der Bresendingsbums funktioniert so nicht, er ist wohl dafuer ausgelegt, dass die Linien immer gleich breit sein sollen - ist ja auch beim Malen sinnvoll. Er gibt sich Muehe, die Linienbreite immer bei 1 zu halten. Das funktioniert aber fuer unsere Anforderungen nicht, denn eine ganze Reihe geschnittener Felder wird so unter den Tisch fallen gelassen.

Ich hab ein wenig dran gebastelt und eine Version erstellt, die das macht, was wir brauchen. Getestet bis zu Vektorlaengen von 1000 geben nun alle 3 Algorithmen das gleiche Ergebnis. Der Bresenham ist auch noch mal ein bisschen schneller:

Timing on 100000 loops:
Didi: 12.894659042358
Quabla: 3.8877940177917
Quabla Enhanced: 3.6832258701324
Gbham: 2.3782210350037

Den Code hab ich an Didi geschickt, dann kann er ihn auf dieses git-Dingens pappen. Is hier bisn unuebersichtlich.

Nachtrag 2 Didi 2010-11-26 10:00:50

Bei einem "realistischeren" Vergleich von Vektoren im Bereich von -5 bis 5 sieht's übrigens so aus:

Timing on 100000 loops:

Didi: 46.379055976868
Quabla: 14.747647047043
Quabla Enhanced: 14.179721832275


Wer macht den Brasenham? Würde mich ja jetzt doch mal interessieren

Nachtrag Didi 2010-11-26 09:54:43

Das kommt übrigens raus:

[.....]
All equal on (-8|-5)
All equal on (-1|6)
All equal on (3|-20)
All equal on (4|-5)
All equal on (-2|-14)
All equal on (14|-12)
All equal on (16|-4)

Timing bei 5000 Berechnungen:

Didi: 12.305481910706
Quabla: 2.3561849594116
Quabla Enhanced: 2.2586059570312

Sooodele Didi 2010-11-26 09:50:50

Aktueller Status:

Ich hab zumindest Quablas Algorithmus mal verstanden und implementiert. Und der scheint gar nich so doof zu sein. Der Algorithmus zumindest, Quabla schon, weil der steht immer im Weg - aber das ist ein anderes Thema.

Jedenfalls, im "einfachen" Vergleich von Zufallsvektoren im Bereich x u. -20 bis 20 sind sich meiner und Quablas einig.
Sobald ich ihn von -100 bis 100 rechnen lasse, gibt's differenzen. Ich vermute mal eher, dass mein ALgorithmus dabei wirklich Felder überspringt, wie ich weiter unten schon vermutet habe... glauben wir mal dem Quabla

Ich hab mein aktuelles Testscript mal auf github hochgeladen, da sieht man dann auch nen schönen Geschwindigkeitsvergleich... auch mit dem "Optimierten Quabla", der die angesprochenen Sonderfälle vorher auflöst. Der Zeitgewinn ist minimal, aber vorhanden

Was den Brasenham betrifft:
Ich bin über den schon drüber gestolpert, hab ihn ebenfalls kurz angeschaut, nicht verstanden und ignoriert ;-)
Wenn jemand ne passende Implementierung liefren will - bitte, dann darf er beim Wettrennen gerne mitmachen

:)idi

Spielverderber! quabla 2010-11-26 07:05:23

Bresenham ulli 2010-11-25 23:00:10
Hallo Didi,

das Problem wie man die überquerten Punkte von A nach B berechnet wurde bereits 1962 von einem Herr Bresenham gelöst (siehe Bresenham-Algorithmus). Da findest du auch Beispielcode. Vielleicht hilfts.

Gruß
Ulli

brainfuck quabla 2010-11-25 22:57:55
Puh - von haskell wusste ich bisher bloss, dass es das gibt. Sieht ja gaaanz anders aus....

Didi: ich hab's dir nochmal nach php umformuliert:
  public function getPassedVectors_quabla()
  {
    $rowvector=$this->getY();
    $colvector=$this->getX();
    
    $points=array();
    $v=new Vector(0,0);
    $points[$v->__toString()]=$v;

    $sx = ($colvector < 0 ? -1 : 1);
    $sy = ($rowvector < 0 ? -1 : 1);
    $colvector = ($sx < 0 ?  - $colvector :  $colvector);
    $rowvector = ($sy < 0 ?  - $rowvector :  $rowvector);

    $vec = ($colvector != 0 ? $rowvector/$colvector : 99999);

    $vx1 = 0;
    $vy1 = 0;
    do {
      $v=(($vy1 + 0.5)/($vx1 + 0.5));
      $vx1 = ($v >= $vec ? $vx1 + 1 : $vx1);
      $vy1 = ($v <= $vec ? $vy1 + 1 : $vy1);
      $v=new Vector($sx*$vx1,$sy*$vy1);
      $points[$v->__toString()]=$v;
    } while (($vx1 != $colvector) || ($vy1 != $rowvector));
    return $points;
  }

[offtopic] Steht doch da... kili 2010-11-25 21:27:54
`Never use tabulations'

Ich habe doch nicht genoergelt, weil Du keine 8er-Einrueckung benuntzt, sondern weil du keine 8er-Einrueckung aber z.T. trotzdem Tabs fuer die Einrueckung benutzt. Und vermutlich ist die Anzeigebreite fuer Tabs (hat nichts mit der Einruechungstiefe zu tun) in Deinem Editor auf etwas anderes als 8 gesetzt.

Z.B. ab Zeile 107 in dem von Dir gepasteten Code wird's echt merkwuerdig.

Was ich meine, ist der `ts'-Parameter im vi(1) (im Gegensatz zum `sw'-Parameter) oder die Option `-x' in less(1). Sowas wie `sw' kann und sollte jeder nach seinem Geschmack oder den von der Steilpolizei vorgegebenen Richtlinien einstellen, aber `ts' sollte immer auf 8 gesetzt bleiben.

So, und jetzt schraube ich weiter an einem PHP-dreizeiler fuer den Zugberechnungsalgorithmus ;-)

Das tut mir leid, kili... Didi 2010-11-25 20:54:48
...

aber:

http://trac.symfony-project.org/wiki/HowToContributeToSymfony#CodingStandards

Und da ich nun mal ein Symfony-Anhänger bin...

Bin gerade am einbauen und muss feststellen, dass es "im ersten Schritt" ein toller Algorithmus ist, um nen kurzen Weg zu finden, aber nicht alle Felder...

*weiterbastel*

Auf jeden Fall.... kili 2010-11-25 20:25:54
koennen wir ja massenhaft Testvektoren mit diversen Implementierungen testen.

Wenn da ueberall das gleich rausplumpst, wird's schon stimmen (oder wie sind alle gleich-doof).

Didi: wenn moeglich (und falls Du ueberhaupt vorhast, Deine Loesung zu veroeffentlichen), dann achte doch bitte darauf, dass Du entweder gar keine Tabs zum Einruecken benutzt, oder 8er-Tabs. Das Ding auf https://gist.github.com/715148 ist naemlich echt augenunfreundlich.

Durchwurmen! Didi 2010-11-25 20:07:32

Also mal abgesehen davon, dass ich kein Haskell oder Scalar kann und mein Perl so lange zurückliegt, kam mein Hirn jetzt mit folgender Lösung auf mich zu (und ich weiß nicht, ob das von Quabla inspiriert ist oder nicht).

Ich beschreib's mal: Es heißt "Durchwurmen"

Ansatz:
(Betrachten wir nur x>0 und y>0, der Rest lässt sich durch Vorzeichen-Umkehr einfach erzeugen
* Solange Zielvektor nicht erreicht, gehe immer ein Feld auf den Zielvektor zu.
* Die Steigung vom letzten Feld zum Zielvektor bestimmt, ob nach rechts, unten, oder diagonal rechts unten.

Ich werde das mal in PHP umsetzen und mit meinem aktuellen vergleichen.

Auch wenn das jetzt weiter unten genau vielleicht so da steht, dann hab ich's halt vorher nicht verstanden, did not compile ;-)


Bleibt evtl. noch zu prüfen, ob es sich lohnt, für die Sonderfälle x=0, y=0 und abs(x)=abs(y) (also waagrecht, senkrech, 45°) eine einfache for-next-Schleife vorzuschalten, da die ja recht einfach zu berechnen sind. Und nur alles andere wird "durchgewurmt"

:)idi


PS: Jetzt wo ich weiß, was ich kodieren will kann ich das, was ich vorhabe, vielleicht sogar in dem, was Quabla gepostet hat, erkennen...

So... kili 2010-11-25 19:23:53
Hier ist dann erstmal meine Haskell-Loesung (die liegt hier schon etliche Jahre

> module Steps(steps) where
> import Ratio
> import List
>
> -- We don't like a negative dx value. Negate, calculate, negate:
> sections dx dy | dx < 0 = [(-x, y) | (x, y) <- sections (-dx) dy]
>
> -- We don't like a negative dy value, either.
> sections dx dy | dy < 0 = [(x, -y) | (x, y) <- sections dx (-dy)]
>
> -- Slope should't be greater than 1. Flip, calculate, flip:
> sections dx dy | dx < dy = [(y, x) | (x, y) <- sections dy dx ]
>
> -- Get the sections with the grid lines, return a sorted list of step pairs.
> sections dx dy = [(x, f x) | x <- nub $ sort (vs ++ hs)] where
>     s = dy % dx -- Slope.
>     f x = 1%2 + (x - 1%2) * s -- Line shifted by 0.5/0.5
>     g y = 1%2 + (y - 1%2) / s -- Inversion of f
>     vs = [1 .. fromIntegral dx] -- vertical grid lines
>     hs = map g [1 .. fromIntegral dy] -- hor. grid lines
>
> -- We truncate the sections to get the final list of steps.
> steps dx dy = (0, 0) : [(f x, f y) | (x, y) <- sections dx dy] where f = truncate

Beispiel:
*Steps> steps 0 0
[(0,0)]
*Steps> steps 1 3
[(0,0),(0,1),(1,2),(1,3)]
*Steps> steps 3 3
[(0,0),(1,1),(2,2),(3,3)]
*Steps> steps 5 (-4)
[(0,0),(1,0),(1,-1),(2,-1),(2,-2),(3,-2),(3,-3),(4,-3),(4,-4),(5,-4)]

Ich glaube, das ist im Prinzip der Algorithmus, den quabla unten gepostet hat, allerdings arbeitet der niicht auf einem Quadrant des Koordinatenkreuzes, sondern nur auf der auf der `flachen' Haelfte, wo also die Steigung <= 1 ist. Mal sehen, ob ich das noch in PHP gegossen bekomme.

Fuer nicht-Haskeller:

- Eine Funktion kann durch mehrere Gleichungen definiert werden (wie `sections' oben). Die erste Gleichung, zu der die Argumente passen, wird genommen (pattern matching und/oder guards).

- Eine Funktionsgleichng wie `f x y z | cond = ...' matched genau dann, wenn `cond' true ist.

- Die Standardfunktion `nub' entfernt doppelte Elemente aus einer Liste.

- `%' ist nicht der Modulo-Operator, sondern baut aus zwei integralen Zahlen eine rationale Zahl (Zaehler % Nenner) zusammen.

- `truncate' rundet (u.a.) eine rationale Zahl nach unten in eine integrale Zahl ab.

Hmmm... Didi 2010-11-25 17:06:01

Aber trotzdem ließe der Algorithmus eben Pixel unbetrachtet, wenn ich das richtig sehe...

:)idi

Overkill... ultimate 2010-11-25 11:42:37
... es mag sein, dass man dadurch die Berechnung nicht unbedingt verringert, aber die Strecken können dafür optisch höchst Anspruchvoll sein. Man kann theoretisch sogar auf Fotos rumfahren...

... und da das ganze als Spiel mit lokalem Multiplayer oder bei Online-Funktion mit Java-Client gedacht war, kann man viele der Berechnungen natürlich auf dem Client ausführen...

Ok... Didi 2010-11-25 11:02:56

Dann mal los:

@quabla: OK, glaub ich Dir, dass meins nich schnell is - aber es tut.
@ultimate: Klingt auch nett -aber irgendwie nach Overkill, oder nicht?

Ich hab unter https://gist.github.com/715148 mal einen lauffähigen Testcase erzeugt.
Das lässt sich ausführen und sagt Dir, ob's passt oder nicht.

Und wenn mir das jemand performanter umschreibt, sag ich brav danke :D

:)idi

| neue Message hinzufügen |
| Anfang | Vorherige | Nächste |

Brought to you by Didi

Letzter Satz im Chat:
Kev (19:05): @Grmpf: Hier ganz exotisch: Rechtswissenschaft :)