# GMLscripts.com

Discuss and collaborate on GML scripts

You are not logged in.

## #1 2015-12-02 16:55:05

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)

Offline

## #2 2015-12-05 01:33:30

xot
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.