[게임알고리즘] 6강 최단경로

다익스트라 알고리즘

 

Main.cpp

#include "ShortestPath.h"
 
#define I 0xFFFFFF
 
int tile[] = {
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, I, 1, 1, 1, 1, 1, I, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, I, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, I, I, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
};
 
int main() {
    SP sp(100);
    
    int path[100], pathNum;
    int test[3][2] = { {0, 12}, {1, 11}, {4, 20} };
    for(int i=0; i<3; i++)
    {
        int* t = test[i];
        sp.run(tile, 10, 8, t[0], t[1], path, pathNum);
        printf("== s(%d) e(%d) %d\n", t[0], t[1], pathNum);
        for(int j=0; j<pathNum; j++)
            printf("%d %s", path[j], j<pathNum-1 ? "=>":"\n");
    }
 
    return 0;
}
 

 

 

ShortestPath.h

#include <stdio.h>
#include <string.h>
 
#define TW 32
#define TH 32
 
struct Node {
    bool v;// visit
    int n;// value
    int* p;
    int pNum;
};
 
struct Point {
    float x, y;
};
 
struct SP
{
    SP(int wh);
    virtual ~SP();
    
    int wh;
    Node* node;
    
    void run(int* data, int w, int h, 
            int start, int end, int* path, int& pathNum);
            
    void run(int* data, int w, int h, 
            Point start, Point end, Point* path, int& pathNum);
};

 

 

ShortestPath.cpp

#include "ShortestPath.h"
 
SP::SP(int wh)
{
    node = new Node[wh];
    this->wh = wh;
}
 
SP::~SP()
{
    delete node;
}
 
void SP::run(int* data, int w, int h, 
            int start, int end, int* path, int& pathNum)
{
    int wh = w*h;
    if( this->wh < wh )
    {
        delete node;
        node = new Node[wh];
        this->wh = wh;
    }
    for(int i=0; i<wh; i++)
    {
        Node* n = &node[i];
        n->v = false;
        n->n = I;
        n->p = new int[wh/2];
        n->pNum = 0;
    }
    Node* n = &node[start];
    //n->v = true;
    n->n = 0;
    n->p[0] = start;
    n->pNum = 1;
    
    for(;;)
    {
        // 방문하지 않은곳들 중에서 가장 비용이 싼곳 찾는다.
        int min = 0xffffff;
        int curr = -1;
        for(int i=0; i<wh; i++)
        {
            if( node[i].v==false &&
                node[i].n < min )
            {
                min = node[i].n;
                curr = i;
            }
        }
        
        // 더 이상 방문할곳이 없으면 나간다.
        if( curr==-1 ) break;
        
        node[curr].v = true;
        
        // 4방향에 대해서 각각 비용을 계산해서 더 작으면 갱신한다.
        int x = curr % w;
        int y = curr / w;
        
#if 0
        int dy[] = { -1, 1, w, -w };
        for (int i = 0; i < 4; ++i)
        {
            int nextV = curr + dy[i];
            if ((i == 0 && x == 0) ||
                (i == 1 && x == w - 1) ||
                (i == 2 && y == 0) ||
                (i == 3 && y == h - 1))
                continue;
            
            Node* d = &node[nextV];
            Node* s = &node[curr];
            
            if( d->n > s->n + tile[nextV] )
            {
                d->n = s->n + tile[nextV];
                memcpy(d->p, s->p, sizeof(int) * s->pNum);
                d->p[ s->pNum ] = nextV;
                d->pNum = s->pNum + 1;
            }
        }
#else
#define exe(con, nextV)                         \
        if( con )                               \
        {                                       \
            Node* d = &node[nextV];            \
            Node* s = &node[curr];              \
            if( d->n > s->n + tile[nextV] )    \
            {                                   \
                d->n = s->n + tile[nextV];     \
                memcpy(d->p, s->p, sizeof(int) * s->pNum);\
                d->p[ s->pNum ] = nextV;       \
                d->pNum = s->pNum + 1;          \
            }                                   \
        }
        exe(x > 0, curr-1);
        exe(x < w-1, curr+1);
        exe(y > 0, curr-w);
        exe(y < h-1, curr+w);
#endif
    }// for(;;)
    
    n = &node[end];
    memcpy(path, n->p, sizeof(int) * n->pNum);
    pathNum = n->pNum;
}
 
void SP::run(int* data, int w, int h, 
            Point start, Point end, Point* path, int& pathNum)
{
    int s = w * (start.y / TH) + start.x / TW;
    int e = w * (end.y / TH) + end.x / TW;
    int* p = new int[w * h / 2];
    run(data, w, h, s, e, p, pathNum);
    for(int i=1; i<pathNum - 1; i++)
    {
        path[i].x = TW * (p[i] % w) + TW / 2;
        path[i].y = TH * (p[i] / w) + TH / 2;
    }
    path[0] = start;
    path[pathNum-1] = end;
}

 

 

매일매일 열심히 게임개발하고 있습니다