Seite 10 von 16

Verfasst: Samstag 9. August 2008, 13:57
von derkai
die Liste spiegelt die Entfernung aller Nachbarfelder eines Feldes X
zu einem Zielfeld wieder. Die Entfernungen belaufen sich auf fast 8 Stellen nach dem komma. Es dürfte nicht vorkommen, dass die Liste gleiche Entfernungen / Elemente enthält.

Habt Dank.

Ich werde Euch bald mal meine neuen Ideen zeigen können.

Kai

Verfasst: Samstag 9. August 2008, 14:59
von derkai
EyDu hat geschrieben:Einmal den Werte und einmal den Index:

Code: Alles auswählen

>>> l = [0.0, 0.0, 80.0, 120.0, 0.0, 0.0]
>>> min(x for x in l if x>0)
80.0
>>> min(i for (i,x) in enumerate(l) if x>0)
2
>>> 

das verstehe ich leider noch nicht :
min ( x for x in l if x > o)

grob übersetzt heisst das doch :
- for x in l
gehe die Liste Element für Element durch
- if x > 0
heisst das : nimm nur das Element, dass gößer null ist ???
- x
aber was macht das x vor dem for ???

Kai

Verfasst: Samstag 9. August 2008, 15:46
von EyDu
Ach, meine Variante mit den Indizes funktioniert gar nicht, das passt nur zufällig bei der Liste. Das hier sollte gehen:

Code: Alles auswählen

min([(i,x) for (i,x) in enumerate(l) if x>0], key=operator.itemgetter(1))
@derkai: Deine Ausführungen sind so weit schon richtig. Mit dem Ausdruck wird ein Generator erzeugt, das hat mit der min-Funktion erst mal nichts zu tun. Oben im Code ist das gleiche noch mal als list comprehension. Das "x" gibt an, was in die Liste mit aufgenommen wird, bzw. in den Generator.

@numerix: Wenn die Anforderung größer 0 lautet, dann gibt es keine Probleme ohne ein Epsilon. Außerdem lässt 0 sich richt gut binär darstellen ;-) Falsch ist allerdings in diesem Fall deine Verwendung von abs ;-)

Verfasst: Samstag 9. August 2008, 16:13
von numerix
EyDu hat geschrieben:@numerix: Wenn die Anforderung größer 0 lautet, dann gibt es keine Probleme ohne ein Epsilon. Außerdem lässt 0 sich richt gut binär darstellen ;-) Falsch ist allerdings in diesem Fall deine Verwendung von abs ;-)
Ja, die "Anforderungen". Fakt ist doch, dass hier Fließkommazahlen im Spiel sind und ich nicht weiß, wo die Nullen herkommen. Falls die mal bei irgendeiner Rechnung ausgepuckt wurden (und nur noch theoretisch 0 sind) nützt mir die "gute Binärdarstellung der Null" gar nichts, weil eben nicht mehr Null steht, wo Null stehen sollte. Insofern ist man mit eine "Unschärfeprüfung" immer auf der sicheren Seite.

Was an dem abs() falsch sein soll, sehe ich nicht. :?:

Verfasst: Samstag 9. August 2008, 16:39
von EyDu
Es macht einfach keinen Sinn in ein Problem mit so wenig Kontext etwas hineinzu interpretieren. Und mit Unschärfe ist man nicht immer auf der sicheren Seite: entstehen die Zahlen aus einer Multiplikation mit kleinen Zahlen und mit der Bedingung größer 0 willst du nur an das Vorzeichen ran, dann ist ein abs einfach falsch. Man kann sich also sonst was für Sonderfälle einfallen lassen.

Zu dem abs aus meinem letzten Thread:

Code: Alles auswählen

>>> alt = [0.0, 0.0, 80.0, 120.0, -40.0, 0.0]
>>> neu = sorted(list(set(alt)))
>>> mini = neu[0] if abs(neu[0])>0.001 else neu[1]
>>> print mini
-40.0

Verfasst: Samstag 9. August 2008, 17:44
von wuf
Hallo derkay

Meine Idee die Nachbarfelder zu ermitteln:

Hier als .pdf-Datei:

http://cid-c8d0cae764f09eef.skydrive.li ... der_01.pdf


Gruss wuf :wink:

