Raytracing on Tile maps, basic concepts

Raytracing 2D concept

Raytracing, as the name implies, involves tracing the path of a ray, or line, to check for collisions. In these tutorials we'll look at how to make use of this on 2D tile maps for determining the area visible to or illuminated by game entities.

View example

To begin with, lets examine the picture below to make sure we understand the concept:

We have four rays, A, B, C, and D moving from the left of the grid to the right. Each ray can move 11 grid squares, but will stop if it encounters an obstable. Ray A is blocked by an obstacle in column 11, so moves 10 squares only. Ray B is blocked at column 4, and so moves only 3 squares. Ray C is blocked at column 8 and moves only 7 squares, but ray D has no obstacle on its path until column 13. As we're only letting the rays move a maximum of 11 squares, the ray completes its full path without being blocked, stopping at column 11.

Each ray is dealt with as follows:

  • Choose a start and end point for each ray
  • Find a list of grid squares touched by this ray from start to end
  • Loop through the list:
    • Add this tile to our list of tiles hit by the ray
    • If the tile is solid, or in some way should block the ray, exit from the loop

So how do we make use of this? If we're plotting tiles hit by a light source, we know that the tiles touched by the ray are illuminated, and those that are blocked by obstacles are not. If we're calculating vision, we know that tiles touched by the ray are visible, and tiles hidden behind obstacles that the ray never reaches are not.

An example of raytracing

Let's make a useful example. In our example, we'll expand rays from a central point to all of the points on the circumference of a circle around this point. We'll be making use of the Bresenhams Circle Algorithm for finding the circumference points, and a line algorithm for plotting the rays.

We'll begin our function, which will take three arguments cx, cy (the centre point of the circle), and cr (the radius of the circle), and use the pointsOnCircumference method to find all the edge points, which we'll store in the edges variable:

function updateRayData(cx, cy, cr)
	var edges = pointsOnCircumference(cx, cy, cr);

We'll also create an object to store the points our rays touch:

	var points = {};

Next, we'll loop through the list of points on the circle circumference and use the pointsOnLine method to create our ray - the list of coordinates used to make a line between the centre point and the current circumference point:

	for(x in edges)
		var line = pointsOnLine(cx, cy, edges[x][0], edges[x][1]);

Looping through the points on the line (or, tracing the path of the current ray), we'll add each point to our list of points touched by the current ray:

		for(l in line)
			points[((line[l][1]*gridW)+line[l][0])] = [line[l][0], line[l][1]];

If the tile on our map obstructs the ray (a 0 value in our mapData array for this example), we break out of the loop for the current line or ray:

			if(mapData[((line[l][1]*gridW)+line[l][0])]==0) { break; }

Finally, we can close each loop and return the list of points touched by all the rays sent out from the central point to the circumference:

	return points;

Look at the example source code of the example to see how rendering is accomplished, but the use of the two functions (pointsOnCircumference and pointsOnLine) and the small custom piece of code is all we need to add raytracing to our example. It's very useful for many games and applications, and there's really no great mystery to it!

Page loaded in 0.012 second(s).