Line Of Sight or Shadow Casting in 2D - VoiceTube: Learn English through videos!

Subtitles section Play video

hello.
In this video, I'm going to be looking at quite a classic algorithm line of sight.
Also known a shadow casting.
And as usual, I'm going to start by showing you what it is that I'm talking about.
So here I have an arena where there's a boundary defined in blue.
And if I hold down my right mouse button like instant shine, a light in this arena on doesn't move the routes around.
I can see that the light is following the mouse cursor.
This is all done in the pixel game, injured by the way with the left mouse button.
I can draw shapes, so I'm going to draw a boundary here and you can see it's it's sort of a tile map array on the nice thing is now when I hold on the right mouse button and turn the light off, we could see that the boundaries cast shadows well, the cash shadows, but they also indicate the locations that can't be seen from where the mouse cursor is.
So this is also a line of sight.
He behaves quite nicely a lot in a few more features and see how it behaves and all of the features cast their own shadows.
In fact, we can add lots and lots and lots of features.
Obviously, some of them are little boundaries and worlds.
We can extend things out.
Lots of interesting shapes.
It doesn't matter.
The algorithm can quite happily deal with any layout of tiles I'll make here at the bottom a small enclosure and the algorithm behaves as you might reasonably expect it to us.
We enter the enclosure.
Visibility of the rest of the field is restricted to the doorway, and in fact, if we close off the doorway, of course, we can't see outside The little room.
Line of sight is very useful in strategy games, So here I've developed a little corridor on.
I'm going to push the agent through the corridor.
We can see he can only see what's inside the corridors.
He's moving around now.
I think that's a really cool algorithm on my implementation of.
It is one of several methods you can use, so let's take a look at how it's done.
But before we get started, this is my very first pixel game engine exclusive video.
So I'd like to spend some time just showing how to set up a pixel game engine project using visual studio.
Now, I know that for many of you, this is all old hat and you know what you're doing, but you'll be surprised.
I get quite a few comments, people saying they don't really know how to settle visual studio.
So please forgive the next couple of minutes.
Whilst I do this.
When you start visual studio, you'll be presented with start page.
I recommend going to file new and selecting project in the list of projects you see, one is called a windows console application.
Give the solution a name.
I'm going to call this one shadow casting to D and press.
OK, now visual studio.
And this is the very latest version of visual studio will go ahead and create some files for you, and it even gives you some hints as to what these files of four.
For my videos, though, I don't really want the file structure it provides.
The first thing I want to do is get rid of the P c h dot h file on the PCH dot CPP file.
So I select them and press delete.
I don't want them I'm not going to use pre compiled headers.
This also, that means I have to get rid of the Include PCH dot h from the main.
What's the matter?
I'm going to get rid of all of these comments to We need to tell it that we don't want to use pre compiled headers in our Project Sigma to project properties and make sure we've got debug selected, appear and expand the C in C plus plus option.
Go to pre compiled headers and in the Tablet says Use priest compiled headers were going to say not using pre compiled headers and click apply Whilst you're here, you might also want to do the same thing for release.
Now I know it's very controversial, but the next thing I want to do is actually include the STD name space, and the only reason I do this is because it's easier to make videos that appear clearer.
Best practice is not to do this.
We're creating a pixel game engine application, so at this point, you Nepali need to go to the one loan coded, get hope and download the head of file, and here it is Oh Elsie pixel game engine dot h.
Grab this file on Copy it into the folder that you created when you created a new solution.
So on my machine, this is the shadow casting to D folder.
I've pasted the head of file into this location.
I don't want to include that file in my source code.
And now there is one last little thing that we need to do, which was different from the console game engine on.
This is currently experimental, so you may not always need to do this, but right now it's something I'm trying out.
And that is before we include the pixel game engine file.
We need to define our application as being one uses the pixel game engine.
And we do that by doing hash define Oh, l see underscore PG underscore application on.
We need to do that before we include the head of file.
And the reason that I'm taking this approach is that instead of having a separate object orientated version off the pixel game engine, I'm trialling just using a single head of file, which means we need somewhere in all of our compiled code, an actual implementation of the pixel game engine on that will be wherever we have defined.
This constant will see PG application.
Now, as most of my videos are single file solution, I will just want to define this constant at the top of my main file.
Next, I want to override the OLC pixel game engine based class.
This is just the same as the council game engine and was shown in the OLC pixel game engine video.
So thanks for putting up with that.
I just needed a little bit of a video reference for the people that ask those questions.
So let's carry on.
Now we've got the basic structure in place.
I'm going to create an object of type shadow casting and call the construct function.
And I want to construct a pixel game engine with resolution pretty high now 6 40 by 4 80 where each pixel is two by two screen pixels, and if that's successful, then start the engine.
At this point, you may want to do a test, compile and run just to make sure everything's set up correctly, we should see a black screen off the dimensions we've just specified very nice.
Now this is a bit of a two for one video because to implement shadow casting or line of sight, we really need to algorithms.
I like the convenience of being able to draw the world's in tiles.
Placing blocks is quite intuitive as we saw it, the Jarrow platforming game.
You could have a selection of blocks and place them wherever you want, but the shadow casting algorithm itself relies heavily on geometry.
And if we had to do geometry for all of the blocks, every single frame, well, I feel that's not very efficient.
So the first stage of the algorithm is to convert our tile map of blocks into a polygon map of edges.
Here I've drawn out on our poetry section, off level or world that based on a tile map so you can see where I've placed the blocks where I haven't placed the blocks in the background.
This is very convenient, as it makes life easy for the level developer.
It's easy to draw particular sprites and set locations.
We've done collisions with tile maps before.
There's lots of advantages to using a tile map, but we don't want to use the geometry of every single block edge to cast shadows because at any given moment there's a lot of edges.
Instead, what we prefer to see is the boundary off the clusters of blocks.
So we're going to come up with an algorithm that will turn a cluster of blocks into a polygon.
We're going to find the bounding edge of this block.
Now I can look at this block and intuitively say, Well, we've got a Vertex here on a Vertex here, Vertex here, one here.
Want Here, here, here and here.
We also have four more verte sees here and in principle.
What I'd like to do is link these verte sees with lines.
And I think it's quite easy to see now that there are far fewer boundary lines than there are block edges.
Once we move out of the block E world off the tile map into the smooth world of the polygon, there are lots of other advantages.
We get a CZ well, we could implement realistic physics and collision detection.
We can have edges which don't align with the natural tile boundaries in the world.
And of course, we can have natural looking Grady INTs and slopes.
I think we'll see a lot more of this album of them popping up in future videos.
I want to construct these polygon boundaries in the most efficient way possible.
So ideally, given a cut out of the larger world, I want to scan through.
It wants to create the set of edges.
So that's exactly what I'm going to do and where to start from the top left and I'm going to scan horizontally across the screen.
And when I get to one end, I'm going to come back to the start on scan the next road.
In this simplified example, the structure that I have for a particular cell in the tile now is quite simple.
It either exists or it doesn't so in some sort of cell structure.
I know I'm gonna have a Boolean for exist, but in order to implement my algorithm, I'm going to need some additional information.
I'm going to add four more billions, which tell me, do the edges exist on these?
Relate to the north, south, east and west edges, and as we saw at the start, a cell may share an edge with other cells.
This implies that any given cell can't actually own an edge, and said it must use one that stored else were So I'm going to also include four interviews which represents the only D off a given edge on the north, south, east or West Side from some edge pool that will create else work.
So let's start manually going through the algorithm.
Firstly, we want to check.
Does the cell we're currently inspecting exist?
Because this cell doesn't exist, This cell doesn't exist except you, etcetera, etcetera, all the way along in our world.
Until we get to one that does exist, we only care about cells that exist.
So we're going to apply tests to this cell on the first test that will try from the perspective of this cell is Do I have a western neighbor?
Well, in this situation, clearly I don't have a western neighbor, so I definitely have a western edge.
But where do I get this edge from?
Well, the only other place an edge could come from is from a northern neighbor that also has a western edge and in effect will take that edge and grow it downwards.
In this situation, we don't have a northern neighbor, so we're going to create a new edge and so will add to our edge pool edge, eh?
And in our cell structure will link our edge.
I d to the location of the edge in the edge Pool will now systematically check the other sides of the tile.
Firstly, we'll check the eastern edge.
So if I haven't Eastern neighbor, which in this case I do, then clearly that isn't an edge necessary between us.
We don't need to do anything further.
Now we need to check our northern neighbor.
Well, I don't have a northern neighbor in this case, so I do need an edge, but work and I get one from Well, I can either get one from my western neighbor or I need to create one of my own.
And since I don't have a western neighbor, I'm goingto have to create one of my own.
So we'll create a new edge called B and will give the idea of that edge to the cell Also drawing the a hedge there.
As you can probably tell already it's a similar situation for this southern edge, too.
We're going to need to create one for this cell.
See, now we're traversing from top left to bottom.
Right.
So this is the next cell that we check on.
We run through exactly the same routine.
Do I have a western neighbor?
Will they do so?
I don't need a western edge.
Do I have an eastern neighbor?
Well, again, I do.
I don't need an eastern edge.
Do I have a northern neighbor?
No, I don't.
So I do need an edge.
But this time, rather than creating one for myself.
What I can see is that my Western neighbor currently already has a northern edge.
So I'm going to extend that edge to suit my needs.
And I'll set my edge.
I d as well.
The final check is Do I have a southern neighbor?
Well, I don't.
So I do need an edge on you've probably already guessed.
I'm going to grow my western neighbors edge as well and set my cells edge.
I d on the southern boundary.
Two suits.
That particular edge.
Exactly.
The same routine occurs for the next cell.
So let's run through it again for this corner cell.
Well, we checked.
Do I have a western neighbor?
I do, so I don't need an edge.
Do I have an eastern neighbor.
I don't in this case, so I do need an edge now.
I can't borrow one from my northern neighbor, so we'll have to create one D and I'll add that edge to the edge pool and set my I d.
Now we check for northern neighbors on just as we've done with the previous cells.
I don't have a northern neighbor, so I do need a northern edge.
But fortunately, my western neighbor has got one I can borrow, so I will extend that edge and set my idea accordingly.
Now, for Southern neighbors, this is the first time we check for Southern and I've got a Southern neighbor.
So I don't need an edge between myself and my southern neighbor, which means I no longer need to extend the edge, see horizontally.
In fact, it's very likely will never need to do anything with see again.
But we don't have to touch it.
It's in the edge pool.
It's got to start in an end point.
It's done so we'll move on the next cell it exists.
Is this Stand alone sell here.
It doesn't have any neighbors, so the consequence of this is going to add four new edges to the edge pool, a western edge on eastern edge, the northern edge on the southern edge.
He if G and H and set the edge.
ID's for 56 and seven.
So the worst case scenario is a map made up of lots of individual blocks.
Carry on testing, but I'm not going to go in as much detail now.
The next block tested is this one that does exist well.
This one needs a new Western edge, which is I now we're up to, but it can borrow from its northern neighbor.
It's eastern edge, and I'll just carry the algorithm along now for the rest of the shape.
Once we've gone through, all of the tiles were interested in will have an edge pool that contains only the bounding edges off the shapes, and the edges are defined by a start on an end coordinate.
It's very possible that edges will share a coordinate, but needless to say, we've converted our tile map into a set of edges, not strictly a polygon, because we're not defined.
What's the inside and the outside off the polygon?
But we can assume that things don't pass through edges in our application.
So I think our first step in code is to implement this algorithm.
Now.
I've gone through it in quite some detail here.
I'm not going to go through the same detail in the coats.
I'll do some cutting pasting.
I will need some basic structures to assist us.
First thing I'll need is an edge, which stores the X and Y components of its start and end points on.
My world is going to be made up of an array of cells.
So this is my cell on.
I've included in it Julian flags for Does the cell exist or not on?
Does it have an edge that exists on all four sides?
And what is the edge I d into the pool of edges?
And just to make the algorithm a little clearer to follow, I'm going to define some Constance for North, South, East and west.
Our world is going to be a two D array off cells.
The world will be defined by two variables world with on world height.
In this case, I've chosen 40 and 30 because if I assume a block size of 16 by 16 pixels that lines up very nicely with our 6 40 by 4 80 resolution.
So essentially the world is a single screen that we can see in on user correct.
I'm going to allocate the memory that holds our world.
Adding code to place blocks in the world is quite simple because we're using the pixel game engine first.
I'm going to define the width of the block, just in case we do want to change things later on on.
I'm going to grab a quick snapshot off the mouse coordinates.
It's important to do this because the mouse coordinates can technically change whilst this function is executing, so grabbing them rights of the staff means that we're going to have consistency through the code to check.
If the user has pressed the left mouse button or clicked, we can call the get mouse function on items.
Zero.
That's the left mass button, and we're going to check to see.
Has it been released this frame?
If it has been released, we're going to get to the index of the cell that it has been clicked in.
Now this looks horrendous, but it's actually quite a simple bit of code we take our input mouse, coordinate on, we do an interview.
Divide with the block width.
So this will tell us how many blocks down the screen is the mouse cursor.
We do the same thing for the X axis.
We take the X most corners, and we also divide that by block with.
And that tells us how far across the screen is the mouse cursor in tiles effectively.
Andi, this is something we've seen many, many times now I equals a y co ordinate times the width of the array plus X, which converts our two d X and Y cornets into a one de cornet in the array.
Once we know the index weaken toggle the exist flag for the cell at that location, staying in on user update.
But I'm going to move it down a bit, will do the drawing code.
And the first thing I want to do is clear the screen all black.
And now I want to draw the blocks from the tile map.
And to do this, I'm going to iterated through them all and simply check if they exist or not.
And if they do exist, I'm going to draw a filled in rectangle at that location.
So this is Kurt, voting back from block space into screen space.
Now, with the width and height set to the block.
Quit and I'm going to draw the rectangle as blue.
Let's take a look.
So who got the screen with the massacre surround, And if I click wherever I click, I place the blue block, and if I select a blue block and click it, it gets rid of it.
Were basically toggling.
Does the block exist at that location or not?
Now we can worry about turning the tile map into a pool of edges on the container.
Goes use for this is a vector called back edges on because I know that doing this type of conversion is going to be incredibly useful for future videos.
I'm going to create a function that explicitly does this.
It converts a binary tile map into what I'm calling the poly map.
It's going to populate this factor with all of the edge information given a particular region of a tile map, so the parameters of this function are a starting X and Y coordinate the width and height of the rectangle off tiles of which I wish to inspect and turn into edges are also going to pass in the block.
Quit parameter, so we know where edges exist in actual space.
And then there's this strange character called Pitch, which is going to be set to end world width.
But I'm leaving it as pitch because we want to be able to use its on arbitrary size maps going forward.
So I'm using the phrase Polly map.
It's a little bit made up, and the first thing I want this function to do is to clear all of the information associate ID with constructing this map.
Naturally, I want to just clear the vector of edges first.
But then, during the construction off, creating this vector, we're populating the cells with additional information.
I need to reset that information effectively back to zero.
So I'm iterating through all of the cells in the region of interest that I'm converting, and for each cell I'm setting that it has no edges a tall and it's not got any edges in the pool again.
Here we see why times wit plus X.
Once we've cleared our map, it's time to start applying our algorithm on.
I'll do this by creating 24 loops X and Y and iterating through the region of interest.
Now you'll notice here I'm actually its rating from one, too, with minus one off the region of interest.
And that's simply because I don't want to have any out of bounds memory errors when I'm checking along the edges off the two D array, I could get away with that for this demonstration.
But going forward, I'll probably want to tighten that up a little bit to accommodate genuine array boundaries.
Now, to stop things getting out of control, I'm going to create some indices which are more convenient to use, so the eye index will be the current cell index in the array.
We can look at our northern neighbors the current cell, but Book one in the UAE direction on our eastern neighbor is the current self plus one in the ex direction.
First, let's check if the cell exists or not.
If it does exist, will check to see doesn't have a western neighbor because if it doesn't have a western neighbor than it needs a western edge, one of the places we can get a western edge from is our northern neighbor by extending it downwards.
So let's see if our northern neighbor does that have a western edge, if it does, will extend it, and we can extend it by looking at our northern neighbors.
Western edge.
I d.
On using that I d to index into our edge pool so we can find which edge is on the western side of our northern neighbor.
And we know that we're going to grow downwards.
So we want to extend the end coordinate of that edge by one block wit down, which is what this line does so in our pool of edges were looking at our northern neighbors western edge I d to get to the edge that is relevant to us.
We're taking the end y coordinate because we're going to extend in the y axis downwards on.
We're increasing that coordinate by the height of one of our blocks.
Just so happens that our blocks are square.
Since we're borrowing an edge that already exists will set the edge.
I d of our current sells western edge to be the same as on northern neighbors, Western edge.
And since the inch exists.
We'll set that to true.
Now, if I didn't have a northern neighbor, I still need an edge from somewhere.
So I'll need to create one to create a new edge object on.
We can use the position.
We are in the array on the block width variable to work out where we are in real space So we can set this start coordinate of our edge X And why here, using wth e array coordinates multiplied by the block with Andi, we know at the moment that our edge is going to be at least one block tall.
So we can specify that, too will add to the edge to our edge pool simply by pushing it into the vector.
And since we've created a new edge, as we did appear, we need to know set to the I d.
On whether the edge exists or not.
For this cell, well, it's a new edge I d on.
We've used the location of it in the vector to specify that I d.
And so that is all of the code required to work out whether we should create a new western edge or borrow from our northern neighbors We now need very similar code for the other four edges, and I'm not going to talk through it all.
I'm going to cut and paste it in, but it's very, very similar.
We just need to be careful of what we're doing when we're constructing the new edge.
So even though I appreciate that seems like a really large amount of code to put it in one go, I hope you can appreciate that is actually very similar to the one that we've just done.
You can probably tell that I'm going a little bit faster than usual on this video.
That's only because there are two parts of the algorithm that I want to include, but I don't want the video to become an hour long.
Now we can go back to our unused update function and actually call our new function to create the poly map.
And here I am calling it, and I'm giving it the region of interest that I wish for it to convert, which in this case is the whole array on.
I specify the block with coordinates so the edges can be done to the right scale on especially the pitch to be the wit of the world.
It's actually the same as the value amusing here, because, coincidentally, the whole world is represented by the single screen I can see.
I think it'll be quite nice to visualize the edges, to help us with some debugging and to make sure that everything is working accordingly.
So after we've drawn the blocks on going to create a little auto four loop to iterated through all of the edges in our vector of edges on, I'll use the drill line function to draw a white line from the starting coordinates.
The ending coordinates off the edge, but to make the ends of the edge a little bit more visible, I'm going to draw a red filled in circle that's each end, I said.
The center of the circle, This is the radius, and this is the color.
Let's take a look.
There's my blank screen on.
I'm going to place a block very nicely.
We can see we've got at least four edges that if I place a block next to it, we could see it's not drawing any more ends of edges.
It's just drawing edge.
So it was look like in that direction, The algorithm is working just fine.
If we branch off from here, we can see that seems okay to Let's go top.
Very nice.
If I've inadvertently drawn some offensive simple here, I do apologize, but I'm just randomly clicking where I need to click thing.
What's probably also worth Jackie is solid objects, so it doesn't necessarily have to be a wall one tile thick.
It does seem to work for that, too.
In fact, we can punch a hole in the middle of this solid, so I'm reasonably confident that we have taken the tile map on.
We have reduced it into some geometric primitives, which might be more useful for doing more complicated geometric maths.
Now that's very nice.
And the performance seems quite reasonable, too, especially given I'm doing this every single frame that I'm rendering.
In most cases, you probably wouldn't need to do that.
You only need to regenerate the poly map if the tile map changes, and in some situations it could be a completely offline, pretty compilation step of how your level data is stopped.
So all in all, I think this is a very useful routine.
Have right so Let's start thinking about the shadow casting on the line of sight bit.
Here, I've got a location off the source of the light or where the player stands, or whatever it is.
We're going to project rays from this source.
Radio Lee out into the scene.
Now I've covered casting rays before.
In fact, one of my very first videos the first person shooter, the command line engine.
We can cast race in all angular directions and see what they hit.
So here we go, cast out some race.
Not very straight razor might have.
But when they intersect with something in the scene, the rail inches shorter on anything that followed that ray length past the intersection point is technically in shadow.
Finally, this one is also in shadow, and I'm sure you can envisage a scenario where we keep doing this all the way around the scene.
But this is really computational, inefficient and in fact we can look at this and derive from it that we're only interested in race that intersect with our line segments.
Even more so, we're only interested in race that seem to intersect with the corners.
So let's explore that for a moment, each edge in the edge pool.
I'm going to project a ray to the start on end point, so in this case, have effectively got four raise.
When the ray into sex with the line, we know the ray effectively starts turning into shadow, but let's consider not looking at areas which are in shadow but instead which areas are in light.
The second rate down was defined by this coordinate, but we can see that it had to intersect with another edge on its way there, and so will record the intersection point that is closest to the source of the array on will do that for all four Ray's cast out, and in fact, let's do the same for all raise for the other object to So we cast rates to each of the vergis is defined by the edges of the other object, drawing the intersection points that are closest along that ray.
If I had in one more point, which is the source, what I'm actually constructed is a fan off triangles.
That's one triangle next triangle, and these triangles construct a polygon, which covers the area that is definitely visible from the source The problem is, it's a bit of a strange pull ago, because if I shaded in this polygon with light, we can see there's some big gaps which are definitely visible.
But they've been ignored by the algorithm.
What can we do about these big gaps that, well, there's a little hack that we can apply.
Instead of casting one ray from the source to a Vertex, we cast three.
Raise one goes directly to it, and we have one either side displaced by a tiny fracture and angle.
So it will miss the Vertex in this case, on that side and on this side.
Well, it'll just hit the line as it normally does.
So three raise one.
Is it theater and one Is it theater, plus or minus some tiny little amount?
These additional rays will affect our image here in the following way, so we'll have one of the rays will continue going until it hits something else, or it hits the boundary of the world as well.
This one on this one and this one into section points are also recorded on Now.
When we draw the triangle fan formed by these points, there's a lot more area to fill in.
In fact, it turns out that it's all of the visible area from the source.
And this is why these two algorithms are interchangeable because the lit up area is the line of sight.
It's all the areas that can be seen in the areas that can't be seen.
Must be in shadow.
So we have cast shadows.
We'll start researching into this topic.
I found two brilliant websites.
She must go and have a look at them.
They outline these algorithms in quite some details.
Have lots of interactive demos you can play with two.
I will, of course, linked to these websites in the tax below.
The 1st 1 allows you to place a light source, much like the demo that we're building, and you can see it has a degree of complexity to it.
But it's quite nice because it talks all of the different stages that you might go through when developing this algorithm.
This is the 2nd 1 and again, a really nice site full of nice toys to play with and some code two and you can see again.
You can interact just as we're doing with edges and shapes and seeing where the race get cast.
In fact, it was this website that gave me the idea off, casting out additional raise for the corners.
Please take the time to check out these sites.
I think it's a wonderful thing that experience developers are taking the time putting the effort into actually doing tutorials like this with interactive elements.
It's a lot of work and yet yields so much to check them out the links in the description below.
So going back to our application, we know that for each edge end, we're going to send out three rays, and we're going to form some triangles from the intersection points of those rays with the edges.
Where to start By creating another function to encapsulate the calculation off our visibility polygon.
There's going to be a set of points that represents the visible space from a source location defined by O X and A Y over a given radius.
But I'm going to use a little bit of modern sea to help me out here.
I'm going to store the points of this polygon as a vector of topples off floats, and you'll notice there are three floats the first float is going to represent the angle from the source off the Vertex that were targeting with the ray and the second to floats are the X and Y location off that Vertex.
We need to store the angle because without it we won't be able to draw sensible triangles in the fan later on.
Since we're going to iterated through our vector of edges toe workout, the coordinates of the world, we should cast raise.
This could theoretically happen in any sort of order, which means when I come to draw these triangles later on, I can't do it sensibly, effectively need to drool these points in some rotational order.
And so the easiest way to do that.
It's not just to store the point on its own but taken arbitrary access from our source point on record.
The theater values off each of the points, so for each point I'll have a theater on an X and A y.
I can then sort these points based on the theatre value to make sure that they're in this clockwise order.
If you've not seen a topple before, it's just a simple way to group things together.
It's a bit like a stroke, but it's very compatible with the standard library.
So as we did before with the edges, the first thing I want to do with my visibility polygon is to clear it.
Then we know that we need to do something for each edge in our vector of edges, so little also four loop to it straight through all of the edges now on edge consists of two points the start and the end.
So for each edge, we're going to have to cast at least to raise directly to hit the start and end points.
Since I need the angle of the ray, I'm going to start by first calculating the radiant of the ray now, depending on whether we're at the start or the end.
So I've used the Turner, a operator here, to select between the start point of the endpoint on.
I'm subtracting from that the source location O X.
I know why giving me two variables are the accent arty.
Why?
Which represents the ray vector.
Now I'm not bothered what our angle is relative to as long as it's consistent, so I'm just going to create another variable base angle and used the Aten to function using the RDX and are the Y values.
So this gives us an angle off our ray vector, and we know that for each ray, actually, we're going to cast three additional raise with a slight deviation between the two.
So I create a temporal variable called angle, which is going to be the angle we will shoot the rate at.
So add another four loop to generate the three additional race we're going to need.
On depending on the Value J in the four loop, we're going to choose an appropriate angle to cast the ray out, too.
So, in effect, we've gone back on ourselves a little bit.
Here we've calculated the Grady int of the ray so we can work out what the angle is.
And then we're using the angle, plus or minus a little bit of deviance to generate the vector of the ray again, which we can easily do.
Taking the co sign and sine of the angle will only cast the ray as long as we've specified the radius value to bay.
As you can probably see, the number of rays were actually projecting into the scene is growing on, the more complicated our scene is with tiles, the more Braves will go into cats.
Now, however, the one thing we guaranteed is that our strategy is more optimal than casting raise out in all directions and seeing what happens at least now raise are going did intelligently to at least some features within the world.
And this is where the really chewy part of the algorithm comes because for every single ray we now need to check for intersection between the ray on all of the edges in the scene, the algorithm has now come down to a simple line segment into section test so we can take to line segments and we want to work out the point at which they intersect.
One way to think about this is to take a known point on each line, represent the line segment as a vector.
Therefore the opposing point becomes existing point.
Plus that vector on, we can add in here a parameter do you want and t too, because if t one is equal to one were at this end of the line.
And if t one is equal to zero, we're at this end off the line and so will find we're into Section Point is by looking at the T values.
And since we're talking about line segment into sections, go and find the line segment into section algorithm of your choice.
I personally like this one, which I discovered on snack overflow.
The answer here is actually a code implementation of the answer above.
I'll put a link in the description below before we can calculate the intersection, we need some additional information, the first of which is we need the vector that represents the edge, which is easy to calculate because it's just one end of the edge subtracted from the other.
We'll also need to make sure that the ray isn't going to be cold linear with the edge.
It's not going to lie on top of it, so I'll check for that by just looking after the values off the vector components on making sure that they're sufficiently different.
For example, if both had a d Y zero, then both the ray on the edge could be horizontal.
There's a chance they could overlap, and there isn't a single solution point that represents the point of intersection.
Now we can calculate the T one and T two values using the line segment Intersection Point algorithm, and in this instance, T one is the distance along the ray and T two is the distance along the edge.
And so if t one is positive, that means we're traveling along the ray in the correct direction.
And if t two lies between zero and one, then we've definitely hit a line segment.
Now that we know we've gotten into section Point, what do we do?
Well, we're only interested in the Intersection Point, which is closest to the source point.
Even though we've detected intersections along many edges, we want to reject most of them on only retain the one that is closest to the source and R T.
One value represents that information.
We don't need to do Pythagoras theorem here to calculate the distance because T one indicates the length along the ray.
And so for each ray that I cast, I'm going to store some temporary variables that represents the minimum t one distance, and I'm also going to store the X and y of the intersection point at that distance, I'll set it to infinity for each Ray to stuff.
But if the t one that represents the intersection point of the ray of just tested is less than our current closest into section point, I'm going to replace it, and I'm also going to calculate the new intersection, point and angle.
Of course.
Now, for all of my race, once I've calculated were the ray ends, I'm going to add that location to my vector of visible Polident points.
Our calculate visibility Polygon has not quite finished yet because right now we've got a vector full of points in any particular order, and so I need to sort them based upon the angle.
Fortunately, the standard live we can provide a nice, simple routine to do this forest.
It provides sort as part of algorithm, and so I'll call the sort routine, giving it the start location of my vector and the end location of the vector.
But our pass in as thesaurus thing criteria a small lambda function.
It's going to sort based upon the angle.
So the two arguments going into the Lambda function are references to the two topples, and we're only interested in the first element of the topple, which is the angle, so we're going to return.
True if the angle of the top on the left is less than the angle, that couple on the right and this will sort it in ascending order every frame.
I wanted to convert our tile map to a poly map, but I don't want it to calculate the visibility polygon every single fame.
I'm only going to do that when I'm holding down the right mouse button.
I also only want to draw anything relating to visibility under the same conditions.
So I'm going to check that the merry sport is held.
But I'm also going to check that the vector off points that we're going to draw at least has something in it.
And so now I want to draw my triangle Fan.
This is quite easy.
Now.
We've got a vector of sorted visibility points.
I'm going to go from the start of the vector to almost the end of it, and I'll use the Phil Triangle routine to draw a triangle from the the Origin Point.
The source where the mouse is to the X and Y points off two successive visible points in our polygon vector, So this will form a triangle.
What I mustn't forget to do.
It also closed the triangle at the end, so we want to draw from the final point to the starting point.
This will have to sit outside the loop.
Let's take a look.
Well, let's try with nothing in.
I'm right clicking.
I don't see anything that's out.
Some obstacles.
Oh, well, it looks like a complete and utter mess.
Well, bits of it a kind of working.
But something's not right.
And the problem here is where information starved were only casting out Ray's wherever we've got information in the scene.
So if I put in lots and lots and lots of points for it to reference room, it starts to look a bit more sensible.
There's still some horrible glitches, though, particularly what is this triangle going up toward zero in the top left?
Well, the spurious triangle is because we've assumed that all of our rays will effectively intersect with something, and this might not necessarily be the case, particularly when we have raised, which have adjusted by a slight angle so we can limit the rays that are added to the vector of polygon points.
By assuming they're only valid if they have in fact hit something so lonely at them.
If this be valid, variably set to true.
And that's only set to true if we have had some sort of collision along the length of the ray.
So let's take a look again.
That's some points in handled, released.
Now we've not got a problem going up toward zero, but things are still looking a bit information staffed.
In fact, if I now put in lots and lots of points is a boundary, I see how it looks then and now it's starting to look a lot more realistic.
So what this is telling me is that our raise that don't intersect with anything need to intersect with something we're going to have to put in an artificial boundary now.
I could do that in our recode.
What I'm going to do instead is just hard code in some boundaries, into a tile map array.
So in on music create where just created the world, I'm going to add in a couple of four loops, which draw some parallel horizontal and vertical cells into the world.
Let's take a look.
Now we can see the boundaries being put in.
I'm now illuminating.
Everything is lit up, put in some obstacles and very nice our race have somewhere to stop now.
And that was what was necessary in order to make this look smooth and work.
If we just quickly change our fill triangles to draw triangles.
Now we can see the individual polygons making up the polygon fan around the point from which were checking for visibility.
I'm curious about the number of Ray's being cast, so I'm going to capture that information on display.
I'll just quickly use the drawstring function to display this information to the user.
No rays being cast right now.
Ah, 168 Rays being cast for unfairly minimal number of objects that we take out a bunch on now cast 70 to raise, even though we've got 123456789 10 11 12 known verte sees in the scene.
This is because we've got duplication of vour theses.
Fortunately, the standard Libra can help us out here to since our vector visibility polygon point is sorted, we can use the unique operator to remove any duplicates.
Why do we need to draw to the same point multiple times, and so we'll do it before and after comparison.
Here is the unique function being called again.
It's part of algorithm on I've passed in a Lambda function again, which compares the topples, but this time it's saying, Please reject this particular topple.
If the X and Y coordinates are similar in this case, I said less than 0.1.
So create a second variable recast, too, and compare them.
So just a little recap.
We've used the unique function to remove all of the duplicates in assorted vector.
It doesn't actually remove anything.
The unique function.
It just reorganizes the vectors that all of the unique stuff is at the start.
So anything after the point returned by the unique function we want to remove on.
Therefore, I'm re sizing the vector based upon the distance.
From the start of the vector to that unique point are now draw how many Rays were actually cast versus how many rays were actually drawing on the screen.
Let's take a look.
So in a blank environment, we're casting 48 rays for the number of rays that were drawing is changing between well 10 and 13.
Little bit of fluctuation.
And that's because it depends if we look at the top right corner here, we can see a bunch of race, but it's certain angles the Rays overlap each other.
There's absolutely no point in drawing triangles that we can't see.
So let's add in a few obstacles, of course, will expect the number of race to increase or casting 100 92 Rays.
But now we're only drawing about 50 rays.
I think this is quite a significant optimization to make lots of features.
840 Ray's cast on were drawing well, about 25% of them.
I'm going to fill in the triangles again now and so we can see we've got quite a robust line of sight or shadow casting algorithm implemented.
Now, at the start of this video, I made it look a little bit more special because I used a sprite off a light sauce on modulated, where it is white here with that sprite.
So this is a bit of pixel game engine trickery.
Now, in photo shop, I have created a sprite that represents a light source emanating out from a central point it's a PNG file.
I'm going to load the Sprite into the pixel game engine, and I'll do that in on user create.
I'm not going to do something a little bit novel for this channel.
I'm going to do some offscreen rendering went to create two additional sprites called Buffett Light Ray and Buffer like Tex on these are going to be surfaces to which I'm going to do some post processing, but I need to create these in on user creates.
You'll see I'm not loading a file.
I'm just giving them a dimension.
They're basically going to be an image buffer toe, which I'll draw things and then modify the pixel game.
Engine supports rendering two different targets by default.
It renders to what you can see on the screen, and we can specify the drawer target by calling the set drawer target function on by specifying no point to is the argument.
That means there isn't any offscreen drawer targets draw to the main target, which is the screen.
So we want to do that before we clear everything to black on any subsequent drawing calls.
So in this case, drawing this string, those calls will be redirected to whatever the drawer target is.
I'm going to use the offscreen buffers to implement a nice lighting effect.
The first thing I want to do is draw my radial light sprite into the correct location in the buffer, and so have specified the target buffer.
I've raised it to black, and now I'm going to draw the sprite into the correct location, which happens to be my mouse cursor.
Now the center of my sprite.
Because the sprite is 5 12 by 5 12 needs to be offset accordingly and then going to render to the second off screen buffer the light rays.
So I'll clear the buffer to Blank.
First on.
All of the Phil Triangle routines will now be targeted at that buffer.
I want to combine these two buffers to draw to the screen on because we're drawing to the screen now.
I set the drawer target to know, and I don't have any additive or special blending modes yet in the pixel game engine.
So I'm going to iterated through each pixel in my offscreen buffer on.
I'm going to check if each pixel has been set.
Remember we cleared it.
Alter blank to begin with.
So if it's been set by one of the light race, it'll no longer be black.
And if that's the case, I want to drool in the current screen location.
X and Y the pixel of my light cast Sprite in the corresponding location.
Let's take a look so I can see my Sprite has now been drawn wherever my mouse cursor is put in some blocks and the light looks a little bit more realistic will notice that the performance has taken a little bit of a hit.
Here.
We've gone down to about 18 frames per second, and this is something to do with how the pixel game engine validates all of the pixels in D book mode.
If we now change from debug mode to release mode and run the same code, we can see the frame rate is a far more acceptable 102 100 francs for second on my machine.
Put in some obstacles.
Very nice.
The use of off screen buffers is a little bit angry into the things we've been doing on this channel, but it's a very common practice in all manner of computer graphics on the fact that we now work with pixels instead of chara