Problem mit A-Star-Algorithmus

Übersicht BlitzMax, BlitzMax NG Allgemein

Neue Antwort erstellen

Skabus

Betreff: Problem mit A-Star-Algorithmus

 BeitragSo, Okt 25, 2009 12:37
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Community,


Ich arbeite seit mehreren Tagen daran meinen A-Star-Algorithmus für das Aves Certim-Kampfsystem
zu schreiben.Anfangs lief es auch wie geschmiert und mittlerweile funktioniert mein A-Star-Algorithmus auch
problemlos, allerdings scheint meine Implementation einen entscheidenen Fehler zu haben...

Zunächst mal nen Beispiel für das Problem.Ich habe als Test eine 30*30-Matrix eingerichtet,
die an den Positionen:

[15,15]
[15,16]
[15,17]
[15,18]
[15,19]
[15,20]

jeweils ein unbegehbares Tile besitzt.Die Startposition des Suchalgorithmus ist an der Position [5,15]
und die Zielkoordinate an der Position [20,18].
Mein Algorithmus funktioniert tadellos, er findet egal welche Versuchsanordnung ich wähle problemlos.
Allerdings findet er einen Pfad den man nicht als Optimalen Pfad ansehen kann.Der Optimale Pfad müsste sein:

Code: [AUSKLAPPEN]

[5,15]
[6,15]
[7,15]
[8,15]
[9,15]
[10,15]
[11,15]
[12,15]
[13,15]
[14,15]
[14,16]
[14,17]
[14,18]
[14,19]
[14,20]
[14,21]
[15,21]
[16,21]
[17,21]
[18,21]
[19,21]
[20,21]
[20,20]
[20,19]
[20,18]


Er findet auch folgerichtig alle diese Positionen, nur das er zwischendurch auf Stellen trifft an denen
er absurde Positionen bevorzugt.Meine aktuelle Ausgabe zu dieser Versuchsanordnung sieht etwa folgendermaßen aus:

Code: [AUSKLAPPEN]

[5,15]
[6,15]
[7,15]
[8,15]
[9,15]
[10,15]
[11,15]
[12,15]
[13,15]
[14,15]
[14,16]
[14,17]
[14,18]
[13,18]
[14,19]
[13,17]
[12,18]
.
.
.
.
.
[20,18]


Wie ihr unschwer erkennen könnt, macht er ne Menge Bewegungen die gar nicht zulässig sind.
Außerdem geht er an manchen Stellen einen oder Zwei Schritte zurück, wärend er dann wieder
2 Schritte nach unten und dann wieder nach vorne geht.Das ist alles in allem weder befriedigend
noch richtig.Ich sitze jetzt bereits mehr als 5 Stunden an diesem Problem und finde einfach
keinen Fehler...

Hier mal mein aktueller Code(bei Unklarheiten, sagt einfach Bescheid, ich habs so gut kommentiert wie es ging)

BlitzMax: [AUSKLAPPEN] 

SuperStrict

'benötigte Includedateien


'Konstanten

Type bla

Field battleColLayer:Int[,]

End Type

Global maxPath:Int

Global ACBS:bla = New bla 
ACBS.battleColLayer = New Int[30,30]

Global j:Int
Global k:Int 

'der TestArray wird mit Werten gefüllt
For j=0 To 29
 For k=0 To 29
  ACBS.battleColLayer[j,k] = 0
 Next
Next

ACBS.battleColLayer[15,15] = 1
ACBS.battleColLayer[15,16] = 1
ACBS.battleColLayer[15,17] = 1
ACBS.battleColLayer[15,18] = 1
ACBS.battleColLayer[15,19] = 1
ACBS.battleColLayer[15,20] = 1


'globale Variablen


Graphics 400,500,0'16,75,GRAPHICS_BACKBUFFER


'Definition des Path-Knoten
Type pathNode

Field x:Int
Field y:Int

Field prevNode:pathNode   'zeigt auf den Vorgängerknoten

End Type


'dieser Klasse stellt die OpenList des Suchalgorithmusn dar
Type openList

 Field prevElement:pathNode

End Type


'Definition der Pathfinding-Klasse

Type ACStarPathfinding

'Membervariablen
Field m_startX:Int
Field m_startY:Int
Field m_targetX:Int
Field m_targetY:Int
Field m_openList:pathNode[]
Field m_closedList:pathNode[]
Field m_path:pathNode[]
Field m_curOpenNode:Int
Field m_curClosedNode:Int
Field m_mapX:Int
Field m_mapY:Int