Verfasst: Samstag 9. August 2008, 18:03
von numerix
EyDu hat geschrieben:Es macht einfach keinen Sinn in ein Problem mit so wenig Kontext etwas hineinzu interpretieren.
Naja, wenig Kontext nenne ich das nicht gerade. Der Thread ist schon 13 Seiten lang und es geht immer noch um das gleiche Programm.
EyDu hat geschrieben:Zu dem abs aus meinem letzten Thread:

Code: Alles auswählen

>>> alt = [0.0, 0.0, 80.0, 120.0, -40.0, 0.0]
>>> neu = sorted(list(set(alt)))
>>> mini = neu[0] if abs(neu[0])>0.001 else neu[1]
>>> print mini
-40.0
Wie wir mittlerweile wissen, geht es hier um Entfernungen und die dürften wohl kaum negativ sein - höchstens im Bereich um die Null herum durch evtl. Fließkomma-Ungenauigkeiten und da ist das abs() genau richtig.

Verfasst: Samstag 9. August 2008, 21:42
von numerix
wuf hat geschrieben:Meine Idee die Nachbarfelder zu ermitteln:
Hier als .pdf-Datei:
http://cid-c8d0cae764f09eef.skydrive.li ... der_01.pdf
Ich habe mir deine PDF-Datei angesehen. Sieht toll (und nach einiger Arbeit) aus.

Man kann das ganze allerdings auch ganz anders angehen - ohne Mittelpunkte, konkrete Hexagone und graphischer Darstellung. Das trifft dann den schon öfter angesprochenen Punkt "Trennung zwischen Logik und Darstellung".

Mit einem Blatt Papier und etwas Zeit zum Basteln lässt sich das Problem "Welches sind die Nachbarfelder" auch so lösen (ich verwende dabei jetzt dein Beispiel aus der PDF mit der dortigen Nummerierung) - probier's mal aus ...

Code: Alles auswählen

# Bestimmung der Nachbarfelder

# 0  4  8  12  16
# 1  5  9  13  17
# 2  6  10 14  18
# 3  7  11 15  19

spaltenzahl = 5
zeilenzahl = 4
position = 10   # Nummer im Feld

spalten = range(spaltenzahl)
zeilen = range(zeilenzahl)
spalte = position // zeilenzahl
zeile = position % zeilenzahl
k = spalte & 1 # unterschiedlicher Versatz bei gerader/ungerader Spalte

n = position-1 if zeile-1 in zeilen else None
s = position+1 if zeile+1 in zeilen else None
if spalte+1 in spalten:
    no = (spalte+1)*zeilenzahl+zeile+k-1 if zeile+k-1 in zeilen else None
    so = (spalte+1)*zeilenzahl+zeile+k if zeile+k in zeilen else None
else:
    no, so = None, None
if spalte-1 in spalten:
    sw = (spalte-1)*zeilenzahl+zeile+k if zeile+k in zeilen else None
    nw = (spalte-1)*zeilenzahl+zeile+k-1 if zeile+k-1 in zeilen else None
else:
    sw, nw = None, None

nachbarn = [n,no,so,s,sw,nw]
print nachbarn

Verfasst: Sonntag 10. August 2008, 00:42
von yipyip
...verstehe das Problem einfach nicht...

Die Nachbarn sind doch eigentlich bekannt:

Nummeriert man die Felder des graphischen Hexfeldes folgendermassen:

Code: Alles auswählen

0,0      0,2      0,4      0,6 ...
     0,1      0,3      0,5 ...
1,0      1,2      1,4     1,6 ...
     1,1      1,3     1,5 ...
2,0      2,2      2,4     2,6 ...
.
.
.
.
ergibt sich eine (programm)logische Repraesentation
als 2-dim. Array mit den entsprechenden Indizes.

Die Nachbarn eines Feldes (i, j) ergeben sich dann
durch die Indexoffsets (-1, -1), (-1, 0), (-1, 1),
(0, -1), (1, 0), (0, 1).

(i = Zeilenindex, j = Spaltenindex)

Das hat Blackjack in seinem Snippet doch schon alles vorgemacht...

Der Unterschied zu einer Rechteck-Pflasterung ist doch nur, dass man statt einer 4er/8er-Nachbarschaft
eine 6er-Nachbarschaft betrachtet.

