YT YouTube2Text

YouTube2Text → Transcripts → Line Of Sight or Shadow Casting in 2D

Line Of Sight or Shadow Casting in 2D — Transcript

by javidx9 · 9,250 words · 1,250 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:00hello in this video I'm going to be
0:03looking at quite a classic algorithm
0:04line-of-sight also known as shadow
0:06casting and as usual I'm going to start
0:09by showing you what it is that I'm
0:11talking about so here I have an arena
0:13where there is a boundary defined in
0:15blue and if I hold down my right mouse
0:17button I can smell shine a light in this
0:20arena and as I move the mouse around I
0:23can see that the light is following the
0:25mouse cursor this is all done in the
0:27pixel game engine by the way with the
0:29left mouse button I can draw shapes so
0:32I'm going to draw a boundary here and
0:35you can see it's sort of a a tile map
0:37array and the nice thing is now when I
0:39hold down the right mouse button and
0:40turn the light on we can see that the
0:42boundaries cast shadows well the cache
0:45shadows but they also indicate the
0:47locations that can't be seen from where
0:49the mouse cursor is so this is also
0:51line-of-sight and it behaves quite
0:54nicely I'll add in a few more features
1:01and see how it behaves and all of the
1:05features cast their own shadows in fact
1:12we can add lots and lots and lots of
1:14features you see some of them are little
1:20boundaries and walls we can extend
1:21things out got lots of interesting
1:22shapes it doesn't matter
1:24the algorithm can quite happily deal
1:26with any layout of tiles
1:34I'll make here at the bottom a small
1:37enclosure and the algorithm behaves as
1:41you might reasonably expect it to as we
1:43enter the enclosure visibility of the
1:45rest of the field is restricted to the
1:47doorway and in fact if we close off the
1:50doorway of course we can't see outside
1:52the little room line of sight is very
1:54useful in strategy games
1:56so here I've developed a little corridor
1:58and I'm going to push the agent through
2:00the corridor and we can see he can only
2:02see what's inside the corridor as he's
2:04moving around now I think that's a
2:09really cool algorithm and my
2:10implementation of it is one of several
2:12methods you can use so let's take a look
2:14at how it's done but before we get
2:16started this is my very first pixel game
2:19engine exclusive video so I'd like to
2:21spend some time just showing you how to
2:23set up a pixel game engine project using
2:25visual studio now I know that for many
2:28of you this is all old hat and you know
2:30what you're doing but you'll be
2:31surprised I get quite a few comments
2:32people saying they don't really know how
2:34to set up visual studio so please
2:35forgive the next couple of minutes
2:37whilst I do this when you start with
2:39your studio you'll be presented with the
2:40start page I recommend going to file new
2:43and selecting project in the list of
2:46projects you'll see one is called a
2:47Windows console application give the
2:50solution a name I'm going to call this
2:51one shadow casting 2d and press ok now
2:54visual studio this is the very latest
2:56version of visual studio we'll go ahead
2:58and create some files for you and it
3:01even gives you some hints as to what
3:02these files are for for my videos though
3:04I don't really want the file structure
3:06it provides the first thing I want to do
3:09is get rid of the PC H dot H file and
3:11the PC H CPP file so I select them and
3:14press Delete I don't want them I'm not
3:17going to use precompiled headers this
3:19also then means I have to get rid of the
3:21include PC H H from the main whilst
3:25method I'm going to get rid of all of
3:27these comments - we need to tell it that
3:29we don't want to use precompiled headers
3:30in our project so go to project
3:32properties and make sure we've got debug
3:34selected up here and expand the C and
3:37C++ option go to precompiled headers and
3:42in the tabloid says use precompiled
3:45headers we're going to say not using
3:47compiled headers and click apply whilst
3:50we're here you might also want to do the
3:51same thing for release now I know it's
3:57very controversial but the next thing I
3:58want to do is actually include the STD
4:02namespace and the only reason I do this
4:05is because it's easier to make videos
4:07that appear clearer best practice is not
4:10to do this we're creating a pixel game
4:12engine application so at this point you
4:15need probably need to go to the one line
4:16code at github and download the header
4:18file and here it is OLC pixel game
4:20engine dot h grab this file and copy it
4:24into the folder that you created when
4:25you created a new solution so on my
4:27machine this is the shadow casting 2d
4:29folder I've pasted the header file into
4:32this location I then want to include
4:34that file in my source code and now
4:42there is one last little thing that we
4:44need to do which was different from the
4:46console game engine and this is
4:47currently experimental so you may not
4:49always need to do this but right now
4:51it's something I'm trying out and that
4:53is before we include the pixel game
4:56engine file we need to define our
4:58application as being one uses the pixel
5:01game engine and we do that by doing hash
5:03define OLC underscore PGE underscore
5:07application and we need to do that
5:09before we include the header file and
5:11the reason that I'm taking this approach
5:14is that instead of having a separate
5:16object orientated version of the pixel
5:18game engine I'm trying just using a
5:20single header file which means we need
5:22somewhere in all of our compiled code an
5:24actual implementation of the pixel game
5:27engine and that will be wherever we have
5:29defined this constant LLC PGE
5:32application now as most of my videos are
5:34a single file solution I will just want
5:37to define this constant at the top of my
5:39main file next I want to override the
5:42OLC pixel game engine base class this is
5:44just the same as the console game engine
5:46and was shown in the OLC pixel game
5:48engine video so thanks for putting up
5:50with that I just needed a little bit of
5:51a video reference for the people that
5:53asked those questions so let's carry on
5:56now we've got the basic structure in
5:58place I'm going to create an object of
6:00type shadow cast
6:01and call the construct function and I
6:05want to construct a pixel game engine
6:07with resolution pretty high now 640 by
6:10480 where each pixel is 2 by 2 screen
6:13pixels and if that's successful then
6:17start the engine at this point you may
6:20want to do a test compile and run just
6:22to make sure everything set up correctly
6:23and we should see a black screen of the
6:26dimensions we've just specified very
6:29nice now this is a bit of a 2 for 1
6:31video because to implement shadow
6:33casting or line of sight we really need
6:35two algorithms I like the convenience of
6:38being able to draw the worlds in tiles
6:41placing blocks is quite intuitive as we
6:43saw with the Jerry Oh Pat forming game
6:45you could have a selection of blocks and
6:47place them wherever you want but the
6:49shadow casting algorithm itself relies
6:51heavily on geometry and if we have to do
6:54geometry for all of the blocks every
6:56single frame well I feel that that's not
6:58very efficient so the first stage of the
7:00algorithm is to convert our tile map of
7:03blocks into a polygon map of edges here
7:06I've drawn out an arbitrary section of
7:09level or world based on a tile map so we
7:12can see where I've placed the blocks
7:13where I haven't placed the blocks in the
7:15background this is very convenient as it
7:17makes life easy for the level developer
7:19it's easy to draw particular sprites in
7:21set locations we've done collisions with
7:23tile maps before there's lots of
7:25advantages to using a tile map but we
7:28don't want to use the geometry of every
7:29single block edge to cache shadows
7:31because at any given moment there's a
7:33lot of edges instead what we prefer to
7:37see is the boundary of the clusters of
7:40blocks so we're going to come up with an
7:41algorithm that will turn a cluster of
7:43blocks into a polygon we're going to
7:45find the bounding edge of this block now
7:47I can look at this block and intuitively
7:49say well we've got a vertex here and a
7:52vertex here a vertex here one here one
7:57here here here and here
8:04we also have four more vertices here and
8:08in principle what I'd like to do is link
8:10these vertices with lines
8:18and I think it's quite easy to see now
8:22that there are far fewer boundary lines
8:24than there are at block edges once you
8:27move out of the blocky world of the tile
8:29map into the smooth world of the polygon
8:31there are lots of other advantages we
8:34get as well we could implement realistic
8:36physics and collision detection we can
8:38have edges which don't align with the
8:40natural tile boundaries in the world and
8:42of course we can have natural-looking
8:44gradients and slopes I think we'll see a
8:46lot more of this algorithm popping up in
8:48future videos I want to construct these
8:51polygon boundaries in the most efficient
8:53way possible so ideally given a cutout
8:56of the larger world I want to scan
8:58through it want to create the set of
9:00edges and so that's exactly what I'm
9:03going to do and where to start from the
9:04top left and I'm going to scan
9:06horizontally across the screen and when
9:08I get to one end I'm going to come back
9:10to the start and scan the next row in
9:14this simplified example the structure
9:16that I have for a particular cell in the
9:19tile map is quite simple it either
9:21exists or it doesn't so in some sort of
9:23cell structure I know I'm going to have
9:26a boolean for exists but in order to
9:31implement my algorithm I'm going to need
9:32some additional information I'm going to
9:34add four more boolean's which tell me
9:38did the edges exist and these relate to
9:41the north south east and west edges and
9:45as we saw at the start a cell may share
9:49an edge with other cells this implies
9:52that any given cell can't actually own
9:54an edge instead it must use one that
9:57stored else were so I'm going to also
10:00include four integers which represent
10:03the ID of a given edge on the north
10:07south east or west side from some edge
10:10pool that will create else were so let's
10:14start manually going through the
10:15algorithm firstly we want to check does
10:18the cell we're currently inspecting
10:20exist because this cell doesn't exist
10:22this cell doesn't exist etc etc etc all
10:24the way along in our world until we get
10:26to why
10:27that does exist we only care about cells
10:30that exist so we're going to apply tests
10:33to this cell and the first test that
10:35we'll try from the perspective of this
10:38cell is do I have a Western neighbor
10:41well in this situation clearly I don't
10:43have a Western neighbor so I definitely
10:46have a western edge but where do I get
10:49this edge from well the only other place
10:52an edge could come from is from a
10:54northern neighbor that also has a
10:56western edge and in effect we'll take
10:59that edge and grow it downwards in this
11:02situation we don't have a northern
11:04neighbor so we're going to create a new
11:07edge and so we'll add to our edge pool
11:10edge a and in our cell structure we'll
11:14link our edge ID to the location of the
11:16edge in the edge pool we'll now
11:19systematically check the other sides of
11:21the tile firstly we'll check the eastern
11:23edge so if I have an Eastern neighbor
11:25which in this case I do then clearly
11:28that isn't an edge necessary between us
11:31we don't need to do anything further now
11:33we need to check our northern neighbor
11:35well I don't have a northern neighbor in
11:38this case so I do need an edge but where
11:41can I get one from well I can either get
11:43one from my western neighbor or I need
11:46to create one of my own and since I
11:48don't have a western neighbor I'm going
11:49to have to create one of my own so we'll
11:51create a new edge called B and we'll
11:54give the ID of that edge to the cell
11:56also drawing the a edge there as you can
11:59probably tell already it's a similar
12:01situation for this southern edge - we're
12:03going to need to create one for this
12:05cell see now we're traversing from top
12:08left to bottom right so this is the next
12:10cell that we check and we run through
12:12exactly the same routine do I have a
12:14Western neighbor well I do so I don't
12:17need a western edge
12:18do I have an Eastern neighbor well again
12:21I do
12:21I don't need an Eastern edge do I have a
12:23northern neighbor no I don't so I do
12:26need an edge but this time rather than
12:28creating one for myself what I can see
12:31is that my Western neighbor currently
12:33already has a northern edge so I'm going
12:37to extend that edge to suit my needs
12:41set my edge ID as well the final check
12:43is do I have a southern neighbor well I
12:46don't so I do need an edge and you've
12:48probably already guessed I'm going to
12:49grow my Western neighbors edge as well
12:51and set my cells edge ID on the southern
12:55boundary to suits that particular edge
12:57exactly the same routine occurs for the
13:00next cell so let's run through it again
13:02for this corner cell well
13:05we check do I have a Western neighbor I
13:08do so I don't need an edge
13:11do I have an Eastern neighbor I don't in
13:14this case so I do need an edge now I
13:17can't borrow one from my northern
13:19neighbor so I'll have to create one D
13:22and I'll add that edge to the edge pool
13:25and set my ID now we check for northern
13:28neighbors and just as we've done with
13:29the previous cells I don't have a
13:30northern neighbor so I do need a
13:32northern edge but fortunately my Western
13:34neighbor has got one I can borrow so I
13:37will extend that edge and set my ID
13:39accordingly now for southern neighbors
13:41this is the first time we check for
13:42southern and I've got a southern
13:44neighbor so I don't need an edge between
13:46myself and my southern neighbor which
13:48means I no longer need to extend the
13:51edge C horizontally in fact it's very
13:54likely we'll never need to do anything
13:55with C again but we don't have to touch
13:57it it's in the edge pool it's got to
13:59start at an end point it's done so we'll
14:02move on the next cell it exists is this
14:04standalone cell here it doesn't have any
14:07neighbors so the consequence of this is
14:10is going to add four new edges to the
14:12edge pool a western edge an eastern edge
14:15a northern edge and a southern edge e F
14:20G and H I'll just set the edge IDs four
14:25five six and seven so the worst case
14:28scenario is a map made up of lots of
14:31individual blocks let's carry on testing
14:34but I'm not going to go in as much
14:35detail now the next block tested is this
14:37one that does exist well this one needs
14:39a new western edge which is I now that's
14:42where up to but it can borrow from its
14:44northern neighbor its eastern edge and
14:48I'll just carry the algorithm along now
14:49for the rest of the shape
15:15once we've gone through all of the tiles
15:16were interested in we'll have an edge
15:18pool that contains only the bounding
15:20edges of the shapes and the edges are
15:23defined by a start and an end coordinate
15:26it's very possible that edges will share
15:28a coordinate but needless to say we've
15:30converted our tile map into a set of
15:33edges not strictly a polygon because
15:36we've not defined what's the inside and
15:38the outside of the polygon but we can
15:40assume that things don't pass through
15:42edges in our application so I think our
15:45first step in code is to implement this
15:47algorithm now I've gone through it in
15:48quite some detail here I'm not going to
15:50go through this same detail in the code
15:52so we'll do some cut and pasting I will
15:54need some basic structures to assist us
15:56the first thing I'll need is an edge
15:57which stores the x and y components of
16:00its start and end points and my world is
16:03going to be made up of an array of cells
16:05so this is my cell and I've included in
16:08it boolean Flags where does the cell
16:09exist or not and does it have an edge
16:12that exists on all four sides and what
16:15is the edge ID into the pool of edges
16:18and just to make the algorithm a little
16:20clearer to follow I'm going to define
16:21some constants for north south east and
16:23west our world is going to be a 2d array
16:27of cells the world will be defined by
16:30two variables world width and will
16:32height in this case I've chosen 40 and
16:3430 because if I assume a block size of
16:3716 by 16 pixels that lines up very
16:40nicely with our 640 by 480 resolution so
16:43essentially the world is a single screen
16:45that we can see in on user create I'm
16:48going to allocate the memory that holds
16:49our world adding code to place blocks in
16:52the world is quite simple because we're
16:54using the pixel game engine first I'm
16:56going to define the width of the block
16:58just in case we do want to change things
17:00later on and I'm going to grab a quick
17:02snapshot of the mouse coordinates it's
17:04important to do this because the mouse
17:06coordinates can technically change
17:08whilst this function is executing so
17:10grabbing them right at the staff means
17:12that we're going to have consistency
17:14through the code to check if the user
17:16has pressed the left mouse button or
17:18clicked we can call the get Mouse
17:20function on item 0 that's the left mouse
17:22button and we're going to check to see
17:24has it been released this frame if it
17:26has been released we're going to get to
17:28the in debt
17:28of the cell that it has been clicked in
17:31now this looks horrendous but it's
17:33actually quite a simple bit of code we
17:34take our input mouse coordinates and we
17:37do an integer divide with the block
17:39width so this will tell us how many
17:41blocks down the screen is the mouse
17:43cursor we do the same thing for the
17:45x-axis we take the X mouse corners and
17:48we also divide that by block width and
17:49that tells us how far across the screen
17:51is the mouse cursor in tiles effectively
17:54and this is something we've seen many
17:56many times now I equals a y-coordinate
17:59times the width of the array plus X
18:02which converts our 2d X&Y coordinates
18:06into a 1d coordinate in the array once
18:09we know the index we can toggle the
18:10exist flag for the cell at that location
18:13staying in unusual update what I'm going
18:15to move it down a bit will do the
18:17drawing code and the first thing I want
18:19to do is clear the screen to all black
18:22and now I want to draw the blocks from
18:24the tile map and to do this I'm going to
18:26iterate through them all and simply
18:28check if they exist or not and if they
18:31do exist I'm going to draw a filled in
18:33rectangle at that location so this is
18:35code versing back from block space into
18:37screen space now with a width and height
18:39set to the block width and I'm going to
18:41draw the rectangle as blue let's take a
18:44look so here got the screen with the
18:51mouse cursor on and if I click wherever
18:53I click I place a blue block and if I
18:57select a blue block and click it it gets
18:59rid of it we're basically toggling does
19:01the block exist at that location or not
19:04now we can worry about turning the tile
19:06map into a pool of edges and the
19:09container I'm going to use for this is a
19:11vector called BEC edges and because I
19:14know that doing this type of conversion
19:17is going to be incredibly useful for
19:19future videos I'm going to create a
19:21function that explicitly does this it
19:23converts a binary tile map into what I'm
19:26calling the poly map ie it's going to
19:28populate this vector with all of the
19:30edge information given a particular
19:32region of a tile map so the parameters
19:35of this function are a starting x and
19:37y-coordinate the width and height of the
19:40rectangle
19:40of tiles of which I wish to inspect and
19:43turn into edges and also going to pass
19:45in the block width parameter so we know
19:47where our edges exist in actual space
19:49and then the cysts a strange parameter
19:51called pitch which is going to be set to
19:53end world width but I'm leaving it as
19:55pitch because we want to be able to use
19:57it on arbitrary size maps going forward
19:59so I'm using the phrase poly map it's a
20:02little bit made-up and the first thing I
20:03want this function to do is to clear all
20:06of the information associated with
20:09constructing this map naturally I want
20:11to just clear the vector of edges first
20:13but then during the construction of
20:16creating this vector we're populating
20:18the cells with additional information I
20:21need to reset that information
20:23effectively back to zero so I'm
20:25iterating through all of the cells in
20:26the region of interest that I'm
20:28converting and for each cell I'm setting
20:30that it has no edges at all and it's not
20:33got any edges in the pool again here we
20:35see Y times width plus X once we've
20:39cleared our map it's time to start
20:41applying our algorithm and I'll do this
20:43by creating two for loops x and y and
20:46iterating through the region of interest
20:48now you'll notice here I'm actually
20:50iterating from one - with - one of the
20:53region of interest and that's simply
20:55because I don't want to have any
20:56out-of-bounds memory errors when I'm
20:58checking along the edges of the 2d array
21:01I can get away with that for this
21:03demonstration but going forward I'll
21:05probably want to tighten that up a
21:06little bit to accommodate genuine array
21:09boundaries now to stop things getting
21:11out of control I'm going to create some
21:13indices which are more convenient to use
21:16so the eye index will be the current
21:19cell index in the array we can look at
21:22our northern neighbor is the current
21:23cell but up one in the Y direction and
21:26our Eastern neighbor is the current self
21:28plus one in the X direction first let's
21:31check if the cell exists or not if it
21:34does exist we'll check to see does it
21:36have a Western neighbor because if it
21:38doesn't have a western neighbor then it
21:39needs a western edge one of the places
21:42we can get a western edge from is our
21:44northern neighbor by extending it
21:45downwards so let's see if our northern
21:47neighbor does that have a western edge
21:50if it does we'll extend it and we can
21:53extend it by
21:54looking at our northern neighbors
21:56western edge ID and using that ID to
22:00index into our edge pool so we can find
22:02which edge is on the western side of our
22:05northern neighbor and we know that we're
22:07going to grow downwards so we want to
22:09extend the end coordinate of that edge
22:12by one block width down which is what
22:15this line does so in our pool of edges
22:18we're looking at our northern neighbors
22:21western edge ID to get to the edge that
22:24is relevant to us we're taking the end
22:27y-coordinate because we're going to
22:28extend in the y-axis downwards and we're
22:30increasing that coordinate by the height
22:32of one of our blocks just so happens
22:34that our blocks are square
22:35since we're borrowing an edge that
22:37already exists we'll set the edge ID of
22:40our current cells western edge to be the
22:43same as our northern neighbors western
22:45edge and since the edge exists we'll set
22:48that to true now if I didn't have a
22:50northern neighbor I still need an edge
22:52from somewhere so I'll need to create
22:54one who creates a new edge object and we
22:56can use the position we are in the array
22:58and the block width variable to work out
23:01where we are in real space so we can set
23:03the start coordinate of our edge X&Y
23:06here using the array coordinates
23:08multiplied by the block width and we
23:11know at the moment that our edge is
23:13going to be at least one block tall so
23:15we can specify that two will add to the
23:17edge to our edge pool simply by pushing
23:20it into the vector and since we've
23:21created a new edge as we did up here we
23:24need to now set the ID and whether the
23:26edge exists or not for this cell well
23:29it's a new edge ID and we've used the
23:31location of it in the vector to specify
23:33that ID and so that is all of the code
23:35required to work out whether we should
23:37create a new western edge or borrow from
23:40our northern neighbors we now need very
23:42similar code for the other four edges
23:44and I'm not going to talk through it all
23:46I'm going to cut and paste it in but
23:48it's very very similar we just need to
23:50be careful of what we're doing when
23:51we're constructing the new edge so even
23:54though I appreciate that seems like a
23:55really large amount of code to put it in
23:57one go I hope you can appreciate that
23:59it's actually very similar to the one
24:01that we've just done you can probably
24:03tell that I'm going a little bit faster
24:05than usual on this video
24:07because there are two parts of the
24:09algorithm that I want to include but I
24:10don't want the video to become an hour
24:12long now we can go back to our own user
24:14update function and actually call our
24:17new function to create the poly map and
24:19here I am calling it and I'm giving it
24:21the region of interest that I wish for
24:23it to convert which in this case is the
24:25whole array and I specify the block
24:27width coordinate so the edges can be
24:29done to the right scale and I specify
24:31the pitch to be the width of the world
24:33which is actually the same as the value
24:35I'm using here because coincidentally
24:37the whole world is represented by the
24:38single screen I can see I think it'll be
24:41quite nice to visualize the edges to
24:43help us with some debugging and to make
24:44sure that everything is working
24:45accordingly so after we've drawn the
24:48blocks and I'm going to create a little
24:49Auto for loop to iterate through all of
24:52the edges in our vector of edges and
24:54I'll use the draw line function to draw
24:57a white line from the starting
24:58coordinates the ending coordinate of the
25:00edge but to make the ends of the edge a
25:03little bit more visible I'm going to
25:04draw a red filled in circle at each end
25:07most of the center of the circle this is
25:09the radius and this is the color let's
25:11take a look so is my blank screen and
25:17I'm going to place a block very nicely
25:19we can see we've got at least four edges
25:21there if I place a block next to it we
25:25can see it's not drawing any more ends
25:26of edges it's just drawing the edge so
25:28it does look like in that direction the
25:30algorithm is working just fine
25:32if we branch off from here we can see
25:37that seems okay too
25:38let's go off the top very nice
25:46if I've inadvertently drawn some
25:49offensive simple here I do apologize but
25:51I'm just randomly clicking where I need
25:54to click I think what's probably also
25:57worth Jacky is solid object so it
25:59doesn't necessarily have to be a wall
26:01one tile thick it does seem to work for
26:06that to that we can punch a hole in the
26:10middle of this solid so I'm reasonably
26:12confident that we have taken the tile
26:14map and we have reduced it into some
26:16geometric primitives which might be more
26:18useful for doing more complicated
26:20geometric maths now that's very nice and
26:23the performance seems quite reasonable
26:24too especially given I'm doing this
26:27every single frame that I'm rendering
26:29and in most cases you probably wouldn't
26:31need to do that you'd only need to
26:32regenerate the poly map if the tile map
26:35changes and in some situations it could
26:37be a completely offline precompilation
26:39step of how your level data is stored so
26:42all in all I think this is a very useful
26:44routine to have right so let's start
26:47thinking about the shadow casting and
26:48the line of sight bit here I've got a
26:51location of the source of the light or
26:54where the player stands or whatever it
26:55is we're going to project rays from this
26:58source radially out into the scene now
27:01I've covered casting rays before in fact
27:03in one of my very first videos the
27:05first-person shooter the command line
27:06engine we can cast rays in all angular
27:09directions and see what they hit so here
27:13we go cast out some rays not very
27:18straight razor might have but when they
27:20intersect with something in the scene
27:22the Ray length is shorter and anything
27:25that followed that ray length past the
27:27intersection point is technically in
27:30shadow and finally this one is also in
27:33shadow and I'm sure you can envisage
27:35your scenario where we keep doing this
27:37all the way around the scene but this is
27:40really computationally inefficient and
27:43in fact we can look at this and derive
27:46from it that we're only interested in
27:48rays that intersect with our line
27:50segments even more so we're only
27:52interested in rays that seemed to
27:54intersect with the cornice so let's
27:56explore that for a moment for each edge
27:58in
27:58the edge cool I'm going to project array
28:01to the start and end point so in this
28:04case I've effectively got four rays when
28:07the Ray intersects with the line we know
28:10the Ray effectively starts turning into
28:12shadow well let's consider not looking
28:15at areas which are in shadow but instead
28:17which areas are in light the second ray
28:20down was defined by this coordinate but
28:23we can see that it had to intersect with
28:25another edge on its way there and so
28:28we'll record the intersection point that
28:31is closest to the source of the array
28:33and we'll do that for all four rays cast
28:36out and in fact let's do the same for
28:39all rays for the other object too so we
28:41cast rays to each of the vertices
28:43defined by the edges of the other object
28:52drawing the intersection points that are
28:55closest along that Ray if I add in one
28:59more point which is the source what I'm
29:03actually constructed is a fan of
29:05triangles there's one triangle next
29:10triangle and these triangles construct a
29:13polygon which covers the area that is
29:16definitely visible from the source the
29:20problem is it's a bit of a strange
29:21polygon because if I shaded in this
29:24polygon with light we can see there's
29:32some big gaps which are definitely
29:35visible but they've been ignored by the
29:37algorithm what can we do about these big
29:40gaps then well there's a little hack
29:42that we can apply instead of casting one
29:45ray from the source to a vertex we cast
29:49three rays one goes directly to it and
29:52we have one either side displaced by a
29:56tiny fraction an angle so it'll miss the
29:58vertex in this case on that side and on
30:02this side well it'll just hit the line
30:04as it normally does so three rays one is
30:08it theta and one is it theta plus or
30:11minus some
30:12tiny little amount these additional ways
30:15will affect our image here in the
30:17following way so we'll have one of the
30:20rays will continue going until it hits
30:22something else or it hits the boundary
30:24of the world as will this one and this
30:27one and this one our intersection points
30:30are also recorded and now when we draw
30:33the triangle fan formed by these points
30:36there's a lot more area to fill in in
30:40fact it turns out that it's all of the
30:42visible area from the source
30:52and this is why these two algorithms are
30:54interchangeable because the lit up area
30:58is the line of sight it's all the areas
30:59that can be seen and the areas that
31:02can't be seen must be in shadow so we
31:04have cast shadows I'll start researching
31:06into this topic I found two brilliant
31:09websites you must go and have a look at
31:11the make outline these algorithms in
31:13quite some detail have lots of
31:14interactive demos you can play with too
31:16I will of course link to these websites
31:18in the text below the first one allows
31:20you to place a light source which like
31:22the demo that we're building and you can
31:24see it has a degree of complexity to it
31:26but it's quite nice because it talks to
31:28all of the different stages that you
31:29might go through when developing this
31:31algorithm this is the second one and
31:33again a really nice site full of nice
31:35toys to play with and some code too and
31:39you can see again you can interact just
31:42as we're doing with edges and shapes and
31:43seeing where the Rays get cast in fact
31:45it was this website that gave me the
31:47idea of casting out additional rays for
31:50the corners please take the time to
31:52check out these sites I think it's a
31:54wonderful thing that experienced
31:55developers are taking the time and
31:57putting the effort into actually doing
31:58tutorials like this with interactive
32:00elements it's a lot of work and yet
32:02yield so much so check them out the
32:04links are in the description below so
32:06going back to our application we know
32:08that for each edge end we're going to
32:10send out three rays and we're going to
32:12form some triangles from the
32:13intersection points of those rays with
32:15the edges I'm going to start by creating
32:19another function to encapsulate the
32:21calculation of our visibility polygon
32:23there's going to be a set of points that
32:25represents the visible space from a
32:28source location defined by Oh X and Oh Y
32:30over a given radius but I'm going to use
32:33a little bit of modern C to help me out
32:35here I'm going to store the points of
32:38this polygon as a vector of tuples of
32:41floats and you'll notice there are three
32:44floats the first float is going to
32:47represent the angle from the source of
32:50the vertex that were targeting with the
32:52Ray and the second two floats are the
32:55X&Y location of that vertex we need to
32:59store the angle because without it we
33:00won't be able to draw sensible triangles
33:03in the fan later on since we're going to
33:05iterate through
33:06our vector of edges to work out the
33:08coordinates of to where we should cast
33:10rays this could theoretically happen in
33:13any sort of order which means when I
33:15come to draw these triangles later on I
33:17can't do it sensibly I effectively need
33:20to draw these points in some rotational
33:23order and so the easiest way to do that
33:25is not just to store the point on its
33:27own but take an arbitrary axis from our
33:31source point and record the theta values
33:34of each of the points so for each point
33:40I'll have a theta and an x and a y I can
33:43then sort these points based on the
33:46theta value to make sure that they're in
33:48this clockwise order if you've not seen
33:51a tuple before it's just a simple way to
33:53group things together it's a bit like a
33:56struct but it's very compatible with the
33:59standard library so as we did before
34:00with the edges the first thing I want to
34:02do with my visibility polygon is to
34:04clear it and then we know that we need
34:06to do something for each edge in our
34:08vector of edges so little also for loop
34:11to iterate through all of the edges now
34:13an edge consists of two points the start
34:16and the end so for each edge we're going
34:18to have to cast at least two Ray's
34:20directly to hit the start and end points
34:22since I need the angle of the Ray I'm
34:25going to start by first calculating the
34:26gradient of the Ray they're depending on
34:28whether we're at the start or the end so
34:30I've used the ternary operator here to
34:32select between the start point or the
34:34end point and I'm subtracting from that
34:35the source location
34:37Oh XR know why giving me two variables
34:39are DX and our dy which represents the
34:41Ray vector now I'm not bothered what our
34:44angle is relative to as long as it's
34:46consistent so I'm just going to create
34:48another variable base angle and use the
34:50atan2 function using the RDX in our dy
34:54values so this gives us an angle of our
34:57ray vector and we know that for each ray
34:59actually we're going to cast three
35:01additional Ray's with a slight deviation
35:03between the two so I'll create a
35:05temporary variable called angle which is
35:07going to be the angle we will shoot the
35:08ray at so I'll add another for loop to
35:11generate the three additional race we're
35:13going to need and depending on the value
35:15J in the for loop we're going to choose
35:17an appropriate angle to
35:19the Rae out - so in effect we've gone
35:22back on ourselves a little bit here
35:23we've calculated the gradient of the Ray
35:25so we can work out what the angle is and
35:27then we're using the angle plus or minus
35:30a little bit of deviance to generate the
35:33vector of the Ray again which we can
35:35easily do taking the cosine and sine of
35:37the angle will only cast the Ray as long
35:39as we've specified the radius value to
35:42be as you can probably see the number of
35:43rays were actually projecting into the
35:45scene is growing and the more
35:47complicated our scene is with tiles the
35:49more graves were going to cast out
35:51however the one thing we're guaranteed
35:53is that our strategy is more optimal
35:54than casting rays out in all directions
35:56and seeing what happens at least our
35:58rays are guided intelligently to at
36:01least some features within the world and
36:03this is where the really chewy part of
36:05the algorithm comes because for every
36:07single ray we now need to check for
36:09intersection between the Ray and all of
36:12the edges in the scene the algorithm has
36:14now come down to a simple line segment
36:16intersection test so we can take two
36:18line segments and we want to work out
36:20the point at which they intersect and
36:22one way to think about this is to take a
36:25known point on each line represent the
36:28line segment as a vector therefore the
36:31opposing point becomes the existing
36:33point Plus that vector and we can add in
36:36here a parameter T 1 and T 2 because if
36:42T 1 is equal to 1 where at this end of
36:45the line and if T 1 is equal to 0 where
36:48at this end of the line and so we'll
36:50find where our intersection point is by
36:52looking at the T values and since we're
36:55talking about line segment intersections
36:57go and find the line segment
36:58intersection algorithm of your choice I
37:01personally like this one which I
37:03discovered on Stack Overflow the answer
37:05here is actually a code implementation
37:06of the answer above I'll put a link in
37:10the description below before we can
37:12calculate the intersection we need some
37:13additional information the first of
37:15which is we need the vector that
37:16represents the edge which is easy to
37:18calculate because it's just one end of
37:20the edge subtracted from the other we'll
37:22also need to make sure that the Ray
37:24isn't going to be collinear with the
37:26edge ie it's not going to lie on top of
37:28it so I'll check for that by just
37:29looking at the values of the vector
37:32component
37:33and making sure that they're
37:34sufficiently different for example if
37:36both had a dy of zero then both the Ray
37:39and the edge could be horizontal there's
37:41a chance they could overlap and there
37:42isn't a single solution point that
37:44represents the point of intersection now
37:46we can calculate the t1 and t2 values
37:49using the line segment intersection
37:51point algorithm and in this instance t1
37:54is the distance along the Ray and t2 is
37:57the distance along the edge and so if t1
37:59is positive that means we're traveling
38:01along the Ray in the correct direction
38:02and if t2 lies between 0 & 1
38:05then we've definitely hit a line segment
38:08now that we know we've got an
38:09intersection point what do we do well
38:12we're only interested in the
38:13intersection point which is closest to
38:15the source point even though we've
38:18detected intersections along many edges
38:20we want to reject most of them and only
38:22retain the one that is closest to the
38:24source and our t1 value represents that
38:27information we don't need to do
38:28Pythagoras theorem here to calculate the
38:30distance because t1 indicates the length
38:32along the Ray and so for each Ray that I
38:35cast I'm going to store some temporary
38:37variables that represents the minimum t1
38:39distance and I'm also going to store the
38:41X&Y of the intersection point at that
38:44distance I'll set it to infinity for
38:46each way to start but if the t1 that
38:48represents the intersection point of the
38:50Ray of just tested is less than our
38:52current closest intersection point I'm
38:55going to replace it and I'm also going
38:57to calculate the new intersection point
38:59and angle of course now for all of my
39:02rays
39:03once I've calculated where the Ray ends
39:05I'm going to add that location to my
39:07vector of visible polygon points our
39:10calculate visibility polygon has not
39:12quite finished yet because right now
39:14we've got a vector full of points in any
39:17particular order and so I need to sort
39:19them based upon the angle fortunately
39:22the standard library can provide a nice
39:23simple routine to do this for us it
39:25provides a sort as part of algorithm and
39:28so I'll call the sort routine giving it
39:31the start location of my vector and the
39:33end location of the vector but I'll pass
39:35in as the sorting criteria a small
39:38lambda function and it's going to sort
39:39based upon the angle so the two
39:41arguments going into the lambda function
39:43are references to the two tuples and
39:45we're only interested in
39:47the first element of the topple which is
39:49the angle so we're going to return true
39:51if the angle of the topple on the left
39:53is less than the angle of the topple on
39:54the right and this will sort it in
39:56ascending order every frame I wanted to
39:58convert our tile map to a poly map but I
40:00don't want it to calculate the
40:02visibility polygon every single frame
40:04I'm only going to do that when I'm
40:05holding down the right mouse button I
40:07also only want to draw anything relating
40:10to visibility under the same conditions
40:12so we were to check that the mouse
40:13button is held but I'm also going to
40:15check that the vector of points that
40:16we're going to draw at least has
40:18something in it and so now I want to
40:20draw my triangle fan this is quite easy
40:23now we've got a vector of sorted
40:25visibility points I'm going to go from
40:27the start of the vector to almost the
40:30end of it and I'll use the fill triangle
40:32routine to draw a triangle from the
40:34origin point the source where the mouse
40:36is to the X&Y points of two successive
40:40visible points in our polygon vector so
40:42this will form a triangle what I mustn't
40:45forget to do is also close the triangle
40:47at the end so we want to draw from the
40:50final point to the starting point this
40:53will have to sit outside the loop let's
40:55take a look well let's try with nothing
40:59in I'm right clicking I don't see
41:00anything let's add some obstacles oh
41:04well it looks like a complete or not a
41:07mess well it's a bitter kind of working
41:10but something's not right and the
41:15problem here is work with information
41:17starved were only casting out Ray's
41:19wherever we've got information in the
41:21scene so if I put in lots and lots and
41:24lots of points for it to reference from
41:27it starts to look a bit more sensible
41:31there's still some horrible glitches
41:34though particularly what is this
41:36triangle going up towards zero in the
41:39top left
41:40well this spurious triangle is because
41:42we've assumed that all of our rays will
41:45effectively intersect with something and
41:47this might not necessarily be the case
41:50particularly when we have raised which
41:52we've adjusted by a slight angle so we
41:54can limit the Rays that are added to the
41:56vector of polygon points by assuming
41:58they're only valid if they have in fact
42:00hit something so lonely at them if this
42:03be valid variable is set to true and
42:05that's only set to true if we have had
42:07some sort of collision along the length
42:09of the Ray so let's take a look again at
42:14some points in and I'll draw at least
42:17now we've not got a problem going up
42:18towards zero but things are still
42:20looking a bit information starved in
42:23fact if I now put in lots and lots of
42:25points as a boundary
42:26I see how it looks then and now it's
42:31starting to look a lot more realistic so
42:34what this is telling me is that our rays
42:36that don't intersect with anything need
42:38to intersect with something we're going
42:39to have to put in an artificial boundary
42:41now I could do that in our ray code what
42:44I'm going to do instead is just hard
42:46code into some boundaries into our tile
42:49map array so in on user create where
42:52I've just created the world I'm going to
42:54add in a couple of for loops which draw
42:56some parallel horizontal and vertical
42:58cells into the world let's take a look
43:02now we can see the boundary has been put
43:07in I'm now illuminating everything is
43:10lit up put in some obstacles and very
43:14nice our Rays have somewhere to stop now
43:17and that was what was necessary in order
43:18to make this look smooth and work if we
43:24just quickly change our fill triangles
43:27to draw triangles now we can see the
43:30individual polygons making up the
43:32polygon fan around the point from which
43:34we're checking for visibility I'm
43:38curious about the number of rays being
43:40cast so I'm going to capture that
43:41information and display
43:43I'll just quickly use the draw string
43:45function to display this information to
43:47the user so no rays being cast and right
43:54now a hundred and sixty eight Ray's
43:55being cast four am fully minimal number
43:58of objects that we take out a bunch and
44:02now cast 72 rays even though we've got 1
44:052 3 4 5 6 7 8 9 10 11 12 known vertices
44:09in the scene this is because we've got
44:12duplication of vs.
44:14fortunately the standard library can
44:16help us out here - since our vector of
44:19visibility polygons points is sorted we
44:22can use the unique operator to remove
44:26any duplicates why do we need to draw to
44:29the same point multiple times and so
44:31we'll do a before and after comparison
44:34here is the unique function being called
44:37again it's part of algorithm and I've
44:39passed in a lambda function again which
44:41compares the tuples but this time it's
44:44saying please reject this particular
44:46topple if the x and y coordinates are
44:49similar in this case I've said less than
44:51naught point 1 so I'll create a second
44:54variable ray cast 2 and compare them so
44:59just a little recap we've used the
45:01unique function to remove all of the
45:03duplicates in our sorted vector it
45:06doesn't actually remove anything the
45:08unique function it just reorganizes the
45:10vector so that all of the unique stuff
45:11is at the start so anything after the
45:14point returned by the unique function we
45:16want to remove and therefore I'm
45:18resizing the vector based upon the
45:20distance from the start of the vector to
45:22that unique point I'll now draw how many
45:25rays were actually cast versus how many
45:27rays were actually drawing on the screen
45:29let's take a look so in a blank
45:35environment we're casting 48 rays for
45:38the number of rays that were drawing is
45:39changing between well 10 and 13 a little
45:43bit of fluctuation and that's because it
45:44depends if we look at the top right
45:46corner here we can see a bunch of rays
45:48but at certain angles the Rays overlap
45:51each other there's absolutely no point
45:53in drawing triangles that we can't see
45:55so let's add in a few obstacles and of
45:58course we'll expect the number of rays
45:59to increase or casting 192 rays but now
46:02we're only drawing about 50 rays I think
46:05this is quite a significant optimization
46:07to make lots of features 840 rays cast
46:11and we're drawing well about 25% of them
46:16I'm going to fill in the triangles again
46:17now and so we can see we've got quite a
46:20robust line of sight or shadow casting
46:22algorithm implement it now at the start
46:25of this video I made it look a little
46:26bit
46:27more special because I used a sprite of
46:29a light sauce and modulated where it is
46:32white here with that sprite so this is a
46:35bit of pixel game engine trickery now in
46:38Photoshop I have created a sprite that
46:40represents a light source emanating out
46:43from a central point it's a PNG file I'm
46:46going to load the sprite into the pixel
46:48game engine and I'll do that in on user
46:50create I'm now going to do something a
46:52little bit novel for this channel I'm
46:54going to do some off-screen rendering
46:56I'm going to create two additional
46:57sprites called buffer light ray and
47:01buffer light Tex and these are going to
47:03be surfaces to which I'm going to do
47:05some post-processing but I need to
47:07create these in on user create you'll
47:09see I'm not loading a file I'm just
47:11giving them a dimension they're
47:12basically going to be an image buffer to
47:14which I'll draw things and then modify
47:16the pixel game engine supports rendering
47:19to different targets by default it
47:21renders to what you can see on the
47:23screen and we can specify the draw
47:25target by calling the set draw target
47:27function and by specifying null pointer
47:30is the argument that means there isn't
47:31any off-screen draw targets draw to the
47:34main target which is the screen so we
47:36want to do that before we clear
47:37everything to black and any subsequent
47:40drawing calls so in this case drawing
47:42the string those calls will be
47:44redirected to whatever the draw target
47:46is I'm going to use the off-screen
47:48buffers to implement a nice lighting
47:50effect the first thing I want to do is
47:53draw my radial light sprite into the
47:56correct location in the buffer and so
47:58I've specified the target buffer I've
48:00erased it to black and now I'm going to
48:03draw the sprite into the correct
48:05location which happens to be my mouse
48:06cursor now the center of my sprite
48:08because the sprite is 512 by 512 needs
48:11to be offset accordingly I'm then going
48:13to render to the second off-screen
48:15buffer the light rays so I'll clear the
48:18buffer to blank first and all of the
48:20fill triangle routines will now be
48:22targeted at that buffer I want to
48:24combine these two buffers to draw to the
48:27screen and because we're drawing to the
48:29screen now I set the draw target to null
48:31and I don't have any additive or special
48:33blending mode yet in the pixel game
48:35engine so I'm going to iterate through
48:37each pixel in my off-screen buffer and
48:40I'm going to check
48:41if each pixel has been set remember we
48:43cleared it all to blank to begin with so
48:45if it's been set by one of the light
48:47rays it'll no longer be blank and if
48:50that's the case I want to draw in the
48:53current screen location X&Y the pixel of
48:57my light cast sprite in the
48:59corresponding location let's take a look
49:02so I can see my sprite has now been
49:04drawn wherever my mouse cursor is put in
49:09some blocks and the light looks a little
49:13bit more realistic well notice that the
49:15performance has taken a little bit of a
49:17hit here we've gone down to about 18
49:19frames per second and this is something
49:21to do with how the pixel game engine
49:23validates all of the pixels in debug
49:26mode if we now change from debug mode to
49:29release mode and run the same code we
49:34can see the frame rate is a far more
49:37acceptable a hundred 200 frames per
49:39second on my machine let's put in some
49:41obstacles very nice
49:46the use of off-screen buffers is a
49:49little bit eglee into the things we've
49:50been doing on this channel but it's a
49:52very common practice in all manner of
49:54computer graphics and the fact that we
49:56now work with pixels instead of
49:57characters allows us to do some higher
49:59fidelity effects and I quite like it if
50:02you've enjoyed this video firstly please
50:04check out some of the links to the
50:05resources I've used in this video
50:07they're in the description below the
50:09source code for this algorithm and the
50:11pixel game engine is also linked and
50:12that's available on the github come and
50:14have a chat on the disk guard give you a
50:16big thumbs up and don't have a think
50:18about subscribing I'll see you next time
50:19take care

About this transcript

This page contains the full transcript of Line Of Sight or Shadow Casting in 2D by javidx9, generated from the public captions YouTube serves with the video. The transcript has 9,250 words across 1,250 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.