Wegkosten

Übersicht

BlitzBasic

Allgemein

	Mattis_the_brain Betreff: Wegkosten	So, März 28, 2004 20:48 Antworten mit Zitat
Moin, also mein Problem is folgendes: -ich habe ein Array für eine Map -jedes Feld im Array zieht eine bestimmte Anzahl an Wegpunkten -ich habe ein beliebiges Ausgangsfeld in diesem Array Nun will all die Felder herausfinden die mit einer bestimmten anzahl von Wegpunkten zu ereichen sind (vom Ausgangsfeld) Please Help!

Mattis_the_brain

Betreff: Wegkosten

So, März 28, 2004 20:48
Antworten mit Zitat

Moin, also mein Problem is folgendes:
-ich habe ein Array für eine Map
-jedes Feld im Array zieht eine bestimmte Anzahl an Wegpunkten
-ich habe ein beliebiges Ausgangsfeld in diesem Array

Nun will all die Felder herausfinden die mit einer bestimmten anzahl von Wegpunkten zu ereichen sind (vom Ausgangsfeld)

Please Help!

	Blatolo	So, März 28, 2004 21:24 Antworten mit Zitat
köntest das ganze ja rekursiv lösen. Habe das mal bei einem A* Pathfinding gemacht. Habe das dort allerdings mit types gemacht. Hier mal mein Lösungsversuch mit arrays. Code: [AUSKLAPPEN] [EINKLAPPEN] Function betreten(x,y,gesamt_kosten) neue_kosten=feld(x,y,0)+gesamt_kosten If neue_kosten<max_kosten feld(x,y,1)=True betreten(x+1,y,neue_kosten) betreten(x+1,y+1,neue_kosten) betreten(x,y+1,neue_kosten) betreten(x-1,y+1,neue_kosten) betreten(x-1,y,neue_kosten) betreten(x-1,y-1,neue_kosten) betreten(x,y-1,neue_kosten) betreten(x+1,y-1,neue_kosten) EndIf End Function Einfach deinem Array eine Dimension hinzufügen. bei 0 in der 3. Dimension stehen die kosten dieses Feldes und in 1 ob es betretbar ist. Bevor diese Function das erste mal aufgerufen wird müssen alle felder auf nicht betretbar gestellt werden. hinterher kannst du dann ganz einfach prüfen ob betretbar. Ist weder optimiert noch garantiere ich dass es funktioniert. Ist nur ein Lösungsvorschlag und es gibt bestimmt bessere. Allerdings werden so auch nur Felder überprüft die überhaupt in Frage kommen denn wenn das vorherige Feld bereits nicht betretbar war dann das nächste erst recht nicht.

Blatolo

So, März 28, 2004 21:24
Antworten mit Zitat

köntest das ganze ja rekursiv lösen.
Habe das mal bei einem A* Pathfinding gemacht.
Habe das dort allerdings mit types gemacht.

Hier mal mein Lösungsversuch mit arrays.
Code: [AUSKLAPPEN]

Function betreten(x,y,gesamt_kosten)
neue_kosten=feld(x,y,0)+gesamt_kosten
If neue_kosten<max_kosten
   feld(x,y,1)=True

   betreten(x+1,y,neue_kosten)
   betreten(x+1,y+1,neue_kosten)
   betreten(x,y+1,neue_kosten)
   betreten(x-1,y+1,neue_kosten)
   betreten(x-1,y,neue_kosten)
   betreten(x-1,y-1,neue_kosten)
   betreten(x,y-1,neue_kosten)
   betreten(x+1,y-1,neue_kosten)
EndIf
End Function

Einfach deinem Array eine Dimension hinzufügen.
bei 0 in der 3. Dimension stehen die kosten dieses Feldes und in 1 ob es betretbar ist.
Bevor diese Function das erste mal aufgerufen wird müssen alle felder auf nicht betretbar gestellt werden.
hinterher kannst du dann ganz einfach prüfen ob betretbar.

Ist weder optimiert noch garantiere ich dass es funktioniert.
Ist nur ein Lösungsvorschlag und es gibt bestimmt bessere.
Allerdings werden so auch nur Felder überprüft die überhaupt in Frage kommen denn wenn das vorherige Feld bereits nicht betretbar war dann das nächste erst recht nicht.

	Omenaton_2	Mo, März 29, 2004 11:01 Antworten mit Zitat