Einen Pfad von einem Feld (i, j) zu einem Feld (n, m)
kann man mit Hilfe eines 'Flood Fill' Algorithmus
bestimmen (rein informell):

1. Markieriere alle Felder als unbesucht
2. setze Feld(n, m) auf 0
3. setze die 6er-Nachbarn von Feld (n, m) auf 1
4. setze deren unbesuchte Nachbarn auf 2
5. deren unbesuchte auf 3
usw.
(Hindernisse werden nicht besucht.)

Dann kommt man in Richtung absteigender Feldwerte
von (i, j) nach (n, m).
Stehen mehrere Felder fuer den Pfad zur Auswahl, dann
kann man zufaellig eines auswaehlen oder weitere Kriterien
zur Auswahl hinzuziehen.

Nach dem gleichen Prinzip kann man den Abstand zwischen
2 Feldern berechnen.

Da wir auf diskreten Strukturen arbeiten, verstehe ich nicht den Einsatz von Fliesskommazahlen.
Wir operieren doch nicht auf dem graphischen Hexfeld !?

Verfasst: Sonntag 10. August 2008, 07:01
von wuf
Hallo numerx un yipyip

Besten Dank für eure interessanten Beiträge. Werde mich noch eingehender damit beschäftigen. Der Algorithmus 'Flood-Fill' ist neu für mich. Habe hierfür schon einige Informationen aus dem Net runtergeladen. Probleme können je nach Background des Erfinders eben auf verschiedene Arten gelöst werden. :lol:

Mit meiner Idee bin ich nicht von einem zeidimensionalen Array ausgegangen sondern von einer Liste (eindimensional linear durchnummeriert) . Ich nehme an das die Berechnung der grafischen Daten (Fliesskommazahlen) auch im logischen Teil erfolgt die dann später,.wenn die GUI existier einfach von dieser für die grafische Darstellung abgerufen werden können.

Gruss wuf :wink:

Verfasst: Sonntag 10. August 2008, 10:56
von derkai
Hallo,

also, den Ansatz zur Ermittlung der Nachbarfelder habe ich bereits
erledigt. Sicher nicht so elegant wie ihr, aber für meine Bedüfnisse
ausreichend. Der Code dazu folgt auch bald. Ich habe nur noch ein
kleines Problem zu lösen.

Bei meiner Berechnung der Abstände von Feld 1 nach Feld 2 (Luftlinie) kommen keine sinnvollen Ergebnisse heraus. Ich glaube das liegt daran :

abstand = sqrt ((abs(mfnx-mfax)**2)-((abs(mfny-mfay))**2))

Wobei mfnx die Mitte x des alten Feldes und mfay die Mitte y des alten
Feldes darstellen.

Die Zahlen werden wohl irgendwie zu gross ? Kann das sein ?

Wie kann ich bei einer Zahl die Nachkommastellen auf zwei Stellen nach dem Komma begrenzen ???

Kai

Verfasst: Sonntag 10. August 2008, 11:19
von EyDu
Den Abstand berechnest du als:

Code: Alles auswählen

sqrt((mfnx-mfax)**2+(mfny-mfay)**2)
Das das Ergebnis viele Nachkommastellen hat ist vollkommen normal, da musst du nichts begrenzen. Zur Darstellung kann man das allerdings machen:

Code: Alles auswählen

"%.2f" % 1.234567

Verfasst: Sonntag 10. August 2008, 11:42
von derkai
ich bekomme den Fehler aber leider nicht weg :

Code: Alles auswählen

# -*- coding: utf-8 -*-
""" Modul zur Berechnung von Hexfeldobjekten"""

from math import sqrt

hexdic = {} # Dictionary (x,y) : x1,y1 ... x6,y6
nachbardic = {} # Dictionary Nachbarfelder

laenge = 20.0
spielreihen = 42
ungerade_spalten = 17
gerade_spalten = ungerade_spalten - 1


""" Funktion zur Berechnung der X,Y Koordinaten """