'diese Methode initialisiert 
Method startPathFinding(startX:Int,startY:Int,targetX:Int,targetY:Int,mapX:Int,mapY:Int)

'lokale Variablen
Local i:Int

'die Start und Zielkoordinaten werden übertragen
m_startX  = startX;
m_startY  = startY;
m_targetX = targetX;
m_targetY = targetY;
m_mapX    = mapX
m_mapY    = mapY

'dimensioniert die OpenList
m_openList   	= New pathNode[m_mapX*m_mapY]
m_closedList 	= New pathNode[m_mapX*m_mapY]
m_path		= New pathNode[m_mapX*m_mapY]

'die Arrays werden initialisiert
For i=0 To (mapX*mapY)-1

m_openList[i]   = New pathNode
m_closedList[i] = New pathNode
m_path[i]		 = New pathNode

m_openList[i].x = -1
m_openList[i].y = -1
m_openList[i].prevNode = New pathNode

m_closedList[i].x = -1
m_closedList[i].y = -1
m_closedList[i].prevNode = New pathNode

m_path[i].x = -1
m_path[i].y = -1
m_path[i].prevNode = New pathNode


Next 

startSearchingPath()

End Method


'die Methode berechnet die Heueristik(Schätzwert) zwischen zwei Punkten
Method calcHeueristik:Int(startX:Int,startY:Int)

 Local heuX:Int
 Local heuY:Int
 
 'anhand des Start und des Zielwertes wird die geschätzte Entfernung
 'berechnet
 heuX = startX - m_targetX 
 If(heuX < 0) Then heuX = heuX * (-1)
 heuY = startY - m_targetY
 If(heuY < 0) Then heuY = heuY * (-1)

 Return (heuX + heuY)
 
End Method



'Die Methode sucht auf der angegebenen Karte nach dem kürzesten Weg
'zwischen der Startkoordinate und dem Zielpunkt
Method startSearchingPath()

'lokale Variablen
Local curPosX:Int    = m_startX;  	'die aktuelle Position um die gesucht werden muss
Local curPosY:Int    = m_startY; 
Local curOpenEntry:Int   = 1;         	'zeigt an an welcher Position sich die OpenList befindet
Local curClosedEntry:Int = 0;         	'zeigt an an welcher Position sich die ClosedList befindet
Local previousNode:pathNode = New pathNode   'der aktuelle Knoten
Local curCost:Int=0               	'speichert die aktuellen Kosten eines Feldes
Local prevCost:Int=0               'speichert die vorherigen Kosten eines Feldes
Local costIndex:Int=0
Local totalCost:Int=0		    	'speichert die Kosten vom Startpunkt zum aktuellen Punkt
Local i:Int=0

Local ISINOLIST:Int = False
Local ISINCLIST:Int = False
Local FOUND:Int = False   'zeigt an ob sich die Zielkoordinate in der 
                          'ClosedList befindet
 

'zunächst wird der Startpunkt in die OpenList aufgenommen
m_openList[0].x = m_startX;
m_openList[0].y = m_startY;
m_openList[0].prevNode = Null;

