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.

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