Profil | Mitglieder | Registrieren | Start | Suche


PHP-Support.de » Programmierung » PHP & MySQL » Browsergames » A*-Algorithmus in PHP    » Hallo Gast [Login | Registrieren]

Neues Thema | Antworten   

Autor Beitrag
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
     A*-Algorithmus in PHP Zitat | Bearbeiten

Hallo,

sagt mal, hat jemand von euch sich schon einmal mit Wegfindungsalgorithmen beschäftigt?

Ich will mein Browsergame realistischer machen und statt dem einfachen Vektorverfahren den A*-Algorithmus verwenden, da dieser auch Hindernisse wie Wasser, Land, Felsen, Häuser, etc. berücksichtigt.

Habe schon ein, zwei Beispiele in JAVA und C/C++ gefunden, jedoch verwenden diese Zeiger und andere Sprachkontrukte, die nicht mit PHP möglich sind.

Kennt jemand bereits einen Ansatz von A* in PHP, bzw. allgemeingültige und sprachenunabhängige Struktogramme?


Gruß, Dennis

www.xentity.de
30.10.2007, 14:55 Profil | PM | E-Mail  
Teralios
Moderator
Perfekter User


Dabei seit: 18.09.2005
Herkunft: Berlin
Posts: 2542
      Zitat | Bearbeiten

Kurz noch mal dazu.
PHP ist eine Scriptsprache die eigentlich für Spiele nicht gedacht ist, und zwar mächtig ist, aber eben nicht so komplex ist, wie eben eine Programmiersprache. Du wirst eventuell selbst etwas entwickeln müssen, aber realismus kannst du von einem... naja einer Scriptsprache wie PHP kaum erwarten, da sie Serverseitig ausgef+ührt wird, und nichts in Echtzeit zum Zeitpunkt gemacht wird, was aber bei Spielen die so arbeiten doch wichtig ist.


30.10.2007, 17:26 Profil | PM | E-Mail  
Andavos
Administrator
Foren-Gott


Dabei seit: 30.11.2003
Herkunft:
Posts: 6264
      Zitat | Bearbeiten

Hallo,
hab meine Facharbeit darüber geschrieben. Sofern ich mal wieder Zeit habe (alles ganz schön stressig) kann ich die ja mal online stellen


www.php-einfach.de, PHP lernen leicht gemacht
www.webhosterwissen.de, Webhosting-Vergleich



30.10.2007, 18:12 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
      Zitat | Bearbeiten

[quote]Orginal von GameR
Kurz noch mal dazu.
PHP ist eine Scriptsprache die eigentlich für Spiele nicht gedacht ist, und zwar mächtig ist, aber eben nicht so komplex ist, wie eben eine Programmiersprache. Du wirst eventuell selbst etwas entwickeln müssen, aber realismus kannst du von einem... naja einer Scriptsprache wie PHP kaum erwarten, da sie Serverseitig ausgef+ührt wird, und nichts in Echtzeit zum Zeitpunkt gemacht wird, was aber bei Spielen die so arbeiten doch wichtig ist.
[/quote]

Hi GameR,
bitte nimm dies nicht als Meckern, sondern nur als Klarstellung.
Ich glaube, ich bin mir ziemlich sicher zu meinen, was die Unterschiede zwischen client- und serverseitige Programmiersprachen sind, bzw. welche Vor- und Nachteile ASP, PHP, Ruby, JavaScript und Java, usw. im Bereich von Webanwendungen haben.
Als Fachinformatiker/SI ganz kurz vor der Prüfung ist das teilweise sogar mein Beruf.

Wenn man sich nicht nur auf PHP konzentriert, dann ist Realismus durchaus erreichbar. Ich möchte da nur an erfolgreiche Browsergames wie die unter der Flagge von gamed.de oder an Travian (BG des Jahres 2006) erinnern.

Und schau mal, ich hatte u.a. nach Struktogramme gefragt, die evtl. im Unterricht, in Vorlesungen verwendet wurden. Sprich: auf eine Not-Plus-Ultra-Lösung habe ich nicht gewartet.
Ich wollte lediglich nicht das Rad neu erfinden... ein PAP zu erstellen, mehrere Stunden Feierabend ins Grübeln stecken und am Ende sagt einer: "... Hatte da mal was im Unterricht..." - Sorry!

Des weiteren finde ich, dass Foren dazu da sind, dass man nach "Nachdenken" und "Onkel Google" als nächstes "Die Wissenden" fragen darf. Andavos wird sich über massig Klicks freuen, wenn das Forum unter "AStar PHP" auf Platz 1 steht(Gibt es noch nicht) und nicht jemand als erste Antwort sofort ein wenig genervt reagiert.

Über eine angeregte Diskussion über die Möglichkeiten und Erfahrungen eines solchen Wegfindung-Algorithmus' (ich denke da an Performance bei Karten von 1000x1000 Quadraten oder die Kartenerstellung) würde ich mich sehr viel mehr freuen.


Gruß, Dennis

www.xentity.de

Post wurde schon 1x editiert, das letzte mal am 30.10.2007 um 19:04 von Dennis
30.10.2007, 19:03 Profil | PM | E-Mail  
Gandonit
Mitglied
Guter User


Dabei seit: 06.04.2007
Herkunft:
Posts: 436
      Zitat | Bearbeiten

Andavos, das wäre toll. Würde mich interessieren...
lg


30.10.2007, 19:09 Profil | PM | E-Mail  
Teralios
Moderator
Perfekter User


Dabei seit: 18.09.2005
Herkunft: Berlin
Posts: 2542
      Zitat | Bearbeiten

Ich sollte nach dem Sport keine Beiträge schreiben, da les ich nicht wirklich nach.

Das ist sogar unter PHP möglich. *sich auf den Schädelhaut.*

Ich hab jetzt auch mal gegooglet, aber bis auf die ganzen verweise auf andere Links nichts gefunden.

So per Überlegung, ist es erst mal die Frage, wie übergebe ich den Graphen, darauf die Werte und ob es begehbar ist oder nicht. Startpunkt und Endpunkt eben so.

Ich glaube auch schwerer wird die heuristik, der rest dürfte aber dann wieder einfacher werden.
Mhhh.....
Müsste man mal genauer nachdenken, aber Schleifen sind ja vorhanden.


Also bis jetzt kurz: So wie es aussieht wirst du entweder ein bereits vorhandenes C++ oder in einer anderen Sprache vorhanden Script umschreiben müssen und an PHP Anpassen oder ein neues entwickeln müssen.


30.10.2007, 22:46 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
      Zitat | Bearbeiten

[quote]Orginal von GameR
Das ist sogar unter PHP möglich.
[/quote]

Glaub mir, sonst hätte ich wirklich nicht gefragt

Einen Dozenten habe ich soweit angesteckt, dass er das sogar mit einer MySQL-Prozedur auf DB-Ebene schaffen will, aber ich glaube nicht daran, dass MySQL so mächtig ist. Wenn er es schafft, dann poste ich es hier.

Es geht mir auch nicht wirklich um die Darstellung dieser Pfade, sondern um die Berechnung der Pfadkosten, bzw. die Länge der Wege.
(Auf einer Karte kann man ja mal versuchen den Seeweg von Hamburg nach Lübeck zu berechnen, ohne den Nord-Ostsee-Kanal zu nutzen.)

Der A*-Algorithmus kann das. Eine Möglichkeit des Karteneinlesens habe ich schon mit einem "Image To ASCII"-Konverter gefunden. Das ist dann ziemlich trivial.

Das Umschreiben wäre natürlich der letzte Schritt.


Gruß, Dennis

www.xentity.de
30.10.2007, 23:18 Profil | PM | E-Mail  
Teralios
Moderator
Perfekter User


Dabei seit: 18.09.2005
Herkunft: Berlin
Posts: 2542
      Zitat | Bearbeiten

[quote]Orginal von Dennis
[quote]Orginal von GameR
Das ist sogar unter PHP möglich.
[/quote]

Glaub mir, sonst hätte ich wirklich nicht gefragt

Einen Dozenten habe ich soweit angesteckt, dass er das sogar mit einer MySQL-Prozedur auf DB-Ebene schaffen will, aber ich glaube nicht daran, dass MySQL so mächtig ist. Wenn er es schafft, dann poste ich es hier.

Es geht mir auch nicht wirklich um die Darstellung dieser Pfade, sondern um die Berechnung der Pfadkosten, bzw. die Länge der Wege.
(Auf einer Karte kann man ja mal versuchen den Seeweg von Hamburg nach Lübeck zu berechnen, ohne den Nord-Ostsee-Kanal zu nutzen.)

Der A*-Algorithmus kann das. Eine Möglichkeit des Karteneinlesens habe ich schon mit einem "Image To ASCII"-Konverter gefunden. Das ist dann ziemlich trivial.

Das Umschreiben wäre natürlich der letzte Schritt.
[/quote]
Du musst im endefekt, wenn du die Karte als Vierecke einbaust nur ein Array übergeben:

array("x" => 5, "y" => 5);
Als zweites wert müsste man ja dann Start und endp8unkt eben so als array überegben, auch mit einer X und Y Kordinate, endpunkt genau so.

Was schwerer werden würde, wäre die Übergabe der nicht passiertbaren gebiete, aber das wäre auch wieder nur ein Array.

Ich glaube das schwäreste wäre die Heuristik.

Wie berechnet man die am besten...
Manhattan... Denn mit der steht und fällt es, wie gut der A* ist.




Post wurde schon 1x editiert, das letzte mal am 31.10.2007 um 11:15 von Teralios
31.10.2007, 09:18 Profil | PM | E-Mail  
Andavos
Administrator
Foren-Gott


