2D Raycasting in Phaser 3 Tilemaps
In the previous post I looked at the use of Phaser.Geom.Intersect methods to execute raycasting. But what if you wanted to carry out 2D ray casting in tilemaps? If you google "Phaser tilemap raycast", you most likely get the following as the top hit.
As it turns out, this is an example in Phaser 2, which uses a method called getRayCastTiles, belong to the tilemap layer class. Having searched the Phaser 3 documentation, I did not immediatley find the same named method. So I went digging in the phaser 2 documentation (https://phaser.io/docs/2.6.2/Phaser.TilemapLayer.html#getRayCastTiles) to find out if it can be replicated in Phaser 3 (the conclusion is that Phaser 3 actually does have more flexible methods to allow you to achieve the same thing).
Phaser 2: getRayCastTiles(line, stepRate, collides, interestingFace)
The official documentatio simply says "Gets all tiles that intersect with the given line". The key sections of the underlying code is as follows:
Phaser.TilemapLayer.prototype.getRayCastTiles = function (line, stepRate, collides, interestingFace) {
if (!stepRate) { stepRate = this.rayStepRate; }
if (collides === undefined) { collides = false; }
if (interestingFace === undefined) { interestingFace = false; }
// First get all tiles that touch the bounds of the line
var tiles = this.getTiles(line.x, line.y, line.width, line.height, collides, interestingFace);
if (tiles.length === 0) {
return [];
}
// Now we only want the tiles that intersect with the points on this line
var coords = line.coordinatesOnLine(stepRate);
var results = [];
for (var i = 0; i < tiles.length; i++) {
for (var t = 0; t < coords.length; t++) {
var tile = tiles[i];
var coord = coords[t];
if (tile.containsPoint(coord[0], coord[1])) {
results.push(tile);
break;
}
}
}
return results;
};The red line calls getTiles method with the top left hand corner of the line, width (the difference between the x coordinates of the end-points) and the height (the difference between the y-coordinates of the end-points); ie the bounding rectangle of the line. Essentially, this method gets all the tiles within the bounding rectangle.
Then the tile is checked against "every point" of the line for overlap. If there is overlap, that tile is stored in array to be returned.
So in essence it is a 2 stage process.
Although Phaser 3 (as far as I can tell) does not have a method exactly the same, there is a "new & improved" version of the above method, which not only accepts a line, but a variety of "shapes" against which to check intersection of tiles.
Phaser 3; getTilesWithinShape(shape [, filteringOptions] [, camera] [, layer])
The documentation described the method as follows:
Gets the tiles that overlap with the given shape in the given layer. The shape must be a Circle, Line, Rectangle or Triangle. The shape should be in world coordinates. If no layer is specified, the maps current layer is used.
If you look at the underlying code for this method, you will see that it takes a slightly different approach, although it is still in 2 stages.
First, the bounding box in terms of tile units (not pixels) is created. The method worldToTileXY(worldX, worldY [, snapToFloor] [, vec2] [, camera] [, layer]) - which converts world XY coordinates to tile coordinates - is used to create the bounding rectangle.
Then getTilesWithin( [tileX] [, tileY] [, width] [, height] [, filteringOptions] [, layer]) method is used to get all the tiles wihtin this bounding box.
// Top left corner of the shapes's bounding box, rounded down to include partial tiles
layer.tilemapLayer.worldToTileXY(shape.left, shape.top, true, pointStart, camera);
var xStart = pointStart.x;
var yStart = pointStart.y;
// Bottom right corner of the shapes's bounding box, rounded up to include partial tiles
layer.tilemapLayer.worldToTileXY(shape.right, shape.bottom, true, pointEnd, camera);
var xEnd = Math.ceil(pointEnd.x);
var yEnd = Math.ceil(pointEnd.y);
// Tiles within bounding rectangle of shape. Bounds are forced to be at least 1 x 1 tile in size
// to grab tiles for shapes that don't have a height or width (e.g. a horizontal line).
var width = Math.max(xEnd - xStart, 1);
var height = Math.max(yEnd - yStart, 1);
var tiles = GetTilesWithin(xStart, yStart, width, height, filteringOptions, layer);Then it loops through all of the tiles, checking to see if the tile "intersects" with the actual shape (say a line). Interestingly it does this by using geometry. Specifically, it "converts" each tile into a geom.rectangle and uses the Geom.Intersects method to see if the tile is colliding with the tile, as shown by the lines in blue below (intersectTest is defined earlier on in the code to the appropriate Geom.Intersects method - in the case of a line, it is the Phaser.Geom.Intersects.LineToRectangle (and LineToRectangle method, actually calls LineToLine method checking the line against each edge of the rectangle)
var tileWidth = layer.tileWidth;
var tileHeight = layer.tileHeight;
if (layer.tilemapLayer) {
tileWidth *= layer.tilemapLayer.scaleX;
tileHeight *= layer.tilemapLayer.scaleY;
}
var results = [];
var tileRect = new Geom.Rectangle(0, 0, tileWidth, tileHeight);
for (var i = 0; i < tiles.length; i++) {
var tile = tiles[i];
layer.tilemapLayer.tileToWorldXY(tile.x, tile.y, point, camera);
tileRect.x = point.x;
tileRect.y = point.y;
if (intersectTest(shape, tileRect)) {
results.push(tile);
}
}
return results;Phaser 3 translation
The long and short of it is that the Phaser 2 getRayCastTiles method can be replaced by the following, in Phaser 3.
getRayCastTiles(line) {
var tiles = this.layer.getTilesWithinShape(this.line, { isNotEmpty: true });
if (tiles.length === 0) {
return [];
}
return tiles
}Which produces the same result as the Phaser 2 example
Since the method returns the actual intersected tiles, you can then loop through those to get other information, such as the distance to the nearest intersected tile and the actual intersection point.
Utilising the other Phaser 3 Geom.Intersects methods
But rather than getting all the intersected tiles, then looping through them yourself, could we not use the existing Phaser 3 methods to get the nearest tile or the actual intersection point? Afterall, we saw in the previous post of phaser 3 phaser 3 methods to do that. For example, by replacing the Phaser.Geom.Intersects.LineToRectangle (which simply returns true or false depending on intersection) with GetLineToRectangle, we could get the actual points of intersection with each rectangle. Another possibility would be to create an array of polygons (instead of creating a rectangle sequentially) and using GetLineToPolygon, then you could get the closest intersection point, as well as the distance to that intersection point. Indeed, if the map does not change, you could create polygons for all the tiles once at the beginning.
For example, the below code loops through every tile of the map and creates a geom.polygon for each (strictly speaking, the right edge coordinate and bottom edge coordinate should have 1 pixel deducted).
createPolygonMap() {
let corner = new Phaser.Geom.Point();
const tiles = this.map.getTilesWithin(0,0,this.map.width, this.map.height,{isNotEmpty: true});
let tileWidth = this.map.tileWidth;
let tileHeight = this.map.tileHeight;
if (this.layer) {
tileWidth *= this.layer.scaleX;
tileHeight *= this.layer.scaleY;
}
tiles.forEach(tile => {
this.map.tileToWorldXY(tile.x, tile.y, corner);
const tileRect = new Phaser.Geom.Polygon([corner.x, corner.y,
corner.x + tileWidth, corner.y,
corner.x + tileWidth, corner.y + tileHeight,
corner.x, corner.y + tileHeight,
corner.x, corner.y]);
this.polygonMap.push(tileRect);
});
}Once you have the tiles as polygons, you can use the various Geom.Intersect methods.
As an example, here is code using GetRaysFromPointToPolygon, the output of which is shown at the top of this post.
And the raycast example from the previous post, adapted to the tilemap (I have not bothered to copy over the 3D rendering code, but it would work).
What was a little bit surprising to me is that it runs slow.
As we saw in the previous post, the GetRaysFromPointToPolygon uses geometry to work through the intersection points of the given line vs every edge of every polygon. Intersection between two lines is a straightforward calculation. So it must the sheer number of tiles & edges to work through. In this particular example, there are 241 "wall" tiles = polygons. Each polygon has 5 points (the start end the "end" vertices overlap) and 4 edges.
Also, because the method shoots 3 rays for every vertex of every polygon, the above code involves shooting (I think) 3 x 5 x 241 = 3,615 rays.
For each ray fired, the ray is checked for intersection against every single polygon (241), which is in fact checking the intersecton of the ray to every edge of the polygon (=4). Hence, the number of intersection checks is 3,615 x 241 x 4 = 3,484,860!
Can we make the above more efficient?
There are lots of different ways of making the above more efficient whilst making use of Phaser 3 Geom.Intersect methods.
Checking for tiles within a AABB
Rather than creating polygons for every single tile at the beginning and shooting rays against the vertices, you could for example shoot a ray in equal intervals in a circle, and each time you fire a ray, you could check for the tiles within the relevant AABB, just like getTilesWithinShape; the simplest but effective form of spatial partioning (of course this form of spatial partioning can still result in checking a lot of tiles, if you for example shoot a ray from the bottom left hand corner of the screen to the top right corner of the screen).
Getting rid of the "non-interesting" faces of tiles
If you google search for algorithms for "uniting" or "merging" multiple polygons into smaller number of polygons, you will find many very sophisticated and mathematically elegant (ie difficult to understand) methods. In our particular case, there there are a number of specific conditions: (i) all the tilesa axis aligned, (ii) same shape, and (iii) they positioned in grid positions. The method I personally found most easy to understand is introduced and explained in the below Youtube video.
The algorithm is extremely elegant in its simplicity. What it does is to look at each tile's 'interesting' face, one by one, and if there is one, it looks to see if the neibhouring tile has a edge that is shared. I have converted the code of the said Youtube video (which is in C++) to Javascript, to accept Phaser 3 tilemap object and to return an array of Phaser 3 Geom.Line objects. Otherwise the code is a literal translation - this is not my original code. It is of the One Lone Coder.
Despite the simple logic of the algorithm, the code is quite long so I will not reproduce it here.
To use it is easy, as I have embedded a method within the RayCaster class.
Specifically, you create a raycaster object, by feeding the scene and the map, then call the createPolygonMap method to work through all the tiles and create the array of "bounding edges".
this.raycaster = new RayCaster(this, this.map);
this.raycaster.createPolygonMap();
The "boundaries" of the tiles (or the edges) are held in an array called vecEdges, hence can be accessed via this.raycaster.vecEdges (although there should be no need to access it directly).
I will say that the result is quite remarkable - the result of running this algorithm is that we end up with 166 edges, as opposed to 241 squares x 4 edges = 964!
With the number of edges considerably reduced, we can simply check the "ray" against the all the edges. From what I can see, whilst there is a GetLineToPolygon method which checks one line against an array of polygons, there is no method to check one line against an array of lines. However, it is easy enough to create a method to do this.
getLineToLines(lineA, lines, out) {
var tempIntersect = new Phaser.Math.Vector3(0,0,Number.MAX_VALUE);
if (out === undefined) { out = new Phaser.Math.Vector3(); }
var closestIntersect = false;
lines.forEach(lineB => {
if (Phaser.Geom.Intersects.GetLineToLine(lineA, lineB, tempIntersect)) {
if (!closestIntersect || tempIntersect.z < out.z) {
out.copy(tempIntersect);
closestIntersect = true;
}
}
})
return (closestIntersect) ? out : null;
}Of course, there is more we can do to optimise this code. The code is checking the line against all lines, irrespective of where the lines are. However, comparing line to line is computationally no so expensive, and in any case I will go into a totally different method of raycasting, in the next post.
Here is the CODEPEN of the code which has the method to calculate the bounding edges.
Comments