1989年開業 情報工学部門 文部科学省登録番号 第22082号 公益社団法人日本技術士会会員 東大阪商工会議所会員

≫サンプルプログラム一覧 

オープンソース/C言語サンプルプログラム 経路探索1(アスキーアート)〜乱数〜

●文字型二次元配列にマッピングされた領域で、
 開始位置から終了位置までの経路を探索する
 プログラムです。
●壁の位置には 'X'、開始位置には 'S'、終了位置
 には 'G' を格納しておきます。
●探索者が通った位置には ',' を格納します。
●探索者は乱数から計算された方向に進みます。
●移動先の位置が壁のとき、移動せずに
 「壁フラグ」を立てておきます。
●「壁フラグ」が立っているときは、距離の検査
 をせずに移動します。
 それ以外のときは、終了位置までの距離が
 現在位置より小さくなるときのみ移動します。
●画面には最終結果を表示します。
 ≫ソースファイルのダウンロード:
  tansaku001.C


【問題】
●何回も試行して結果を確認してみよう。
●開始位置、終了位置を変えてみよう。
●壁の設定を変えて、経路がどのように変化する
 か確認してみよう。
●「壁フラグ」が立っているとき、距離の検査を
 しないのはなぜか。

/******************************************/
/*  経路探索(アスキーアート)            */
/*                                        */
/*  領域には壁が設定されている            */
/*  開始位置からランダムに経路探索をする  */
/*  終了位置に到達したら終了する          */
/******************************************/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define  TMAX 500                                       // 試行回数MAX
#define  XMAX  60                                       // 領域水平方向MAX
#define  YMAX  30                                       // 領域垂直方向MAX

char  buf[YMAX][XMAX];                                  // 領域配列
int   xS=0,xE=XMAX-1;                                   // 開始位置
int   yS=0,yE=YMAX-1;                                   // 終了位置

void  INIbuf(void);                                     // 領域設定

void  main( )
{
    char  Sc=',';                                       // 探索者の文字
    int   x,y,dx,dy;                                    // 探索者位置
    int   wx,wy,w,dst2;                                 // 終了距離2乗
    int   waFG=0;                                       // 壁フラグ
    int   i,j;
    unsigned long seed;                                 // 乱数の種

    printf("\n経路探索(AA)\n");

    time(&seed);                                        // 時刻取得(秒)
    srand(seed);                                        // 乱数の種をまく

    INIbuf( );                                          // 領域設定
    x=xS; y=yS;                                         // 最初の位置

    for( j=0; j<TMAX; j++ )
      {
        dx=rand( )%3-1;                                 // 移動量x(-1,0,1)
        if ( x==0 && dx<0 ) continue;                   // 左端
        if ( x==XMAX-1 && dx>0 ) continue;              // 右端

        dy=rand( )%3-1;                                 // 移動量y(-1,0,1)
        if ( y==0 && dy<0 ) continue;                   // 上端
        if ( y==YMAX-1 && dy>0 ) continue;              // 下端
        if ( dx==0 && dy==0 ) continue;                 // 移動なし

        if ( buf[y+dy][x+dx]=='X' )                     // 壁あり
          { waFG=1; continue; }

        if ( waFG==0 )                                  // 壁なしのとき
          {
            wx=xE-x; wy=yE-y;
            dst2=wx*wx+wy*wy;                           // 終了距離2乗(現在)
            wx=xE-(x+dx); wy=yE-(y+dy);
            w=wx*wx+wy*wy;                              // 終了距離2乗
            if ( w>=dst2 ) continue;                    // 距離が縮まらない
          }

        x+=dx; y+=dy;                                   // 探索者位置更新
        if ( x==xE && y==yE ) break;                    // 終了位置到達

        buf[y][x]=Sc;                                   // 探索者通過
        waFG=0;
      }

    //--結果表示--
    for( y=0; y<YMAX; y++ )
      { printf("\n%.*s",XMAX,&buf[y][0]); }             // 1行表示
    printf("\n試行回数=%d",j);
    if ( j>=TMAX ) printf(" 探索失敗!!");
    printf("\n");
}