'nun werden die ersten 4 Felder zur OpenList hinzugefügt
'welche um das Startfeld herum sind

  If(ACBS.battleColLayer[curPosX+1,curPosY] <> 1)
  	m_openList[curOpenEntry].x 	      = curPosX+1
  	m_openList[curOpenEntry].y 	    	 = curPosY
  	curOpenEntry:+1
  EndIf


  If(ACBS.battleColLayer[curPosX-1,curPosY] <> 1)
  	m_openList[curOpenEntry].x = curPosX-1
  	m_openList[curOpenEntry].y = curPosY
  	curOpenEntry:+1
  EndIf

  If(ACBS.battleColLayer[curPosX,curPosY+1] <> 1)
  	m_openList[curOpenEntry].x = curPosX
  	m_openList[curOpenEntry].y = curPosY+1
  	curOpenEntry:+1
  EndIf

  If(ACBS.battleColLayer[curPosX,curPosY-1] <> 1)
  	m_openList[curOpenEntry].x = curPosX
  	m_openList[curOpenEntry].y = curPosY-1 
  	curOpenEntry:+1
  EndIf

  'die Startposition wird in die ClosedList aufgenommen
   m_closedList[0].x 	   = m_openList[0].x
   m_closedList[0].y 	   = m_openList[0].y
   m_closedList[0].prevNode = Null

  'die Startposition wird aus der Liste gelöscht
  popElement(0)
  curOpenEntry:-1
  curClosedEntry:+1


  'nachdem dies geschehen ist, wird überprüft welches Feld zur ClosedList
  'hinzugefügt wird
  For i=0 To curOpenEntry-1

	'zunächst werden die Kosten berechnet, die sich aus dem aktuellen Feld und der
	'Heueristik berechnet
	
	curCost =  (totalCost + 1) + calcHeueristik(m_openList[i].x,m_openList[i].y)
	
	'sofern wir nicht direkt am Anfang der Betrachtung sind
	'wird geschaut ob die aktuellen Kosten kleiner sind als die vorherigen
	'sollte dem so sein wird das aktuelle Feld als bestes Feld übernommen 
	If(i <> 0)
	
	 If(curCost < prevCost)
	
	   prevCost = curCost
	   costIndex = i
	
	 EndIf
		
	Else
	
	 'sind wir noch am Anfang wird die aktuellen Kosten als vorherige Kosten
	 'vermerkt
	 prevCost  = curCost
      costIndex = i	
	EndIf
  Next



  'nachdem die Betrachtung beendet wurde, wurde das beste Feld ermittelt
  'nun wird es der closedList hinzugefügt und aus der offenen Liste gelöscht
  m_closedList[curClosedEntry].x 		= m_openList[costIndex].x
  m_closedList[curClosedEntry].y 		= m_openList[costIndex].y
  m_closedList[curClosedEntry].prevNode = m_closedList[curClosedEntry-1]

  'RuntimeError(m_closedList[curClosedEntry].x + "," + m_closedList[curClosedEntry].y)

  'prevNode wird aktualisiert
  'previousNode    = m_closedList[curClosedEntry]
 
  'die totalen Kosten werden aktualisiert
  totalCost = totalCost + 1

  'das Feld wird aus der openList gelöscht
  popElement(costIndex)
  curOpenEntry:-1

  'das aktuell betrachtete Feld wird übernommen
  curPosX = m_closedList[curClosedEntry].x 
  curPosY = m_closedList[curClosedEntry].y

  curClosedEntry:+1

'nachdem dies getan ist, wird eine Schleife initialisiert
'in der der Rest dea Suchalgorithmuses durchgeführt wird


While FOUND = False  

'es werden 4 weitere Felder zur OpenList hinzugefügt