Idee: Mach eine Rutine, wo alle Felder in einem bestimmen Umkreis deines Ausganspunktes herum nach und nach, schön der Reihe nach, in einer Schleife vorübergehend als Zielfeld für deine Pathfindingrutine angegeben werden. Wenn du von Pathfinding zurückkehrst, speichere die Feld-ID irgendwo, falls Path gefunden wurde und die Wegkosten die angegeben Kostengrenze nicht überschritten habe. Am Ende hast du dann eine Liste mit Feld-IDs, die alle deine Bedingungen erfüllen.

Omenaton_2

Mo, März 29, 2004 11:01
Antworten mit Zitat

Idee:

Mach eine Rutine, wo alle Felder in einem bestimmen Umkreis deines Ausganspunktes herum nach und nach, schön der Reihe nach, in einer Schleife vorübergehend als Zielfeld für deine Pathfindingrutine angegeben werden.

Wenn du von Pathfinding zurückkehrst, speichere die Feld-ID irgendwo, falls Path gefunden wurde und die Wegkosten die angegeben Kostengrenze nicht überschritten habe.
Am Ende hast du dann eine Liste mit Feld-IDs, die alle deine Bedingungen erfüllen.

	MasterK	Mo, März 29, 2004 13:12 Antworten mit Zitat
suche mal nach dem floyd-warshall-algorithmus, der sollte glaube ich das sein was du brauchst

MasterK

Mo, März 29, 2004 13:12
Antworten mit Zitat

suche mal nach dem floyd-warshall-algorithmus, der sollte glaube ich das sein was du brauchst

	soli	Mo, März 29, 2004 14:07 Antworten mit Zitat
Da ist ein Beispiel dafür drin. http://www.blitzbase.de/quellcode/pathfinding.zip
solitaire

soli

Mo, März 29, 2004 14:07
Antworten mit Zitat

Da ist ein Beispiel dafür drin.
http://www.blitzbase.de/quellcode/pathfinding.zip

solitaire

	Blatolo	Mo, März 29, 2004 14:18 Antworten mit Zitat
Er möchte ja nur wissen ob ein Feld mit einem bestimmten maximal kosten wert erreicht werden kann oder nicht. Er hat nicht gefragt wie man dann rauskriegt auf welchem weg man dieses Feld erreichen kann. Sonst könnte ich auch mal mein A* Pathfinding uppen.

Blatolo

Mo, März 29, 2004 14:18
Antworten mit Zitat

Er möchte ja nur wissen ob ein Feld mit einem bestimmten maximal kosten wert erreicht werden kann oder nicht.
Er hat nicht gefragt wie man dann rauskriegt auf welchem weg man dieses Feld erreichen kann.
Sonst könnte ich auch mal mein A* Pathfinding uppen.

	TheShadow Moderator	Mo, März 29, 2004 17:31 Antworten mit Zitat
hm - das geht nicht so einfach... weil wenn du dich auf einen punkt fixierst, dann kannst du den weg sehr gut "optimieren" wenn du einfach flood-fill nimmst, dann wird es "unoptimiert"...
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Mo, März 29, 2004 17:31
Antworten mit Zitat

hm - das geht nicht so einfach... weil

wenn du dich auf einen punkt fixierst, dann kannst du den weg sehr gut "optimieren"

wenn du einfach flood-fill nimmst, dann wird es "unoptimiert"...

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	dubitat	Mo, März 29, 2004 19:11 Antworten mit Zitat
werden die kosten vorher berechnet oder nicht? ach sinnloser post weil ich keine variable von dir kenne und das jetzt so nícht machen kann![/code]
Erare humanum est - Irren ist Menschlich

dubitat

Mo, März 29, 2004 19:11
Antworten mit Zitat

werden die kosten vorher berechnet oder nicht? ach sinnloser post weil ich keine variable von dir kenne und das jetzt so nícht machen kann![/code]

Erare humanum est - Irren ist Menschlich

	Mattis_the_brain	Di, März 30, 2004 14:27 Antworten mit Zitat
Also ich habe wie schon gesagt ein Array mit den außmaßen von 10;10 in so und jetzt kann jedes Feld in diesem Array die Werte 1 bis 3 annehmen. Dieser Wert ist die Menge an Wegpunkten die zum betreten dieses Feldes benötigt werden. Jetzt sagen wir mal einfach das wir vom Punkt 5;5 ausgehen... so jetzt möchte ich aber nicht wisen wie ich zu einem ganz bestimmten Punkt komme sondern welche Felder ich mit einer bestimmten Menge von Wegpunkten alles ereichen kann.

