ユーニックス総合研究所

  • home
  • archives
  • c-way-point-nav

C言語によるウェイポイントナビゲーションの基礎【ゲームプログラミング】

  • 作成日: 2023-09-13
  • 更新日: 2023-12-24
  • カテゴリ: C言語

ウェイポイントナビゲーション

ゲームプログラムにおいて敵やプレイヤーの移動は重要な処理です。
しかしゲームのマップなどは障害物もあったりしてなかなかスムーズには移動できません。

そういう時にアプローチとして、人の手を入れて移動しやすくするということを行う場合があります。
具体的には移動点をマップ上に配置して、その点に向けてプレイヤーなどを移動させる、と言う具合です。
この点をウェイポイントと言います。そしてこのウェイポイント上を移動させることをウェイポイントナビゲーションと言います。

今回はこのウェイポイントナビゲーションをC言語で実装してみたいと思います。

プログラムの動作風景

今回のプログラムを実行すると以下のような動作になります。

ソースコード全文

ソースコードは以下になります。
ライセンスはMITです。 

#include <stdio.h>  
#include <stdlib.h>  
#include <unistd.h>  
#include <assert.h>  

enum {  
    MAP_WIDTH = 20,  
    MAP_HEIGHT = 10,  
};  

enum {  
    N,  // 北  
    E,  // 東  
    S,  // 南  
    W,  // 西  
};  

typedef struct {  
    int x, y;  
} Vector2i;  

typedef struct WayPoint {  
    Vector2i pos;  

    // 東西南北に存在するウェイポイントへのリンク  
    struct WayPoint *links[4];  
} WayPoint;  

typedef struct {  
    Vector2i pos;  

    // ウェイポイント上の移動で次の目標になるウェイポイント  
    struct WayPoint *target_way_point;  

    // ウェイポイント上の移動で前にいたウェイポイント  
    struct WayPoint *before_way_point;  
} Player;  

Player player;  
WayPoint way_points[16];  
int way_points_len;  

// 20 x 10  
const char *map = \  
    "    w               \n"  
    "                    \n"  
    "                    \n"  
    "    w        w      \n"  
    "                    \n"  
    "                    \n"  
    "    w        w      \n"  
    "                    \n"  
    "                    \n"  
    "             w      \n"  
    ;  

// way_pointsから引数posにマッチするウェイポイントを探して返す  
WayPoint *find_way_point_by_pos(Vector2i pos) {  
    for (int i = 0; i < way_points_len; i++) {  
        if (way_points[i].pos.x == pos.x &&  
            way_points[i].pos.y == pos.y) {  
            return &way_points[i];  
        }  
    }  

    return NULL;  
}  

void build_way_points(void) {  
    Vector2i pos = {0};  

    // mapからウェイポイントの位置を探しウェイポイントを保存する  
    for (const char *p = map; *p; p++) {  
        char c = *p;  
        if (c == '\n') {  
            pos.x = 0;  
            pos.y++;  
        } else if (c == 'w') {  
            pos.x++;  
            WayPoint *wp = &way_points[way_points_len];  
            wp->pos = pos;  
            way_points_len++;  
        } else {  
            pos.x++;  
        }  
    }  

    // 構築したウェイポイントにリンクを張る  
    for (int i = 0; i < way_points_len; i++) {  
        WayPoint *wp = &way_points[i];  

        // N  
        // 現在のwpから上方向（北）に存在するウェイポイントを検索  
        for (int y = wp->pos.y - 1; y >= 0; y--) {  
            Vector2i p = { wp->pos.x,  y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[N] = found;  
                break;  
            }  
        }  

        // E  
        // 現在のwpから右方向（東）に存在するウェイポイントを検索  
        for (int x = wp->pos.x + 1; x < MAP_WIDTH; x++) {  
            Vector2i p = { x, wp->pos.y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[E] = found;  
                break;  
            }  
        }  

        // S  
        // 現在のwpから下方向（南）に存在するウェイポイントを検索  
        for (int y = wp->pos.y + 1; y < MAP_HEIGHT; y++) {  
            Vector2i p = { wp->pos.x,  y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[S] = found;  
                break;  
            }  
        }  

        // W  
        // 現在のwpから左方向（西）に存在するウェイポイントを検索  
        for (int x = wp->pos.x - 1; x >= 0; x--) {  
            Vector2i p = { x, wp->pos.y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[W] = found;  
                break;  
            }  
        }  
    }  
}  