'es wird zunächst getestet ob das neue Feld begehbar ist 
  If(ACBS.battleColLayer[curPosX+1,curPosY] <> 1)

     'ist es begehbar wird geschaut ob es nicht bereits in der OpenList vorhanden ist
     For i=0 To curOpenEntry-1
		If(m_openList[i].x = curPosX+1 And m_openList[i].y = curPosY) ISINOLIST = True 
     Next 

     'sollte dem nicht so sein wird geschaut ob er sich in der ClosedList befindet
     For i=0 To curClosedEntry-1
		If(m_closedList[i].x = curPosX+1 And m_closedList[i].y = curPosY) ISINCLIST = True 
     Next      

     If(ISINOLIST = False And ISINCLIST = False)

      'hat das Feld alle Tests bestanden wird es zur OpenList hinzugefügt
  	 m_openList[curOpenEntry].x 	     = curPosX+1
  	 m_openList[curOpenEntry].y 	     = curPosY
  	 curOpenEntry:+1
   
     EndIf

     ISINOLIST = False
     ISINCLIST = False
  EndIf

  If(ACBS.battleColLayer[curPosX-1,curPosY] <> 1)

     For i=0 To curOpenEntry-1
		If(m_openList[i].x = curPosX-1 And m_openList[i].y = curPosY) ISINOLIST = True 
     Next 

     For i=0 To curClosedEntry-1
		If(m_closedList[i].x = curPosX-1 And m_closedList[i].y = curPosY) ISINCLIST = True 
     Next      

     If(ISINOLIST = False And ISINCLIST = False)

      m_openList[curOpenEntry].x 		= curPosX-1
  	 m_openList[curOpenEntry].y 		= curPosY
  	 curOpenEntry:+1
     EndIf
     ISINOLIST = False
     ISINCLIST = False
  EndIf


  If(ACBS.battleColLayer[curPosX,curPosY+1] <> 1)

     For i=0 To curOpenEntry-1
		If(m_openList[i].x = curPosX And m_openList[i].y = curPosY+1) ISINOLIST = True 
     Next 

     For i=0 To curClosedEntry-1
		If(m_closedList[i].x = curPosX And m_closedList[i].y = curPosY+1) ISINCLIST = True 
     Next      

     If(ISINOLIST = False And ISINCLIST = False)
  	 m_openList[curOpenEntry].x 		= curPosX
  	 m_openList[curOpenEntry].y 		= curPosY+1
  	 curOpenEntry:+1
     EndIf
     ISINOLIST = False
     ISINCLIST = False
  EndIf


  If(ACBS.battleColLayer[curPosX,curPosY-1] <> 1)
     For i=0 To curOpenEntry-1
		If(m_openList[i].x = curPosX And m_openList[i].y = curPosY-1) ISINOLIST = True 
     Next 

     For i=0 To curClosedEntry-1
		If(m_closedList[i].x = curPosX And m_closedList[i].y = curPosY-1) ISINCLIST = True 
     Next      

     If(ISINOLIST = False And ISINCLIST = False)
  	 m_openList[curOpenEntry].x 		= curPosX
  	 m_openList[curOpenEntry].y 		= curPosY-1
  	 curOpenEntry:+1
     EndIf
     ISINOLIST = False
     ISINCLIST = False
  EndIf

  'als nächstes wird wieder geprüft, welches Feld das beste ist
  For i=0 To curOpenEntry-1

	'zunächst werden die Kosten berechnet, die sich aus dem aktuellen Feld und der
	'Heueristik berechnet
	
	curCost =  (totalCost + 1) + calcHeueristik(m_openList[i].x,m_openList[i].y)
	
	'sofern wir nicht direkt am Anfang der Betrachtung sind
	'wird geschaut ob die aktuellen Kosten kleiner sind als die vorherigen
	'sollte dem so sein wird das aktuelle Feld als bestes Feld übernommen 
	If(i <> 0)
	
	 If(curCost < prevCost)
	
	   prevCost = curCost
	   costIndex = i
	
	 EndIf
	Rem ElseIf(curCost = prevCost) Then
	   prevCost = curCost
	   costIndex = i	
	End Rem
	Else
	
	 'sind wir noch am Anfang wird die aktuellen Kosten als vorherige Kosten
	 'vermerkt
	 prevCost  = curCost
      costIndex = i
	
	EndIf

  Next


  'nachdem das beste Feld gefunden wurde, wird es der ClosedList hinzugefügt 
  m_closedList[curClosedEntry].x = m_openList[costIndex].x
  m_closedList[curClosedEntry].y = m_openList[costIndex].y
  m_closedList[curClosedEntry].prevNode = m_closedList[curClosedEntry-1]

  'prevNode wird aktualisiert
  previousNode.x	= (getNode(curPosX,curPosY)).x
  previousNode.y	= (getNode(curPosX,curPosY)).y

  'die totalen Kosten werden aktualisiert
  totalCost = totalCost + 1

  'das Feld wird aus der openList gelöscht
   popElement(costIndex)
   curOpenEntry:-1

  'das aktuell betrachtete Feld wird übernommen
  curPosX = m_closedList[curClosedEntry].x 
  curPosY = m_closedList[curClosedEntry].y 
 
  'sollte der aktuelle Eintrag in der ClosedList den Zielkoordinaten entsprechen
  'wird der Suchvorgang erfolgreich beendet
  If(m_closedList[curClosedEntry].x = m_targetX And m_closedList[curClosedEntry].y = m_targetY) Then FOUND = True

  curClosedEntry:+1 

Wend


'als letztes wird der optimale Pfad in einen Array gespeichert
'damit ist der Suchalgorithmus erfolgreich beendet worden
getPath(curClosedEntry) 

End Method


'diese Methode löscht ein Element aus der OpenList und 
Method popElement(n:Int)

Local tempArray:pathNode[m_mapX*m_mapY]
Local i:Int = 0
Local curPos:Int=0

For i=0 To (m_mapX*m_mapY)-1

 tempArray[i] = New pathNode

Next 


'zunächst wird der angegebene Eintrag gelöscht
m_openList[n].x = -1
m_openList[n].y = -1
m_openList[n].prevNode = Null