def berechne_felder (xpos, ypos) :

    x1 = xpos
    y1 = ypos
    x2 = x1 + laenge
    y2 = y1
    x3 = x2 + (laenge/2.0)
    y3 = y2 + ((laenge * sqrt(3.0)/2.0))
    x4 = x2
    y4 = (sqrt(3.0) * laenge) + y2
    x5 = x1
    y5 = y4
    x6 = x1 - (laenge / 2.0)
    y6 = y3
    mittex = round((x1 + laenge /2.0),2)
    mittey = round ((y3),2)
    mitte  = (mittex, mittey)
    
    return x1,y1,x2,y2,x3,y3,x4,y4,x5,y5,x6,y6,mitte

 
""" Funktion zur Erstellung von Listen und Dictionarys der
    gesamten Spielflaeche """

def erstelle_hexfeldobjekte (spielreihen, ungerade_spalten):

    gerade_spalten = ungerade_spalten-1
    xpos = xorg = 20
    ypos = yorg = 10
    xoffset = laenge * 1.5
    yoffset = sqrt(3) * laenge

    for reihe in range(spielreihen):

        if reihe %2 == 0:

            for feld in range (ungerade_spalten) :

                feldid = (reihe+1,feld+1)
                hexdic[feldid] = berechne_felder (xpos, ypos)
                xpos = xpos + xoffset * 2
            xpos = xorg + xoffset
            ypos = ypos + yoffset / 2

        else :

            for feld in range (gerade_spalten) :

                feldid = (reihe+1,feld+1)
                hexdic[feldid] = berechne_felder (xpos, ypos)
                xpos = xpos + xoffset * 2
            xpos = xorg
            ypos = ypos + yoffset / 2
    

""" Funktion zur Berechnung der Nachbarfelder eines Feldes aller Hexagone """

def berechne_nachbarfelder (hexdic):

    """      _0_
          5 /   \1
          4 \___/2
              3                                     
    """

    zek = hexdic.keys() # zwischenergebnis keys
    zew = []            # zwischenergebnis werte

    for x in zek :
        nf00 = x[0]-2
        nf01 = x[1]
        nf10 = x[0]-1
        nf11 = x[1] + (1 - (x[0]%2))
        nf20 = x[0]+1
        nf21 = x[1] + (1 - (x[0]%2))
        nf30 = x[0]+2
        nf31 = x[1]
        nf40 = x[0]+1
        nf41 = x[1] - (x[0]%2)
        nf50 = x[0]-1
        nf51 = x[1] - ((x[0]%2)*1)

        zew = [(nf00,nf01),(nf10,nf11),(nf20,nf21),(nf30,nf31),(nf40,nf41),(nf50,nf51)]
           
        count = 0

        for z in zew :
            if zew [count][0] < 1  or zew [count][1] < 1 : zew [count] = (0,0)
            if zew [count][0] > spielreihen or zew [count][1] > ungerade_spalten : zew [count] = (0,0)

            count += 1

        nachbardic [x] = zew


""" Funktion zur Berechnung der Entfernung Luftlinie Feldmitten """

def abstand_luft (feldalt, feldneu) :

    mfax = hexdic [feldalt] [12] [0] # steht fuer mitte feld alt x
    mfay = hexdic [feldalt] [12] [1] # steht fuer mitte feld alt y
    mfnx = hexdic [feldneu] [12] [0] # steht fuer mitte feld neu x
    mfny = hexdic [feldneu] [12] [1] # steht fuer mitte feld neu y

    abstand = round(sqrt (abs((abs(mfnx-mfax))**2)-((abs(mfny-mfay))**2)),2)
    
    return abstand


""" Funktion zur Berechnung des kürzesten Nachbarfeldes zum Ziel """
""" ruft Funktion abstand_luft auf"""

def abstand_felder (feldalt, feldneu) :

    back = []                       # liste rueckgabewerte entfernungen
    felder_ziel = []                # liste mit den Feldern zum Zielfeld

    print feldalt, feldneu

    for i in nachbardic[feldalt] :

        print i[0], i[1]
           
        if i[0] < 1.0 or i[1] < 1.0 : back.append (0.0)

        else : back.append (abstand_luft (i, (feldneu)))

    print back
   

  

        
    

            
            






Verfasst: Sonntag 10. August 2008, 11:43
von derkai
die Testdatei :

Code: Alles auswählen

from funktionen import *

