A* (A star) is one of the most popular algorithms for the path finding in the computer science. It looks for the optimal way with mixing DFS(Depth First Search)and BFS(Breadth First Search) while as it uses the Heuristic method.

Here I introduce this algorithm with one RPG prototype which I implemented many years back (actually, back in my university school days).

Let's take a look at the two screenshots.

The actual game screen is on the left side whereas right one additionally visualizes the structure of the game map. As you can see them, this game was implemented with 2d style map data which is constructed with 2 dimensional grids. Each grids have proper information including position, size, graphical data and one boolean whether are any obstacles there or not. Actually, the grids in the screenshot are displayed larger than actual size in the game for your easier understanding. If the grid is filled with red color, then it's obstacle space where the player character can't go to. So, we can understand as it's blocked space. You may think some grids looks having obstacles even though they doesn't filled with the red color. Considering perspective, those obstacles are over the player character so it's available space. Let's suppose the player character moves to one arbitrary position(grid) then let's see how A* algorithm works for the path finding.

Before starting, we can implement a grid with a Node. A node is a data structure normaly used in Linked List.

Suppose the yellow node is the destination. It looks for the available nodes from the player character's (It tries the BFS). After investigated the available 8 directions nodes, It selects one which is the closest to the destination. In this case, green arrow node.
In the meantime, it handles the internal data structure. Mainly, it constructs two linked lists (exactly, Stack) which are Open Node and Close Node. The Open Node is a candidate list which needs to investigate the list nodes further. That is, we must visit 8 directions nodes (near 8 grids) from one node. If we don't perform this yet, then this node goes appending in the Open Node. The Close Node, on the other hand, is a list that consisted of the nodes which we don't need to investigate further. And notice this, every time we append one node in the Open Node, it can sort the nodes by distance between a node and the destination.

So far, the Open Node has a green arrow node plus the yellow arrow nodes and the Close Node has only the starting point node.

Let's move on to the next. This time, It visits 8 directions nodes from the green arrow node. (It tries the DFS. A* goes through the best nodes first)
Now, the Open Node has new yellow and green arrow nodes additionally and the Close Node has the starting point node and the light green arrow node.

Yellow arrow: New nodes appended in the Open Node.
Light yellow arrow: The nodes appended in the Open Node previously.
Green arrow: A new node appended in the Close Node.
Light green arrow: the node appended in the Close node in the previous step.

Soon it reaches to a cul-de-sac, it tries to navigate with a candidate node from the Open Node. In this case, the available way is only the lower node.

Again, it tries to navigate a candidate node from the Open Node because all directions are unavailable. They are blocked or already visited. So the result will be the above picture.

Since the next candidate node in the Open Node would be the closest to the destination, it would be just right of the starting point. But we can find out soon that the around 8 nodes of it were already visited before, so it will be moved to the Close Node immediately. Now, the next candidate node would be just above the starting point. However, it should be moved to the Close Node also by the same reason. So the next candidate would be the most upper side node in the below picture.

But in this case if we figure out the next candidates around it, they all are more apart from the destination compared to a candidate node in the Open Node. So the next candidate will be the right bottom node from the starting point.
If we keep going through this sequence, we can finally reach to the destination.

Lastly, we can get a path if we track back the white arrows. Those white arrow nodes would be in the Close Node, so just iterate nodes from the last to the first reversely.

If you can understand the A* theory then let's take a look at the code now.

//A node structure 
typedef struct node_s {
    int degree;                       //Depth info. Same with the depth in the tree data structure 
    int distance;                     //Distance between this node and the destination 
    int value_factor;                 //Evaluated value (degree + distance) 
    int x, y;                         //Grid position 
    struct node_s* direct[8];         //Neighbor nodes around this 
    struct node_s* prev_node;         //Previous node in the linked list  
    struct node_s* next_node;         //Next node in the linked list.  
} node_t;
//A stack for node sorting
typedef struct node_stack_s {
    node_t*  node;                    //A node in this stack position
    struct node_stack_s*  next_node;  //Next node stack
} node_stack_t;