Dabei seit: 30.11.2003
Herkunft:
Posts: 6264
      Zitat | Bearbeiten

Hallo,
so habs mal hochgeladen, viel Spaß beim lesen:

Download

(Hoffe es gefällt euch)


www.php-einfach.de, PHP lernen leicht gemacht
www.webhosterwissen.de, Webhosting-Vergleich





Post wurde schon 1x editiert, das letzte mal am 31.10.2007 um 18:10 von Andavos
31.10.2007, 18:08 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
      Zitat | Bearbeiten

[quote]Orginal von Andavos
Hallo,
so habs mal hochgeladen, viel Spaß beim lesen:

Download

(Hoffe es gefällt euch)
[/quote]

Vielen Dank, ich setzt mich gleich mal ran.

[quote]Orginal von GameR
Du musst im endefekt, wenn du die Karte als Vierecke einbaust nur ein Array übergeben:

array("x" => 5, "y" => 5);
Als zweites wert müsste man ja dann Start und endp8unkt eben so als array überegben, auch mit einer X und Y Kordinate, endpunkt genau so.

Was schwerer werden würde, wäre die Übergabe der nicht passiertbaren gebiete, aber das wäre auch wieder nur ein Array.

Ich glaube das schwäreste wäre die Heuristik.

Wie berechnet man die am besten...
Manhattan... Denn mit der steht und fällt es, wie gut der A* ist.
[/quote]

Die Karte würde ich als 2D-Array erstellen, entweder 0 (begehbar) oder 1 (unbegehbar). Da die Indizies auch Integer wären, kann man die zur Navigation nehmen.

Schwierig fand ich erstmal die Speicherung des erlangten Wissens.

Die Manhatten-Heuristik ist nicht schwer, relativ simpel. Gehst einfach in der Horizontalen bis der x-Wert gleich dem Zielwert ist, dann in der Vertikalen bis der y-Wert gleich dem Zielwert ist. Diese Anzahl der Schritte addierst du und hast den heuristischen Entfernungswert. Diese Form der Heuristik reicht erstmal aus, die könnte man später durch einen aufwändigeren Algorithmus austauschen.
EDIT: Oder wie Andavos es gemacht hat: Satz des Pythagoras, um den direkten Weg anzugeben. In diesem Fall ist der geschätzte Wert stets kleiner als der echte Weg. Manhattans Wert ist meist auch kleiner, aber näher am echten Wert dran. Faustregel: je näher am eigentlich Wert desto schneller die Wegefindung

So, jetzt erstmal schauen, was Andavos da gezaubert hat Bin ja schon ganz aufgeregt


Gruß, Dennis

www.xentity.de

Post wurde schon 2x editiert, das letzte mal am 31.10.2007 um 20:55 von Dennis
31.10.2007, 20:18 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
      Zitat | Bearbeiten

So, bin mit der Aufarbeitung durch...

@ Andavos
Erstmal ein großes "Respekt" für die Leistung, dann bekommst du noch ein "Neid" für den Info-LK (hätte auch gern die Möglichkeit gehabt) und ein Danke für das Bereitstellen deiner Arbeit, inkl.den Algorithmus in Wort und Pseudocode.

Ist aber so nicht ganz, wie ich es suche, bzw. wie ich es vorhabe. Du hast ja die dynamische Wegefindung wunderbar umgesetzt, doch die dynamische Routenfindung, für die der A* ausgezeichnet ist, hast du bereits selbst vorbearbeitet(Tabelle verbindung).

Ich hoffe, dass ich dank deiner Arbeit dies noch umsetzen kann.

P.S.: Kommst du eigentlich aus Potsdam?
P.S.: Kannst du bitte den "Gast"-Beitrag löschen - sorry


Gruß, Dennis

www.xentity.de
01.11.2007, 15:50 Profil | PM | E-Mail  
Teralios
Moderator
Perfekter User


Dabei seit: 18.09.2005
Herkunft: Berlin
Posts: 2542
      Zitat | Bearbeiten

[quote]Orginal von Dennis
So, bin mit der Aufarbeitung durch...

@ Andavos
Erstmal ein großes "Respekt" für die Leistung, dann bekommst du noch ein "Neid" für den Info-LK (hätte auch gern die Möglichkeit gehabt) und ein Danke für das Bereitstellen deiner Arbeit, inkl.den Algorithmus in Wort und Pseudocode.

Ist aber so nicht ganz, wie ich es suche, bzw. wie ich es vorhabe. Du hast ja die dynamische Wegefindung wunderbar umgesetzt, doch die dynamische Routenfindung, für die der A* ausgezeichnet ist, hast du bereits selbst vorbearbeitet(Tabelle verbindung).

Ich hoffe, dass ich dank deiner Arbeit dies noch umsetzen kann.

P.S.: Kommst du eigentlich aus Potsdam?
P.S.: Kannst du bitte den "Gast"-Beitrag löschen - sorry
[/quote]
Der A* ist auch dafür gedacht.

Was du angehst ist wirklich diese Routenfindung auch auf Knoten bassieren, so wie dort.

Ich glaube ein guten Ansatz wenn du evnt schon gefunden hast. http://www.policyalmanac.org/games/aStarTutorial_de.html

Glaub das kommt an den, den man als spiel haben will auch nahe ran, würde aber auch mit einer Datenbank so gehen, also ist deml, finde ich von Anvados ähnlich, nur das ich mehr knoten mit einander verbinde.


01.11.2007, 16:06 Profil | PM | E-Mail  
Andavos
Administrator
Foren-Gott


Dabei seit: 30.11.2003
Herkunft:
Posts: 6264
      Zitat | Bearbeiten

Hallo,
also eine super Anleitung findet man hier:
A* Pfadfindung für Anfänger

Dies eignet sich besonders für Spiele.

Dies hab ich mal nach dem Tutorial umgesetzt und folgenden C-Codes geschrieben:

 Code 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
//A*, nur Bewegung in die 4 Himmelsrichtungen
#include <stdio.h>
#include <conio.h>

#define LEER ' '
#define WALL '#'    
#define START 'S'
#define ZIEL 'Z'  
#define WALK 'X'

#define ROWS 10
#define COLUMS 10
                
                  


#ifdef __unix__
    #define clrscr() printf("\x1B[2J")
    #define SYSTEM_ENDE
#elif __BORLANDC__ && __MSDOS__
    #include <conio.h> 
    #define SYSTEM_ENDE fflush(stdin); getchar();
#elif __WIN32__ || _MSC_VER
    #define clrscr() system("cls")  
    #define SYSTEM_ENDE fflush(stdin); getchar();
#else
    #define clrscr() printf("clrscr() - Fehler!!\n")
    #define SYSTEM_ENDE
#endif

struct point_tb {
   int x;
   int y; 
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int f; //Gesamt
   int parent; //Vorgänger-Objekt
};

struct point {
   int x; //Colum
   int y; //Row
};

//Punkte zu einer Tabelle hinzufügen
struct point *add_close(struct point point,struct point *close, int *nr);
int *add_open(int *open, int pnr, int bewegung, int *nr);
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr);

//Überprüfen ob Punkt in Tabelle vorhanden
int is_open(struct point point, int *open);
int is_close(struct point point, struct point *close);

//Punkte finden
void find_neigh(struct point point,struct point neigh[4]); //Nachbaren finden
int find_next(int *open); //Nächsten Punkt wählen

//Entfernung schätzen
int schaetz(struct point point, struct point ziel);

//Ziel gefunden => Pfad ausgeben
void ziel_found(struct point point,int parent);


void print_field(void); //Spielfeld ausgeben
struct point find(char c); //Koordinate zu c finden




        
        
//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze[ROWS][COLUMS] = {   {'S','#',' ','#',' ',' ',' ',' ',' ',' '}, //0
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //1
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //2
                              {' ','#',' ',' ',' ','#',' ','#',' ',' '}, //3
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //4   ROW | y
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //5
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //6
                              {' ','#',' ','#',' ','#',' ',' ',' ',' '}, //7
                              {' ','#',' ','#',' ','#',' ','#',' ','#'}, //8
                              {' ',' ',' ','#',' ',' ',' ','#',' ','Z'} }; //9;

                        
                        
                        
//                        0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze2[10][10] = {   {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //0
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //1
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //2
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //3
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //4   ROW | y
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //5
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //6
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //7
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //8
                        {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '} }; //9
                               


struct point_tb pt[ROWS*COLUMS+1]; //Tabelle mit allen Punkten
int n_open = 1; //Anzahl der Elemente in Open
int schritte = 0; //Anzahl an Durchläufen





/*********************************************************
                  Funktionen
**********************************************************/




//Überprüfte Points in Close eintragen
struct point *add_close(struct point point,struct point *close, int *nr) { 
   struct point end = {-1,-1};
     
   close = (struct point *) realloc(close,((*nr)+2)*sizeof(struct point));
   close[*nr] = point;
   close[(*nr)+1] = end;
   
   (*nr)++;   
   
   return close;
}


//Überprüfte Points in Open eintragen
int *add_open(int *open, int pnr, int bewegung, int *nr) { 
   int g_tmp;
     
   open = (int *) realloc(open,((*nr)+2)*sizeof(int));
   g_tmp = pt[pnr].g;
   
   if(bewegung < g_tmp) {
      pt[pnr].g = bewegung;
      pt[pnr].f = pt[pnr].g+pt[pnr].h;
   }
   
   open[*nr] = pnr;
   open[(*nr)+1] = -1;
      
   
   (*nr)++;
   n_open++;
   
   return open;
}


//Punkt zur Punktetabelle hinzufügen
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr) {
   pt[*pnr].x = point.x;
   pt[*pnr].y = point.y; 
   pt[*pnr].parent = parent;
   pt[*pnr].g = bewegkost;
   pt[*pnr].h = schaetzkost;
   pt[*pnr].f = bewegkost+schaetzkost;
   
   //Endpunkt
   pt[(*pnr)+1].x = -1;
   pt[(*pnr)+1].y = -1; 
   
   (*pnr)++;
}






