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.