Obviously, we can get the evaluated value (a sum of degree and distance) but you can modify the units of the degree and distance properly for your case. For your reference, If the minimum value of the degree is 1, then 1 is good to the distance between adjancent 2 nodes.

Now, let's declare global Open Node, Close Node and one stack.

node_t *OPEN = NULL, *CLOSED = NULL;
node_stack_t* STACK = NULL;

Let's see the pseudo code of next functions because it's not much importance. But pretty enough just with commentary.

//Initialize list and stack (also clean up resources)
void init_astar()
    //Remove all nodes while iterating Open Node
    //Remove all nodes while iterating Close Node
    //Remove all stack resources while iterating the stack.
//Check whether the node in the given position is blocked or not. 
bool is_available_grid(int x, int y)
    //Implement whether the player character can move to this node or not.
    //If it's available, return TRUE.
    //otherwise (in case of blocked?), return FALSE. 
//Check whether the node in the given position is existed in Open Node. 
node_t* is_open(int x, int y)
    //Iterate Open Node to find the node in the position.
    //If it does, return the node.
//Check whether the node in the given position is existed in CLOSE NODE. 
node_t* is_closed(int x, int y)
    //Iterate CLOSE NODE to find the node in the position.
    //If it does, return the node.
//Insert a given node in the stack. 
void push_into_stack(node_t* node)
    //Allocate one stack node.
    //Set the input node to the stack node. 
    //Push the stack node into the stack.
//Remove a node from the stack. 
node_t* pop_from_stack()
    //Get the last stack node from the stack.
    //Remove stack node.
    //Return the node of the stack node

Please refer the attached file if you wanna see the actual source code of above functions.

Now, it's a little more serious. Next is the path finding function.