//Überprüft ob Punkt auf Open-Liste ist
int is_open(struct point point, int *open) {
   int i;
   
   for(i=0;pt[i].x != -1;i++) {    
      if(pt[i].x == point.x && pt[i].y == point.y)
         return 1;
   }
   
   return 0;
}


  
//Überprüft ob Punkt auf Close-Liste ist
int is_close(struct point point, struct point *close) {
   int i;
  
   for(i=0;close[i].x != NULL;i++)  {
      if(close[i].x == point.x && close[i].y == point.y) {         
         return 1;
      }
         
   } 
   
   return 0;
}





//Findet Nachbaren
void find_neigh(struct point point,struct point neigh[4]) {
   int colum = point.x;
   int row = point.y;     
   int i=0;
     
   for(i=0;i<4;i++) {
      neigh[i].x = -1;
      neigh[i].y = -1;
   }
   i=0;
         
     
   if((colum+1) < COLUMS && maze[row][colum+1] != WALL) { //Rechts davon
      neigh[i].y = row;
      neigh[i++].x = colum+1;      
   }    
   
     
   if((colum-1) >= 0 && maze[row][colum-1] != WALL) {  //Links davon
      neigh[i].y = row;
      neigh[i++].x = colum-1;      
   }
     
     
   if((row+1) < ROWS && maze[row+1][colum] != WALL) { //Darunter
      neigh[i].y = row+1;
      neigh[i++].x = colum;      
   }
   
   if((row-1) >= 0 && maze[row-1][colum] != WALL) { //Oberhalb
      neigh[i].y = row-1;
      neigh[i++].x = colum;      
   }   
         
}

//Findet den nächsten Knoten
int find_next(int *open) {
   int i;
   int next=-1;
   int tmp = -1;
   int i_tmp;
   
   
   for(i=0;open[i] != -1;i++) {      
      if(open[i] != -2 && (tmp == -1 || pt[open[i]].f < tmp) ) {
         next = open[i];     
         tmp = pt[next].f;
         i_tmp = i;
      } 
   }
   
   //Elemente auf -2 setzen = Gelöscht
   open[i_tmp] = -2;
   n_open--;
   
   //printf("Next: %d   %d|%d  f:%d  g:%d\n",next,pt[next].x,pt[next].y,pt[next].f,pt[next].g);
   
   return next;
}




//Entfernung Schätzen
int schaetz(struct point point, struct point ziel) {
   int colum = point.x;
   int row = point.y;
   int dif_colum = (colum > ziel.x) ? colum-ziel.x : ziel.x-colum;
   int dif_row = (row > ziel.y) ? row-ziel.y : ziel.y-row;
   
   return (dif_row+dif_colum);   
}





void ziel_found(struct point point,int parent) {
   int i=0;
               
   //Weg Einzeichen
   while(pt[parent].parent != -1) {
      maze[pt[parent].y][pt[parent].x] = WALK;
      parent = pt[parent].parent;
   }
   
   maze[pt[parent].y][pt[parent].x] = START; //Start
   maze[point.y][point.x] = ZIEL; //Ziel
   
   print_field(); 
   printf("\n Rechenschritte: %d \n",schritte);
   
   getch();
   exit(0);
}
   





void print_field(void) {
   int i,j;
   clrscr();
   
   //Head-Ausgeben
   printf("\n    ");   
   for(i=0;i<COLUMS;i++)
      printf("%2d  ",i);   
      
   printf("\n   ");   
   for(i=0;i<COLUMS;i++)
      printf("+---");
   
   printf("+\n");
   

   for(i = 0; i < ROWS; i++) {
      printf("%2d |",i);
      for(j=0; j < COLUMS; j++) {
         printf(" %c |",maze[i][j]);
      } 
      
      printf("\n   ");
      for(j=0;j<COLUMS;j++)
         printf("+---");
      
      printf("+\n");      
   } 
}

  
struct point find(char c) {
   struct point point;
   int i,j,check=0;
   
   
   for(i=0;i<10 && check == 0;i++) {
      for(j=0;j<10;j++) {
         if(maze[i][j] == c) {
            check = 1;
            point.x = j;
            point.y = i;
         }
      }
   }
   
   return point;
}
             
      
      
/*******************************************************************************
                               MAIN
********************************************************************************/                

int main(void) {
   print_field();  
    
   struct point start = find(START);//Start
   struct point ziel = find(ZIEL); //Ziel
   struct point neigh[4]; //Nachbarn
   struct point next_node = start; //Nächster Knoten

 
   maze[start.y][start.x] = LEER;
   maze[ziel.y][ziel.x] = LEER;      
   
   int i=0;
   int pnr = 0; //Anzahl der Punkte in pt
   int parent = 0; //Vorgänger objetkt
   
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int rueck = 1; //Zurueckgelegte Kosten
   
   //Close-Liste
   struct point *close = (struct point *) malloc(sizeof(struct point));
   int nr_close = 0;
   
   //Open-Liste
   int *open = (int *) malloc(sizeof(int));
   int nr_open = 0;
   
   open[0] = -1;
   
   //Füge Start zur Punktetabelle hinzu
   add_point(next_node,-1,0,schaetz(start,ziel),&pnr); 
   
   
   do {      
      schritte++;
      //Füge Start in Close-Tabelle
      close = add_close(next_node,close,&nr_close);
       
      //Finde Nachbaren 
      find_neigh(next_node,neigh);
       
      for(i=0;i<4 && neigh[i].x != -1;i++) {           
         if(neigh[i].x == ziel.x && neigh[i].y == ziel.y)
            ziel_found(neigh[i],parent);           
               
         if(is_close(neigh[i],close)) 
            continue;
            
         if(!is_open(neigh[i],open)) {            
            h = schaetz(neigh[i],ziel);              
            open = add_open(open,pnr,rueck,&nr_open);
            add_point(neigh[i],parent,rueck,h,&pnr);
         }                                   
      } 
            
      
      //Kürzesten Punkt finden
      parent = find_next(open);
      next_node.x = pt[parent].x;
      next_node.y = pt[parent].y;
      rueck = pt[parent].g+1;      
         
      
   } while(n_open != 0);
   
  
   
   
   printf("Es existiert kein Weg zum Ziel!\n");
              
   getch();
   return 0;
}


 Code 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
//A*, Bewegung in 4 Himmelsrichtung, Baum als Speicherstruktur

#include <stdio.h>
#include <conio.h>

#define LEER ' '
#define WALL '#'    
#define START 'S'
#define ZIEL 'Z'  
#define WALK 'X'

#define ROWS 10
#define COLUMS 10

#ifdef __unix__
    #define clrscr() printf("\x1B[2J")
    #define SYSTEM_ENDE
#elif __BORLANDC__ && __MSDOS__
    #include <conio.h> 
    #define SYSTEM_ENDE fflush(stdin); getchar();
#elif __WIN32__ || _MSC_VER
    #define clrscr() system("cls")  
    #define SYSTEM_ENDE fflush(stdin); getchar();
#else
    #define clrscr() printf("clrscr() - Fehler!!\n")
    #define SYSTEM_ENDE
#endif



struct point {
   int x; //Colum
   int y; //Row
};


struct point_tb {
   int id; //Primary Key
   
   int x;
   int y;
   int g; //Geschätze Kosten
   int b; //Bewegungskosten
   int f; //Gesamt
   
   struct point_tb *parent;
   struct point_tb *left;
   struct point_tb *right;
};

struct open_list {
   int f; //Primary Key
   
   int id;  
   
   struct point_tb *point;
   
   struct open_list *left;
   struct open_list *right;   
};

struct close_list {
   int id; //Primary Key  
    
   struct close_list *left;
   struct close_list *right;  
}; 






   

// Anzahl der Points in Liste
int pt_n, open_n, close_n;
   





//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze[ROWS][COLUMS] = {   {'S','#',' ','#',' ',' ',' ',' ',' ',' '}, //0
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //1
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //2
                              {' ','#',' ',' ',' ','#',' ','#',' ',' '}, //3
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //4   ROW | y
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //5
                              {' ','#',' ','#',' ','#',' ','#',' ',' '}, //6
                              {' ','#',' ','#',' ','#',' ',' ',' ',' '}, //7
                              {' ','#',' ','#',' ','#',' ','#',' ','#'}, //8
                              {' ',' ',' ','#',' ',' ',' ','#',' ','Z'} }; //9;

//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze2[ROWS][COLUMS] = {   {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //0
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //1
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //2
                              {' ',' ',' ',' ',' ','#',' ',' ',' ',' '}, //3
                              {' ',' ',' ','S',' ','#',' ','Z',' ',' '}, //4   ROW | y
                              {' ',' ',' ',' ',' ','#',' ',' ',' ',' '}, //5
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //6
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //7
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //8
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '} }; //9;
                        
                        
                        
                        
     
int make_id(struct point point) {
   return point.x*COLUMS+point.y;
}                   


void print_close(struct close_list *close) {
   if(close != NULL) {      
      print_close(close->left);
      printf("%d\n",close->id);
      print_close(close->right);
   } 
}

