Pfadsuche

[delimitr]

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);
}