range_finder - update?

paul23 · 2008-01-07 19:00:46

Well I was looking a bit at the pathfinding functions available for gm.. And I started to wonder something: what is the use of mp_linear_path?

Well I think I've found it:

mp_linear_path(path,xg,yg,stepsize,checkall) This function computes a straight-line path for the instance from its current position to the position (xg,yg) using the indicated step size. It uses steps as in the function mp_linear_step(). The indicated path must already exist and will be overwritten by the new path. (See a later chapter on how to create and destroy paths.) The function will return whether a path was found. The function will stop and report failure if no straight path exists between start and goal. If it fails a path is still created that runs till the position where the instance was blocked.

Notice the last line. - It creates a straight path till a certain blocked position!

Isn't this (almost) exactly the same as what range_finder does?

** Returns:
** exact distance to the nearest instance of given (object)
** in direction (dir) from the given point (x,y),
** or (-1) if no instance is found.

If you would use mp_linear_path_object() (and temporary place the instance at the "given position" and convert the range+dir vector to the end point x/y) you could simply use path_get_length() to return the needed distance.

I haven't had the time to test this myself, so I wonder if it's faster (though I think it is, seeing this is the only use I've found for mp_linear_path -creating a straight path between two point can be done much faster -note that the stepsize should be 1 for the most acurate results).

xot · 2008-01-07 21:02:34

Hmmmm, very interesting find. I must admit a lot of ignorance when it comes to the motion planning functions. It looks like it might make for a good alternative to range finder -- if it is faster ... and I don't see how it couldn't be.

To get it to work as a drop-in replacement, you'd need to dynamically create a 1x1 pixel object and a working path the first time the script it called. That's not a problem, I do something very similar with my collision_triangle() script. Definitely worth exploring.

EDIT: Whoops, that's the old version of the function with the separate init function. This illustrates the concept: draw_rectangle_dashed()

Last edited by xot (2008-01-07 21:44:17)

paul23 · 2008-01-09 08:13:15

Well an extra object isn't needed at all.
Made a small script already (still need to do some speed testing...)

Expand/*
**  Usage:
**      range_finder(x,y,dir,range,object)
**
**  Given:
**      x,y         position in room
**      dir         direction to look in degrees
**      range       the greatest distance to look in pixels
**      object      which objects to look for, or keyword all
**
**  Returns:
**      exact distance to the nearest instance of given (object)
**      in direction (dir) from the given point (x,y),
**      or (-1) if no instance is found.
**
**
**  GMLscripts.com
*/
{
    //sprite_index = obj_tracer;
    var _x,_y,dir,range,object,distance,path,_mask_index,newspr;
    path = path_add();
    _mask_index = mask_index;
    newspr = sprite_create_from_screen(0,0,1,1,false,false,false,true,0,0);
    _x = x;_y = y;
    x = argument0; //start points
    y = argument1;
    dir = argument2;
    range = argument3;
    object = argument4;
    mask_index = newspr;

    mp_linear_path_object(path,x+lengthdir_x(range,dir),y+lengthdir_y(range,dir),1,object);
    distance = path_get_length(path);
    x=_x;y=_y;
    mask_index = _mask_index;
    sprite_delete(newspr);
    path_delete(path);

    return distance;
}

It "works"..
HOwever it doesn't always bear the same results as the "current" range_find() script. First of all it's always rounded (down) to the nearest integer.. Secondly there's something strange about the paths.. - When working with the "full path" (in which case there is no collision at all) the distance becomes like "0.00000000x" less than the actual distance (and thus testing "if (distance == range)" will always be false. (this might happen at the other places too, however I doubt it would really cause problems).
Also there's a pretty "big" difference I can't really get an explanation for, one of the most extreme cases is show here:

The yellow "bullet" is the point to look from, the white line is the line in the looking direction. The green pixel (on the corner of the big block) is the range_find - point found with the mp_linear_step method. And the blue point (in this case below the message, at maxdistance) is the point foud with the old range_find() script. (and the message says <old-range_find-value>|dir2:<new-range_find-value>.
I can't really find any explanation as to why the linear_step (with a 1 size mask) does find a collision, while collision_line doesn't.

Maybe this is because collision line returns a collision if 1 pixel OVERLAPS a pixel of the line completely. And mp_linear_path returns a collision at the moment 2 pixels are next to each other (though this isn't completely true: at parallel movement it doesn't find a collision either), I'm thinking this after seeing
< that picture..
You see the blue dot is slightly "inside" the block (position_meeting returns true), while the green dot is outside the block (position meeting returns false).

A slight improvement might be made by making the newly created sprite (and path?) into 2 global variables... However I don't think it would be such an improvement in speed. (will return later with some speed testing results). Also a note should be taken: it's impossible to take "itself" into account. (well it's not that difficult to add the possibility -simply create a new instance to "calculate" with-, however I think it's pretty much useless). Also this method takes "precise" collision into account whenever precise is set on.

EDIT: forget it.. I did speed test and well, it's really, really slow - especially on larger areas (I'm talking about 100-1000 times as slow!)! if you're intersted in the result file is here

Last edited by paul23 (2008-01-09 10:46:04)

xot · 2008-01-09 13:36:03

Wow, that much slower. That's sort of surprising, although in retrospect it shouldn't be. I expected collision_line() to be a good deal faster than a sprite collision, but I also thought the compiled mp_* functions might be an improvement over the overhead of using a GML-based search as in range_finder(). However, the magnitude of difference does make sense because the mp_* functions have to use a pixel-by-pixel linear search with a slow sprite collision call every pixel, versus the binary search using collision_line() that's in range_finder(). For a search distance of 1000 pixels, that's a 1000:10 difference in number of checks.

paul23 · 2008-01-09 18:23:36

True, however I didn't expect it to be so large already.

I expected to see something like: under 64 pixels distances mp_linear_step is faster, above collision_lines are faster. An even more thorough "research" shows that the current "cross point" of the two functions is around 6-8 pixels.

icuurd12b42 · 2008-12-12 00:00:47

It's the same problem with move_contact, as we found in the laser thread on the GMC... nothing's beaten the range finder method so far.

Me I always motifify the range_finder to return the instance and set up a few instance/me,ber variables which I always need everytime I call the script

__dist //the distance
__x //the point of impact
__y //the point of impact

GMLscripts.com

#1 2008-01-07 19:00:46

range_finder - update?

#2 2008-01-07 21:02:34

Re: range_finder - update?

#3 2008-01-09 08:13:15

Re: range_finder - update?

#4 2008-01-09 13:36:03

Re: range_finder - update?

#5 2008-01-09 18:23:36

Re: range_finder - update?

#6 2008-12-12 00:00:47

Re: range_finder - update?

Board footer