void print_open(struct open_list *open) {
   if(open != NULL) {      
      print_open(open->left);
      printf("%d (%d): %d \n", open->id, open->point->id, open->f);
      print_open(open->right);
   } 
}

void print_pt(struct point_tb *pt) {
   if(pt != NULL) {      
      print_pt(pt->left);
      printf("%d: %d\n",pt->id,pt->f);
      print_pt(pt->right);
   } 
}

                        
//Entfernung Schätzen
int schaetz(struct point point, struct point ziel) {
   int colum = point.x;
   int row = point.y;
   int dif_colum = (colum > ziel.x) ? colum-ziel.x : ziel.x-colum;
   int dif_row = (row > ziel.y) ? row-ziel.y : ziel.y-row;
   
   return (dif_row+dif_colum);   
}

void print_field(void) {
   int i,j;
   clrscr();
   
   //Head-Ausgeben
   printf("\n    ");   
   for(i=0;i<COLUMS;i++)
      printf("%2d  ",i);   
      
   printf("\n   ");   
   for(i=0;i<COLUMS;i++)
      printf("+---");
   
   printf("+\n");
   

   for(i = 0; i < ROWS; i++) {
      printf("%2d |",i);
      for(j=0; j < COLUMS; j++) {
         printf(" %c |",maze[i][j]);
      } 
      
      printf("\n   ");
      for(j=0;j<COLUMS;j++)
         printf("+---");
      
      printf("+\n");      
   } 
}

struct point find(char c) {
   struct point point;
   int i,j,check=0;
   
   
   for(i=0;i<10 && check == 0;i++) {
      for(j=0;j<10;j++) {
         if(maze[i][j] == c) {
            check = 1;
            point.x = j;
            point.y = i;
         }
      }
   }
   
   return point;
}

//Findet Nachbaren
void find_neigh(struct point point,struct point neigh[4]) {
   int colum = point.x;
   int row = point.y;     
   int i=0;
     
   for(i=0;i<4;i++) {
      neigh[i].x = -1;
      neigh[i].y = -1;
   }
   i=0;
         
     
   if((colum+1) < COLUMS && maze[row][colum+1] != WALL) { //Rechts davon
      neigh[i].y = row;
      neigh[i++].x = colum+1;      
   }    
   
     
   if((colum-1) >= 0 && maze[row][colum-1] != WALL) {  //Links davon
      neigh[i].y = row;
      neigh[i++].x = colum-1;      
   }
     
     
   if((row+1) < ROWS && maze[row+1][colum] != WALL) { //Darunter
      neigh[i].y = row+1;
      neigh[i++].x = colum;      
   }
   
   if((row-1) >= 0 && maze[row-1][colum] != WALL) { //Oberhalb
      neigh[i].y = row-1;
      neigh[i++].x = colum;      
   }          
}


/********************** ADD *************/
struct point_tb *add_point(struct point_tb *pt, 
                           struct point point, 
                           int g, int b,
                           struct point_tb *parent,
                           struct point_tb **act_point) {
   int id = make_id(point);
   
   if(pt == NULL) {
      pt = (struct point_tb *) realloc(pt,(++pt_n)*sizeof(struct point_tb));
      pt->id = id;
      pt->x = point.x;
      pt->y = point.y;
      pt->f = b+g;
      pt->g = g;
      pt->b = b;
      pt->parent = parent;
      pt->left = pt->right = NULL;
      
      *act_point = pt;
      
     
   } else if(pt->id >= id) {
      pt->left = add_point(pt->left, point, g, b, parent, act_point);
   } else {
      pt->right = add_point(pt->right, point, g, b, parent, act_point);
   }
   
      
   return pt;
}

struct close_list *add_close(struct close_list *close, struct point point) {
   int id = make_id(point);
  
   if(close == NULL) {
      close = (struct close_list *) realloc(close, (++close_n)*sizeof(struct close_list));
      close->id = id;
      close->left = close->right = NULL;      
   } else if(close->id >= id) {
      close->left = add_close(close->left,point);
   } else {
      close->right = add_close(close->right,point);
   }
   
   return close;    
}


struct open_list *add_open(struct open_list *open, struct point point, struct point_tb *parent, int f) {
   int id = make_id(point);
   
   if(open == NULL) {
      open = (struct open_list *) realloc(open, (++open_n)*sizeof(struct open_list));
      open->f = f;
      open->id = id;
      open->left = open->right = NULL;
      
      //printf("%d\n",&parent->id); getchar();
      open->point = parent;
   } else if(open->f >= f) {
      open->left = add_open(open->left,point,parent,f);
   } else {
      open->right = add_open(open->right,point,parent,f);
   }
   
   return open;
}




int is_close(struct point point, struct close_list *close) {
   int id = make_id(point);
   
   if(close == NULL) 
      return 0;
   else if(close->id == id)
      return 1;
   else if(close->id > id)
      return is_close(point,close->left);
   else
      return is_close(point,close->right);     
}


int is_open(struct point point, struct open_list *open, int f) {
   int id = make_id(point);
   
   while(open != NULL && open->id != id) {
      if(open->f > f)
         open = open->right;
      else
         open = open->left;      
   }
   
   if(open == NULL)
      return 0;
   else
      return 1;
         
}



/********** Loeschen ****************/

void suche_ersatz(int *neu_f, int *neu_id, struct point_tb **neu_point, struct open_list **zeiger) {
   struct open_list *tmp;
   
   if(*zeiger != NULL) {
      if((*zeiger)->left==NULL) {
         *neu_f = (*zeiger)->f; 
         *neu_id = (*zeiger)->id; 
         *neu_point = (*zeiger)->point; 
                 
         tmp=*zeiger;
         *zeiger=(*zeiger)->right;
         free(tmp);
      }
      else
         suche_ersatz(neu_f,neu_id,neu_point, &((*zeiger)->left));
   }
}

void loesche_open(struct open_list **zeiger) {
   struct open_list *tmp;
   int tmp_f, tmp_id;
   struct point_tb *tmp_point;
   
      
   if((*zeiger)->left == NULL && (*zeiger)->right == NULL) {
      //Kein Nachkomme
      free(*zeiger);
      *zeiger = NULL;
      
   } else if((*zeiger)->left == NULL) {
      //1 Linker Nachkomme
      tmp = *zeiger;
      *zeiger = (*zeiger)->right;
      free(tmp); 
   } else if((*zeiger)->right == NULL) {
      //1 Rechter Nachkomme
      tmp = *zeiger;
      *zeiger = (*zeiger)->left;
      free(tmp);      
   } else {
      //2 Nachkommen     
      suche_ersatz(&tmp_f, &tmp_id, &tmp_point,  &((*zeiger)->right));
      (*zeiger)->f = tmp_f;
      (*zeiger)->id = tmp_id;
      (*zeiger)->point = tmp_point;
   }
   
   --open_n;
   

}



struct point_tb *find_next(struct open_list *open) {
      
   while(open->left != NULL) 
      open = open->left;
          
   return open->point;
   
}

void find_path(struct point_tb *act_point) {
   
   while(act_point->parent != NULL) {  
      maze[act_point->y][act_point->x] = 'X';
      act_point = act_point->parent;
   }
   
   
   print_field(); 


   getch();
   exit(0); 
      
}
   

int main(void) {
   struct point start = find(START);//Start
   struct point ziel = find(ZIEL); //Ziel
   struct point neigh[4]; //Nachbarn
   struct point next_node = start; //Nächster Knoten
   
   
   // ************** Listen ********
   struct close_list *close = (struct close_list *) malloc(sizeof(struct close_list));
   struct open_list *open = (struct open_list *) malloc(sizeof(struct open_list));
   struct point_tb *pt = (struct point_tb *) malloc(sizeof(struct point_tb));
   struct point_tb *parent = (struct point_tb *) malloc(sizeof(struct point_tb));
   struct point_tb *act_point = (struct point_tb *) malloc(sizeof(struct point_tb));
   struct open_list **del_open = &open;
   
   struct open_list *tmp;
   
   
   close = NULL;
   open = NULL;
   pt = NULL;
   parent = NULL;
   
   
   int g; //Geschätze Kosten
   int b=1; //Bewegungskosten
   int rueck = 1; //Zurueckgelegte Kosten
   
   struct point min = {0,0};//Start
   struct point max = {10,10}; //Ziel   
   
   int i=0,j=0;
   
   parent = pt = add_point(pt, start, 0, 0, NULL, &act_point); 
   open = add_open(open,start,NULL,0);
   
   
   
   print_field();
   
   
   
   do {  
      //Wenn Ziel ist => Pfad ausgeben 
      if(next_node.x == ziel.x && next_node.y == ziel.y) {         
         find_path(parent->parent);
      }
      
      //Punkt der geschlossenen Liste hinzufuegen
      close = add_close(close, next_node);
          
      // Ersten Punkt aus open loeschen
      del_open = &open;      
      while((*del_open)->left != NULL)
         del_open = &(*del_open)->left;      
      
      loesche_open(del_open); 
        
        
      //Finde die Nachbar  
      find_neigh(next_node,neigh);
      
      
     
      
      for(i=0;i<4 && neigh[i].x != -1;i++) {
         
         if(is_close(neigh[i],close))
            continue;
                       
         g = schaetz(neigh[i],ziel);
         
         if(!is_open(neigh[i],open,g+b)) {            
            pt = add_point(pt,neigh[i],b,g,parent,&act_point);
            open = add_open(open,neigh[i],act_point,g+b);     
         }                                               
      }
      
      
      //Nächsten Punkt finden
      if(open != NULL) {
         parent = find_next(open);
                  
         next_node.x = parent->x;
         next_node.y = parent->y;   
      }
           
      
   } while(open != NULL);
   
   
   printf("Kein Weg gefunden!!");
   
   
   
   
   getch();
   return 0;
}


 Code 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
