Inlist, which is a sort of the Linked List, is an optimized linked list for the data structure and it's behavior performance. The key point of Inlist is, it embeds a user data in its own data structure, does not have a user data separately. Let's see an example quickly.

Firstly, let me describe a normal Linked List data structure. We can suppose that data structure would be provided with an API like a useful library.

//A list node information. data field points actual user data.
struct ListNode {
    ListNode *prev;
    ListNode *next;
    void *data;
};
//A data structure for accessing list nodes. struct List { ListNode *head; ListNode *last; };

It's just a common Linked List data structure. No problems even though no explanation. See next.

//Create a new list.
List* list_create() {
    return (List*) calloc(1, sizeof(List));
};
//Append a new item(node) in a list. bool list_append_item(List* list, void *data ) { if (list == null) return false; //Create a new node. ListNode *node = (ListNode*) calloc(1, sizeof(ListNode)); if (node == null) return false; node->data = data; //In case of the first node. if (list->last == null) { list->head = list->last = node; return true; } //Append a new node in the list. ListNode *last = list->last; last->next = node; node->prev = last; list->last = node; return true; }


list_create() generates a list and the other one appends a new node in the list. I believe you already know Linked List so we won't look at the above code in detail. (Just in case, you can easily find a Linked List concept by googling.)

So far, it looks nice. We can provide a sort of free functions with regard to the above additionally but I'd like to skip them because they are actually at outside of the stake.

Then, we can suppose a user uses our functions in this scenario.

//User data structure
struct UserData {
    int idx;
    int val;
};

void main() {

    List *list = list_create(); 
 
    //Set up a list.

    //Create arbitrary 100 items. Skiping here, but create_userdata() creates a UserData data and returns it.
    for (int idx = 0; idx < 100; ++idx) {       
       UserData *usrdat = create_userdata(idx, idx * 100);
       list_append_item(list, usrdat);
    }
 
    //Verify that list is correct or not.

    //It would be better if we provide a function, list_foreach(), to iterate a list...
    ListNode *node = null;
    UserData *usrdat = null;

    list_foreach(list, node,  usrdat, UserData) {
        if (usrdat)
            printf("%d %d\n", usrdat->idx, usrdat->val );
    }

    //Skip the free sequence..
}

Seems very well. But for some people who are likely to ask me how to implement list_foreach(), I'm adding the function code here.

#define list_foreach( list, node, usrdat, DATA_TYPE ) \
    for (node = list->head, usrdat = (DATA_TYPE*) _get_usr_data(node); node; node = _prev_get_next(node), usrdat = (DATA_TYPE*) _get_usr_data(node))


The code won't be the perfect however at least, we can imagine such that code we can define.

_prev_get_next() is an internal function which returns a next node, _get_user_data() is an internal function which returns user data from a node. Both of them actually are not important, we don't need to waste time by diving them to dig. So let's skip them.

So far, we've looked a normal Linked List and its peripheral functions usage. Here point we have to notice again is the next sequence that builds up a working Linked List.

1. Create a list(list_create()).
2. Create a user data(create_userdata())
3. After creating a node, store user data in that node(list_append_item()).
4. Append a new node in the list(list_append_item()).

By this time, if we see a figure of its structure, it must be looked like this.

The key point here is, on building the structure, it needs to allocate 2 pieces of fragmented data memory per one item. Plus, every loop, it requires referring pointers, node->data, to access user data.

Then, let's take a look at the difference with Inlist. Inlist reduces memory allocation count as well as pointer access count by merging Node and UsrData like the next figure.


Someone may think, it's a piece of cake. If user implements the list manually, they could have implemented it like the above. On the other hands, if you provide the list function to users or implement it internally as a re-usable function for yourself, you are possibly somewhat impressed.

Now, we understand the concept of the Inlist. Let's start to implement it quickly. I will modify the previous list code and here I will show you the just different parts of the code. Let's take a look at UsrData first.

#define LISTNODE ListNode node;  //Define for user convenience.

//User data structure
struct UserData {
    //Firstly, adds a field using that macro.
    LISTNODE;
    int idx;
    int val;
};


Like above the figure, modified UserData to include ListNode data fields. Next, let's modify List and ListNode.

