Exploring the Geom.Intersects.GetLineToPolygon method
In my exploration of 2D raycasting using Phaser 3, I created simple 2D raycasters using Phaser 3's built in Geom.Intersects.GetLineToPolygon method. As I continued to play around with this method, I encountered situations where the raycast would not detect intersections when clearly it was intersecting. After a fair bit of bagging my head against the wall, I discovered that the Geom.Intersects.GetLineToPolygon method is coded in such a way that if the "ray" is vertical, it returns null.
This tutorial is about my customised version of the GetLineToPolygon to overcome this feature in the Phaser's built-in method.
Where is the problem?
As explained in my previous post of this series, GetLineToPolygon method works by looping through the vertices of all the polygons, creating Geom.Line objects for successive vertices, and calling GetLineToLine method (for a more detailed explanation, please go here, if you are interested).
<static> GetLineToLine(line1, line2 [, out])
This method is described by the official documentation as follows:
Checks for intersection between the two line segments and returns the intersection point as a Vector3, or null if the lines are parallel, or do not intersect. The z property of the Vector3 contains the intersection distance, which can be used to find the closest intersecting point from a group of line segments.
And the underlying code of this method is as follows. You will note that the red highlighted line is checking if line1 is vertical, and in the blue highlighted line, if line1 is indeed vertical, (ie line1.x1 = line1.x2, hence dx1 = 0), then the method immediately returns false.
var GetLineToLine = function (line1, line2, out) {
var x1 = line1.x1;
var y1 = line1.y1;
var x2 = line1.x2;
var y2 = line1.y2;
var x3 = line2.x1;
var y3 = line2.y1;
var x4 = line2.x2;
var y4 = line2.y2;
var dx1 = x2 - x1;
var dy1 = y2 - y1;
var dx2 = x4 - x3;
var dy2 = y4 - y3;
var denom = dy2 * dx1 - dx2 * dy1;
// Make sure there is not a division by zero - this also indicates that the lines are parallel.
// If numA and numB were both equal to zero the lines would be on top of each other (coincidental).
// This check is not done because it is not necessary for this implementation (the parallel check accounts for this).
if (dx1 === 0 || denom === 0) {
return false;
}
var T2 = (dx1 * (y3 - y1) + dy1 * (x1 - x3)) / (dx2 * dy1 - dy2 * dx1);
var T1 = (x3 + dx2 * T2 - x1) / dx1;
// Intersects?
if (T1 < 0 || T2 < 0 || T2 > 1) {
return null;
}
if (out === undefined) {
out = new Vector3();
}
return out.set(
x1 + dx1 * T1,
y1 + dy1 * T1,
T1
);
};This is a little bit inconvenient for our purposes and requires us to use an alternative line to line intersection algorithm; thankfully Phaser 3 provides another line to line intersection method that does cope with vertical lines.
<static> LineToLine(line1, line2 [, out])
This is another method of the same Phaser.Geom.Intersects class, and is described as follows:
Checks if two Lines intersect. If the Lines are identical, they will be treated as parallel and thus non-intersecting.
In terms of functionality, this method returns true/false depending on whether there is intersection, as well as the point of intersection. This method also uses a different algorithm (described in the comments as being based off an explanation and expanded math presented by Paul Bourke, here). Importantly, this algorithm does return true when there is intersection even if line1 is vertical.
Functional differences vs GetLineToLine
In contrast to the GetLineToLine method:
LineToLine method does not return the distance to the point of intersection, although it is calculated within the method
LineToLine method only returns true if there is truly an intersection between the "segments", whereas the GetLineToLine method returns true if the "line" intersects (ie even if beyond the end point of the segment), by virtue of the red highlighted check.
var LineToLine = function (line1, line2, out)
{
if (out === undefined) { out = new Point(); }
var x1 = line1.x1;
var y1 = line1.y1;
var x2 = line1.x2;
var y2 = line1.y2;
var x3 = line2.x1;
var y3 = line2.y1;
var x4 = line2.x2;
var y4 = line2.y2;
var numA = (x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3);
var numB = (x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3);
var deNom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
// Make sure there is not a division by zero - this also indicates that the lines are parallel.
// If numA and numB were both equal to zero the lines would be on top of each other (coincidental).
// This check is not done because it is not necessary for this implementation (the parallel check accounts for this).
if (deNom === 0) {
return false;
}
// Calculate the intermediate fractional point that the lines potentially intersect.
var uA = numA / deNom;
var uB = numB / deNom;
// The fractional point will be between 0 and 1 inclusive if the lines intersect.
// If the fractional calculation is larger than 1 or smaller than 0 the lines would need to be longer to intersect.
if (uA >= 0 && uA <= 1 && uB >= 0 && uB <= 1) {
out.x = x1 + (uA * (x2 - x1));
out.y = y1 + (uA * (y2 - y1));
return true;
}
return false;
};
Customised GetLineToPolygon method
Having figured out the above, it is very easy to create our own version of the GetLineToPolygon method by utilising the LineToLine method as opposed to the GetLineToLine method. And if I am going to customise the code, I might as well make a few other changes. In the end I made the following adaptations to come up with a revised ray-caster class.
use of LineToLine method as opposed to GetLineToLine
ability to set a "limit" to the length of the ray cast
a new object called "RaycastHit2D" (yes, I did get the name from a certain Game Engine) to return the following information relating to the intersection:
RaycastHit2D.point: intersection point as a Math.Vector2;
RaycastHit2D.fraction: the "fraction" along the cast ray, indicating the distance from the origin
RaycastHit2D.tangent: tangent of the line segment intersected as a Math.Vector2
RaycastHit2D.slope: angle of the line segment intersected, in radians
RaycastHit2D.normal: normal to the line segment intersected as a Math.Vector2
class RayCaster
All the code that does the actual ray casting, I have encapsulated in a class called RayCaster. In order to use it, you first instantiate it, like so:
this.rays = new RayCaster(this, this.player.x, this.player.y);Then you must tell it where to look for the objects to check for collisions, with the setColliderLayer method
this.rays.setColliderLayer(this.obstacles);And then you're ready to go. I've implemented two basic methods for casting rays: (i) castCone, which casts 30 rays across an angle range (which can be set with the setCone method - just feed an angle in radians), and (ii) castRay, which casts a single ray.
Both methods return the RaycastHit2D object, which will be null if the ray did not intersect with anything.
castCone() method
I have recreated the simple raycaster from the previous post (I have deleted all of the wall rendering code since that's not the purpose of this post), below using the new customised ray casting class and the castCone() method.
The code may look a bit long, but almost half of it is pretty much copy & pasting of the GetLinePolygon method code from Phaser 3. The critical amendment is the following, within the LineToLine method. Specifically:
I have deleted the check for uA <=1 (uA being the "distance" from the start of line1 to the intersection as a fraction of the total length of line1) which allows intersections beyond the end point of the ray to be returned
more intersection information is returned than the original code
if (uA >= 0 && uB >= 0 && uB <= 1) {
out.point = new Phaser.Math.Vector2(x1 + (uA * (x2 - x1)), y1 + (uA * (y2 - y1)));
out.fraction = uA;
out.tangent = new Phaser.Math.Vector2(line2.x2 -line2.x1, line2.y2 - line2.y1).normalize();
out.slope = Phaser.Geom.Line.Angle(line2);
out.normal = Phaser.Geom.Line.GetNormal(line2);
return out;
}
return false;
};
castRay(origin, angle, distance)
This method is used to cast a single ray from the origin, at angle, and you can also specify the distance beyond which the ray caster will not "see" (if you do not specify it, the length of the ray will not be limited).
Despite its simplicity, you can achieve quite a lot things with 2D ray casting. For example, you can cast multiple rays vertically and horizontally from your player object to give the player certain awareness of its surrounding (eg is the player on flat ground? is it stuck against a wall?).
I have implemented below a simple example where you can make Mr Dude climb up a slope. Clearly, this is for illustrative purposes only since you should be using Matter physics engine to do this. Nevertheless, it is fun. The code is (very) abridged & partial implementation of code from a C++ Youtube tutorial, accessible here.
Comments