526:
527:
528:
529:
530:
531:
//A*, Bewegung auch Diagonal (max. 8 Nachbarfelder)
#include <stdio.h>
#include <conio.h>

#define LEER ' '
#define WALL '#'    
#define START 'S'
#define ZIEL 'Z'  
#define WALK 'X'

#define ROWS 10
#define COLUMS 10
                
                  


#ifdef __unix__
    #define clrscr() printf("\x1B[2J")
    #define SYSTEM_ENDE
#elif __BORLANDC__ && __MSDOS__
    #include <conio.h> 
    #define SYSTEM_ENDE fflush(stdin); getchar();
#elif __WIN32__ || _MSC_VER
    #define clrscr() system("cls")  
    #define SYSTEM_ENDE fflush(stdin); getchar();
#else
    #define clrscr() printf("clrscr() - Fehler!!\n")
    #define SYSTEM_ENDE
#endif

struct point_tb {
   int x;
   int y; 
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int f; //Gesamt
   int parent; //Vorgänger-Objekt
};

struct point {
   int x; //Colum
   int y; //Row
};

//Punkte zu einer Tabelle hinzufügen
struct point *add_close(struct point point,struct point *close, int *nr);
int *add_open(int *open, int pnr, int bewegung, int *nr);
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr);

//Überprüfen ob Punkt in Tabelle vorhanden
int is_open(struct point point, int *open);
int is_close(struct point point, struct point *close);

//Punkte finden
void find_neigh(struct point point,struct point neigh[]); //Nachbaren finden
int find_next(int *open); //Nächsten Punkt wählen

//Entfernung schätzen
int schaetz(struct point point, struct point ziel);

//Ziel gefunden => Pfad ausgeben
void ziel_found(struct point point,int parent);


void print_field(void); //Spielfeld ausgeben
struct point find(char c); //Koordinate zu c finden




        
        
//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze[ROWS][COLUMS] = {   {'S',' ',' ',' ',' ','#',' ',' ',' ',' '}, //0
                              {' ',' ','#',' ',' ',' ',' ','#',' ',' '}, //1
                              {'#',' ','#',' ',' ','#',' ','#',' ',' '}, //2
                              {' ',' ',' ','#',' ','#',' ',' ','#',' '}, //3
                              {' ',' ','#',' ',' ','#',' ',' ','#',' '}, //4   ROW | y
                              {' ',' ',' ',' ','#','#',' ',' ',' ',' '}, //5
                              {' ','#',' ',' ',' ','#','#','#',' ',' '}, //6
                              {' ',' ','#',' ',' ',' ',' ',' ',' ',' '}, //7
                              {' ',' ',' ','#',' ','#',' ',' ','#',' '}, //8
                              {'#',' ',' ',' ',' ','#',' ',' ','#','Z'} }; //9;

                        
                        
                        
//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze2[ROWS][COLUMS] = {   {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //0
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //1
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //2
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //3
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //4   ROW | y
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //5
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //6
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //7
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //8
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '} }; //9;


struct point_tb pt[ROWS*COLUMS+1]; //Tabelle mit allen Punkten
int n_open = 1; //Anzahl der Elemente in Open
int schritte = 0; //Anzahl an Durchläufen





/*********************************************************
                  Funktionen
**********************************************************/




//Überprüfte Points in Close eintragen
struct point *add_close(struct point point,struct point *close, int *nr) { 
   struct point end = {-1,-1};
     
   close = (struct point *) realloc(close,((*nr)+2)*sizeof(struct point));
   close[*nr] = point;
   close[(*nr)+1] = end;
   
   (*nr)++;   
   
   return close;
}


//Überprüfte Points in Open eintragen
int *add_open(int *open, int pnr, int bewegung, int *nr) { 
   int g_tmp;
     
   open = (int *) realloc(open,((*nr)+2)*sizeof(int));
   g_tmp = pt[pnr].g;
   
   if(bewegung < g_tmp) {
      pt[pnr].g = bewegung;
      pt[pnr].f = pt[pnr].g+pt[pnr].h;
   }
   
   open[*nr] = pnr;
   open[(*nr)+1] = -1;
      
   
   (*nr)++;
   n_open++;
   
   return open;
}


//Punkt zur Punktetabelle hinzufügen
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr) {
   pt[*pnr].x = point.x;
   pt[*pnr].y = point.y; 
   pt[*pnr].parent = parent;
   pt[*pnr].g = bewegkost;
   pt[*pnr].h = schaetzkost;
   pt[*pnr].f = bewegkost+schaetzkost;
   
   //Endpunkt
   pt[(*pnr)+1].x = -1;
   pt[(*pnr)+1].y = -1; 
   
   (*pnr)++;
}






//Überprüft ob Punkt auf Open-Liste ist
int is_open(struct point point, int *open) {
   int i;
   
   for(i=0;pt[i].x != -1;i++) {    
      if(pt[i].x == point.x && pt[i].y == point.y)
         return i;
   }
   
   return -1;
}


  
//Überprüft ob Punkt auf Close-Liste ist
int is_close(struct point point, struct point *close) {
   int i;
  
   for(i=0;close[i].x != -1;i++)  {
      if(close[i].x == point.x && close[i].y == point.y) {         
         return 1;
      }
         
   } 
   
   return 0;
}





//Findet Nachbaren
void find_neigh(struct point point,struct point neigh[]) {
   int colum = point.x;
   int row = point.y;     
   int i=0;
     
    
   for(i=0;i<8;i++) {
      neigh[i].x = -1;
      neigh[i].y = -1;
   } 
   
   i=0; 

         
     
   if((colum+1) < COLUMS && maze[row][colum+1] != WALL) { //Rechts davon
      neigh[i].y = row;
      neigh[i++].x = colum+1;      
   }    
   
     
   if((colum-1) >= 0 && maze[row][colum-1] != WALL) {  //Links davon
      neigh[i].y = row;
      neigh[i++].x = colum-1;      
   }
     
     
   if((row+1) < ROWS && maze[row+1][colum] != WALL) { //Darunter
      neigh[i].y = row+1;
      neigh[i++].x = colum;      
   }
   
   if((row-1) >= 0 && maze[row-1][colum] != WALL) { //Oberhalb
      neigh[i].y = row-1;
      neigh[i++].x = colum;      
   }   
   
   
   //Diagonal
   
   //Links-Oben
   if( (row-1) >= 0 && (colum-1) >= 0 && 
       maze[row-1][colum] != WALL && maze[row][colum-1] != WALL && //Keine Wand schneiden
       maze[row-1][colum-1] != WALL) {
            
      neigh[i].y = row-1;
      neigh[i++].x = colum-1;
   }
   
   //Rechts-Oben
   if( (row-1) >= 0 && (colum+1) < COLUMS &&
       maze[row-1][colum] != WALL && maze[row][colum+1] != WALL &&
       maze[row-1][colum+1] != WALL) {
            
      neigh[i].y = row-1;
      neigh[i++].x = colum+1;
   }
   
   //Links-Unten
   if( (row+1) < ROWS && (colum-1) >= 0 &&
       maze[row+1][colum] != WALL && maze[row][colum-1] != WALL &&
       maze[row+1][colum-1] != WALL) {
      
      neigh[i].y = row+1;
      neigh[i++].x = colum-1;
   }
   
   //Rechts-Unten
   if( (row+1) < ROWS && (colum+1) < COLUMS &&
      maze[row+1][colum] != WALL && maze[row][colum+1] != WALL &&
      maze[row+1][colum+1] != WALL) {
                
      neigh[i].y = row+1;
      neigh[i++].x = colum+1;
   }
         
}

//Findet den nächsten Knoten
int find_next(int *open) {
   int i;
   int next=-1;
   int tmp = -1;
   int i_tmp;
   
   
   for(i=0;open[i] != -1;i++) {      
      if(open[i] != -2 && (tmp == -1 || pt[open[i]].f < tmp) ) {
         next = open[i];     
         tmp = pt[next].f;
         i_tmp = i;
      } 
   }
   
   //Elemente auf -2 setzen = Gelöscht
   open[i_tmp] = -2;
   n_open--;
   
   //printf("Next: %d   %d|%d  f:%d  g:%d\n",next,pt[next].x,pt[next].y,pt[next].f,pt[next].g);
   
   return next;
}




//Entfernung Schätzen
int schaetz(struct point point, struct point ziel) {
   int colum = point.x;
   int row = point.y;
   int dif_colum = (colum > ziel.x) ? colum-ziel.x : ziel.x-colum;
   int dif_row = (row > ziel.y) ? row-ziel.y : ziel.y-row;
   
   return ( (dif_row+dif_colum)*10 );   
}





void ziel_found(struct point point,int parent) {
   int i=0;
   
   
   
   
   
   //Weg Einzeichen
   while(pt[parent].parent != -1) {
      maze[pt[parent].y][pt[parent].x] = WALK;
      parent = pt[parent].parent;
   }
   
   
   
   
   
   maze[pt[parent].y][pt[parent].x] = START; //Start
   maze[point.y][point.x] = ZIEL; //Ziel
   
   print_field(); 
   printf("\n Rechenschritte: %d \n",schritte);
   
   //printf("\n\nPT:\n");
   
   for(i=0;pt[i].x != -1;i++) {    
      //printf("%d  %d|%d  f:%d\n",i,pt[i].x,pt[i].y,pt[i].f);
   }
   
   getch();
   exit(0);
}
   





