Frage für Profis

[remi_meier]

Beispiel:
Knoten : (X/Y)
K0 : (1/1)
K1 : (3/4)
K2 : (7/8)
K3 : (2/9)
K4 : (5/7)

Diese Daten sind aber für den Algorithmus nicht relevant, nur die Distanzen
zwischen den Knoten:
von bis = Distanz
K1 K1 = 0
K1 K2 = 4.5
K1 K3 = 5.1
usw..
Diese Distanzen habe ich in einem Array gespeichert (X = von, Y = Bis),
also von K1 bis K2 schau ich im Array unter (1, 2), wo die Distanz abgespeichert
ist. Die X/Y-Koordinaten werden nur zum Berechnen der Distanzen benötigt.

Die Knoten sind also durch Distanzen zu anderen Knoten definiert. Es reicht
dem Algorithmus die Weglängen zwischen Punkten zu kennen um den kürzesten
Weg zu finden! Wieso soll der auch noch genau wissen, wo die sind? Das
kannst du leicht wieder rausfinden, denn es wird ja der Weg in folge von
Knotennummern zurückgegeben, nun musst du nur noch in z.B. einem
Array unter dieser Nummer nachschaun.

Hoffe das reicht.
greetz
Remi

[unix]

Ähm das versteh ich nicht

Data.l 1, 1, 1, 1
Data.l 1, 1, 1, 1
Data.l 1, 1, 1, 1
Data.l 1,1, 1, 1

das müssten 16 Knoten mit jeweils 1 Distanz sein weil 4*4 = 16

Oder versteh ich das Falsch?

Aber wenn ich bei SKnoten 14 eingebe meldet er Fehler warum?

[remi_meier]

Nein, damit hast du nur 4 Knoten definiert.

Code: Alles auswählen

-------
0|3|5
-------
6|0|6
-------
7|1|0
-------

Beachte, dass die Diagonale immer 0 ist, da von K1 zu K1 die Distanz
logischerweise 0 ist!
Also wenn du vom Knoten 1 zum Knoten 2 die Distanz ablesen willst,
gehst du in die 2. Zeile, 3. Spalte! Wenn du von K0 zu K1 willst, schaust
du in die 1. Zeile, 2. Spalte. Die Knotennummer (+1) ist hierbei der Index
in der Tabelle (VonKnoten = Y, BisKnoten = X, oder umgekehrt).
Du musst die Distanzen von allen Knoten zu allen Knoten abspeichern!
Also von 0 zu 0, von 0 zu 1, von 0 zu 2
von 1 zu 0 von 1 zu 1 von 1 zu 2
von 2 zu 0 von 2 zu 1 von 2 zu 2
Damit entsteht eine 2Dimensionale Tabelle, wo du die Distanzen ablesen
kannst, dabei wird auch unterschieden zwischen von K0 zu K2 und von K2
zu K0! Also Hin- und Rückweg kann unterschiedlich sein.

Überleg dir einfach mal, wie du alle Distanzen zwischen allen Punkten
abspeichern musst, damit sie in ein 2d-Array passen. Überleg dir, wieviele
Distanzen es gibt zwischen allen und allen.

Ich kann grad nicht einfacher erklären, wenn du es noch nicht verstehst,
frag nochmals und hoff darauf, dass dir jemand anders besser helfen kann.
(nicht böse gemeint! Ich bin nur oft schlecht im Erklären...)

greetz
Remi

[unix]

Ich hoffe ich komme diesmal näher an deiner theorie

| K1|K2|K3
------------
K1 0|3|5
------------
K2 6|0|6
------------
K3 7|1|0
------------
wenn es so ist das ist die distanz von K1 -> K2 = 6 und K2 -> K1 3
irgendwie unlogisch

Knoten = Anzahl Felder?

Wenn dann so:

| K1|K2|K3
------------
K1 0|3|6
------------
K2 3|0|3
------------
K3 6|3|0
------------

oder?

[remi_meier]

Du hast mich richtig verstanden!
Beide Tabellen stimmen, nur dass die erste ein Spezialfall ist, z.B. ist die
eine Richtung von K1 zu K2 verstopft und die von K2 zu K1 läuft halt flüssig!
Es muss ja nicht sein, dass es in beide Richtungen gleich gut geht, aber
im Allgemeinen kannst du die Tabelle symmetrisch bezüglich der Diagonalen
aufbauen.
Meine Tabelle war auch für 3 Knoten
Aber du hast es richtig verstanden!

greetz
Remi

[unix]