For i=0 To (m_mapX*m_mapY)-1

If(m_openList[i].x <> -1)

 tempArray[curPos].x = m_openList[i].x
 tempArray[curPos].y = m_openList[i].y
 tempArray[curPos].prevNode = m_openList[i].prevNode

 curPos:+1

EndIf

Next

'nun wird die openList vollständig gelöscht
'und die neuen Werte hinzugefügt
For i=0 To (m_mapX*m_mapY)-1

m_openList[i].x = -1
m_openList[i].y = -1
m_openList[i].prevNode = Null

m_openList[i].x = tempArray[i].x
m_openList[i].y = tempArray[i].y
m_openList[i].prevNode = tempArray[i].prevNode


Next 

End Method

'diese Methode lies den ermittelten Pfad aus und speichert ihn in den Ergebnis-Array
Method getPath(curClosedEntry:Int)

'lokale Variablen
Local e:Int=0
Local actNode:pathNode = New pathNode 
Local FOUND:Int = False

actNode.prevNode = New pathNode

'der Eintrag des Zielfeldes wird auf actNode übernommen
actNode.x 	  = m_closedList[curClosedEntry-1].x
actNode.y 	  = m_closedList[curClosedEntry-1].y
actNode.prevNode = m_closedList[curClosedEntry-1].prevNode


'der letzte Eintrag der ClosedListt wird zurüclverfolgt und die jeweiligen
'Vorgänger in den path-Array gespeichert, bis der Startpunkt wieder erreicht ist
While FOUND = False
  'die Koordinaten werden dem Array übergeben
  m_path[e].x = actNode.x 
  m_path[e].y = actNode.y 

  If(actNode.x = m_startX And actNode.y = m_startY) Then FOUND = True

  If(actNode.prevNode.prevNode <> Null) Then 

	actNode.x 	  = actNode.prevNode.x
	actNode.y 	  = actNode.prevNode.y
	actNode.prevNode = actNode.prevNode.prevNode

    e:+1
  Else
   FOUND = True
  EndIf

  If(e+1 > (m_mapX*m_mapY)) Then FOUND = True
Wend
maxPath = e

End Method

'diese Methode gibt anhand der übergebenen Parameter ein Node der ClosedList zurück
'sollte ein Fehler aufgetreten sein, wird NULL zurückgeben
Method getNode:pathNode(posX:Int,posY:Int)

'lokale Variablen
Local e:Int

For e=0 To (m_mapX*m_mapY)-1

If(m_closedList[e].x <> -1) Then 
 If(m_closedList[e].x = posX And m_closedList[e].y = posY) Then
  Return m_closedList[e]
 EndIf
EndIf

Next

End Method

End Type


Global ACS:ACStarPathfinding = New ACStarPathfinding 

Global QUIT:Int = False
Global p:Int

'die Testschleife
While QUIT <> True

ACS.startPathFinding(5,15,20,18,30,30)

DrawText("Der ermittelte Pfad wird ausgegeben",5,10)

DrawText("cur: " + ACS.m_closedList[24].x + "," + ACS.m_closedList[24].y + " bevor: " + ACS.m_closedList[24].prevNode.x + "," + ACS.m_closedList[24].prevNode.y,5,20)

For p=0 To (ACS.m_mapX*ACS.m_mapY)-1

If(ACS.m_closedList[p].x <> -1) Then DrawText ACS.m_closedList[p].x + "," + ACS.m_closedList[p].y,5,30+(10*p)

Next 

If(KeyHit(KEY_ESCAPE) = True) Then QUIT = True

Flip

Wend


Und wer sich dazu mal die compilierte Version anschauen mag, der kann die hier ziehen:

DOWNLOAD


Ich hab bereits herausgefunden, dass dieser Murks bei Stellen passiert andem die berechneten
Kosten + der Heueristik exakt gleich sind.Das passiert z.B. an der Stelle [14,18] die Bewegung von
auf [14,19] hat einen Kostenwert von 18 ebenso die Position [13,18] die ebenfalls 18 als Kostenwert aufweist.

Das kann aber doch eigentlich gar nicht sein oder?Oder fehlt mir ne Beschreibung die solche Ausnahmen
abfängt?Ich bin momentan ziemlich verzweifelt.Ich saß gestern 8 Stunden dran.Heute 5 Stunden.
Ich find einfach keine Lösung für das Problem...