Mattis_the_brain

Di, März 30, 2004 14:27
Antworten mit Zitat

Also ich habe wie schon gesagt ein Array mit den außmaßen von 10;10 in so und jetzt kann jedes Feld in diesem Array die Werte 1 bis 3 annehmen.
Dieser Wert ist die Menge an Wegpunkten die zum betreten dieses Feldes benötigt werden. Jetzt sagen wir mal einfach das wir vom Punkt 5;5 ausgehen... so jetzt möchte ich aber nicht wisen wie ich zu einem ganz bestimmten Punkt komme sondern welche Felder ich mit einer bestimmten Menge von Wegpunkten alles ereichen kann. Rolling Eyes

	BIG BUG	Di, März 30, 2004 15:57 Antworten mit Zitat
Also doch sowas wie Blatolos Lösung...(hier nur in 4 richtungen aber noch ein wenig optimiert): Code: [AUSKLAPPEN] [EINKLAPPEN] Function ermittle_betretbar(x,y,Wegpunkte) neue_WP=Wegpunkte - feld_kosten(x,y) if neue_kosten < betretbar(x,y)-1 return ;schon ermittelt If neue_kosten < 0 then return ;Wegpunkte aufgebraucht If x < 0 or y < 0 or x > MAX_X or y > MAX_Y then return ;Grenzen betretbar(x,y) = neue_kosten+1 ermittle_betretbar(x+1,y, neue_WP) ermittle_betretbar(x,y+1, neue_WP) ermittle_betretbar(x-1,y, neue_WP) ermittle_betretbar(x,y-1, neue_WP) End Function In dem Feld betretbar steht nach dem Ausführen dieser Funktion, wieviele Aktionspunkte pro Zielpunkt nach dem betreten noch übrig sind(+1). 0 heisst nicht betretbar. Wie bei Incubation, falls das jemand kennt...
B3D-Exporter für Cinema4D!(V1.4) MD2-Exporter für Cinema4D!(final)

BIG BUG

Di, März 30, 2004 15:57
Antworten mit Zitat

Also doch sowas wie Blatolos Lösung...(hier nur in 4 richtungen aber noch ein wenig optimiert):
Code: [AUSKLAPPEN]

Function ermittle_betretbar(x,y,Wegpunkte)
neue_WP=Wegpunkte - feld_kosten(x,y)

if neue_kosten < betretbar(x,y)-1 return ;schon ermittelt
If neue_kosten < 0 then return ;Wegpunkte aufgebraucht
If x < 0 or y < 0 or x > MAX_X or y > MAX_Y then return ;Grenzen

betretbar(x,y) = neue_kosten+1
ermittle_betretbar(x+1,y, neue_WP)
ermittle_betretbar(x,y+1, neue_WP)
ermittle_betretbar(x-1,y, neue_WP)
ermittle_betretbar(x,y-1, neue_WP)

End Function

In dem Feld betretbar steht nach dem Ausführen dieser Funktion, wieviele Aktionspunkte pro Zielpunkt nach dem betreten noch übrig sind(+1). 0 heisst nicht betretbar. Wie bei Incubation, falls das jemand kennt...

B3D-Exporter für Cinema4D!(V1.4)
MD2-Exporter für Cinema4D!(final)

	Ava Gast	Di, März 30, 2004 16:20 Antworten mit Zitat