struct ListNode {
    ListNode *prev;
    ListNode *next;
    void *data;  //No more use.
};

struct List {    
    //Nothing changed.
    ListNode *head;
    ListNode *last;
};

Now, it doesn't need to allocate ListNode but build Linked List via UserData.

//Append a new  item(node) in the list.
bool list_append_item(List* list, void *data) {

    if (list == null || data == null) return false;

    //Create a new node. Not necessary anymore.
    ListNode *node = (ListNode*) calloc(1, sizeof(ListNode));
    if( node == NULL ) return false;
    node->data = data;

    //Convert to ListNode.
    //In fact, simply use typename to access list node from user data if it is C++...
    ListNode* node = (ListNode*) data;

    //In case of the first node.
    if (list->last == null) {       
        list->head = list->last = data;
        return true;
     }

    //Append a new node in the list.
    ListNode *last = list->last;
    last->next = node;
    node->prev = last;
    list->last = node;

    return true;
}

No big changes, but just use void* type data(exactly for UserData) instead of the ListNode* to construct the list.

Lastly, let's take a look at the code which describes the iterator body of the list.

#define list_foreach(list, usrdat) \
    for (usrdat = list->head, usrdat; usrdat = _prev_get_next(usrdat))
 
void main() {
 
    //Create a list and set it up here...

    UserData *usrdat = null;
    list_foreach(list, usrdat) {
        printf("%d %d\n", usrdat->idx, usrdat->val);
    }
}


You might be noticed that it is simpler than previous one because it doesn't need to access a user data from a node anymore. But, of course, it has a con that user needs to declare LISTNODE field in the first line of the UserData structure. But actually it is not big deal. Other than that, we can still provide utility functions for user convenience.

So far, we've taken a look at the Inlist. It is a compact data structure across the nodes, also it's possible to access to user data faster than normal version. But it must be used when the data is designed to work along with the list. Actually, this Inlist concept was introduced in Enlightenment opensource project years ago. If you are interested in it more than this, you can visit here to look the whole functionalities and its implementation bodies.


저작자 표시
신고

I'm gonna talk about corner cases in my smartphone life in China, a worse than other situations. One of annoying stuff is some apps don't support the copy text function. For instance, Baidu(is a kind of google in China) app toggles a context menu when I do long press on the screen. 



In the context menu, there is not a text copy item. Sure, I can use other web browsers to avoid this suck (yay, good bye!), But just curious why they don't support the copy text? Actually, from Baidu web-surfing, I could find a bunch of users asked about this similar situations, they seemed be annoying about this strange corner.  


This is not only the Baidu web app problem but other apps also do. For example, Baidu Map, Didichuxing(a kind of Uber) are one of the essential tools for my daily life in China. Practically, a lot of citizens and tourists also depend on these apps. Let's jump into Baidu map.


Baidu map


This is worse. Of course Baidu map is not irreplaceable but still it is a representative map app in China. Somewhat it is better than other foreign companies maps (i.e, google map) because it is specialized in China region and data. When user searches a region, it suggests additional information such as most favorite restaurants, tourists attractions etc. That is not surprising, it is a common feature all over the map apps.


Point here is, when I searched a good place and think to dig it more, I need to research it using a web browser. That means, I need to copy one of information-address, phone number, store name, region name, etc- and then paste in the search box of the browser. But, It doesn't allow me to copy this information. Oops, you know, Chinese is very difficult to type if you don't know how to read the Chinese characters. First time, it is outrageous. It is very annoying when I could not read them. In the end, I give up searching and go back to the google map because English is better than Chinese to me. Of course, we can use Chinese dictionary then find how to read the Chinese characters and then research it. But I'm sure it is also horribly inconvenient.


Now, question, why they don't allow us to search the characters? I imagine two scenarios.


 A. intentional purpose (for contents protection)

 B. technical issue.

 C. design problem (Is it considerable? Or just have no idea why they need to support it)


At least, I'm sure there is not an intentional purpose because that information is not serious data at all. Also, when you use a browser using desktop PC, it still allows user to copy text information. So, it just leads to A or B problems.