void init(void) {  
    build_way_points();  
}  

void find_next_target_way_point(void) {  
    if (!player.target_way_point) {  
        // 目標のウェイポイントが設定されていなければ適当なウェイポイントに設定する  
        player.target_way_point = &way_points[0];  
        return;  
    }  

    WayPoint *wp = player.target_way_point;  

    // linksから生きているリンクを探す  
    WayPoint *alive_way_points[4];  
    int alive_way_points_len = 0;  

    for (int i = 0; i < 4; i++) {  
        if (wp->links[i]) {  
            // 生きているリンクかつ、前にいたウェイポイントじゃなければ保存  
            alive_way_points[alive_way_points_len++] = wp->links[i];  
        }  
    }  

    assert(alive_way_points_len != 0);  

    if (alive_way_points_len == 1) {  
        // 生きているリンクが1つしかないならそれを目標にする  
        player.before_way_point = player.target_way_point;  
        player.target_way_point = alive_way_points[0];  
    } else {  
        // 生きているリンクからランダムに次のウェイポイントを探す  
        // 前にいたウェイポイントは除外する  
        WayPoint *next_way_point = NULL;  
        do {  
            int i = rand() % alive_way_points_len;  
            next_way_point = alive_way_points[i];  
        } while (next_way_point == player.before_way_point);  

        player.before_way_point = player.target_way_point;  
        player.target_way_point = next_way_point;  
    }  
}  

void player_move_on_way_points(void) {  
    if (!player.target_way_point) {  
        // 目標のウェイポイントが設定されていない  
        find_next_target_way_point();  
    } else if (player.target_way_point->pos.x == player.pos.x &&   
               player.target_way_point->pos.y == player.pos.y) {  
        // 目標のウェイポイント上にプレイヤーが存在する  
        find_next_target_way_point();  
    }  

    // ウェイポイントの座標に単純な追跡をする  
    // プレイヤーの座標をウェイポイントの座標に近づけていく  
    WayPoint *t = player.target_way_point;  
    if (player.pos.x < t->pos.x) {  
        player.pos.x++;  
    } else if (player.pos.x > t->pos.x) {  
        player.pos.x--;  
    }  
    if (player.pos.y < t->pos.y) {  
        player.pos.y++;  
    } else if (player.pos.y > t->pos.y) {  
        player.pos.y--;  
    }  
}  

void update(void) {  
    player_move_on_way_points();  
}  

void draw(void) {  
    system("clear");  // Windows: system("cls");  

    for (int y = 0; y < MAP_HEIGHT; y++) {  
        for (int x = 0; x < MAP_WIDTH; x++) {  
            int ok = 0;  

            if (x == player.pos.x && y == player.pos.y) {  
                putchar('P');  
                ok = 1;  
            }  
            if (!ok) {  
                for (int i = 0; i < way_points_len; i++) {  
                    WayPoint *wp = &way_points[i];  
                    if (x == wp->pos.x && y == wp->pos.y) {  
                        putchar('w');  
                        ok = 1;  
                        break;  
                    }  
                }  
            }  
            if (!ok) {  
                putchar('.');  
            }  
        }  
        putchar('\n');  
    }  
}  

int main(void) {  
    init();  

    for (;;) {  
        update();  
        draw();  
        usleep(1000 * 200);  
    }  

    return 0;  
}

ちょっと長くなっちゃいましたが、頑張って解説したいと思います。

プログラムの仕様

今回作るプログラムはウェイポイントのデモです。
ウェイポイントは構造体で、座標とそれから周囲のウェイポイントへのリンクを持っています。
このリンクは東西南北で4方向のリンクになるので配列としては要素4つの配列になります。

文字列のマップデータをパースして、マップデータ上に書かれたウェイポイントの文字を見つけたら、ウェイポイントを作成し、その座標をそのウェイポイントに保存します。ウェイポイントは配列の中に保存されています。