Würd mich sehr freuen, wenn mir jemand helfen könnte der bereits in BMax einen A-Star-Algorithmus geproggt hat oder Ahnung davon hat.

Vielen Dank im vorraus!


MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Midimaster

 BeitragSo, Okt 25, 2009 13:45
Antworten mit Zitat
Benutzer-Profile anzeigen
hast du denn schon eine funktion eingebaut, die mehrere pfad varianten prüft und dann die beste auswählt?

wie beim schach, wo man ja auch ein paar züge im vorraus prüfen sollte, bevor man sich zu schritt 1 entscheidet.

Skabus

 BeitragSo, Okt 25, 2009 13:50
Antworten mit Zitat
Benutzer-Profile anzeigen
Midimaster hat Folgendes geschrieben:
hast du denn schon eine funktion eingebaut, die mehrere pfad varianten prüft und dann die beste auswählt?

wie beim schach, wo man ja auch ein paar züge im vorraus prüfen sollte, bevor man sich zu schritt 1 entscheidet.


Hm, laut den Aufzeichnungen über den A*-Algorithmus reicht es aus, vom Ende den Vorgänger zurückzuverfolgen.Was aber aus genannten Gründen nicht geht.

Ne Funktion die den günstigsten Pfad durch prüfen mehrerer Pfadvarianten herausfindet wäre ne Idee.
Frage wäre dann nur, wie genau ich mehrere Pfade prüfen soll...?

Hab ich den A*-Algorithmus falsch verstanden?Weil ich bissher davon ausging, dass er am Ende immer
nur einen, eben den günstigsten Pfad, findet.Und nicht mehrere Varianten...


MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Midimaster

 BeitragSo, Okt 25, 2009 14:33
Antworten mit Zitat
Benutzer-Profile anzeigen
da hab ich keine Ahnung von ACBS... aber ich habe mir den Code angesehen und sehe da keine Optimierung, die über den nächsten Stein hinausgeht. scheint auch keine Rekursion drin zu sein, oder?

Ich hab das früher mal gemacht und dann ist man da immer jeden möglichen Stein (Knoten) durchgegangen und von dort aus wieder jede Möglichkeit, eben durch Rekursion. immer tiefer. Dann sind die ersten Äste und damit Knoten ausgeschieden, weil alle 3 Fortsetzungen nicht zum Ziel geführt haben. Irgendwann wird die Rekursion dann wieder kleiner und am Ende kann eigentlich nur ein möglicher Weg übrig bleiben.

Erschwerend kommt bei deinem Beispiel dazu, dass es auch noch "Kosten" gibt. Hier können man ja bei jedem erfolgreichen Pfad vergleichen, ob er mit den Kosten nierdiger bleibt, als der bisher beste Pfad. Dann verwerf ich den bisher besten am nähesten Knoten. Wenn nicht, behandlte ich diesen Ast wie "führt nicht zum Ziel".

ComNik

 BeitragSo, Okt 25, 2009 14:54
Antworten mit Zitat
Benutzer-Profile anzeigen
Naja der A* macht das ja eigentlich schon an der Wurzel des neuen "Asts". Er prüft alle umliegenden Felder indem er deren Kosten bildet. Welche Heuristik verwendest du?
Das beste Feld wird für den Weg zum Ziel benutzt. Aber A* findet nicht immer den optimalen Weg!

Ich hab gerade keine Zeit deinen Code anzuschauen aber ich werds nachher mal tun,
viel Glück!

lg
ComNik
WIP: Vorx.Engine

BladeRunner

Moderator

BeitragSo, Okt 25, 2009 14:56
Antworten mit Zitat
Benutzer-Profile anzeigen
Du kannst Dir meinen Kram mal im Codearchiv angucken. Wenn es nur eine Pfaddivergenz ist könnte es sein dass die Diagonalen fehlerhaft bewertet werden, Du könntest hier die Kosten geringfügig erhöhen.
A* gibt wie Du schon sagtest nur einen Pfad zurück, nämlich den billigsten.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

Skabus

 BeitragSo, Okt 25, 2009 15:02
Antworten mit Zitat
Benutzer-Profile anzeigen
BladeRunner hat Folgendes geschrieben:
Du kannst Dir meinen Kram mal im Codearchiv angucken. Wenn es nur eine Pfaddivergenz ist könnte es sein dass die Diagonalen fehlerhaft bewertet werden, Du könntest hier die Kosten geringfügig erhöhen.
A* gibt wie Du schon sagtest nur einen Pfad zurück, nämlich den billigsten.