In point of S/W development view, basically software platforms support a text widget or similar UI components which support text copy/paste function in default. If some text part or text view of the application doesn't enable the copy text function, I guess it probably uses an extra component, not the default one, for the text area. I don't like to talk to you it is wrong because we don't understand its background. However, I'm still curious why they don't support it, Is it difficult? Or they just think it is just a trivial function?


I checked Google map and Naver map(a famous Korean map app) just in case. And then surprisingly I just realized Naver map doesn't support multi-language feature. Also, it doesn't support text copy function for whole text area but does only for some of them. Still, it is inconvenient for me but I think it's better than Baidu map.


Naver map


Then how about Google? Impressive! It supports not only multi-language but also text copy function.


Support Multi-Language


Copy text information


If you see the above Google map figure, its copy text UI interface is not a default one. It seems one of the additional or extra ones(just my guess). So I am surprised because it means they intentionally added that feature for this user scenario that I encountered.


Default copy and paste UI interface


I'm not one google sucker but a little surprised by google. Because in China, people cannot use Google service but google apps still perfectly works for Chinese. (Of course it needs VPN)  


Today, we checked one use-case even though a trivial one, but I'd like to say this, every software companies can develop similar software products but their quality and service won't be same. As if it is a kind of this, masterpiece or not. That comes from a difference of software design. When we design a software, do we consider user scenarios enough? Do we design a software for user convenient or just try to copy the prime one? It is clear that, with enough considering user scenarios to make them convenient, users definitely feel your software is better and feel a greater identity of your company.

저작자 표시
신고

Recently, I tried implementing "Text on path" prototype. Even it's not a new concept nor a striking function, still it's an interesting feature to understand UI & graphics. Actually, many drawing tools (ie, MS Photoshop, Inkscape, gimp, etc) have provided it since a long time ago.

For those people who don't know about "Text on path", it is a feature that displays a text on an arbitrary virtual path like the next figure.


Even though this kind of text effects does nothing in point of functionality view, this may work for users to get interested in your application UI or to understand your application context easier. Here is a perfect use-case that this feature is effectively used in a real application (Samsung Android Milk app).


Then how could you implement it? If you are an app developer, probably you could use the convenient easy API set which is provided from your UIFW system. But my question is not for the situation. Sometimes you may need to implement by your hand beyond the framework. This page is for the it.

Most of all, you need to understand two points for this. First is a path information and second is a drawing method. Most UIFWs have their own Path data interface. A traditional path interface might look like this. (just in C style)

Path *path = create_path();
move_to(path, pos_x, pos_y);
line_to(path, to_x, to_y);
circle_to(path, center_x, center_y, radius);
curve_to(path, start_pt, ctrl_pt1, ctrl_pt2, end_pt);
...

This path data keeps the path information internally. You can move the start position using move_to() and then link following path points using line_to(), circle_to() and curve_to(). Probably there would be more functions for path but skip others here now. I don't think this path will have a nice visual but point here is, you can give the path information using sort of those interfaces.

Once the path data is set, all path coordinates per *pixels* could be generated by some interpolation algorithm during a ready stage of your program. Normally, Linear Interpolation provides good quality for this.


Or you can apply other interpolation formulas such as polynomial and spline.

I believe you can generate line, circle and some rectangular shapes path coordinates easily. It doesn't require complex formulas for them. But how about curves? How can you generates pixels for curves? One generic method for representing a curve is a using Bezier Curve. This algorithm has been universally used in graphics and even it works for this text on path. Basically, this requires 4 points - start point, end point and two control points. Start point is the start position and end point is end position for your path. Two control points actually decide the path curve style.


The curve path can be completed with this formula.


Please refer Bezier Curve wikipedia page for more details.

//progress: A normalized value (0 ~ 1) in bezier curve. 0 indicates the position of start point and 1 indicates the position of end point.
get_bezier_curve_pos(progress)
{
    v[0];    //1st control point x coordinate
    v[1];    //1st control point y coordinate
    v[2];    //2nd control point x coordinate
    v[3];    //2nd control point y coordinate
    ...
    tx = (pow((1 - progress), 3) * 0) + (3 * progress * pow((1 - progress), 2) * v[0]) + (3 * pow(progress, 2) * (1 - progress) * v[2]) + (pow(progress, 3) * 1);
    ty = (pow((1 - progress), 3) * 0) + (3 * progress * pow((1 - progress), 2) * v[1]) + (3 * pow(progress, 2) * (1 - progress) * v[3]) + (pow(progress, 3) * 1);
    ...
    return tx, ty;
}