ウェイポイントの配列を作成したら、次にその各ウェイポイントにリンクを貼ります。
各ウェイポイントの東西南北の座標を走査して、存在するウェイポイントをリンクとして配列に保存します。
つまりウェイポイント間のリンクの構築は自動で行います。
方向を東西南北に限定しているので、斜めにウェイポイント間を移動するということはしません。
興味ある人はプログラムを改造してみてください。

このウェイポイントのルート上をプレイヤーに移動させます。

ゲームループではプレイヤーの持っている目標のウェイポイントに単純な追跡をします。
プレイヤーの座標を目標のウェイポイントの座標に近づけるだけの処理です。

そして目標のウェイポイント上にプレイヤーが到達したら、次のウェイポイントを探します。
このときに、目標のウェイポイントが持っているリンクから次のウェイポイントを決定します。
リンクが1つしかない場合は、そのリンクを次の目標に設定します。
リンクが複数の場合は、ランダムに次のウェイポイントを決定します。
この時、前にいたウェイポイントは除外するようにします。

プレイヤーは座標と目標ウェイポイント、それから前にいたウェイポイントを持っています。

こんな感じの仕様になります。

定数

enum {  
    MAP_WIDTH = 20,  
    MAP_HEIGHT = 10,  
};  

enum {  
    N,  // 北  
    E,  // 東  
    S,  // 南  
    W,  // 西  
};

定数は以上になります。
MAP_WIDTHはマップの横幅、MAP_HEIGHTはマップの高さを表す定数です。

今回はマップをデータ行列にしていません。
ですのでdraw()ではif文とかを駆使して描画しています。
実用的なゲームにしたい場合はデータ行列を作ったほうが良いと思います。

N, E, S, Wは東西南北を表す定数です。

  • N ... North（北）
  • E ... East（東）
  • S ... South（南）
  • W ... West（西）

東西南北は人間の身体で言うと北が頭、東が右肩、南が足、西が左肩になります。

構造体と変数

typedef struct {  
    int x, y;  
} Vector2i;  

typedef struct WayPoint {  
    Vector2i pos;  

    // 東西南北に存在するウェイポイントへのリンク  
    struct WayPoint *links[4];  
} WayPoint;  

typedef struct {  
    Vector2i pos;  

    // ウェイポイント上の移動で次の目標になるウェイポイント  
    struct WayPoint *target_way_point;  

    // ウェイポイント上の移動で前にいたウェイポイント  
    struct WayPoint *before_way_point;  
} Player;  

Player player;  
WayPoint way_points[16];  
int way_points_len;  

// 20 x 10  
const char *map = \  
    "    w               \n"  
    "                    \n"  
    "                    \n"  
    "    w        w      \n"  
    "                    \n"  
    "                    \n"  
    "    w        w      \n"  
    "                    \n"  
    "                    \n"  
    "             w      \n"  
    ;

Vector2iは座標を表す構造体です。

WayPointはウェイポイントを表す構造体で、座標とリンクを持っています。
リンクはWeyPointのポインタ配列です。

Playerは座標と目標ウェイポイント、それから前にいたウェイポイントを持っています。
これらのウェイポイントは次の目標ウェイポイントの決定に使われます。

グローバル変数はplayerがプレイヤー。
way_pointsがウェイポイントの配列。
way_points_lenがway_pointsの長さです。

mapがマップデータです。
マップデータは文字列になっています。
wという文字がウェイポイントをあらわす文字です。
ウェイポイントの初期化ではこの文字を検出してウェイポイント構築します。

main関数

int main(void) {  
    init();  

    for (;;) {  
        update();  
        draw();  
        usleep(1000 * 200);  
    }  

    return 0;  
}

main関数の構造です。
まずinit()で初期化をします。
それから無限ループに入ってupdate()とdraw()を呼び出します。
処理はループ一回ごとにちょっとずつ進みます。
update()でゲームの更新処理、draw()でゲームの描画処理をします。

ループの中でusleep()で休憩を入れています。
これを取っちゃうとビジーループになってしまうので気を付けてください。

init関数

void init(void) {  
    build_way_points();  
}

init関数では初期化をします。
build_way_points()でウェイポイントの構築だけしています。

