Line Of Sight or Shadow Casting in 2D

hello in this video I'm going to be looking at quite a classic algorithm line-of-sight also known as 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 is a boundary defined in blue and if I hold down my right mouse button I can smell shine a light in this arena and as I move the mouse around I can see that the light is following the mouse cursor this is all done in the pixel game engine 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 sort of a a tile map array and the nice thing is now when I hold down the right mouse button and turn the light on we can see that the boundaries cast shadows well the cache shadows but they also indicate the locations that can't be seen from where the mouse cursor is so this is also line-of-sight and it behaves quite nicely I'll add 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 you see some of them are little boundaries and walls we can extend things out got 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 as 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 and I'm going to push the agent through the corridor and we can see he can only see what's inside the corridor as he's moving around now I think that's a really cool algorithm and 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 you 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 set up visual studio so please forgive the next couple of minutes whilst I do this when you start with your studio you'll be presented with the start page I recommend going to file new and selecting project in the list of projects you'll see one is called a Windows console application give the solution a name I'm going to call this one shadow casting 2d and press ok now visual studio this is the very latest version of visual studio we'll go ahead and create some files for you and it even gives you some hints as to what these files are for 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 PC H dot H file and the PC H CPP file so I select them and press Delete I don't want them I'm not going to use precompiled headers this also then means I have to get rid of the include PC H H from the main whilst method I'm going to get rid of all of these comments - we need to tell it that we don't want to use precompiled headers in our project so go to project properties and make sure we've got debug selected up here and expand the C and C++ option go to precompiled headers and in the tabloid says use precompiled headers we're going to say not using compiled headers and click apply whilst we'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 namespace 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 need probably need to go to the one line code at github and download the header file and here it is OLC pixel game engine dot h grab this file and copy it into the folder that you created when you created a new solution so on my machine this is the shadow casting 2d folder I've pasted the header file into this location I then 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 and 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 OLC underscore PGE underscore application and we need to do that before we include the header file and the reason that I'm taking this approach is that instead of having a separate object orientated version of the pixel game engine I'm trying just using a single header file which means we need somewhere in all of our compiled code an actual implementation of the pixel game engine and that will be wherever we have defined this constant LLC PGE application now as most of my videos are a 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 base class this is just the same as the console 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 asked 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 cast and call the construct function and I want to construct a pixel game engine with resolution pretty high now 640 by 480 where each pixel is 2 by 2 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 set up correctly and we should see a black screen of the dimensions we've just specified very nice now this is a bit of a 2 for 1 video because to implement shadow casting or line of sight we really need two algorithms I like the convenience of being able to draw the worlds in tiles placing blocks is quite intuitive as we saw with the Jerry Oh Pat forming 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 have to do geometry for all of the blocks every single frame well I feel that 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 an arbitrary section of level or world based on a tile map so we 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 in 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 cache shadows because at any given moment there's a lot of edges instead what we prefer to see is the boundary of 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 and a vertex here a vertex here one here one here here here and here we also have four more vertices here and in principle what I'd like to do is link these vertices with lines and I think it's quite easy to see now that there are far fewer boundary lines than there are at block edges once you move out of the blocky world of the tile map into the smooth world of the polygon there are lots of other advantages we get as 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 gradients and slopes I think we'll see a lot more of this algorithm popping up in future videos I want to construct these polygon boundaries in the most efficient way possible so ideally given a cutout of the larger world I want to scan through it want to create the set of edges and 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 and scan the next row in this simplified example the structure that I have for a particular cell in the tile map is quite simple it either exists or it doesn't so in some sort of cell structure I know I'm going to have a boolean for exists but in order to implement my algorithm I'm going to need some additional information I'm going to add four more boolean's which tell me did the edges exist and 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 instead it must use one that stored else were so I'm going to also include four integers which represent the ID of a given edge on the north south east or west side from some edge pool that will create else were 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 etc etc etc all the way along in our world until we get to why that does exist we only care about cells that exist so we're going to apply tests to this cell and the first test that we'll 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 we'll 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 we'll add to our edge pool edge a and in our cell structure we'll link our edge ID to the location of the edge in the edge pool we'll now systematically check the other sides of the tile firstly we'll check the eastern edge so if I have an 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 where can 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 going to have to create one of my own so we'll create a new edge called B and we'll give the ID of that edge to the cell also drawing the a edge there as you can probably tell already it's a similar situation for this southern edge - 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 and we run through exactly the same routine do I have a Western neighbor well I 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 set my edge ID as well the final check is do I have a southern neighbor well I don't so I do need an edge and you've probably already guessed I'm going to grow my Western neighbors edge as well and set my cells edge ID on the southern boundary to 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 check 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 I'll have to create one D and I'll add that edge to the edge pool and set my ID now we check for northern neighbors and 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 ID 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 C horizontally in fact it's very likely we'll never need to do anything with C again but we don't have to touch it it's in the edge pool it's got to start at an end point it's done so we'll move on the next cell it exists is this standalone cell here it doesn't have any neighbors so the consequence of this is is going to add four new edges to the edge pool a western edge an eastern edge a northern edge and a southern edge e F G and H I'll just set the edge IDs four five six and seven so the worst case scenario is a map made up of lots of individual blocks let's 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 that's where up to but it can borrow from its northern neighbor its 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 we'll have an edge pool that contains only the bounding edges of the shapes and the edges are defined by a start and 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've not defined what's the inside and the outside of 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 this same detail in the code so we'll do some cut and pasting I will need some basic structures to assist us the first thing I'll need is an edge which stores the x and y components of its start and end points and my world is going to be made up of an array of cells so this is my cell and I've included in it boolean Flags where does the cell exist or not and does it have an edge that exists on all four sides and what is the edge ID into the pool of edges and just to make the algorithm a little clearer to follow I'm going to define some constants for north south east and west our world is going to be a 2d array of cells the world will be defined by two variables world width and will 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 640 by 480 resolution so essentially the world is a single screen that we can see in on user create 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 and I'm going to grab a quick snapshot of the mouse coordinates it's important to do this because the mouse coordinates can technically change whilst this function is executing so grabbing them right at 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 item 0 that's the left mouse 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 in debt 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 coordinates and we do an integer 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 mouse corners and we also divide that by block width and that tells us how far across the screen is the mouse cursor in tiles effectively and this is something we've seen many many times now I equals a y-coordinate times the width of the array plus X which converts our 2d X&Y coordinates into a 1d coordinate in the array once we know the index we can toggle the exist flag for the cell at that location staying in unusual update what 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 to all black and now I want to draw the blocks from the tile map and to do this I'm going to iterate 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 code versing back from block space into screen space now with a width and height set to the block width and I'm going to draw the rectangle as blue let's take a look so here got the screen with the mouse cursor on and if I click wherever I click I place a blue block and if I select a blue block and click it it gets rid of it we're 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 and the container I'm going to use for this is a vector called BEC edges and 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 ie it's going to populate this vector 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 of tiles of which I wish to inspect and turn into edges and also going to pass in the block width parameter so we know where our edges exist in actual space and then the cysts a strange parameter 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 it on arbitrary size maps going forward so I'm using the phrase poly 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 associated with constructing this map naturally I want to just clear the vector of edges first but then during the construction of 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 at all and it's not got any edges in the pool again here we see Y times width plus X once we've cleared our map it's time to start applying our algorithm and I'll do this by creating two for loops x and y and iterating through the region of interest now you'll notice here I'm actually iterating from one - with - one of 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 of the 2d array I can 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 neighbor is the current cell but up one in the Y direction and our Eastern neighbor is the current self plus one in the X direction first let's check if the cell exists or not if it does exist we'll check to see does it have a Western neighbor because if it doesn't have a western neighbor then 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 we'll extend it and we can extend it by looking at our northern neighbors western edge ID and using that ID 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 width down which is what this line does so in our pool of edges we're looking at our northern neighbors western edge ID 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 and 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 we'll set the edge ID of our current cells western edge to be the same as our northern neighbors western edge and since the edge 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 who creates a new edge object and we can use the position we are in the array and the block width variable to work out where we are in real space so we can set the start coordinate of our edge X&Y here using the array coordinates multiplied by the block width and we know at the moment that our edge is going to be at least one block tall so we can specify that two 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 up here we need to now set the ID and whether the edge exists or not for this cell well it's a new edge ID and we've used the location of it in the vector to specify that ID 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 it's 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 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 own user 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 and I specify the block width coordinate so the edges can be done to the right scale and I specify the pitch to be the width of the world which is actually the same as the value I'm using 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 and I'm going to create a little Auto for loop to iterate through all of the edges in our vector of edges and I'll use the draw line function to draw a white line from the starting coordinates the ending coordinate of 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 at each end most of the center of the circle this is the radius and this is the color let's take a look so is my blank screen and I'm going to place a block very nicely we can see we've got at least four edges there if I place a block next to it we can see it's not drawing any more ends of edges it's just drawing the edge so it does look like in that direction the algorithm is working just fine if we branch off from here we can see that seems okay too let's go off the 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 I think what's probably also worth Jacky is solid object so it doesn't necessarily have to be a wall one tile thick it does seem to work for that to that we can punch a hole in the middle of this solid so I'm reasonably confident that we have taken the tile map and 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 and in most cases you probably wouldn't need to do that you'd only need to regenerate the poly map if the tile map changes and in some situations it could be a completely offline precompilation step of how your level data is stored so all in all I think this is a very useful routine to have right so let's start thinking about the shadow casting and the line of sight bit here I've got a location of the source of the light or where the player stands or whatever it is we're going to project rays from this source radially out into the scene now I've covered casting rays before in fact in one of my very first videos the first-person shooter the command line engine we can cast rays in all angular directions and see what they hit so here we go cast out some rays not very straight razor might have but when they intersect with something in the scene the Ray length is shorter and anything that followed that ray length past the intersection point is technically in shadow and finally this one is also in shadow and I'm sure you can envisage your scenario where we keep doing this all the way around the scene but this is really computationally inefficient and in fact we can look at this and derive from it that we're only interested in rays that intersect with our line segments even more so we're only interested in rays that seemed to intersect with the cornice so let's explore that for a moment for each edge in the edge cool I'm going to project array to the start and end point so in this case I've effectively got four rays when the Ray intersects with the line we know the Ray effectively starts turning into shadow well let's consider not looking at areas which are in shadow but instead which areas are in light the second ray down was defined by this coordinate but we can see that it had to intersect with another edge on its way there and so we'll record the intersection point that is closest to the source of the array and we'll do that for all four rays cast out and in fact let's do the same for all rays for the other object too so we cast rays to each of the vertices defined by the edges of the other object drawing the intersection points that are closest along that Ray if I add in one more point which is the source what I'm actually constructed is a fan of triangles there'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 polygon 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 then well there's a little hack that we can apply instead of casting one ray from the source to a vertex we cast three rays one goes directly to it and we have one either side displaced by a tiny fraction an angle so it'll 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 rays one is it theta and one is it theta plus or minus some tiny little amount these additional ways 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 will this one and this one and this one our intersection points are also recorded and 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 and the areas that can't be seen must be in shadow so we have cast shadows I'll start researching into this topic I found two brilliant websites you must go and have a look at the make outline these algorithms in quite some detail have lots of interactive demos you can play with too I will of course link to these websites in the text below the first one allows you to place a light source which 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 to all of the different stages that you might go through when developing this algorithm this is the second one and again a really nice site full of nice toys to play with and some code too and you can see again you can interact just as we're doing with edges and shapes and seeing where the Rays get cast in fact it was this website that gave me the idea of casting out additional rays for the corners please take the time to check out these sites I think it's a wonderful thing that experienced developers are taking the time and putting the effort into actually doing tutorials like this with interactive elements it's a lot of work and yet yield so much so check them out the links are 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 I'm going to start by creating another function to encapsulate the calculation of our visibility polygon there's going to be a set of points that represents the visible space from a source location defined by Oh X and Oh Y over a given radius but I'm going to use a little bit of modern C to help me out here I'm going to store the points of this polygon as a vector of tuples of floats and you'll notice there are three floats the first float is going to represent the angle from the source of the vertex that were targeting with the Ray and the second two floats are the X&Y location of 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 iterate through our vector of edges to work out the coordinates of to where we should cast rays 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 I effectively need to draw these points in some rotational order and so the easiest way to do that is not just to store the point on its own but take an arbitrary axis from our source point and record the theta values of each of the points so for each point I'll have a theta and an x and a y I can then sort these points based on the theta value to make sure that they're in this clockwise order if you've not seen a tuple before it's just a simple way to group things together it's a bit like a struct 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 and then we know that we need to do something for each edge in our vector of edges so little also for loop to iterate through all of the edges now an edge consists of two points the start and the end so for each edge we're going to have to cast at least two Ray's 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 gradient of the Ray they're depending on whether we're at the start or the end so I've used the ternary operator here to select between the start point or the end point and I'm subtracting from that the source location Oh XR know why giving me two variables are DX and our dy 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 use the atan2 function using the RDX in our dy values so this gives us an angle of our ray vector and we know that for each ray actually we're going to cast three additional Ray's with a slight deviation between the two so I'll create a temporary variable called angle which is going to be the angle we will shoot the ray at so I'll add another for loop to generate the three additional race we're going to need and depending on the value J in the for loop we're going to choose an appropriate angle to the Rae out - so in effect we've gone back on ourselves a little bit here we've calculated the gradient 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 cosine and sine of the angle will only cast the Ray as long as we've specified the radius value to be as you can probably see the number of rays were actually projecting into the scene is growing and the more complicated our scene is with tiles the more graves were going to cast out however the one thing we're guaranteed is that our strategy is more optimal than casting rays out in all directions and seeing what happens at least our rays are guided 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 and all of the edges in the scene the algorithm has now come down to a simple line segment intersection test so we can take two line segments and we want to work out the point at which they intersect and 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 the existing point Plus that vector and we can add in here a parameter T 1 and T 2 because if T 1 is equal to 1 where at this end of the line and if T 1 is equal to 0 where at this end of the line and so we'll find where our intersection point is by looking at the T values and since we're talking about line segment intersections go and find the line segment intersection algorithm of your choice I personally like this one which I discovered on Stack 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 collinear with the edge ie it's not going to lie on top of it so I'll check for that by just looking at the values of the vector component and making sure that they're sufficiently different for example if both had a dy of zero then both the Ray and 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 t1 and t2 values using the line segment intersection point algorithm and in this instance t1 is the distance along the Ray and t2 is the distance along the edge and so if t1 is positive that means we're traveling along the Ray in the correct direction and if t2 lies between 0 & 1 then we've definitely hit a line segment now that we know we've got an intersection 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 and only retain the one that is closest to the source and our t1 value represents that information we don't need to do Pythagoras theorem here to calculate the distance because t1 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 t1 distance and I'm also going to store the X&Y of the intersection point at that distance I'll set it to infinity for each way to start but if the t1 that represents the intersection point of the Ray of just tested is less than our current closest intersection 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 rays once I've calculated where the Ray ends I'm going to add that location to my vector of visible polygon 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 library can provide a nice simple routine to do this for us it provides a 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 I'll pass in as the sorting criteria a small lambda function and it's going to sort based upon the angle so the two arguments going into the lambda function are references to the two tuples 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 topple on the left is less than the angle of the topple 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 frame 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 we were to check that the mouse button is held but I'm also going to check that the vector of 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 fill triangle routine to draw a triangle from the origin point the source where the mouse is to the X&Y points of two successive visible points in our polygon vector so this will form a triangle what I mustn't forget to do is also close 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 let's add some obstacles oh well it looks like a complete or not a mess well it's a bitter kind of working but something's not right and the problem here is work with 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 from it starts to look a bit more sensible there's still some horrible glitches though particularly what is this triangle going up towards zero in the top left well this 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 we've 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 variable is 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 at some points in and I'll draw at least now we've not got a problem going up towards zero but things are still looking a bit information starved in fact if I now put in lots and lots of points as 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 rays 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 ray code what I'm going to do instead is just hard code into some boundaries into our tile map array so in on user create where I've just created the world I'm going to add in a couple of for loops which draw some parallel horizontal and vertical cells into the world let's take a look now we can see the boundary has been put in I'm now illuminating everything is lit up put in some obstacles and very nice our Rays 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 we're checking for visibility I'm curious about the number of rays being cast so I'm going to capture that information and display I'll just quickly use the draw string function to display this information to the user so no rays being cast and right now a hundred and sixty eight Ray's being cast four am fully minimal number of objects that we take out a bunch and now cast 72 rays even though we've got 1 2 3 4 5 6 7 8 9 10 11 12 known vertices in the scene this is because we've got duplication of vs. fortunately the standard library can help us out here - since our vector of visibility polygons points 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 a before and after comparison here is the unique function being called again it's part of algorithm and I've passed in a lambda function again which compares the tuples but this time it's saying please reject this particular topple if the x and y coordinates are similar in this case I've said less than naught point 1 so I'll create a second variable ray cast 2 and compare them so just a little recap we've used the unique function to remove all of the duplicates in our sorted vector it doesn't actually remove anything the unique function it just reorganizes the vector so that all of the unique stuff is at the start so anything after the point returned by the unique function we want to remove and therefore I'm resizing the vector based upon the distance from the start of the vector to that unique point I'll 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 a 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 rays but at 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 and of course we'll expect the number of rays to increase or casting 192 rays but now we're only drawing about 50 rays I think this is quite a significant optimization to make lots of features 840 rays cast and we're 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 implement it now at the start of this video I made it look a little bit more special because I used a sprite of a light sauce and modulated where it is white here with that sprite so this is a bit of pixel game engine trickery now in Photoshop 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 now going to do something a little bit novel for this channel I'm going to do some off-screen rendering I'm going to create two additional sprites called buffer light ray and buffer light Tex and 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 create 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 to which I'll draw things and then modify the pixel game engine supports rendering to different targets by default it renders to what you can see on the screen and we can specify the draw target by calling the set draw target function and by specifying null pointer is the argument that means there isn't any off-screen draw targets draw to the main target which is the screen so we want to do that before we clear everything to black and any subsequent drawing calls so in this case drawing the string those calls will be redirected to whatever the draw target is I'm going to use the off-screen 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 I've specified the target buffer I've erased 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 512 by 512 needs to be offset accordingly I'm then going to render to the second off-screen buffer the light rays so I'll clear the buffer to blank first and all of the fill triangle routines will now be targeted at that buffer I want to combine these two buffers to draw to the screen and because we're drawing to the screen now I set the draw target to null and I don't have any additive or special blending mode yet in the pixel game engine so I'm going to iterate through each pixel in my off-screen buffer and I'm going to check if each pixel has been set remember we cleared it all to blank to begin with so if it's been set by one of the light rays it'll no longer be blank and if that's the case I want to draw in the current screen location X&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 well 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 debug 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 a hundred 200 frames per second on my machine let's put in some obstacles very nice the use of off-screen buffers is a little bit eglee into the things we've been doing on this channel but it's a very common practice in all manner of computer graphics and the fact that we now work with pixels instead of characters allows us to do some higher fidelity effects and I quite like it if you've enjoyed this video firstly please check out some of the links to the resources I've used in this video they're in the description below the source code for this algorithm and the pixel game engine is also linked and that's available on the github come and have a chat on the disk guard give you a big thumbs up and don't have a think about subscribing I'll see you next time take care

Channel: javidx9

Views: 101,304

Rating: 4.9757133 out of 5

Keywords: one lone coder, onelonecoder, learning, programming, tutorial, c++, beginner, olcconsolegameengine, command prompt, ascii, game, game engine, line of sight, algorithm, shadow casting, shadow mapping, light sources, field of view, olcpixelgameengine, olc::pixelgameengine, pixelgameengine, tile mapping

Id: fc3nnG2CG8U

Length: 50min 23sec (3023 seconds)

Published: Fri Oct 12 2018