Autor Beitrag
anno2007
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 68

Win 7, Ubuntu
Delphi XE
BeitragVerfasst: Di 03.06.08 14:47 
Hi,
ich hab ein echtes Problem, und hab kein Plan wie ich die Sache angehen soll.
Ich hab ein Spielfeld in einem 2 Dimensionalen Array eingetragen.
0 = Spielfeld.
1 = Blockade.
2 = Ziel.
(Das war meine Idee, wenn jemand eine viel leichtere kennt, fände ich es nett, wenn er mir die mitteilen könnte :D):

Moderiert von user profile iconNarses: Bild als Anhang hochgeladen (1)

Jetzt Würfele ich eine Zahl Beispielsweise 5 und starte mit meiner "Spielefigur" im Punkt 13,13.

Also:

Moderiert von user profile iconNarses: Bild als Anhang hochgeladen (2)
(Gelbe Punkte: alle Zugmöglichkeiten, bei der Würfelzahl 5)

So, jetzt will ich eine Prozedur schreiben, die mir alle diese Möglichkeiten ausgibt.

Das erste zu gehende Feld ist leicht mit if und then zu bestimmen, aber danach muss jedes weitere Feld aber wieder überprüft werden, ... .
Mit mehren Verschachteleten For-Schleifen müsste das doch zu lösen sein, aber ich kapiere nicht, wie ich die For-Schelifen verschachteln muss, bzw. wieviele verschachtelt werden müssen.

Ich hoffe mir kann irgendjemand auch nur Ansatzweise helfen.
Danke,
anno2007
Einloggen, um Attachments anzusehen!
BenBE
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 8721
Erhaltene Danke: 191

Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
BeitragVerfasst: Di 03.06.08 15:27 
user profile iconanno2007 hat folgendes geschrieben:
Hi,
ich hab ein echtes Problem,

Gibt's auch unechte Probleme?

user profile iconanno2007 hat folgendes geschrieben:
Ich hab ein Spielfeld in einem 2 Dimensionalen Array eingetragen.
0 = Spielfeld.
1 = Blockade.
2 = Ziel.
(Das war meine Idee, wenn jemand eine viel leichtere kennt, fände ich es nett, wenn er mir die mitteilen könnte :D):

Moderiert von user profile iconNarses: Bild als Anhang hochgeladen (1)

Jetzt Würfele ich eine Zahl Beispielsweise 5 und starte mit meiner "Spielefigur" im Punkt 13,13.

Also:

Moderiert von user profile iconNarses: Bild als Anhang hochgeladen (2)
(Gelbe Punkte: alle Zugmöglichkeiten, bei der Würfelzahl 5)

So, jetzt will ich eine Prozedur schreiben, die mir alle diese Möglichkeiten ausgibt.

Das erste zu gehende Feld ist leicht mit if und then zu bestimmen, aber danach muss jedes weitere Feld aber wieder überprüft werden, ... .
Mit mehren Verschachteleten For-Schleifen müsste das doch zu lösen sein, aber ich kapiere nicht, wie ich die For-Schelifen verschachteln muss, bzw. wieviele verschachtelt werden müssen.

Ich hoffe mir kann irgendjemand auch nur Ansatzweise helfen.
Danke,
anno2007


Typischer Fall für Breitensuche und Backtracking.
Bei DelphiGL gibt's einige Informationen dazu.

_________________
Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
hazard999
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 162

Win XP SP2
VS 2010 Ultimate, CC.Net, Unity, Pex, Moles, DevExpress eXpress App
BeitragVerfasst: Di 03.06.08 15:40 
Such mal nach A*

oder auch A Star oder A Stern genannt.

---Moderiert von user profile iconNarses: Beiträge zusammengefasst---

oder für die mathematiker.

suche den kürzesten weg s im gerichteten graphen g.

_________________
MOV EAX, Result;MOV BYTE PTR [EAX], $B9;MOV ECX, M.Data;MOV DWORD PTR [EAX+$1], ECX;MOV BYTE PTR [EAX+$5], $5A;MOV BYTE PTR [EAX+$6], $51;MOV BYTE PTR [EAX+$7], $52;MOV BYTE PTR [EAX+$8], $B9;MOV ECX, M.Code;MOV DWORD PTR [EAX+$9], ECX


Zuletzt bearbeitet von hazard999 am Di 03.06.08 15:51, insgesamt 1-mal bearbeitet
anno2007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 68

Win 7, Ubuntu
Delphi XE
BeitragVerfasst: Di 03.06.08 15:45 
Zitat:
Gibt's auch unechte Probleme?

Nein eigentlich nicht :D .

Ich hab mir jetzt mal im DGL-Wiki die Breitensuche angeschaut.
Rein Textlich würde ich auch sagen, dass ist genau das, was ich suche, aber ich habe keine Ahnung wie ich das in Quelltext umsetzten könnte. Mit der Sufu hab ich auch nicht wirklich was gefunden. Wäre es möglich, dass du mir ien Bespiel geben könntest. Ich bin nicht wirklich gut in Delphi, und hoffe, das ihr mir ein bisschen helfen könnt 8).

//Edit: Ok, hab mir wohl ein bischen viel Zeit genommen fürs antworten, werd ich mir auch noch anschauen :D .


Zuletzt bearbeitet von anno2007 am Di 03.06.08 15:47, insgesamt 1-mal bearbeitet
hazard999
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 162

Win XP SP2
VS 2010 Ultimate, CC.Net, Unity, Pex, Moles, DevExpress eXpress App
BeitragVerfasst: Di 03.06.08 15:45 
Das ganze als Graph im Speicher abzulegen ist teilweise einfacher.

würde ungefähr so ausschauen


Bsp 1:
ausblenden Quelltext
1:
2:
3:
4:
5:
    A
    |
D - S - B
    |
    C

In Beziehungen:

Punkt S hat die Wege nach
A
B
C
D

Bsp 2:
Kein möglicher Weg nach C (Blokade)
ausblenden Quelltext
1:
2:
3:
4:
5:
    A
    |
D - S - B
    
    C


In Beziehungen:

Punkt S hat die Wege nach
A
B
D

Und jetzt noch mit Kosten:
(Berg auf gehts schwerer)


ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
      A
      |
      3
      |
D - 1-S - 2-B
      
      C


In Beziehungen:

Punkt S hat die Wege nach
A Kostet 3 (bergauf)
B Kostet 2 (eben)
D Kostet 1 (bergab)

---Moderiert von user profile iconNarses: Beiträge zusammengefasst---

www.gamasutra.com/fe...0801/pathfinding.htm

_________________
MOV EAX, Result;MOV BYTE PTR [EAX], $B9;MOV ECX, M.Data;MOV DWORD PTR [EAX+$1], ECX;MOV BYTE PTR [EAX+$5], $5A;MOV BYTE PTR [EAX+$6], $51;MOV BYTE PTR [EAX+$7], $52;MOV BYTE PTR [EAX+$8], $B9;MOV ECX, M.Code;MOV DWORD PTR [EAX+$9], ECX


Zuletzt bearbeitet von hazard999 am Di 03.06.08 15:50, insgesamt 1-mal bearbeitet
anno2007 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 68

Win 7, Ubuntu
Delphi XE
BeitragVerfasst: Di 03.06.08 18:43 
Ok, dann danke ich euch ganz Herzlich, aber um solch "komplizierte" Sachen zu programmieren bin ich noch nicht fit genug, iuch versuceh das ganze jetzt auf eine andere Art zu lösen. :wink:

mfg
anno2007