Danke dir^^

Hab deinen Code bereits betrachtet.
Ich glaube das Problem ist, dass ich keine Diagonalen habe.

Bewegungen in Aves Certim laufen stehts nach dem alten Prinzip Hoch,Runter,Links,Rechts.
Und will man diagonal so muss man eben rechts-hoch,links-hoch etc.

Ich glaube das ist auch der Grund warum ich Stellen habe an denen für 3 umliegenden Felder die Kosten
exakt gleich sind.Aber bissher funktionierte das auch.Ich habe den Code ja soweit angepasst, dass man
eben nur in 4 Himmelsrichtungen gehen kann.

Allersdings hab ich keine Lösung gefunden wie ich an den Stellen verfahren soll, an dem 3 oder 4
Felder die gleichen Kosten haben.



@ComNik: Ich nutze die Manhatten-Methode...also Distanz vom aktuellen Feld zum Zielfeld.
Würd mich freuen wenn du dir das mal anschauen könntest^^


Vielen Dank schonmal!

MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

BladeRunner

Moderator

BeitragSo, Okt 25, 2009 15:06
Antworten mit Zitat
Benutzer-Profile anzeigen
hm, also bei mir funktioniert auch die 4-Weg-Suche Fehlerfrei.
Du könntest die Kostenrechnung mal auf Float umstellen, um genauer zu werden. Das könnte helfen. Int ist ja doch sehr grob.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

Skabus

 BeitragSo, Okt 25, 2009 15:10
Antworten mit Zitat
Benutzer-Profile anzeigen
BladeRunner hat Folgendes geschrieben:
hm, also bei mir funktioniert auch die 4-Weg-Suche Fehlerfrei.
Du könntest die Kostenrechnung mal auf Float umstellen, um genauer zu werden. Das könnte helfen. Int ist ja doch sehr grob.


In wie fern auf Float umsteigen?Die Kosten pro Bewegung sind ja von Feld x zu Feld y immer 1.
Oder soll ich die Kostenverteilung für einzelne Felder verändern?


MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

BladeRunner

Moderator

BeitragSo, Okt 25, 2009 15:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Also, ein einzelner Schritt kostet immer eins, das stimmt.
Aber Du schätzt ja die Kosten vom aktuellen Punkt zum Ziel, und das per Pythagoras. Und dabei komen ja durchaus sehr ungrade Werte raus.

Beispiel: Du stehst an 0|0 und Ziel ist 7|6.
Deine bisherigen Laufkosten sind 0, dazu Heuristik: sqr(7²+6²)= 9.22
von 1|0: Kosten 1 + Heuristik sqr(6²+6²) = 9.48
von 0|1: kosten 1 + Heuristik sqr(7²+5²) = 9.60
Also ist - obwohl beide Schritte rechnerisch ungünstiger als der Startschritt sind, der Schritt zu 1|0 der günstigere noch unbekannte schritt und wird daher gewählt werden.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

Skabus

 BeitragSo, Okt 25, 2009 15:22
Antworten mit Zitat
Benutzer-Profile anzeigen
Achso...

Ich hatte son Dokument im Inet gefunden, das A* erklärt hat und aus dem was dort stand hab ich folgendes interpretiert:

BlitzMax: [AUSKLAPPEN] 

'die Methode berechnet die Heueristik(Schätzwert) zwischen zwei Punkten
Method calcHeueristik:Int(startX:Int,startY:Int)

 Local heuX:Int
 Local heuY:Int
 
 'anhand des Start und des Zielwertes wird die geschätzte Entfernung
 'berechnet
 heuX = startX - m_targetX 
 If(heuX < 0) Then heuX = heuX * (-1)
 heuY = startY - m_targetY
 If(heuY < 0) Then heuY = heuY * (-1)

 Return (heuX + heuY)

End Method


Dann probier ich gleich mal ob das per Pythagoras genauer wird.Danke^^


MfG Ska


EDIT: Klasse, jetzt funktioniert es richtig.Vielen vielen Dank!
Die Manhatten-Methode ist für den 4-Wege Suchalgorithmus anscheinend
zu ungenau!Mit Pythagoras und Float-Genauigkeit gehts!Vielen Dank! Very Happy
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Midimaster

 BeitragSo, Okt 25, 2009 16:21