Ich hab Dir mal eben kurz ein ganz simples Beispiel geschrieben. Es ist nicht besonders schön, nicht besonders übersichtlich aber vielleicht hilft es Dir ja trotzdem irgendwie weiter!? (so als kleiner Denkanstoss) Code: [AUSKLAPPEN] [EINKLAPPEN] Graphics 800, 600, 16, 2 Global mapWidth = 32 Global mapHeight = 32 Global tileSize = 32 Dim mapMove(mapWidth - 1, mapHeight - 1) Dim moveCost(mapWidth - 1, mapHeight - 1) For x = 0 To mapWidth - 1 For y = 0 To mapHeight - 1 moveCost(x, y) = Rand(1, 5) Next Next Repeat SetBuffer BackBuffer() : Cls scanMap(Int(Floor(MouseX()/tileSize)), Int(Floor(MouseY()/tileSize))) drawMap() Color 255, 0, 0 : Plot MouseX(), MouseY() Flip Until KeyHit(1) : End Function scanMap(x, y, move = 12, refresh = True) If move < 1 Then Return False If x < 0 Or x > mapWidth - 1 Then Return False If y < 0 Or y > mapHeight - 1 Then Return False If KeyHit(1) Then End If refresh Then Dim mapMove(mapWidth - 1, mapHeight - 1) If move <= mapMove(x, y) Then Return False mapMove(x, y) = move move = move - moveCost(x, y) If move < 1 Then Return False scanMap(x-1,y-1,move-1, False) scanMap(x,y-1,move, False) scanMap(x+1,y-1,move-1, False) scanMap(x-1,y,move, False) scanMap(x+1,y,move, False) scanMap(x-1,y+1,move-1, False) scanMap(x,y+1,move, False) scanMap(x+1,y+1,move-1, False) Return True End Function Function drawMap() For x = 0 To mapWidth - 1 For y = 0 To mapHeight - 1 col = moveCost(x, y) * 25 Color col, col, col Rect x * tileSize, y * tileSize, tileSize - 1, tileSize - 1, False If mapMove(x, y) > 0 Then Color 255, 0, 0 : Text (x + 0.5) * tileSize, (y + 0.5) * tileSize, mapMove(x, y), True, True Next Next End Function

Ava

Gast

Di, März 30, 2004 16:20
Antworten mit Zitat

Ich hab Dir mal eben kurz ein ganz simples Beispiel geschrieben. Es ist nicht besonders schön, nicht besonders übersichtlich Rolling Eyes

aber vielleicht hilft es Dir ja trotzdem irgendwie weiter!? (so als kleiner Denkanstoss)
Code: [AUSKLAPPEN]

Graphics 800, 600, 16, 2

Global mapWidth = 32
Global mapHeight = 32
Global tileSize = 32
Dim mapMove(mapWidth - 1, mapHeight - 1)
Dim moveCost(mapWidth - 1, mapHeight - 1)

For x = 0 To mapWidth - 1
For y = 0 To mapHeight - 1
moveCost(x, y) = Rand(1, 5)
Next
Next

Repeat
SetBuffer BackBuffer() : Cls
scanMap(Int(Floor(MouseX()/tileSize)), Int(Floor(MouseY()/tileSize)))
drawMap()
Color 255, 0, 0 : Plot MouseX(), MouseY()
Flip
Until KeyHit(1) : End

Function scanMap(x, y, move = 12, refresh = True)
If move < 1 Then Return False
If x < 0 Or x > mapWidth - 1 Then Return False
If y < 0 Or y > mapHeight - 1 Then Return False
If KeyHit(1) Then End
If refresh Then Dim mapMove(mapWidth - 1, mapHeight - 1)
If move <= mapMove(x, y) Then Return False
mapMove(x, y) = move
move = move - moveCost(x, y)
If move < 1 Then Return False
scanMap(x-1,y-1,move-1, False)
scanMap(x,y-1,move, False)
scanMap(x+1,y-1,move-1, False)
scanMap(x-1,y,move, False)
scanMap(x+1,y,move, False)
scanMap(x-1,y+1,move-1, False)
scanMap(x,y+1,move, False)
scanMap(x+1,y+1,move-1, False)
Return True
End Function

Function drawMap()
For x = 0 To mapWidth - 1
For y = 0 To mapHeight - 1
col = moveCost(x, y) * 25
Color col, col, col
Rect x * tileSize, y * tileSize, tileSize - 1, tileSize - 1, False
If mapMove(x, y) > 0 Then Color 255, 0, 0 : Text (x + 0.5) * tileSize, (y + 0.5) * tileSize, mapMove(x, y), True, True
Next
Next
End Function

	Mattis_the_brain	Di, März 30, 2004 16:30 Antworten mit Zitat
Thx @Ava genau das hab ich gesucht. Muss nur noch ne kleinigkeit abändern aber an sonsten funzt das genau so wies soll

Mattis_the_brain

Di, März 30, 2004 16:30
Antworten mit Zitat

Thx @Ava genau das hab ich gesucht. Muss nur noch ne kleinigkeit abändern aber an sonsten funzt das genau so wies soll Very Happy

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Wegkosten

Betreff: Wegkosten

Ava