This logic performs to get x, y position on a bezier curve. tx, ty are a pair of xy coodinates. You can get coordinates by giving progress value from 0 to 1. 0 is the start point of the curve and 1 is the end point of the curve. 0.5 is the center point of the curve. If you connect one more than bezier curves by giving several points set(start, end and 2 control points), you can make a long complex arbitrary curving path.

Now, you can generate pixel coordinates of a curving path. Next step is an actual drawing.

(For your information, you can refer the next website to simulate a bezier curve with your control points.)

Firstly, you need a text to draw. But you don't need to implement text rendering feature in your program. Instead, use the existing functions as possible. For instance, you can use one text rendering library such as Freetype. Or, probably your platform may support its own text rendering feature. Since those text rendering requires a huge amount of pages for understanding, I'd rather skip it here. You can google it by yourself.

If you use a text drawing library, defintely those libraries provide an API that returns the generated bitmap of a text. In this case, you can get a bitmap of a glyph or a bitmap of a text(sentence). Rather than glyph, text may be much better because that some languages such as Hindi, its glyphs connected each others. In that case, you can make the completed curved text only with a text.



Now, let's suppose you have a text bitmap. Next work is to bend the text bitmap. If your graphics system has a method to draw textures based on the polygons, that's the most easiest way for this. Or you can use a 3D rendering system such as OpenGL/Direct3D directly. I'm sorry, I don't take cover 3D graphics topics such as polygon and texture mapping here. If you are unfamiliar with that, please go to revise your 3d graphics lesson first.

Suppose you use the polygon based drawing. You need to construct a mesh for curved text area. You can achieve that with some linear algebra idea. Let's compute polygon vectices. Since you have a Bezier curve, you can get vectors along with a curving path by progress.


p1 = get_bezier_curve_pos(0.0);    //Point 1 at 0.0
p2 = get_bezier_curve_pos(0.01);    //Point 2 at 0.01
v = p2 - p1;    //A vector
normalize(v);

You got the first segment vector. Compute it's upper vertex. Transform the vector by -90 degree then increase the vector length by half of text height.

rad = degree_to_radian(90);
matrix2 = { cos(rad), -sin(rad), sin(rad), cos(rad) };    //Euler angle
v *= matrix2;
normalize(v);
v *= (text_height * 0.5);

v1 = v + p1;    //Don't forget the origin of the vector.


Compute the lower vertex. Simply, you can invert the upper vector here.

v2 = -v + p1;


Obviously, you got the 2 vertices. For one polygon, you need next 2 vertices more. Repeat the above sequence with the line segment between 0.01 ~ 0.02.

p1 = get_bezier_curve_pos(0.01);    //Point 1 at 0.01
p2 = get_bezier_curve_pos(0.02);    //Point 2 at 0.02
v = p2 - p1;    //A vector
normalize(v);

v *= matrix2;
normalize(v);
v *= (text_height * 0.5);

v3 = v + p1;
v4 = -v + p1;




Repeat this to the end of the curve. ( ~ 1.0)


Pretty easy. Now you can see how does "Text on path" mesh accomplished! Segments count in the screenshots might not be matched exactly. As far as decrease the segment distance, you will have a fine-grained result. Last step is texture mapping. Since you already have a text bitmap, you can use the bitmap as a texture.


Next video shows my prototype.

저작자 표시
신고
Recently, Tizen released Tizen Studio 1.0 for the Tizen developers. The orignal Tizen SDK components converged all together while their functionalities are improved. Also, UX has been nicely improved. IDE, GUI Builder, Debugger, Profiler and etc, all components have more strong consistent user experience now. Absolutely, it's good news for Tizen developers. :)