void  INIbuf( )
/*------------*/
/*  領域設定  */
/*------------*/
{
    memcpy(&buf[ 0][0],"                       XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 1][0],"                       XXXXXXXXXXX                          ",XMAX);
    memcpy(&buf[ 2][0],"                                                            ",XMAX);
    memcpy(&buf[ 3][0],"     XXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 4][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 5][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 6][0],"     XXXXXXXXXXXX                  XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 7][0],"     XXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 8][0],"     XXXXXXXXXXXXXXXXX             XXXXXXXXXXXXXXX          ",XMAX);
    memcpy(&buf[ 9][0],"     XXXXXXXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[10][0],"     XXXXXXXXXXXXXXXXX                                      ",XMAX);
    memcpy(&buf[11][0],"                           XXXXXXXXXXXXXXX                  ",XMAX);
    memcpy(&buf[12][0],"     XXX      XXX          XXXXXXXXXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[13][0],"     XXX      XXX          XXXXXXXXXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[14][0],"     XXX   XXXXXXXXXXXXX          XXXXXXXX     XXXXXXXXX    ",XMAX);
    memcpy(&buf[15][0],"           XXXXXXXXXXXXX          XXXXXXXX                  ",XMAX);
    memcpy(&buf[16][0],"           XXXXXXXXXXXXX   XXXXXX     XXXX                  ",XMAX);
    memcpy(&buf[17][0],"   XXX  XXXXXXXXXXXXX      XXXXXX     XXXX                  ",XMAX);
    memcpy(&buf[18][0],"   XXX  XXXXXXXXXXXXX      XXXXX  XXXXXXXX                  ",XMAX);
    memcpy(&buf[19][0],"        XXXXXXXXXXXXX                                       ",XMAX);
    memcpy(&buf[20][0],"                               XXXXXXX                      ",XMAX);
    memcpy(&buf[21][0],"            XXXXXXX            XXXXXXX                      ",XMAX);
    memcpy(&buf[22][0],"            XXXXXXX   XXXXXXXXXXXXX      XXXXXXXXXXXXXX     ",XMAX);
    memcpy(&buf[23][0],"      XXXXXXXXXXXXX   XXXXXXXXXXXXX      XXXXXXXXXXXXXX     ",XMAX);
    memcpy(&buf[24][0],"      XXXXXXX         XXXXXXXXXXXXX       XXXXXXXXXXX       ",XMAX);
    memcpy(&buf[25][0],"      XXXXXXX             XXXXXXXXX       XXXXXXXXXXX       ",XMAX);
    memcpy(&buf[26][0],"      XXXXXXX             XXXXXXXXX    XXXXXXXXXXXXXX       ",XMAX);
    memcpy(&buf[27][0],"      XXXXXXX         XXXXXXXXXXXXX    XXXXXXXXXXXXXX       ",XMAX);
    memcpy(&buf[28][0],"                      XXXXXXXXXXXXX                         ",XMAX);
    memcpy(&buf[29][0],"                                                            ",XMAX);

    buf[yS][xS]='S'; buf[yE][xE]='G';
}
   

©著作者からのお願い

●プログラムの著作者、著作権者は佐伯英子です。
●このページで公開するプログラムは、複製、改変、無償再配布できます。
●再配布に当たっては、必ず著作者名を明記し、ソースも公開してください。
●改変後に再配布される場合も、原著作者を明記していただき、ソースも公開してください。
●これらのプログラムを使って、有償サービスをしていただいてもかまいません。
●これらのプログラムは、改変されたものも含めて、無断で有償再配布しないでください。
●これらは、再再配布以降にも引き継がれます。

         【ご利用例】
●ブログやホームページ、印刷物に掲載していただいてもかまいません。(出典明記)
●学校の授業や実習、会社の研修、有料の講座などでお使いいただけます。(出典明記)
無断で販売しないでください。
----------------------------------------
●お問合せはどうぞこちらから
----------------------------------------
■著作権法全文(e-Govウェブサイト)■
法令全般



佐伯英子技術士事務所 〒542-0073 大阪市中央区日本橋 1-14-13 サンオフィス日本橋601  E-mail: yfb22332@nifty.com