Antworten mit Zitat
Benutzer-Profile anzeigen
Aber funktioniert so eine Methode denn noch, wenn man eine Mauer im Weg hat?

Beispiel:

Z=Ziel
A=Ausgangspunkt
x=Mauer

Code: [AUSKLAPPEN]

xxxxxxxxxxxxxxxxxxxxxx
x                    x
x         z          x
x                    x
x      xxxxxxxx      x
x                    x
x                    x
x         A          x
x                    x
xxxxxxxxxxxxxxxxxxxxxx

Firstdeathmaker

 BeitragSo, Okt 25, 2009 16:31
Antworten mit Zitat
Benutzer-Profile anzeigen
Mal ne dumme Frage, aber wieso wollt ihr da überhaupt den Pythagoras benutzen? x + y Differenz reicht doch aus wenn es nur rechts links runter rauf Bewegung gibt.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

Skabus

 BeitragSo, Okt 25, 2009 17:18
Antworten mit Zitat
Benutzer-Profile anzeigen
Firstdeathmaker hat Folgendes geschrieben:
Mal ne dumme Frage, aber wieso wollt ihr da überhaupt den Pythagoras benutzen? x + y Differenz reicht doch aus wenn es nur rechts links runter rauf Bewegung gibt.


Nein das reicht eben nicht.Das hatte ich ja vorher versucht.Aber an einigen Stellen führt das dazu, dass die Summe aus Kosten und Heueristik an 3 oder 4 Feldern gleich ist und der Suchalgorithmus willkürlich einen davon auswählt.In meinem Fall führte das zu sehr seltsamen Bewegungsverhalten...

Mit Pythagoras funktioniert es so wie es soll.

Midimaster: Keine Ahnung ob es für so einen Fall funktioniert.Für solche Fälle brauche in zum Glück
keinen Algorithmus.Außerdem ist ihm die Mauer sicherlich vollkommen schnuppe.Denn solange sich
der Start und Zielbereich innerhalb des Mauerquadrats befindet, ist es vollkommen egal ob da noch Mauern drum rum sind.

Dann verkleinert sich eben der Suchbereich entsprechend.Die Mapgrenzen sind quasi ja auch Mauern...
Aber es könnte evtl. sein dass er in Extremfällen keinen Weg findet oder keinen optimalen.


MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Midimaster

 BeitragSo, Okt 25, 2009 18:10
Antworten mit Zitat
Benutzer-Profile anzeigen
ich meine doch nicht die mauer drumrum, sonder die zwischen den objekten. euer algo würde direkt auf die mauer zuhalten, oder?

Noobody

 BeitragSo, Okt 25, 2009 18:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Der Algorithmus würde direkt auf die Mauer zusteuern, merken, dass da ein Hindernis ist und es nachher umschiffen (da die Wegkosten für durch die Mauer auf unendlich gesetzt werden).

Falls Diagonalen erlaubt sind, wird er irgendwann abbrechen, da er merkt, dass der diagonale Weg weniger kostspielig ist und den Diagonalen weiter untersuchen.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

n-Halbleiter

 BeitragSo, Okt 25, 2009 18:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Mit der Pythagoras-Distanz-Heuristik schon. Es gibt verschiedene andere Heuristiken, die dann vor der Mauer schon die Richtung ändern lassen, aber das ist an sich egal. xD

Auf jeden Fall wird dann spätestens bei der Mauer um die Mauer "gefahren", sofern die Hindernis-Erkennung drin ist. Wink

EDIT: Too late...
mfg, Calvin
Maschine: Intel Core2 Duo E6750, 4GB DDR2-Ram, ATI Radeon HD4850, Win 7 x64 und Ubuntu 12.04 64-Bit
Ploing!
Blog
"Die Seele einer jeden Ordnung ist ein großer Papierkorb." - Kurt Tucholsky (09.01.1890 - 21.12.1935)

Skabus

 BeitragSo, Okt 25, 2009 18:37
Antworten mit Zitat
Benutzer-Profile anzeigen
n-Halbleiter hat Folgendes geschrieben:

Auf jeden Fall wird dann spätestens bei der Mauer um die Mauer "gefahren", sofern die Hindernis-Erkennung drin ist. Wink


Naja wenn keine Hinderniserkennung drin ist, ist A* ja auch nen bissle für den A...rm, oder? Very Happy



MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group