void print_field(void) {
   int i,j;
   clrscr();
   
   //Head-Ausgeben
   printf("\n    ");   
   for(i=0;i<COLUMS;i++)
      printf("%2d  ",i);   
      
   printf("\n   ");   
   for(i=0;i<COLUMS;i++)
      printf("+---");
   
   printf("+\n");
   

   for(i = 0; i < ROWS; i++) {
      printf("%2d |",i);
      for(j=0; j < COLUMS; j++) {
         printf(" %c |",maze[i][j]);
      } 
      
      printf("\n   ");
      for(j=0;j<COLUMS;j++)
         printf("+---");
      
      printf("+\n");      
   } 
}

  
struct point find(char c) {
   struct point point;
   int i,j,check=0;
   
   
   for(i=0;i<10 && check == 0;i++) {
      for(j=0;j<10;j++) {
         if(maze[i][j] == c) {
            check = 1;
            point.x = j;
            point.y = i;
         }
      }
   }
   
   return point;
}
             
      
      
/*******************************************************************************
                               MAIN
********************************************************************************/                

int main(void) {
   print_field();  
    
   struct point start = find(START);//Start
   struct point ziel = find(ZIEL); //Ziel
   struct point neigh[8]; //Nachbarn
   struct point next_node = start; //Nächster Knoten

 
   maze[start.y][start.x] = LEER;
   maze[ziel.y][ziel.x] = LEER;      
   
   int i=0,j=0,tmp=0;
   int pnr = 0; //Anzahl der Punkte in pt
   int parent = 0; //Vorgänger objetkt
   
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int rueck = 0, rueck_new=0; //Zurueckgelegte Kosten
   
   //Close-Liste
   struct point *close = (struct point *) malloc(sizeof(struct point));
   int nr_close = 0;
   
   //Open-Liste
   int *open = (int *) malloc(sizeof(int));
   int nr_open = 0;
   
   open[0] = -1;
   
   //Füge Start zur Punktetabelle hinzu
   add_point(next_node,-1,0,schaetz(start,ziel),&pnr); 
   
   
   do {      
      schritte++;
      //Füge Start in Close-Tabelle
      close = add_close(next_node,close,&nr_close);
       
      //Finde Nachbaren 
      find_neigh(next_node,neigh);
       
      for(i=0;i<8 && neigh[i].x != -1;i++) {           
         if(neigh[i].x == ziel.x && neigh[i].y == ziel.y)
            ziel_found(neigh[i],parent);           
               
         if(is_close(neigh[i],close)) 
            continue;
            
         if( (j = is_open(neigh[i],open)) == -1) { 
               
            if( (next_node.x-neigh[i].x) != 0 && (next_node.y-neigh[i].y) != 0 )
               rueck_new = 14; //Diagonal
            else
               rueck_new = 10; //Horizontal
                    
            h = schaetz(neigh[i],ziel);              
            open = add_open(open,pnr,rueck+rueck_new,&nr_open);
            add_point(neigh[i],parent,rueck+rueck_new,h,&pnr);
         } else { //Punkt ist schon in pt eingetragen  
                     
            if( (next_node.x-neigh[i].x) != 0 && (next_node.y-neigh[i].y) != 0 )
               rueck_new = 14; //Diagonal
            else
               rueck_new = 10; //Horizontal      
            
            if(pt[j].g > (rueck+rueck_new) ) { //Es gibt dahin einen kürzeren Weg                         
               pt[j].f = pt[j].h+rueck+rueck_new;             
               pt[j].g = rueck+rueck_new;             
               pt[j].parent = parent;                                     
            }             
         }                                  
      } 
            
      
      //Kürzesten Punkt finden
      parent = find_next(open);
      next_node.x = pt[parent].x;
      next_node.y = pt[parent].y;
      rueck = pt[parent].g;      
         
      
   } while(n_open != 0);
   
   /*
   printf("\nClose:\n");
   
   for(i=0;close[i].x != -1;i++) {    
      printf("%d: %d|%d \n",i,close[i].x,close[i].y);
   }
   
   printf("\n\nOpen:\n");
   
   for(i=0;open[i] != -1;i++) {    
      printf("%d  %d|%d\n",open[i],pt[open[i]].x,pt[open[i]].y);
   } 
   
   
   printf("\n\nPT:\n");
   
   for(i=0;pt[i].x != -1;i++) {    
      printf("%d  %d|%d  f:%d\n",i,pt[i].x,pt[i].y,pt[i].f);
   }
   */
   
   
   printf("Es existiert kein Weg zum Ziel!\n");
              
   getch();
   return 0;
}


 Code 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
526:
527:
528:
529:
530:
531:
532:
533:
534:
535:
536:
537:
538:
539:
540:
541:
542:
543:
544:
545:
546:
547:
548:
549:
550:
551:
552:
553:
554:
555:
556:
557:
558:
559:
560:
561:
562:
563:
564:
565:
566:
567:
568:
569:
570:
571:
572:
573:
574:
575:
576:
577:
578:
579:
580:
581:
582:
583:
584:
585:
586:
587:
588:
589:
590:
591:
592:
593:
594:
595:
596:
597:
598:
599:
600:
601:
602:
603:
604:
605:
606:
607:
608:
609:
610:
611:
612:
613:
614:
615:
616:
617:
618:
619:
620:
621:
622:
623:
624:
625:
626:
627:
628:
629:
630:
631:
632:
633:
634:
635:
636:
637:
638:
639:
640:
641:
642:
643:
644:
645:
646:
647:
648:
649:
650:
651:
652:
653:
654:
655:
656:
//A*, Bewegung diagonal + Baum als Speicherstruktur

#include <stdio.h>
#include <conio.h>

#define LEER ' '
#define WALL '#'    
#define START 'S'
#define ZIEL 'Z'  
#define WALK 'X'

#define ROWS 10
#define COLUMS 10
                
                  


#ifdef __unix__
    #define clrscr() printf("\x1B[2J")
    #define SYSTEM_ENDE
#elif __BORLANDC__ && __MSDOS__
    #include <conio.h> 
    #define SYSTEM_ENDE fflush(stdin); getchar();
#elif __WIN32__ || _MSC_VER
    #define clrscr() system("cls")  
    #define SYSTEM_ENDE fflush(stdin); getchar();
#else
    #define clrscr() printf("clrscr() - Fehler!!\n")
    #define SYSTEM_ENDE
#endif

struct point_tb {
   int x;
   int y; 
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int f; //Gesamt
   int parent; //Vorgänger-Objekt
};

struct point {
   int x; //Colum
   int y; //Row
};

struct open_list {
   int parent; //Vorgänger-Objekt
   int f; //Gesamtkosten
   struct open_list *left;
   struct open_list *right;
};

struct open_list *open;


void loesche(struct open_list **, int);
void suche_ersatz(int *, struct open_list **);
void loesche_knoten(struct open_list **);

//Punkte zu einer Tabelle hinzufügen
struct point *add_close(struct point point,struct point *close, int *nr);
void add_open(int pnr, int bewegung, int f);
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr);

//Überprüfen ob Punkt in Tabelle vorhanden
int is_open(struct point point, struct open_list *);
int is_close(struct point point, struct point *close);

//Punkte finden
void find_neigh(struct point point,struct point neigh[]); //Nachbaren finden
int find_next(struct open_list *); //Nächsten Punkt wählen

//Entfernung schätzen
int schaetz(struct point point, struct point ziel);

//Ziel gefunden => Pfad ausgeben
void ziel_found(struct point point,int parent);


void print_field(void); //Spielfeld ausgeben
struct point find(char c); //Koordinate zu c finden




        
        
//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze[ROWS][COLUMS] = {   {'S',' ',' ',' ',' ','#',' ',' ',' ',' '}, //0
                              {' ',' ','#',' ',' ',' ',' ','#',' ',' '}, //1
                              {'#',' ','#',' ',' ','#',' ','#',' ',' '}, //2
                              {' ',' ',' ','#',' ','#',' ',' ','#',' '}, //3
                              {' ',' ','#',' ',' ','#',' ',' ','#',' '}, //4   ROW | y
                              {' ',' ',' ',' ','#','#',' ',' ',' ',' '}, //5
                              {' ','#',' ',' ',' ','#','#','#',' ',' '}, //6
                              {' ',' ','#',' ',' ',' ',' ',' ',' ',' '}, //7
                              {' ',' ',' ','#',' ','#',' ',' ','#',' '}, //8
                              {'#',' ',' ',' ',' ','#',' ',' ','#','Z'} }; //9;

                        
                        
                        