erstelle_hexfeldobjekte (spielreihen, ungerade_spalten)
berechne_nachbarfelder(hexdic)
#print hexdic
#print nachbardic
print nachbardic [1,1]
#print nachbardic [2,1]
#print nachbardic [3,1]
print hexdic[1,1][12]
#print hexdic[2,1][12]
#abstand_luft((1,1),(3,3))
abstand_felder ((1,1),(2,1))






Verfasst: Sonntag 10. August 2008, 11:54
von derkai
Erklärung :

ich erzeuge :

Liste hexdic :
Schlüssel : Zeile, FeldNr der einzelnen Felder
Werte : x1,y1, usw + Element 12 ist die Feldmitte des Feldes

Liste nachbardic :
Schlüssel : Zeile, FeldNr. der einzelnen Felder
Werte : die Werte sind die Nachbarfelder, die mit der Funktion
erstelle_hxfeldobjekte erzeugt werden.

So weit so gut.

mit der Funktion abstand_luft sollen die Abständer der jeweiligen
Nachbarfelder eines Feld X berechnet werden.

Also wird mit der Funktion abstand_felder eine Iteration gestartet.
Es werden aus dem Dictionary Nachbardic die Werte (Nachbarfelder) an die Funktion abstand_luft übergeben und einzelnd iteriert. Dies gschieht nur für feldalt, da feld neu natürlich immer gleich ist.

Die berechneten Abstände sollen in der Liste back gespeichert werden.

BSP :
es werden die Werte (1,1) und (2,1) an die Funktion abstand_luft übergeben. Die Werte der Nachabrfelder im Dictionary für Nachbardic mit dem Schlüssel (1,1) stimmen auch.

Jedoch und das ist das Problem, die Berechnung der Abstände stimmt nicht. Es müßte lauten : (0,0),(0,0),(wert),(wert),(0,0),(0,0)

TUT es aber nicht.

Irgendwo liegt ein Fehler, aber wo ?

Da die kürzeste Entfernung zu einem Ziel nun einmal eine Gerade ist,
wird im Anschluss gesagt : Wiederhole die Berechnung mit dem Nachbarfeld, dass die kürzeste Entfernung zum Ziel hat -> und das so lange, bis Feldalt und Feldnneu übereinstimmen.

HIEIEIELFE

Kai

Verfasst: Sonntag 10. August 2008, 12:08
von derkai
ich glaub jetzt hab ich es doch. Es ist ein Gedanken Fehler bei mir.

Wenn ich den Abstand der Felder von feldalt(1,1) und neuen Feld
feldneu(2,1) berechnen möchte, dann erhalte ich natürlich bei Nachbarfeld
feldalt(2,1) und neuen Feld(2,1) gleiche Werte bei der Berechnung. Dem
zu Folge muss eine "0" zurückgegeben werden.

Oder ?

Kai

Verfasst: Sonntag 10. August 2008, 12:10
von derkai
jetzt habe ich aber dass Problem, dass ich bei der Berechnung bspweise von
feldalt(1,1) nach feldneu(5,1) einen Wert nan erhalte. Was ist denn das jetzt schon wieder ? und wie stelle ich das ab ?

Kai

Verfasst: Sonntag 10. August 2008, 12:38
von HWK
EyDu hat geschrieben:Den Abstand berechnest du als:

Code: Alles auswählen

sqrt((mfnx-mfax)**2+(mfny-mfay)**2)
Eine einfachere Variante:

Code: Alles auswählen

math.hypot(mfnx-mfax, mfny-mfay)
MfG
HWK

Verfasst: Sonntag 10. August 2008, 12:50
von derkai
SUPER : mit hypot ist mein Fehler auch direkt weg.

Jetzt muss ich mich "nur" noch darum kümmern, dass
wenn ein Nachbarfeld bereits das Zielfeld ist eine logische Folge entsteht.

Danke
Kai

Verfasst: Sonntag 10. August 2008, 13:13
von BlackJack
@derkay: "nan" == "not a number", dass bekommt man bei einigen Rechnungen, deren Ergebnis nicht definiert sind, zum Beispiel wenn man versucht +unendlich und -unendlich zu addieren. Anscheinend gibt's das bei Dir auch wenn man von einer negativen Zahl die Wurzel zieht. Bei mir kommt an der Stelle eine Ausnahme (ValueError: math domain error).