In the mean time, if you are a big fan of Tizen Studio EDC Editor, I'd like to give you a tip that a way of launching EDC Editor on the Linux console mode. Of course, you could use EDC Editor on the Tizen Studio through the standard route but sometimes you'd better launch it manually if your project is not supposed to use Tizen IDE. Any case is ok, but this tip is for that case.

I believe you already have the Tizen Studio on Linux (Ubuntu) PC. Necessary components and EDC Editor executable must be installed properly. Let me suppose your Tizen Studio is installed in the HOME directory (/home/user/tizen-studio). You can see the EDC Editor in tizen-studio/tools/edc-editor and necessary libraries(EFL) in tizen-studio/tools/efl-tools. The only thing you need to do is just set PATH and LD_LIBRARY_PATH to edc-editor and efl-tools. Let's try to launch EDC Editor with this commands.

$PATH=/home/user/tizen-studio/tools/edc-editor/bin:/home/user/tizen-studio/tools/efl-tools/bin:$PATH LD_LIBRARY_PATH=/home/user/tizen-studio/tools/edc-editor/lib:/home/user/tizen-studio/tools/efl-tools/lib/ ~/tizen-studio/tools/edc-editor/bin/enventor

Even though you have installed EFL libraries manually on your PC, you must set the PATH and LD_LIBRARY_PATH to EFL in the tizen studio because Tizen EFL is little different with upstream version. It has customized functionalities so the behavior may be different. Also, It's not surprise that executable name is enventor. Actually EDC Editor is customized to Tizen wise from EFL Enventor project. Anyhow, you must see the EDC Editor window.



To launch the EDC Editor with specific EDC file, launch it with this file name.

$PATH=/home/user/tizen-studio/tools/edc-editor/bin:/home/user/tizen-studio/tools/efl-tools/bin:$PATH LD_LIBRARY_PATH=/home/user/tizen-studio/tools/edc-editor/lib:/home/user/tizen-studio/tools/efl-tools/lib/ ~/tizen-studio/tools/edc-editor/bin/enventor sample.edc

Lastly, If you need to set the resource paths then use the below options. Those options could be applied multiple times.

$PATH=/home/user/tizen-studio/tools/edc-editor/bin:/home/user/tizen-studio/tools/efl-tools/bin:$PATH LD_LIBRARY_PATH=/home/user/tizen-studio/tools/edc-editor/lib:/home/user/tizen-studio/tools/efl-tools/lib/ ~/tizen-studio/tools/edc-editor/bin/enventor sample.edc  -i ./my_image_path -i ./my_image_path2 -s ./my_sound_path -s ./my_sound_path2 -f ./my_font_path -f ./my_font_path2 


If you think the command is too long then please write a your script. I believe It would be a piece of cake by you. :)


저작자 표시
신고
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.

Annotation
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;
 
    OPEN=present;   

    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;   
        }
          
        //Succeed!
        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;
 
        count++;             
    }          
    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.
    //Left
    if( is_available_grid(x - 1, y) ) {
        extend_child_node(node, x-1, y, dest_x, dest_y, LEFT_IDX);
        extended=1;
    }
    
    //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;

            make_sort(old);
        }
 
    //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;
                    
        insert_node(child);
 
        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;                                  
            push_into_stack(direct);
        }
    }
 
    //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;    
                push_into_stack(direct);
            }
        }
    }
}

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;
        return;
    }
 
    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.

astar.cpp
저작자 표시
신고



EFL provides multiple widget categories and a vast collection of low level and high level APIs to create UI layouts tailored to specific application requirements.
In addition, the programming model also uses a script language called EDC (Edje Data Collection), so that the application logic can be separated from the UI design. Using EDC, application developers can also make complex and dynamic UI layouts. The Tizen SDK has rich collection of UI creation tools and documentation for application developers to make use of the above facilities.
During the course of this webinar, Hermet will introduce the concepts involved in creating complex UI layouts using EFL. The topics covered include EDC, API interactions and different widget classes and how all of these can be combined to build a complex UI layout for an application.
In addition, the usage of dynamic EDC editor tool, Enventor, is discussed. If you are an application developer building native applications for Tizen devices or in general want to understand the native UI programming model of Tizen, this webinar is for you.
저작자 표시
신고