GMLscripts.com

Juju

Member

Registered: 2015-10-01

Posts: 45

nearest_point_on_path()

Expand///nearest_point_on_path( x, y, path, pathX, pathY, absolute )
//  
//  Finds the point on a path closest to an analysis point. Echoes the arguments and functionality of draw_path().
//  
//  !!! Will not give accurate results with curved paths.
//  
//  argument0:  x-coordinate of the analysis point.
//  argument1:  y-coordinate of the analysis point.
//  argument2:  Target path.
//  argument3:  Relative x-position of the path in the room (See draw_path).
//  argument4:  Relative y-position of the path in the room (See draw_path).
//  argument5:  If the path coordinates are relative or absolute (See draw_path).
//  
//  return   :  "true" if a point has been found, "false" otherwise.
//              {{global.nearest_point_on_path_x, global.nearest_point_on_path_y}} gives the position of the closest point on the path in absolute coordinates.

var xx, yy, path, pathX, pathY, absolute;
var closestLine, closestDist, closestX, closestY;
var closed, points, Ax, Ay, Bx, By;
var i, iLoop, dx, dy, lenSqr, t, Cx, Cy, perpDist;

xx       = argument0;
yy       = argument1;
path     = argument2;
pathX    = argument3;
pathY    = argument4;
absolute = argument5;

if ( !absolute ) {
    xx -= pathX - path_get_point_x( path, 0 );
    yy -= pathY - path_get_point_y( path, 0 );
}

closestLine = noone;
closestDist = 999999;
closestX = noone;
closestY = noone;

points = path_get_number( path );
closed = path_get_closed( path );
Bx = path_get_point_x( path, 0 );
By = path_get_point_y( path, 0 );

for( i = 1; i < points + closed; i++ ) {
    iLoop = i mod points;
    
    Ax = Bx;
    Ay = By;
    Bx = path_get_point_x( path, iLoop );
    By = path_get_point_y( path, iLoop );
    
    dx = Bx - Ax;
    dy = By - Ay;
    lenSqr = sqr( dx ) + sqr( dy );
    if ( lenSqr == 0 ) t = -1 else t = dot_product( xx - Ax, yy - Ay,   dx, dy ) / lenSqr;
    
    if ( t < 0 ) {
        Cx = Ax;
        Cy = Ay;
    } else if ( t > 1 ) {
        Cx = Bx;
        Cy = By;
    } else {
        Cx = Ax + t * dx;
        Cy = Ay + t * dy;
    }
    
    var perpDist = point_distance( xx, yy,   Cx, Cy );
    
    if ( perpDist < closestDist ) {
        closestLine = i;
        closestDist = perpDist;
        closestX = Cx;
        closestY = Cy;
    }
    
}

if ( closestLine != noone ) {
    
    if ( !absolute ) {
        closestX += pathX - path_get_point_x( path, 0 );
        closestY += pathY - path_get_point_y( path, 0 );
    }
    
    global.nearest_point_on_path_x = closestX;
    global.nearest_point_on_path_y = closestY;
    return true;
    
}

return false;

Came during a discussion on how to make a camera follow a racecar round a track Wipeout-style. Unfortunately, GM doesn't make it easy to work backwards from a point index to the position parameter (called pos in functions such as path_get_x) so GM's native curved paths cannot be supported. For the particular implementation I was working on, this isn't a problem, but it is a little annoying that a general solution is out of reach.

Do we know the algorithm GM uses to smooth its paths? R-D-P?

Edit: Added a smoothing algorithm based on Catmull-Rom. Example of implementation here.

Last edited by Juju (2015-12-02 18:37:05)

xot

Administrator

Registered: 2007-08-18

Posts: 1,240

Re: nearest_point_on_path()

Good idea for a script. I made something like this a long time ago but somehow it never made its way here.

Sometime back I determined that GM's paths are based on quadratic Bezier splines.

I don't have the exact implementation with regard to speed.

Follow the link for an obsolescent script and a demonstration.

http://gmc.yoyogames.com/index.php?show … try3748894

---

Abusing forum power since 1986.