//Starting point: start_x, start_y, and destination: dest_x, dest_y
node_t* find_path( int start_x, int start_y, int dest_x, int dest_y ) {
    node_t* present=NULL;    //Starting point node
    //Add the starting point node. Reversely, starting point is the destination here.
    //That means, navigate from the destination to the starting point. 
    //Destination to Starting point as I mentioned above. We can rewind the completed list to figure out the path. 
    present = (node_t*) calloc(1, sizeof(node_t));        
    present->degree = 0;    
    present->distance=  pow((dest_x- start_x), 2) + pow((dest_y - start_y), 2);    //Originally, it requires a square root but not necessary.
    present->value_factor = present->distance;    // distance + degree
    present->x= dest_x;                                          
    present->y= dest_y;

    node_t* best=NULL;      //best keeps the best path list.
    int count=0;     //Count a iteration to prevent the infinite loop.
     //Begin the investigation. But limit the loop count, just in case.
     while(count< FINDPATH_LIMIT) {
        //No more candidates. Probably, we found the path?
        if (OPEN == NULL) {
            return best;
        best = OPEN;    //Begin with investigating a candidate in the Open Node.
        OPEN = best->next_node;    //The next node should be set to a next candidate for next step.
        best->next_node = CLOSED;    //Appends the Closed Nodes to a current best one so that we can keep a constructed path properly.
        CLOSED=best;   //Move to the Closed Node because this best node will be visited in this time.
        //Failed at path finding.
        if(best == NULL) {
            return NULL;   
        if (best->x == start_x && best->y == start_y)  
            return best;
        //Extends neighbor nodes from a current node.
        if (make_child(best, start_x, start_y) == 0 && count == 0) 
            return NULL;
    return best;

Continue to make_child() function.

 //the node to extends, and destination x, y. it also returns a value of extension fact.
bool make_child(node_t* node, int dest_x, int dest_y) {
    bool extended = false;    //Return true if it extended any childs.
    int x = node->x;
    int y = node->y;
    //Create children nodes if they were available space.
    if( is_available_grid(x - 1, y) ) {
        extend_child_node(node, x-1, y, dest_x, dest_y, LEFT_IDX);
    //Implement last 7 directions in the same manner. Differences are just x, y positions.
    //Right: x + 1, y
    //Top: x, y - 1
    //Bottom: x, y + 1
    //Top Left: x - 1, y - 1
    //Top Right: x + 1, y - 1
    //Bottom Left: x - 1, y + 1
    //Bottom Right: x + 1, y + 1 
    return extened;

I hope you understood so far. But actually in this game, it would be more realistic that if we allow diagonal moving only if two adjacent grids are available so. The change won't be difficult at all. I believe you can make it yourself.

Don't allow diagonal moving if two adjacent grids are blocked

Next function is extend_child_node(). This function is designed to extend a node and sort it if necessary.

//A node to extend, a current node position, the destination position, a direction to extend
void extend_child_node(node_t* node, int cur_x, int cur_y, int dest_x, int dest_y, int cur_direct) {
    node_t *old = NULL, *child = NULL;
    int i;
    int degree= node->degree + 1;
    //If a extending node is existed in Open Node, pick it up.
    if (old = Is_open(cur_x, cur_y)) { 

        node->direct[cur_direct] = old;
        //Reset the node. Notice that node order is reversed.
        if (degree < old->degree) {
            old->prev_node = node;
            old->degree = degree;
            old->value_factor = old->distance + old->degree;
    //If a extending node is existed in Close Node.
    } else if (old = is_close(cur_x, cur_y)) {

        node->direct[cur_direct] = old;
        //In some cases, degree won't be valid. Sort it again.
        if (degree < old->degree) {
            old->prev_node = node;
            old->degree = degree;
            old->value_factor = old->distance + old->degree;

    //Create a child node and push it into Open Node.
    } else {

        if ((child = (node_t*) calloc(1, sizeof(node_t))) == NULL) 
            return;    //Lack of memory?
        child->prev_node = node;
        child->degree = degree;
        child->distance =  (cur_x - dest_x) * (cur_x - dest_x) + (cur_y - dest_y) * (cur_y - dest_y);
        child->value_factor = child->distance + child->degree;
        child->x = cur_x;
        child->y = cur_y;
        node->direct[cur_direct] = child;        

It's getting more complex and complex!! If you cannot understand the source code, please draw a temporary path and follow step with this logic. it's going over!

//old: A new node for re-evaluation 
void make_sort(node_t* old) {
    node_t *direct, *previous;
    int i;
    int degree = old->degree + 1;
    for (i=0; i<8; i++) {
        if ((direct = old->direct[i]) == NULL) continue;
        //Updates nodes. Use a stack for children
        if (direct->degree > degree) {
            direct->prev_node = old;
            direct->degree  = degree;
            direct->value_factor  = direct->distance + direct->degree;                                  
    //Updates nodes using a stack.
    while (STACK) {

        previous = pop_from_stack();
        for (i=0; i<8; i++) {

            if ((direct = previous->direct[i]) == NULL) break;

            if (direct->degree > previous->degree + 1) {
                direct->prev_node = previous;
                direct->degree  = previous->degree + 1;
                direct->value_factor  = direct->distance + direct->degree;    

Here, it handles an exceptional case which hasn't been mentioned in the above example. It just re-evaluate the nodes when the Close Node needs update.

Lastly, append a node to the Open Node. Point is, it keeps the order in distance when it push a node.

//new node
void insert_node(node_t* present) {
    node_t* old = NULL, *temp = NULL;
    if (OPEN == NULL) {
        OPEN = present;
    temp = OPEN;
   //Find a node which has a higher value factor than the present.
    while (temp && (temp->value_factor < present->value_factor)) {
        old = temp;  
        temp = temp->next_node;
    //Reconstruct the list. Now these list are sorted by distance.
    if (old) {
        present->next_node = temp;
        old->next_node = present;
    } else {
        present->next_node = temp;
        OPEN = present;

Somewhat difficult to describe the complex logic by me. But you could hopefully understand what I am talking here. Otherwise, please read the source code considerably.

Anyhow, A* is done here. This logic is for a standard case so definitely you could optimize it further. For instance, we can skip the list of nodes if they just construct a straight way. Or probably we can add a way point in the map in such cases doors and gates. Definitely it would be much better for the path finding. In case of 3D map, I believe it's not much different even though. But you need to google for more information.

저작자 표시
Enventor which is also known as a dynamic EDC (Edje Data Collections) Editor, is a EDC script editor tool that supports text editing and previewing functions for the EDC source code. When your application requires real-time changeable layouts like animated ones, you can write the layout design using EDC script, compile it into EDJ format file, and import it into your application using a UI layout component. You can also write design layouts from simple to complex ones using the EDC script with Enventor. Enventor helps you write EDC script code easier and finish your work faster.

Development Environment
  • Ubuntu 16.04
  • vim
  • EFL 1.18

  • https://www.enlightenment.org/about-enventor

    저작자 표시

    Tool: Corel Painter, Wacom INTUOS ART

    저작자 표시

    Tool: Corel Painter, Wacom INTUOS ART

    저작자 표시

    Tool: Corel Painter, Wacom INTUOS ART

    저작자 표시

    Edgar Roni Figaro
    Tool: Corel Painter, Wacom INTUOS ART

    저작자 표시

    1996년 중학생 시절의 이야기이다. 당시 살던 동네의 환경은 그다지 좋진 않았다. 동네 거리는 전봇대의 너저분한 전선들과 늘어진 차량들의 불법 주차로 매우 어수선했었는데, 도로 바닥마저 여기저기 금이 가 있거나 시멘트를 덧대어 곳곳이 울퉁불퉁하여 보기 좋지 않았었다. 하물며 길가엔 언제나 쓰레기가 고여있었고 전봇대 밑둥 역시 항상 쓰레기 더미가 존재했다. 그 시절 나의 통학 풍경은 그러했다. 하지만 더 인상적인 풍경 중 하나는 통학 길에 있는 작은 하천이었는데, 학교를 가기 위해서는 그 하천을 따라가다가 하천 위의 허름한 다리를 나는 지나야만 했었다. 물론, 그 하천 부근 역시 도시의 매연으로 검게 그을리고 쓰레기가 썩어서 여기저기가 시커맸으며 하천의 물 또한 오염되어 악취로 가득했다. 특히 탁한 하천의 썩은물은 녹조까지 심했으며 수포와 더러운 쓰레기가 수면 위 곳곳에 존재했다. 그 곳 풍경과 악취는 나에게 결코 좋은 인상을 남기진 못했다. 심지어, 난 가끔 그 하천의 물을 마시곤 녹색 괴물로 변해버리는 상상을 하곤 했었으니깐. 어쨌든, 나의 통학길의 풍경은 그러했다. 평균 나의 학교 통학 시간은 어림잡아 30분. 평소 나는 학교를 달리다시피 다녔으며 특히나 지루한 등하교 시간은 나에게 너무나 아까운 시간이었다.

    어느날, 난 늦잠을 자곤 허겁지건 학교를 향해 뛰어갔다. 때는 이른 여름이었다. 그날도 역시 하천을 지나 학교로 가야만 했는데, 하천을 따라 놓인 길을 지날 즈음에 난 속보로 걸어가고 있었다. 그런데 멀리 보이는 하천 다리 중간 즈음에, 눈에 띄는 작은 뭔가가 다리 밑에 붙어 있는 것을 보았다. 서퍼런 작은 무언가였는데 여름날 아침의 하천 다리 밑은 대낮처럼 훤했다. 게다가 하천 다리 밑 천장은 매연으로 시커멓게 그을린 이끼들로 뒤덮여 있었기 때문에 그것은 대조적으로 눈에 띄게 잘 보였다. 하천 다리에 도달할 때 쯤, 난 그게 새임을 알 수 있었다. 그건 파랑새였다. 어느날 갑자기 그 새는 하천 다리 밑에 둥지를 짓곤 홀로 살기 시작한 것이다. 새의 파란 빛깔이 신기했지만 그다지 나의 관심거리는 되지 못했다. 난 파랑새를 스쳐지나가듯 쳐다보곤 지나갔다.

    이후, 이상하게도 그 하천을 지날 때마다 나는 다리 밑에 그 파랑새가 있는지 꼭 확인을 했다. 처음에는 그냥 그럴려니 했지만 그 새는 왠지 모르게 나의 이목을 집중시켰다. 무엇보다도 나는 그 새가 그곳에 머물고 있는 것이 신기했다. 파랑새를 처음보기도 했지만 새가 보유한 파란 깃털은 하천 다리 밑의 매연으로 그을린 새까만 그곳과는 너무 대조적이었다. 한마디로 어울리지가 않았다. 최소한 그 새가 아름다운 정경의 숲 속에 살아야 한다고 난 생각했다.

    비 오는 어느 날, 하교길에 난 그 새를 가까이 가서 관찰해 보기로 결심했다. 오후 다섯 시쯤이었고 비가 추적추적 내리고 있었다. 다리 밑에는 아무도 없었다. 우산을 든 채, 난 홀로 다리 밑에 서서 위를 올려다 보았다. 다리의 천정 높이는 내가 서있는 도로로부터 약 4미터 가량의 높이로 그다지 높진 않았다. 하늘에서 떨어지는 빗소리와 다리에 맺힌 빗물이 떨어지는 소리가 뒤엉켜 다리 밑에서 웅성웅성 메아리를 치고 있었다. 난 비에 옷이 홀딱 젖은 채, 지푸라기와 흙으로 만든 새 집을 가만히 올려다 보았다. 집은 겸손하다시피 작았으며 그 안의 파랑새는 눈을 감고 조용히 잠들어 있었다. 그 새는 내 주먹보다도 더 작아 보였다. 몸은 마치 작은 푸른 잎사귀처럼 보였으며 그 사이로 아담한 검은 부리만이 눈에 살짝 비쳤다. 나는 그 새를 멍하니 바라보았다. 근데 그 새가 가진 파란 빛깔은 왠지 모르게 구슬펐다. 그 새는 잠을 자면서도 덜덜 떨고 있었다. 한참을 바라보곤, 난 집으로 발걸음을 곧장 옮겼다.

    이후, 나는 그 새가 조금씩 걱정되기 시작했다. 그 새가 병들진 않을지 의심되기도 하였다. 그곳은 그 새가 살기엔 적합한 곳은 결코 아니라고 생각했다. 그 새의 보금자리가 따로 필요한 건 아닌지, 대기 오염으로 인해 질식하는 건 아닌지, 내가 직접 그 새를 그곳으로부터 구원해줘야 하는건 아닌지 이런 저런 생각으로 가득했다. 하지만, 내가 할 수 있는 일은 아무것도 없었다. 집에 도착하면 금새 그 새의 존재를 잊을 수 있었지만, 하천을 지나갈 때면 그 새를 다시 확인하곤 잊고 있었던 그 새가 다시 신경쓰였다.

    그 새는 언제나 집에 머물고 있었다. 하지만 난 한 번도 그 새가 노래를 하거나 우는 모습을 보진 못했다. 그 새는 그저 고요히 잠을 자거나 둥지에서 여기저기 가만히 두리번 거릴 뿐이었다. 무엇보다도 그 새를 볼 때마다 측은한 감정이 들기도 했는데, 텅빈 새까만 다리 밑에 홀로 있는 그 새는 왠지모르게 가엽고 슬퍼보였다.

    여름의 막바지 쯤, 그날도 둥지 안의 그 새를 지켜보았다. 그 새는 어느덧 많이 야위여 있었다. 그 새의 파란 빛깔의 깃털 또한 탁한 남갈색으로 바래 있었다. 난 그 새가 매우 안쓰러웠다. 그 새는 마치 최후의 통첩을 기다리는 것처럼 불안해 보였다. 어쩌면 나한테만 그렇게 보였을지도 모른다. 하지만 그럴지 언정, 그 파랑새는 누군가가 돌봐줘야 할 야윈 소녀같은 존재처럼 내게 느껴졌다. 난 그 새가 머지 않아 이 곳을 떠날 것이라는 것을 직감했다. 말로 표현할 수 없는 안타까움이 밀려왔다.

    그 때가 내가 본 파랑새의 마지막 모습이었다. 정확히 그 다음날, 그 둥지에는 파랑새는 없었다. 먹이를 찾아 잠시 자리를 비웠을 거라고 생각해 봤지만 통학하는 동안 그 새를 다시는 볼 수 없었다. 그저 버려진 둥지만 다리 밑에 고스란히 남아있었을 뿐. 이후, 한 동안 난 그 새가 매우 그리웠다. 이미 떠나고 존재하지 않은 그 파랑새가 지녔던 순수한 미와 매력을 난 뒤늦게 깨달았던 것이다.

    난 그 새가 죽었는지 살았는지 한동안 알 수 없었다가 주위 사람들로부터 그 새에 대한 이야기를 뒤늦게 들을 수 있었다. 소문에 의하면, 누군가는 그 파랑새가 다른 새와 같이 하늘 멀리 날아가는 걸 봤다고 했다. 그리고 그 때 그 새는 소리내어 노래했다고도 했다. 나에게는 상상도 할 수 없는 이야기였다. 하지만, 난 그 소문을 들었을 때 비로소 마음의 위로가 되었다. 최소한 그 새는 더러운 도시에서 오염되어 죽진 않았으니깐. 하지만 한편으로는 아쉽기도 하였으며 마음이 아려 오기도 하였다. 만약 파랑새처럼 고귀한 자연의 동물과 사람들이 한 곳에서 같이 살 수 있었더라면 난 그 아름다운 파랑새를 매일같이 바라볼 수 있었을텐데 하는 아쉬움이 컸기 때문이다. 하지만 현실의 세상은 그렇지 못했으며 작고 어린 내가 그 새를 해줄 수 있었던 일 또한 아무것도 없었다.

    "차라리 그 파랑새와 함께 자연으로 돌아간 그 새가 나였더라면..."

    그 새에 대한 그리움과 미련, 가슴앓이로 고생하던 그 때 난, 그렇게 괴로워하며 아파했을 뿐이었다.

    저작자 표시

    Material: Ballpoint, Watercolor(black), Canvas

    저작자 표시

    Hermet Park is a senior software engineer who 's worked on Tizen platform in Samsung Electronics since 2009. He specializes in Tizen UI framework and has contributed to improvement of Tizen UX and UI, Tizen graphics system and convenient tools for application development. Also, he involved in projects such as Samsung mobile, wearable and TV products. He has also worked in EFL open source community under the nick name 'Hermet' for years as well as runs EFL Korea community as an evangelist to spread it in Korea. Most of the times, he hangs out at home and plays video games or investigate IT trends and SW technology but at times, he is such a dreamer. He loves reading books, writing essays, drawings, playing the piano so on.

    Email hermetpark@gmail.com
    LinkedIn linkedin.com/in/hermetpark


    This is a my first piano song that I've practiced.
    The title is "Stones" which is the theme of the Ultima games which I'd been totally into.
    That melody touches me whenever I listen, it makes me feel if I go back in old days.
    Peaceful, Sad, Lovely and Soothing.
    Even the playing is a little awful, I believe you guys love this song if you were also a big pan of Ultima.