build_way_points関数

// way_pointsから引数posにマッチするウェイポイントを探して返す  
WayPoint *find_way_point_by_pos(Vector2i pos) {  
    for (int i = 0; i < way_points_len; i++) {  
        if (way_points[i].pos.x == pos.x &&  
            way_points[i].pos.y == pos.y) {  
            return &way_points[i];  
        }  
    }  

    return NULL;  
}  

void build_way_points(void) {  
    Vector2i pos = {0};  

    // mapからウェイポイントの位置を探しウェイポイントを保存する  
    for (const char *p = map; *p; p++) {  
        char c = *p;  
        if (c == '\n') {  
            pos.x = 0;  
            pos.y++;  
        } else if (c == 'w') {  
            pos.x++;  
            WayPoint *wp = &way_points[way_points_len];  
            wp->pos = pos;  
            way_points_len++;  
        } else {  
            pos.x++;  
        }  
    }  

    // 構築したウェイポイントにリンクを張る  
    for (int i = 0; i < way_points_len; i++) {  
        WayPoint *wp = &way_points[i];  

        // N  
        // 現在のwpから上方向（北）に存在するウェイポイントを検索  
        for (int y = wp->pos.y - 1; y >= 0; y--) {  
            Vector2i p = { wp->pos.x,  y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[N] = found;  
                break;  
            }  
        }  

        // E  
        // 現在のwpから右方向（東）に存在するウェイポイントを検索  
        for (int x = wp->pos.x + 1; x < MAP_WIDTH; x++) {  
            Vector2i p = { x, wp->pos.y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[E] = found;  
                break;  
            }  
        }  

        // S  
        // 現在のwpから下方向（南）に存在するウェイポイントを検索  
        for (int y = wp->pos.y + 1; y < MAP_HEIGHT; y++) {  
            Vector2i p = { wp->pos.x,  y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[S] = found;  
                break;  
            }  
        }  

        // W  
        // 現在のwpから左方向（西）に存在するウェイポイントを検索  
        for (int x = wp->pos.x - 1; x >= 0; x--) {  
            Vector2i p = { x, wp->pos.y };  
            WayPoint *found = find_way_point_by_pos(p);  
            if (found) {  
                wp->links[W] = found;  
                break;  
            }  
        }  
    }  
}

build_way_points関数ではまずマップデータ（map）をパースします。
そして文字wを検出して、その文字がある座標を使ってウェイポイントを作成します。
作成と言っても配列の要素を初期化するだけです。

それから構築したウェイポイントの配列の各ウェイポイントにリンクを貼っていきます。
リンクのアルゴリズムはウェイポイント座標の東西南北の座標を見て、その東西南北の位置にあるウェイポイントをリンクとして保存するという感じになっています。

このアルゴリズムだとウェイポイントの位置が直線状からずれているとリンクとして検出されません。
このずれを許容できるようにすると多少ずれていてもリンクとして保存されますので、複雑なウェイポイントルートになるかもしれません。
興味ある人は試してみてください。

update関数

void update(void) {  
    player_move_on_way_points();  
}

update関数ではplayer_move_on_way_points()を呼び出します。
ゲームロジックを追加したい場合はこのupdate()を拡張します。
今回はプレイヤーをウェイポイント上で移動させるだけですのでこれだけです。

player_move_on_way_points関数

void player_move_on_way_points(void) {  
    if (!player.target_way_point) {  
        // 目標のウェイポイントが設定されていない  
        find_next_target_way_point();  
    } else if (player.target_way_point->pos.x == player.pos.x &&   
               player.target_way_point->pos.y == player.pos.y) {  
        // 目標のウェイポイント上にプレイヤーが存在する  
        find_next_target_way_point();  
    }  

    // ウェイポイントの座標に単純な追跡をする  
    // プレイヤーの座標をウェイポイントの座標に近づけていく  
    WayPoint *t = player.target_way_point;  
    if (player.pos.x < t->pos.x) {  
        player.pos.x++;  
    } else if (player.pos.x > t->pos.x) {  
        player.pos.x--;  
    }  
    if (player.pos.y < t->pos.y) {  
        player.pos.y++;  
    } else if (player.pos.y > t->pos.y) {  
        player.pos.y--;  
    }  
}