Code: Alles auswählen

  Data.l  0,1,2,3,4,#M,#M,7,8,#M,10,11,12,#M,14,#M
  Data.l  1,0,1,2,3,#M,#M,6,7,#M,9,10,11,#M,13,#M   
  Data.l  2,1,0,1,2,#M,#M,5,6,#M,8,9,10,#M,12,#M
  Data.l  3,2,1,0,1,#M,#M,4,5,#M,7,8,9,#M,11,#M
  Data.l  4,3,2,1,0,#M,#M,3,4,#M,6,7,8,#M,10,#M
  Data.l  #M,#M,#M,#M,#M,0,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M
  Data.l  #M,#M,#M,#M,#M,#M,0,#M,#M,#M,#M,#M,#M,#M,#M,#M
  Data.l  7,6,5,4,3,#M,#M,0,1,#M,3,4,5,#M,7,#M
  Data.l  8,7,6,5,4,#M,#M,1,0,#M,2,3,4,#M,6,#M
  Data.l  #M,#M,#M,#M,#M,#M,#M,#M,#M,0,#M,#M,#M,#M,#M,#M
  Data.l  10,9,8,7,6,#M,#M,3,2,#M,0,1,2,#M,4,#M
  Data.l  11,10,9,8,7,#M,#M,4,5,#M,1,0,1,#M,3,#M
  Data.l  12,11,10,9,8,#M,#M,5,4,#M,2,3,0,#M,2,#M
  Data.l  #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,0,#M,#M
  Data.l  14,13,12,11,10,#M,#M,7,6,#M,4,3,2,#M,0,#M
  Data.l  #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,0

sollte so aussehen

0 = Weg, 1 = Mauer

0000
0110
0100
0101

oder?

[remi_meier]

Z.T. richtig. (Ev. auch ganz, glaub ich aber nicht)
Also wenn du nicht willst, dass der Algorithmus direkt von K1 zu K15 springt,
ohne dir den Weg auszugeben, solltest du überall #M verwenden, wenn
sie nicht direkte Nachbarn sind! Also nirgends mehr als 1 eintragen. Es
könnte hier dabei rauskommen, dass der Output so aussieht:
0, 14
anstatt:
0, 4, 8, 12, 14

Also nur dort eine reale Distanz eintragen, wo die Knoten direkt Nachbarn
sind, sonst wird der ev. übersprungen. Ausser du willst Fluglinien

[unix]

OK so funct


; 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Data.l 0 ,1 ,#M,#M,1 ,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M ;0
Data.l 1 ,0 ,1 ,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M ;1
Data.l #M,1 ,0 ,1 ,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M ;2
Data.l #M,#M,1 ,0 ,#M,#M,#M,1 ,#M,#M,#M,#M,#M,#M,#M,#M ;3
Data.l 1 ,#M,#M,#M,0 ,#M,#M,#M,1 ,#M,#M,#M,#M,#M,#M,#M ;4
Data.l #M,#M,#M,#M,#M,0 ,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M ;5
Data.l #M,#M,#M,#M,#M,#M,0 ,#M,#M,#M,#M,#M,#M,#M,#M,#M ;6
Data.l #M,#M,#M,1 ,#M,#M,#M,0 ,#M,#M,#M,1 ,#M,#M,#M,#M ;7
Data.l #M,#M,#M,#M,1 ,#M,#M,#M,0 ,#M,#M,#M,1 ,#M,#M,#M ;8
Data.l #M,#M,#M,#M,#M,#M,#M,#M,#M,0 ,#M,#M,#M,#M,#M,#M ;9
Data.l #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,0 ,1 ,#M,#M,1 ,#M ;10
Data.l #M,#M,#M,#M,#M,#M,#M,1 ,#M,#M,1 ,0 ,#M,#M,#M,#M ;11
Data.l #M,#M,#M,#M,#M,#M,#M,#M,1 ,#M,#M,#M,0 ,#M,#M,#M ;12
Data.l #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,0 ,#M,#M ;13
Data.l #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,1 ,#M,#M,#M,0 ,#M ;14
Data.l #M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,#M,0 ;15


Kanste mal Prob

danke für alles
jetzt muss ich schaun wie ich das nein MapEdit bekomm

[unix]

OK wollte nun für meine Map 8X8 eine Distanztabelle erstellen

Code:

Code: Alles auswählen

;******************************** Map lesen ************************************************************* 

#Map = 0
Global Mw.l, Mh.l

