Iis entity inside block built with vector points

[RobsoN]

Hello, is it possible to determine whether an individual is inside block built with vector(origin) points?

Ive got nodes for AI pathfinding. I just need to know where the player/bot is. Blocks are made from vector points (childs).

Any help pls?

[kung foo man]

What is your "block"? Pictures help as basis for discussion.

You just need to find the nearest LINE to a POINT: http://en.wikipedia.org/wiki/Distanc...oint_to_a_line

The lines are defined between two waypoints. The Nearest-Waypoint-Is-Best-Waypoint-Method is wrong, a picture for illustration:



The nearest waypoint would go through a wall.

If you dont want to use node-based path-finding, use navigation meshes: http://www.ai-blog.net/archives/000152.html

IzNoGod made some great work for navmeshes, but I dont know if he wants to share. Though thats even more complex than normal waypoints.

[IzNoGoD]

		ispointinsidenode(point,node)
{
    //DONT CHECK HEIGHT OF POINT. IMPORTANT!
    //now, for each child of [node] find another connected child of [node]
    first=undefined;
    previous=undefined;
    posneg=0;
    inside=true;
    child=level.child[node.child[0]];
    for(iterations=0;iterations<node.child.size&&(!isdefined(first)||first.num!=child.num);iterations++)
    {
        for(i=0;i<child.conn.size;i++)
        {
            if(isinarray(child.conn[i],node.child))
            {
                //this connection is one of the node ones
                if(!isdefined(first))
                    first=child;
                if(!isdefined(previous)||previous.num!=child.conn[i])
                {
                    //not one that has already been checked
                    previous=child;
                    child=level.child[child.conn[i]];
                    ans=vectorprod2d(point-previous.origin,child.origin-previous.origin);
                    if(posneg==0)
                    {
                        if(ans<0)
                            posneg=-1;
                        else if(ans>0)
                            posneg=1;
                    }
                    else if(ans*posneg<0)
                        return false;
                }
            }
        }
    }
    return true;
}

vectorprod2d(vec1,vec2)
{
    num=vec1[0]*vec2[1]-vec1[1]*vec2[0];
    return num;
} 
	

Abuses some cross product stuff (http://en.wikipedia.org/wiki/Cross_product), right hand rule

[RobsoN]

Kong foo man I'm not sure if you understand me. This is best example of my question


Iznogod, thanks you for this code. I have tried to "translate" it for my lang, but I failed. The code is just too difficult for me to understand - I'm not good @ physics, math (ye, then a lot of ppl will ask me - why im programming when im bad @ this subjects. I won't comment them..). It would be a pity if I would replace variables at the mine and still don't understand how does it works, but anyways again thanks for your code!

P.S: I'm using triggers for localize players but i don't like this idea. Every new node i need to create trigger in radiant. So messy/a lot of time.

[kung foo man]

The trick is to find an easy definition of "inside". The point is inside, when the point is always on the same side of each line (good definition for convex hulls, not concave hulls).

And calculating the side of a point is an often asked question: http://wiki.processing.org/w/Find_wh..._a_point_is_on

Also try to google: point inside concave polygon


If you actually want to understand, what you are doing, start with some basics, e.g. derive 20 times a day the formula of the dot-product from a common triangle

Google for: derive dot product

[RobsoN]

kung foo man, Thanks you so much for this simple and understandable post! It should help me a lot.

I will answer if I'll solve the problem or if I'll have any questions.

[RobsoN]

So, i found the answer! It's c++ code but you easly can convert it to cod2 (like me).

		bool pointInPolygon() 
{ 

    int i, j = 0; 
    bool oddNODES = false; 
    for (i = 0; i < polySides; i++) 
    { 
        j++; 
        if (j == polySides) 
            j = 0;
            
        if (polyY[i] < y && polyY[j] >= y || polyY[j] < y && polyY[i] >= y) 
        { 
            if (polyX[i] + (y - polyY[i]) / (polyY[j] - polyY[i]) * (polyX[j] - polyX[i]) < x) 
            { 
                oddNODES = !oddNODES; 
            } 
        } 
    } 

return oddNODES; 
} 
	

It works pretty nice!

Again thanks kong foo man for the help!