//                              0   1   2   3   4   5   6   7   8   9   //Colum | x               
char maze2[ROWS][COLUMS] = {   {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //0
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //1
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //2
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //3
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //4   ROW | y
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //5
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //6
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //7
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '}, //8
                              {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '} }; //9;


struct point_tb pt[ROWS*COLUMS+1]; //Tabelle mit allen Punkten
int n_open = 1; //Anzahl der Elemente in Open
int schritte = 0; //Anzahl an Durchläufen





/*********************************************************
                  Funktionen
**********************************************************/

void print_tree(struct open_list *zeiger) {
   if(zeiger != NULL) {    
      
      print_tree(zeiger->left);         
      printf("Parent: %d    f: %d\n",zeiger->parent,zeiger->f);      
      print_tree(zeiger->right);
   }    
}


//Überprüfte Points in Close eintragen
struct point *add_close(struct point point,struct point *close, int *nr) { 
   struct point end = {-1,-1};
     
   close = (struct point *) realloc(close,((*nr)+2)*sizeof(struct point));
   close[*nr] = point;
   close[(*nr)+1] = end;
   
   (*nr)++;   
   
   return close;
}

struct open_list *add_tree(struct open_list *zeiger, int f, int parent) {
   
   if(zeiger == NULL) {
      zeiger = (struct open_list *) malloc(sizeof(struct open_list));
      
      if(zeiger == NULL) {
         printf("Kein Platz mehr !!!");
         exit(0);
      }
      
      
      
      zeiger->f = f;
      zeiger->parent = parent;
      zeiger->left = zeiger->right = NULL;    
   } else if(zeiger->f >= f) {
      zeiger->left = add_tree(zeiger->left,f,parent);
   } else {
      zeiger->right = add_tree(zeiger->right,f,parent);
   }
   
   return zeiger;
}


//Überprüfte Points in Open eintragen
void add_open(int pnr, int bewegung, int f) { 
   int g_tmp;
   g_tmp = pt[pnr].g;
   
   if(bewegung < g_tmp) {
      pt[pnr].g = bewegung;
      f = pt[pnr].f = pt[pnr].g+pt[pnr].h;
   }
   
   open = add_tree(open,f,pnr);


   n_open++;

}


//Punkt zur Punktetabelle hinzufügen
void add_point(struct point point, int parent, int bewegkost, int schaetzkost, int *pnr) {
   pt[*pnr].x = point.x;
   pt[*pnr].y = point.y; 
   pt[*pnr].parent = parent;
   pt[*pnr].g = bewegkost;
   pt[*pnr].h = schaetzkost;
   pt[*pnr].f = bewegkost+schaetzkost;
   
   //Endpunkt
   pt[(*pnr)+1].x = -1;
   pt[(*pnr)+1].y = -1; 
   
   (*pnr)++;
}






//Überprüft ob Punkt auf Open-Liste ist
int is_open(struct point point, struct open_list *zeiger) {
   int i,ret;
   
   /*
   for(i=0;pt[i].x != -1;i++) {    
      if(pt[i].x == point.x && pt[i].y == point.y)
         return i;
   } */
   if(zeiger != NULL) {
      if(zeiger->parent > (ROWS*COLUMS+2))
         return -1;
         
      printf("\n\nis_open: \n");
      print_tree(open);
      
      
      if(pt[zeiger->parent].x == point.x && pt[zeiger->parent].y == point.y)
         return zeiger->parent;
      
      if( (ret = is_open(point, zeiger->left)) != -1)
         return ret;
         
      if( (ret = is_open(point, zeiger->right)) != -1)
         return ret;
   }
   
   
   
   return -1;
}


  
//Überprüft ob Punkt auf Close-Liste ist
int is_close(struct point point, struct point *close) {
   int i;
  
   for(i=0;close[i].x != -1;i++)  {
      if(close[i].x == point.x && close[i].y == point.y) {         
         return 1;
      }
         
   } 
   
   return 0;
}





//Findet Nachbaren
void find_neigh(struct point point,struct point neigh[]) {
   int colum = point.x;
   int row = point.y;     
   int i=0;
     
    
   for(i=0;i<8;i++) {
      neigh[i].x = -1;
      neigh[i].y = -1;
   } 
   
   i=0; 

         
     
   if((colum+1) < COLUMS && maze[row][colum+1] != WALL) { //Rechts davon
      neigh[i].y = row;
      neigh[i++].x = colum+1;      
   }    
   
     
   if((colum-1) >= 0 && maze[row][colum-1] != WALL) {  //Links davon
      neigh[i].y = row;
      neigh[i++].x = colum-1;      
   }
     
     
   if((row+1) < ROWS && maze[row+1][colum] != WALL) { //Darunter
      neigh[i].y = row+1;
      neigh[i++].x = colum;      
   }
   
   if((row-1) >= 0 && maze[row-1][colum] != WALL) { //Oberhalb
      neigh[i].y = row-1;
      neigh[i++].x = colum;      
   }   
   
   
   //Diagonal
   
   //Links-Oben
   if( (row-1) >= 0 && (colum-1) >= 0 && 
       maze[row-1][colum] != WALL && maze[row][colum-1] != WALL && //Keine Wand schneiden
       maze[row-1][colum-1] != WALL) {
            
      neigh[i].y = row-1;
      neigh[i++].x = colum-1;
   }
   
   //Rechts-Oben
   if( (row-1) >= 0 && (colum+1) < COLUMS &&
       maze[row-1][colum] != WALL && maze[row][colum+1] != WALL &&
       maze[row-1][colum+1] != WALL) {
            
      neigh[i].y = row-1;
      neigh[i++].x = colum+1;
   }
   
   //Links-Unten
   if( (row+1) < ROWS && (colum-1) >= 0 &&
       maze[row+1][colum] != WALL && maze[row][colum-1] != WALL &&
       maze[row+1][colum-1] != WALL) {
      
      neigh[i].y = row+1;
      neigh[i++].x = colum-1;
   }
   
   //Rechts-Unten
   if( (row+1) < ROWS && (colum+1) < COLUMS &&
      maze[row+1][colum] != WALL && maze[row][colum+1] != WALL &&
      maze[row+1][colum+1] != WALL) {
                
      neigh[i].y = row+1;
      neigh[i++].x = colum+1;
   }
         
}

void loesche(struct open_list **zeiger, int such) {
   if((*zeiger) == NULL)
      printf("Zahl nicht gefunden\n");
   else if((*zeiger)->parent == such) /* Gefunden! */
      loesche_knoten(zeiger);
   else if((*zeiger)->parent >= such)
      loesche(&((*zeiger)->left),such);
   else
      loesche(&((*zeiger)->right),such);
}


void suche_ersatz(int *neu_wert, struct open_list **zeiger) {
   struct open_list *tmp;
   
   if(*zeiger != NULL) {
      if((*zeiger)->left==NULL) {
         *neu_wert=(*zeiger)->parent;         
         tmp=*zeiger;
         *zeiger=(*zeiger)->right;
         free(tmp);
      }
      else
         suche_ersatz(neu_wert, &((*zeiger)->left));
   }
}

void loesche_knoten(struct open_list **zeiger) {
   struct open_list *tmp;
   int tmp_wert=-1;
   
   if((*zeiger)->left == NULL && (*zeiger)->right == NULL) {
      printf("Kein Nachkomme\n");
      //Kein Nachkomme
      free(*zeiger);
      *zeiger = NULL;
   }
      
      
   /*   
   } else if((*zeiger)->left == NULL) {
      printf("1 Nachkomme\n");
      //1 Linker Nachkomme
      tmp = *zeiger;
      *zeiger = (*zeiger)->right;
      free(tmp); 
   } else if((*zeiger)->right == NULL) {
      printf("15 Nachkomme\n");
      //1 Rechter Nachkomme
      tmp = *zeiger;
      *zeiger = (*zeiger)->left;
      free(tmp);      
   } else {
      printf("2 Nachkomme\n");
      //2 Nachkommen
      
      suche_ersatz(&tmp_wert, &((*zeiger)->right));
      (*zeiger)->parent = tmp_wert;
   } */
   
}

//Findet den nächsten Knoten
int find_next(struct open_list *zeiger) {
   
   int i;
   int next=-1;
   int tmp = -1;
   int i_tmp;
   
   while(zeiger->left != NULL)
      zeiger = zeiger->left;
   
   
   
   tmp = zeiger->parent;   
   loesche(&zeiger,zeiger->parent); 
   
   
   
   return tmp;
   
   /*
   for(i=0;open[i] != -1;i++) {      
      if(open[i] != -2 && (tmp == -1 || pt[open[i]].f < tmp) ) {
         next = open[i];     
         tmp = pt[next].f;
         i_tmp = i;
      } 
   }
   
   //Elemente auf -2 setzen = Gelöscht
   open[i_tmp] = -2;
   n_open--;
   
   //printf("Next: %d   %d|%d  f:%d  g:%d\n",next,pt[next].x,pt[next].y,pt[next].f,pt[next].g);
   */
   
   return next;
}




//Entfernung Schätzen
int schaetz(struct point point, struct point ziel) {
   int colum = point.x;
   int row = point.y;
   int dif_colum = (colum > ziel.x) ? colum-ziel.x : ziel.x-colum;
   int dif_row = (row > ziel.y) ? row-ziel.y : ziel.y-row;
   
   return ( (dif_row+dif_colum)*10 );   
}





void ziel_found(struct point point,int parent) {
   int i=0;
   
   
   
   
   
   //Weg Einzeichen
   while(pt[parent].parent != -1) {
      maze[pt[parent].y][pt[parent].x] = WALK;
      parent = pt[parent].parent;
   }
   
   
   
   
   
   maze[pt[parent].y][pt[parent].x] = START; //Start
   maze[point.y][point.x] = ZIEL; //Ziel
   
   print_field(); 
   printf("\n Rechenschritte: %d \n",schritte);
   
   //printf("\n\nPT:\n");
   
   for(i=0;pt[i].x != -1;i++) {    
      //printf("%d  %d|%d  f:%d\n",i,pt[i].x,pt[i].y,pt[i].f);
   }
   
   getch();
   exit(0);
}
   





void print_field(void) {
   int i,j;
   clrscr();
   
   //Head-Ausgeben
   printf("\n    ");   
   for(i=0;i<COLUMS;i++)
      printf("%2d  ",i);   
      
   printf("\n   ");   
   for(i=0;i<COLUMS;i++)
      printf("+---");
   
   printf("+\n");
   

   for(i = 0; i < ROWS; i++) {
      printf("%2d |",i);
      for(j=0; j < COLUMS; j++) {
         printf(" %c |",maze[i][j]);
      } 
      
      printf("\n   ");
      for(j=0;j<COLUMS;j++)
         printf("+---");
      
      printf("+\n");      
   } 
}

  
struct point find(char c) {
   struct point point;
   int i,j,check=0;
   
   
   for(i=0;i<10 && check == 0;i++) {
      for(j=0;j<10;j++) {
         if(maze[i][j] == c) {
            check = 1;
            point.x = j;
            point.y = i;
         }
      }
   }
   
   return point;
}
             
      
      
/*******************************************************************************
                               MAIN
********************************************************************************/                

int main(void) {
   print_field();  
   
   open = (struct open_list *) malloc(sizeof(struct open_list));
   open = NULL;
    
   struct point start = find(START);//Start
   struct point ziel = find(ZIEL); //Ziel
   struct point neigh[8]; //Nachbarn
   struct point next_node = start; //Nächster Knoten

 
   maze[start.y][start.x] = LEER;
   maze[ziel.y][ziel.x] = LEER;      
   
   int i=0,j=0,tmp=0;
   int pnr = 0; //Anzahl der Punkte in pt
   int parent = 0; //Vorgänger objetkt
   
   int h; //Geschätze Kosten
   int g; //Bewegungskosten
   int rueck = 0, rueck_new=0; //Zurueckgelegte Kosten
   
   //Close-Liste
   struct point *close = (struct point *) malloc(sizeof(struct point));
   int nr_close = 0;
   
   //Open-Liste
   //int *open = (int *) malloc(sizeof(int));
   int nr_open = 0;
   
   int count = 0;
   
   //Füge Start zur Punktetabelle hinzu
   add_point(next_node,-1,0,schaetz(start,ziel),&pnr); 
   
   
   do {      
      schritte++;
      //Füge Start in Close-Tabelle
      close = add_close(next_node,close,&nr_close);
       
      //Finde Nachbaren 
      find_neigh(next_node,neigh);
       
      for(i=0;i<8 && neigh[i].x != -1;i++) {           
         if(neigh[i].x == ziel.x && neigh[i].y == ziel.y)
            ziel_found(neigh[i],parent);           
               
         if(is_close(neigh[i],close)) 
            continue;
            
         if( (j = is_open(neigh[i],open)) == -1) { 
               
            if( (next_node.x-neigh[i].x) != 0 && (next_node.y-neigh[i].y) != 0 )
               rueck_new = 14; //Diagonal
            else
               rueck_new = 10; //Horizontal
                    
            
            h = schaetz(neigh[i],ziel);         
           
                 
            add_open(pnr,rueck+rueck_new,h+rueck+rueck_new);
            add_point(neigh[i],parent,rueck+rueck_new,h,&pnr);                                  
         } else { //Punkt ist schon in pt eingetragen  
                     
            if( (next_node.x-neigh[i].x) != 0 && (next_node.y-neigh[i].y) != 0 )
               rueck_new = 14; //Diagonal
            else
               rueck_new = 10; //Horizontal      
            
            if(pt[j].g > (rueck+rueck_new) ) { //Es gibt dahin einen kürzeren Weg                         
               pt[j].f = pt[j].h+rueck+rueck_new;             
               pt[j].g = rueck+rueck_new;             
               pt[j].parent = parent;                                     
            }             
         }                                  
      } 
            
      
      //Kürzesten Punkt finden
      parent = find_next(open);
      printf("find_next %d\n",parent); getchar();
      next_node.x = pt[parent].x;
      next_node.y = pt[parent].y;
      rueck = pt[parent].g;      
         
      
   } while(n_open != 0);
   
  
   
   
   printf("Es existiert kein Weg zum Ziel!\n");
              
   getch();
   return 0;
}


Evt. hilfts ja weiter

PS: Zum kompilieren verwende ich Dev-C++



www.php-einfach.de, PHP lernen leicht gemacht
www.webhosterwissen.de, Webhosting-Vergleich





Post wurde schon 1x editiert, das letzte mal am 01.11.2007 um 18:35 von Andavos
01.11.2007, 18:34 Profil | PM | E-Mail  
oz
Mitglied
Guter User


Dabei seit: 20.05.2005
Herkunft:
Posts: 449
      Zitat | Bearbeiten

@Andavos: Den Link hatte GameR schon gepostet...


01.11.2007, 22:28 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
     Sortierung der Ergebnisse Zitat | Bearbeiten

Muss jetzt einfach mein Lieblingsforum mal um Rat fragen, Google spuckt kein passendes Beispiel aus:

Ich habe als A*-openListe folgendes Array:

Array (
[0] => Array (
[7] => 9.414 )
[1] => Array (
[8] => 8
[7] => 9
[6] => 10
[5] => 11
[4] => 12
[3] => 13
[2] => 14
[0] => 16 )
)

Wie ihr sehen könnt, ist die zweite Dimension schon anhand der Werte geordnet, das mache ich mit asort. Aber das 1. Array mit den sortierten Arrays soll nochmal nach dem kleinsten Wert geordnet werden, sprich das 1D-Array soll anhand der kleinsten 2D-Array-Elementen sortiert werden.

array_multisort habe ich schon ausprobiert, aber ich bekomme das nicht auf meine Bedürfnisse angepasst. Folgender Code klappt schon mal nicht:

 PHP 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
<?
for ($i=0;$i<=count($this->oList);$i++)
    if (
is_array($this->oList[$i]))
        
asort($this->oList[$i]);

if (
is_array($this->oList))
{
    
//asort($this->oList);

    
$sortArray = array();
    foreach(
$this->oList as $key => $array){
        
$sortArray[$key] = $array;
    }

    
array_multisort($sortArraySORT_ASCSORT_NUMERIC$this->oList);
}

$this->oList $sortArray;
?>


Hat schon jemand Erfahrungen damit gemacht, bzw. kann helfen?


Gruß, Dennis

www.xentity.de

Post wurde schon 2x editiert, das letzte mal am 21.03.2008 um 00:26 von Dennis
21.03.2008, 00:23 Profil | PM | E-Mail  
Snowball
Mitglied
Guter User


Dabei seit: 21.06.2007
Herkunft: Polen
Posts: 407
      Zitat | Bearbeiten

Ich vermute das du das für ein Browsergame verwenden willst, sonst wärst du ja nicht in dem Bereich des Forums. Solch ein Algorithmuss ist nicht gerade mal Performant und wenn dieser dann noch ständig angewendet wird, wird dein Anbieter eventuell ziehmlich sauer^^

Eventuell würde ich das einfach in C lassen, und halt die Positionen aus der Datenbank holen. Das C Programm rechnet das dann aus und trägt die Werte wieder in MySQL ein. Wenn du das über ein externen Programm machst hat das auch die Vorteile, das du wesentlich mehr damit mahcen kannst. Du kannst nun sagen das überal wo blau auf dem Bild ist, kein weg ist, und das du dich zumbeispiel auf grünen flächen schneller bewegst. Und dasalles automatisch, du musst die pielfarben und daten nicht per hand aus dem Bild heraus nehmen, sondern das einfach eine Funktion überlassen!


Alles was ein Coder brauch:
http://iuploads.iu.ohost.de/iuploads/
http://iuploads.iu.ohost.de/cpaste/
26.04.2008, 18:50 Profil | PM | E-Mail  
Dennis
Mitglied
Aktiver User


Dabei seit: 20.04.2004
Herkunft: Hennigsdorf (b Berlin)
Posts: 105
      Zitat | Bearbeiten

[quote]Orginal von Snowball
Ich vermute das du das für ein Browsergame verwenden willst, sonst wärst du ja nicht in dem Bereich des Forums. Solch ein Algorithmuss ist nicht gerade mal Performant und wenn dieser dann noch ständig angewendet wird, wird dein Anbieter eventuell ziehmlich sauer^^[/quote]

Da kann ich dir zustimmen, es ist für ein Browsergame. Bei der Erstellung und bei Tests bin ich bislang nicht auf Performance-Probleme gestoßen - bislang habe ich auch eher kleinere Karten verwendet. Es ist mir klar, dass die Laufzeit exponentiell wachsen wird.

[quote]Orginal von Snowball
Eventuell würde ich das einfach in C lassen, und halt die Positionen aus der Datenbank holen. Das C Programm rechnet das dann aus und trägt die Werte wieder in MySQL ein. Wenn du das über ein externen Programm machst hat das auch die Vorteile, das du wesentlich mehr damit mahcen kannst.[/quote]

Mit C habe ich noch nicht soviel gemacht, nur 2 Semester C++/C#, aber auch nicht intensiv.
Wenn ich die Strecken in eine DB eintrage, dann brauche ich den Algorithmus prinzipiell nicht.

Was ich vorhabe ist während der Laufzeit eine Art Stauumfahrung mit Hilfe eines benutzerabhängigen Faktors. Bestimmte Felder sollen mit diesem Faktor multipliziert werden, um deren Kosten zu erhöhen und damit eine Umfahrung zu ermöglichen. Je höher dieser Faktor, desto besser. Ist der Faktor klein, fährt man genau durch die Gefahrenzone.

Mein Projekt habe ich auf meiner Internetseite beschrieben: xentity.de




Gruß, Dennis

www.xentity.de
07.05.2008, 23:55 Profil | PM | E-Mail  
Seiten (1):  1 
PHP-Support.de » Programmierung » PHP & MySQL » Browsergames » A*-Algorithmus in PHP   

Neues Thema | Antworten   


Powered by Command Board 1.0 - Beta 2.0 © 2004-08 PHP-Einfach | Impressum | Datenschutz