OpenFile(#Map,"H:\Map0.mp")
 
 Mw = ReadLong()
 Mh = ReadLong()
 
 Debug mw
 Debug mh

Dim Layer(Mw,Mh)

For y = 1 To Mh
 For x = 1 To Mw
  NLayer = ReadLong()
  Debug NLayer
  Layer(x,y) = NLayer
 Next
Next

CloseFile(#Map)


;********************** distanzen errechnen uns schreiben ************************************************

#M = 999999


;           von   nach
Dim Knoten(mw*mh,mw*mh)




For yv = 1 To mh
 For xv = 1 To mw
    
   tv.l = yv
   Repeat
     
    tv-1
   
    If tv > 0 
     kv.l + mw
    EndIf      
     
   Until tv < 1
   kv + xv
  
  
   Lv = Layer(xv,yv)
  
  
  
   For yn = 1 To mh
    For xn = 1 To mw
      
     tn.l = yn
      Repeat
     
       tn-1
   
       If tn > 0 
        kn.l + mw
       EndIf      
     
      Until tn < 1
      kn + xn
      
      
      
      Ln = Layer(xn,yn)
      
      dX.f = xv - xn 
      DistanzX = Abs(dX)
      
      dY.f = yv - yn 
      DistanzY = Abs(dY)
      
      
      
      If Lv = 0 And DistanzX < 2 And DistanzY < 2
       If Ln = 0  
         Knoten(kv,kn) = 1
       Else
         Knoten(kv,kn) = #M        
       EndIf
      Else
       Knoten(kv,kn) = #M
      EndIf
      
      
      
      Knoten(kv,kn) = Result
    
    Next
   Next
   
 Next
Next  
  
  
    
  
  
  
  
     

Debug "Knoten"

For v = 1 To mw*mh
 For n = 1 To mw*mh
  Debug Knoten(v,n)
 Next
Next


End

Bei dieser Map

1=Mauer
0=Weg

Code: Alles auswählen

DataSection

Mapsice:
 Data.l 8, 8

Layers:
 Data.l 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0
 Data.l 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0
 Data.l 0 ,0 ,1 ,1 ,1 ,1 ,0 ,0
 Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0
 Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,1
 Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,0
 Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,0
 Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0
 Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0

EndDataSection

nur bekomme ich eine fehlermeldumg

PureBasic24936031.exe hat ein Problem festgestellt und muss beendet werden.

Was habe ich falsch gemacht?

[remi_meier]

Hab mir deinen Code nicht angeschaut, aber ich würds in etwa wie folgt
machen:

Code: Alles auswählen

;******************************** Map lesen ************************************************************* 

#Map = 0 
Global Mw.l, Mh.l 


Restore Mapsize
Read Mw
Read Mh
  
Debug Mw 
Debug Mh 

Restore Layers
Dim Layer(Mw,Mh) 

For y = 0 To Mh - 1
  For x = 0 To Mw - 1
    Read NLayer
    Layer(x,y) = NLayer 
  Next 
Next 




;********************** distanzen errechnen uns schreiben ************************************************ 

#M = 999999 



Max = Mw * Mh - 1
;           von nach 
Dim Knoten(Max, Max) 


For v = 0 To Max
  For n = 0 To Max
    If v = n
      Knoten(v, n) = 0
      Continue
    EndIf
    
    xv = v % Mh
    yv = Int(v / Mh)
    xn = n % Mh
    yn = Int(n / Mh)
    
    
    ; ob nachbarn
    If ((xv + 1 = xn Or xv - 1 = xn Or xn = xv) And (yv + 1 = yn Or yv - 1 = yn Or yv = yn))
      Debug "von "+Str(xv)+ " " + Str(yv) + " nach " +Str(xn) +" "+Str(yn) + " = " + Str(Layer(xn, yn))
      
      ; wenn knoten selber nicht mauer
      If Layer(xv, yv) = 1
        Knoten(v, n) = #M
        Continue
      EndIf
      
      ; wenn erreichbar
      If Layer(xn, yn) = 0
        Knoten(v, n) = 1
      Else
        Knoten(v, n) = #M
      EndIf
    EndIf
    
  Next
Next  



Debug "Knoten" 

For v = 1 To Max
  For n = 1 To Max
    Debug Knoten(v,n) 
  Next 
Next 


End

DataSection 

Mapsize: 
Data.l 8, 8 

Layers: 
Data.l 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 
Data.l 0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 
Data.l 0 ,0 ,1 ,1 ,1 ,1 ,0 ,0 
Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 
Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,1 
Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,0 
Data.l 0 ,0 ,1 ,0 ,1 ,1 ,1 ,0 
Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 
Data.l 0 ,0 ,1 ,0 ,0 ,0 ,0 ,0 

EndDataSection

Hab den Code nicht gross getestet, aber wenn er noch Bugs hat, so kanns
dir mindestens eine Idee geben.