この関数ではプレイヤーを目標ウェイポイントに向けて移動させます。
移動方法はx座標とy座標をif文で比較して、座標を増減させるだけです。

プレイヤーが目標ウェイポイントを持っていない、あるいはプレイヤーの座標が目標ウェイポイント上にある場合、次の目標ウェイポイントを検索します。

find_next_target_way_point関数

void find_next_target_way_point(void) {  
    if (!player.target_way_point) {  
        // 目標のウェイポイントが設定されていなければ適当なウェイポイントに設定する  
        player.target_way_point = &way_points[0];  
        return;  
    }  

    WayPoint *wp = player.target_way_point;  

    // linksから生きているリンクを探す  
    WayPoint *alive_way_points[4];  
    int alive_way_points_len = 0;  

    for (int i = 0; i < 4; i++) {  
        if (wp->links[i]) {  
            // 生きているリンク（NULLじゃに）なら保存  
            alive_way_points[alive_way_points_len++] = wp->links[i];  
        }  
    }  

    assert(alive_way_points_len != 0);  

    if (alive_way_points_len == 1) {  
        // 生きているリンクが1つしかないならそれを目標にする  
        player.before_way_point = player.target_way_point;  
        player.target_way_point = alive_way_points[0];  
    } else {  
        // 生きているリンクからランダムに次のウェイポイントを探す  
        // 前にいたウェイポイントは除外する  
        WayPoint *next_way_point = NULL;  
        do {  
            int i = rand() % alive_way_points_len;  
            next_way_point = alive_way_points[i];  
        } while (next_way_point == player.before_way_point);  

        player.before_way_point = player.target_way_point;  
        player.target_way_point = next_way_point;  
    }  
}

この関数ではプレイヤーの目標ウェイポイントを更新します。
この関数が今回のプログラムのキモです。

アルゴリズムとしては、現在の目標ウェイポイントの持つリンクから次の目標ウェイポイントを探します。
この時、条件として以下があります。

  • リンクが1つの場合はそのリンクを目標に設定する
  • リンクが前にいたウェイポイントであれば、そのリンクは除外する

この条件にするとプレイヤーがウェイポイントルート上で来た道をすぐもどっちゃうという動作を減らすことができます。
このほうが移動処理が自然に見えるのでこうしています。

まず目標ウェイポイント（target_way_point）のリンクからNULLポインタじゃないポインタを配列（alive_way_points）に保存します。

そしてalive_way_pointsの長さが1なら、0番目の要素を次の目標ウェイポイントにします。
長さが1以外なら、ランダムに次の目標ウェイポイントを決定します。
do while文でループ処理をして、next_way_pointが前にいたウェイポイントじゃない間、ループします。
next_way_pointに次の目標ウェイポイントが保存されますので、ループから抜けたらこれをplayer.target_way_pointに設定します。
player.target_way_pointを更新する前にこれをplayer.before_way_pointに保存しています。

draw関数

void draw(void) {  
    system("clear");  // Windows: system("cls");  

    for (int y = 0; y < MAP_HEIGHT; y++) {  
        for (int x = 0; x < MAP_WIDTH; x++) {  
            int ok = 0;  

            if (x == player.pos.x && y == player.pos.y) {  
                putchar('P');  
                ok = 1;  
            }  
            if (!ok) {  
                for (int i = 0; i < way_points_len; i++) {  
                    WayPoint *wp = &way_points[i];  
                    if (x == wp->pos.x && y == wp->pos.y) {  
                        putchar('w');  
                        ok = 1;  
                        break;  
                    }  
                }  
            }  
            if (!ok) {  
                putchar('.');  
            }  
        }  
        putchar('\n');  
    }  
}

draw関数ですがデータ行列を作っていないのでif文で泥臭く処理しています。
プレイヤーとウェイポイント、それから何も存在しないことを表す「.」を描画します。
プレイヤー「P」でウェイポイントは「w」です。

おわりに

今回はC言語でウェイポイントナビゲーションをやってみました。
なにか参考になれば幸いです。

カテゴリー

メニュー