D
Man tippt die Karte zeilenweise ein, tippt X für Hindernis oder G für "Goal",
dann gibt man die Startkoordinaten ein und der Pfad wird gesucht.
Erst Flood-Fill bis zum Ziel - mit gleichmäßig umsortierter Prozeßwarteschlange - , danach wird der Weg der Aufrufe vom Ziel rückwärts markiert (jeder Aufruf hat eine eigene Nummer ) und somit der Pfad eingezeichnet.
#include <stdlib.h>
#define UNPASSABLE 1
#define PASSABLE 0
#define ALREADY_PASSED 2
#define GOAL 3
#define MARK 4
#define FX_SIZE 7
#define FY_SIZE 7
unsigned char field[FX_SIZE][FY_SIZE];
typedef
struct
{
int x,y;
unsigned rec_count;
signed int prevID;
signed int ID;
unsigned inactivated;
void *prev, *next; /* Ende mit NULL terminiert */
}
rec_control;
rec_control *iteration_buf;
rec_control *Start;
signed int ID_upcount;
unsigned ID_subtract;
void insert_pos(int x, int y, int rec_count, int ID )
{
rec_control *getlast, *old ;
if( field[x][y]==ALREADY_PASSED )return;
else field[x][y]=ALREADY_PASSED;
printf("Haenge Position %d %d in die Kette...\n",x,y);
getlast=Start;
while( getlast->next != NULL )
{
getlast=getlast->next;
}
old=getlast;
getlast->next=malloc(sizeof ( rec_control ));
getlast=getlast->next;
getlast->prev=old;
getlast->next=NULL;
getlast->x=x;
getlast->y=y;
getlast->rec_count=rec_count+1;
getlast->inactivated=0;
getlast->ID=ID_upcount;
getlast->prevID=ID;
ID_upcount++;
/* Kettedumpen debug */
getlast=Start;
while(getlast!= NULL )
{
printf("Pointer in der Kette hat die Koordinaten %d %d und die Aktivierung %d...\n",
getlast->x, getlast->y, getlast->inactivated );
getlast=getlast->next;
}
/* bis hier */
}
int fill( rec_control *pos)
{
printf("Bin am Anfang der Fuellfunktion mit den Koordinaten %d %d...\n",pos->x, pos->y ); /*debug */
while ( pos->inactivated==1 && pos->next!= NULL ) pos=pos->next;
if ( pos->inactivated==1 ) return 0;
pos->inactivated=1;
ID_subtract=0;
printf("Bin am Anfang der Fuellfunktion mit den Koordinaten %d %d...\n",pos->x, pos->y ); /*debug */
if ( pos->x-1 >= 0 ) if (field[pos->x-1][pos->y]==0 )
{
insert_pos(pos->x-1, pos->y, pos->rec_count, pos->ID);
}
if ( pos->x-1 >= 0 )
{
if ( field[pos->x-1][pos->y]==3 ) {iteration_buf=pos; return 1; }
}
if ( pos->x+1 < FX_SIZE ) if ( field[pos->x+1][pos->y]==0 )
{
insert_pos(pos->x+1, pos->y, pos->rec_count, pos->ID);
}
if (pos->x+1 < FX_SIZE )
{
if ( field[pos->x+1][pos->y]==3 ){iteration_buf=pos; return 1; }
}
if ( pos->y-1 >= 0 ) if ( field[pos->x][pos->y-1]==0 )
{
insert_pos(pos->x, pos->y-1, pos->rec_count, pos->ID );
}
if (pos->y-1 >= 0 )
{
if ( field[pos->x][pos->y-1]==3 ){iteration_buf=pos; return 1; }
}
if ( pos->y+1 < FY_SIZE ) if( field[pos->x][pos->y+1]==0 )
{
insert_pos(pos->x, pos->y+1, pos->rec_count, pos->ID);
}
if (pos->y+1 < FY_SIZE )
{
if( field[pos->x][pos->y+1]==3 ){iteration_buf=pos; return 1; }
}
return 0;
}
void backsort()
{
rec_control *buf;
do
{
iteration_buf=Start;
if ( iteration_buf->next != NULL )
{
while( iteration_buf->rec_count <=
((rec_control *)(iteration_buf->next ))->rec_count )
{
printf("in der Suchschleife ... debug ");
if( iteration_buf->next != NULL ) iteration_buf=iteration_buf->next;
else break;
if ( iteration_buf->next == NULL ) break;
}
} else break;
if ( iteration_buf->next != NULL )
{
printf("Habe einen Treffer gelandet %d %d, vertausche...\n",
iteration_buf->rec_count, ((rec_control *)(iteration_buf->next))->rec_count); /*debug*/
if ( iteration_buf != Start )
((rec_control *) (iteration_buf->prev ))->next=iteration_buf->next;
printf("vorm if debug\n");
if(
(rec_control *) ( (rec_control *) (iteration_buf->next ))
->next
!= NULL )
{
( (rec_control *) ( (rec_control *) (iteration_buf->next ))
->next ) -> prev=iteration_buf;
}
printf("hinterm if debug...\n");
((rec_control *) (iteration_buf->next ))->prev=iteration_buf->prev;
iteration_buf->prev=iteration_buf->next;
printf("eins weiter...\n");
buf=
((rec_control *) (iteration_buf->next ))->next;
((rec_control *) (iteration_buf->next ))->next=iteration_buf;
iteration_buf->next=buf;
printf("bin durch...\n");
}
}while ( iteration_buf->next != NULL );
iteration_buf=Start;
printf("Am Ende der Sortierfunktion...\n");
}
void mark_path()
{
int older_ID;
for(;;)
{
field[iteration_buf->x][iteration_buf->y]=MARK;
printf("Id hat den Wert %d an den Koordinaten %d %d...\n", iteration_buf->prevID,
iteration_buf->x, iteration_buf->y );
older_ID=iteration_buf->prevID;
if (older_ID != -1 )
{
iteration_buf=Start;
while(iteration_buf->ID!= older_ID )
iteration_buf=iteration_buf->next;
}
else break;
}
}
void find_path(unsigned x, unsigned y) /* entspricht der Kontrollfunktion */
{
Start=malloc(sizeof(rec_control));
Start->prev=NULL;
Start->next=NULL;
Start->x=x;
Start->y=y;
Start->rec_count=0;
Start->inactivated=0;
Start->prevID=-1;
Start->ID=-1;
Start->next=NULL;
iteration_buf=Start;
while ( fill(iteration_buf) == 0 ) { printf("Rufe die Ruecksortier-\n"
"funktion auf...\n"); /* debug*/ backsort(); }
mark_path();
}
int main(void)
{
int x,y;
char c;
ID_upcount=0;y=0;
ID_subtract=0;
printf("Das Feld hat die Groesse %d mal %d .\n"
"Leerzeichen fuer Durchgangsweg, x fuer Block und g fuer Ziel...\n"
,FX_SIZE, FY_SIZE );
do
{
x=0;
do
{
do{ c=getch();} while (c!=' ' && c != 'x' && c != 'g' );
putch(c);
if(c==' ') field[x][y]=PASSABLE;
else if (c=='g' ) field[x][y]=GOAL;
else field[x][y]=UNPASSABLE;
x++;
}
while(x<FX_SIZE);
printf("\n");
y++;
}
while( y<FY_SIZE );
printf("\nBitte Startkoordinaten X und Y eingeben:\n");
scanf("%d %d",&x,&y);
find_path(x,y);
y=0;
do
{
x=0;
do
{
if (field[x][y]==MARK )putch('p');
else if ( field[x][y]==UNPASSABLE ) putch('x');
else if ( field[x][y]==PASSABLE || field[x][y]== ALREADY_PASSED ) putch(' ');
else if ( field[x][y]==GOAL ) putch('g');
x++;
}
while(x<FX_SIZE);
printf("\n");
y++;
}
while( y<FY_SIZE );
getch();
return (0);
}
