Line Of Sight or Shadow Casting in 2D 

0:00 _Intro_ 2:26 _Setting up Pixel Engine in VS_ 5:41 Setting up demo 6:30 _Theory talk_ 7:02 *Theory* - Converting tiles to edges (on paper) 8:26 _Talk about advantages of converting tiles to edges_ 8:50 *Theory* - Algorithm (on paper) 15:44 Implementation - Generating edges 26:21 _Optimization talk_ 26:45 *Theory* - Ray casting? (on paper) 31:05 _Resources_ 32:17 Implementation _Setup_ - Visibility 32:58 *Theory* - Ray casting order? (on paper) 33:50 Implementation - Visibility 35:42 _Ray/Edge intersection talk_ 36:02 Implementation _Setup_ - Ray/Edge intersection 36:13 *Theory* - Ray/Edge intersection (on paper) 37:01 _Resources_ - Line intersection Algorithm 37:11 Implementation - Ray/Edge intersection 39:57 Implementation - Casting shadows 40:56 _Implementation result_ 41:40 Implementation - Bug fixing 42:12 _Implementation result_ 42:42 Implementation - Generating boundaries 43:03 _Implementation result_ 43:23 _Visualizing light only with rays_ 44:14 Implementation - Reducing numbers of rays 45:33 _Implementation result_ 46:37 Implementation - Adding sprite for light source 49:02 *Final result* 49:26 Compiling in release mode 49:46 _Off screen buffer talk_

I haven’t enjoyed RU-vid videos this much in a long time, fantastic content!

I've just scrolled through your channel and you answer lots of questions and have tutorials on everything I've been trying to do. Pseudo 3d. Check Shadows. Check. Zoom and panning. Check Thanks a lot

There's an important error in your raycast function. In it you solve for t1 by dividing by rdx. If the ray being tested is vertical, rdx will be zero and therefore the result will be NaN. To fix this, add a check for rdx != 0 before that step. If rdx == 0, use the following to solve for t1 instead: t1 = (e2 .sy + sdy * t2 - oy) / rdy I implemented this and it fixed the issue. Hope this helped anyone else who had this problem.

the moment you pointed out the "fan" was triangles my mind was blown. fascinating video - thank you for sharing all these resources!

I can't tell you how much this video helped me, I've been struggling to get LOS working for months, and it works perfectly now (i'm making a 2d maze game). Thank you! I cut the number of extra rays needed down to 1 (rather than 2) by making a Point struct with an enum to describe the point type based on which walls it connects (north, east end west, north/west corner, T-junction etc) . If they are "continuer" types (end of a wall and corners) I add an extra ray slightly further along toward the end of the wall, or outwards from the corner, 0.1f is enough. Currently working on how to cull un-needed rays - will post result and method if I find one. Thanks again javidx9, you are a life saver!

26:09 How dare you draw the Holy Hand Grenade of Antioch without the proper blessing!

This guy is ridiculously talented. Well done man The tutorials are much appreciated!

Thanks for including the set up. I'm very new to this stuff and it was very helpful. I know lots of people may know that stuff and not want to watch more explaination about it but for me that is amazingly helpful. Love your channel.

Thank you for coming to youtube! I love your work!

long videos are good thank you for all you're doing, great stuff

Absolutely Awesome Video

Your content is very compelling, well constructed, and excellent video quality. Keep up the good work! I have learned so much from you!

I was having problem understanding Ray casting in voxel engines, and your video made it very clear how it's done. I understood everything you explain in one go and don't have to rewind to jump back and forth topics. You explain things in a linear and structured fashion which I think sets you apart from most other programming channels. Keep up the good work!

I LOVED HOW U EXPLAINED THE FAN of triangle CONCEPT

Excellent video! Your explanations are very clear and very well visualised. Thank you for sharing your expertise!

perfect time for a javid video :D

A pleasure to watch. Thanks.

I've noticed that in a 4 edge tiled enviroment, bounding vertices always have an even number of edges attached, and any vertex with an odd number will not be relevant. So using this idea the first step would be to purge the irrelevant vertices from a grid array. Also, the number of edges in a row/column will be the number of vertex in that row/col divided by 2 (duh. but has neat properties). This means that you can start and end connections intermitently any time you encounter another vertex when running down the row/col without worrying about messing up the geometry. That way you can convert a vertex grid into an array of edges with starting and ending points. Then merge edges into vertex shapes by checking their vertices. Select one edge, compare to the next one, if they share a point, push the new vertex of the two into an ordered array until you find the edge that closes the shape by also checking if the starting and ending vertices match up, select another free edge if there are any left, repeat. You'll end up with an array of closed shapes and uninterrupted edges (hopefully).

This is gonna come in real handy for GameHut's 16-bit PUBG demake.

Thanks for sharing this video. Lots to learn indeed.

Always such great content!

Wow, this is just what I was looking for! Thank you so much, I haven’t seen the video yet but based off of your other ones I’m sure this will not disappoint! It’s late at night where I am atm so I will provide an update at some other time on how my project is going after watching and hopefully implementing this into my own project..

this is amazing. thank you so much. you could absolutely charge for these videos.

Great video and very clear explanation, keep doing this great job!

I've been working on this on and off for last couple weeks, and lo and behold a video appears in my feed. :P Decided to scrap the method I had been trying and go to something like this and after an afternoon of work got everything working. :D Thanks for the resource, would have been amazing to have few weeks earlier though. Definitely going to be very valuable to others.

This channel is amazing. Thank you for this!

Thanks. It's a great idea to include the little VS setup. I switched from code:blocks a week or so back and it was surprising how little information on this there was.

If you don't teach you should. Your explanation of things are so clear and concise that I was able to convert your code into C#. Well at least for the converting cells into a polygon. I am now working on the visibility polygon. Awesome work!

Thanks for your amazing videos. I dont do any C++, but they way you explain things makes it so easy to follow along and understand i have no problem applying it to javascript. Keep it up - maybe one day you'll bless us with javascript game dev videos :-)

awesome channel, hope to get visual studios, seems like a neat program. Keep it up!

This is a beautifully-done tutorial, sir. Edit: Just got it working in Java :)

Another short and simple video, great to watch right before a sleep at 3AM ;) tx

Nice video! I once programmed something similar in C# with OpenGL I used my own method which was to iterate over every vertex of the obstacles as lines and then using dot product of the line's normal and the vertex-player direction vector to detect whether the player can see the line or not. It only works for convex shapes tho...

Was just about to go to sleep but this is better!

I just found your channel and enjoy these videos. I feel like youll gain lots of subscribers

Finally I found a channel that teaches you useful algorithms for making 2D and 3D games while also teaching you new math. I was looking for a channel like this for ages! However I do not code in C++ and will have to learn it.

really good video thx

I think there is alternative way of "filling the gaps" than shown at 30:08 . Look, after you sort the list of triangles, you will find that between neighboring ones there will be "gaps in angles" eg.: between triangle A starting at alpha_1 and ending at alpha_2, and triangle B starting at beta_1 and ending at beta_2, there can be no triangle starting at alpha_2 and ending at beta_1. This means you can add a triangle starting at alpha_2 and ending at beta_1, with radius of the maximal radius allowed in your app. Of course, you have to take into account that the resulting triangle could have got an angle bigger than 180°, so there should be also some kind of function that will cut that triangle into smaller pieces :).

New subscriber... instant follower!

In my game, I am using the fast raycasting from your other video for lighting. Implemented a bit different than here, as raycasting is calculated, it adds light to the tile it is in, which gets reduced as the ray travels on. If a solid tile is hit, light is reduced, rather than blocked, giving a semi transparent property. Ray distance is limited by how far it takes the light to attenuate to zero. It casts 1 ray to each tile of the edge of the effective light reach. The light level at each tile is then moved to a texture (it is actually a shade drawn alpha blended over other tiles...), that is then stretched over the viewing area, making it look very natural. This also means only 1 draw call is used for the entire scene, combined with the efficient algorithm, lighting is nearly free performance wise.

As for the nearest neighbor algorithm, something that might be a little more efficient would be to use a kernel scheme. You will have to take into an account for and check for world boundary edges and corner cases, however, we can model it after something like this where each bit represents a specific direction being present. Of the 4 bits starting with the MSB being West we would end up with W,N,E,S respectively. If there is a 1 present that direction is set. If you notice there are no values of {5,7,A,B} which makes sense since 5 = 0101 where North and South would be combined. The same for 7 which would be 0111 giving a combination of N, S, & E and A being 1010 as this would result in E & W. None of those cases makes any sense, so those values don't exist in the kernel. So you'll never have opposing directions - bits set simultaneously and you'll never have 3 bits present as there are either only 1 or 2 bits set or none for the location of the object being the center of the kernel. This has good symmetry since the center object always has a value of 0 when you are looking for the 8 adjacent neighbors and is very versatile for many applications! NW, N, NE, 1100, 0100, 0110 W, C, E, = 1000, 0000, 0010 SW, S, SE 1001, 0001, 0011 We can create a descriptive enum or class enum for this: enum DirKernel { CE = 0x00, // Center SO = 0x01, // South EA = 0x02, // East SE = 0x03, // South East NO = 0x04, // North NE = 0x06, // North East WE = 0x08, // West SW = 0x09, // South West NW = 0x0C // North West }; We can have a const lookup_kernel in two different manners: const unsigned lookup[3][3] = { {12, 4, 6 }, {8, 0, 2}, {9, 1, 3}}; or by having const std::array { 12,4,6,8,0,2,9,1,3}; Now the actual values above are completely arbitrary as one could start with N and have that as either the MSB or LSB and you can go in a CCW or CW direction... just as long as you stay consistent with the bit patterns and making sure that none of them have more than 2 or opposing directions set. Now, know that we are only going to have 4 bits that are used for independent directions. This can possibly be simplified even further to make the algorithms even more efficient by using `std::bitset direction`. There are so many possibilities that one can do with this kind of design. We can see that the current sell on the world scan here will be at the center of these lookup tables (kernels) and the values will give the bit indicator of a cell's neighboring location and direction. However, the downside to this would be more memory consumption in that each cell would have to its own (x,y) world coordinate and or grid position along with two arrays. Now the arrays are not large in themselves such that one would be an std::array neighbors and the other would be std::array neighbors_exist... As the world is being generated by the clicking of the mouse to either draw or delete such a box, these arrays would need to be updated and since they are arrays, you have const time access, linear time iteration. The math performed to test a single cell with its eight neighbors would be simply bitwise arithmetic and logic. You could even use `std::vector` instead of `array` since we know that these arrays will always be 9 in size and never change if preferred. With modern c++ we might be able to get away with a simple for loop... for (auto& c : cells) { c.check_neighbors() } And we can use the kernels within check_neighbors method... which could theoretically reduce a lot of the multiplication and nested if loops... You don't have to specifically have an if west, then if north, then if south, etc... Just loop through the grid or vector of cells and check each cell's neighbor's vector and apply the kernel to it to generate the vector of bools. The nice thing about this with the kernel is the symmetry. The current cell will always be in the center of the kernel as it will always have 4 cells before it and 4 cells after it and it will always have a value of 0. In the enum it doesn't look or appear this way as they are listed numerically in ascending order, however, they would be in the kernel vector of values as seen above in the lookup tables. {NW, N, NE, W , C, E, SW,S,SE}... Also what is nice is if you need to get a particular neighbor's existing record you can query into that vector anytime and retrieve a dir_kern::NW which is very descriptive instead of hardcoded or defined. Don't get me wrong; I truly enjoy watching your videos, and I learn quite a bit. I like seeing other people's perspectives, their train of thoughts, their problem-solving abilities, and their algorithm building or designing techniques, but I also like to give possible insight on specific topics. Yes, there might be a slightly larger memory footprint but the speeds of the calculations would reduce bottlenecks. Besides that, the extra memory can be stored in a hashmap if needed for future use and fast lookup time. You will see many tricks like this when performing specific lighting and shading techniques within DirectX, OpenGL - SpirV shaders to perform complex calculations very efficiently. Create a mask and a kernel saves a bunch of computational times which is great when you begin to work with large 3D scenes with lots of objects and multiple lights. It's a good technique for ray, light, and shadow casting, applying filters, etc. You can see them here a little bit: learnopengl.com/Advanced-Lighting/SSAO and you can see them in some of these www.rastertek.com/tutindex.html. Not only this, but this kernel setup also works very well with a physics engine for collision detections, pathfinding, AI algorithms, A* search, and more. It can even be used in 3D Audio Rendering for directional sound displacement! It can be used in animations and even particle engines! Outside of this, I did like how you converted the intersection lines into triangle fans to reduce the number of rays that are being cast out, yet it will still cover a full 360-degree rotation field of view. I also liked your pre/post-processing - deferred rendering and only drawing when something is present or updated. Excellent optimizations!

Thank you! Thank you! Thank you! Thank you! Thank you!

thank you for this video. ive been trying to come up with my own way of casting 2d shadows a while ago and failed which then stopped me from actually making the game i was gonna build

Very nice !

Fantastic!!

Love your video, I was Playing with P5.js library and wanted to create some RayCasting, but my aproach was very bad, your algorithm is far better, will try to use it and write it in JS. Nice Content, new Subscriber here. Im not a native english speaker so sorry if I made some mistakes.

Normally I don't comment, but your videos are really great

this is awesome!!

great content. I believe the co linearity test you perform is only good for axis aligned co linearity, therefore mis detecting other tilted cases

Excellent! :-D

best channel.

you rock! Um abraço brasileiro!

great job. i likey

The most visually satisfying first 1:30

Hmm. Sprite is a neat trick, but.... For some game engines you might want to have the "character" with different light sources, or even variable ones, so you need, instead, a "falloff" effect, and.. it maybe possible to create a "fake boundary", based on that falloff (which could be useful in some cases). At least, the case I would use this for would need this, in any case.

Thanks for showing quite large text (for those like me watching on a phone)

If you go to new Project/Windows Desktop Wizard/Applicationtype:Console Application you can create a truly blank console app without the precompiled headers. Just uncheck those and check empty project.

"This is the very latest version of Visual Studio" *Yellow update flag in the top right corner* Loved the vid!

I love the mood that line of sight brings to a game. I was just looking to see if there was some other way. My own Unity based solution does some math on a shadow structure to cast the shadow onto a render texture achieving much the same result but using this in my shaders everywhere to pick visibility based on the LOS. It's pretty good but I was wondering about system that can be more efficient, less gpu\memory bound.

1:28 I know this means nothing, but this is the exact frame used in the thumbnail.

Great video--you always put out amazing stuff. Do you have any pointers on limited line of sight, such as a flashlight with a limited angle or a softer light that doesn't extend to the edges of the screen? Or at least where to begin my research into the topic?

javidx9: **posts detailed step by step raycasting engine** **gets 34K views** Random dude: **posts 'How to ddos' free python script** **gets millions of views** RU-vid this isnt fair :(

Great video ✨ I found this while trying to find out if it’s possible to do ray casting against arbitrarily shaped pixel formations. Like the terrain in Worms for example or if I were to draw a bit of terrain in a bitmap editing software where transparent pixels mean “pass through” and black pixels mean “solid”. Is it possible then to cast rays and find out what the normals of the terrain is at different points? I can figure out how to do it with a polygon etc but not with an arbitrary pixel shape. Maybe I could use something like marching squares to make a polygon out of the pixels?

Neat!

I use a rather crude version of this in my game and would upgrade to something closer to this however I need to optimize it quite a bit, one of the reference articles talk about using a sweeping ray to detect the closest line segments and only use those segments for the rest of the algorithm. I need to figure out to implement that optimization but not quite sure where to start, any ideas?

For edge_id[] and edge_exists[] you could use struct(s) instead and if u ever need to index them u can just use a pointer. Also i think these could be one uint where edge id 0 is no edge.

Hey there, great video as always. I am just wondering, would this stuff not be a bit easier, if you use the points of the lines facing the player and then cast rays from these points to form a quad. Like in the old 3D shadow volume stuff? No sorting or line intersection would be needed and visually it should look the same. So you do not draw triangles for the visible area, you would obstruct the hidden space. But anyways, big fan :)

For types used to index arrays in C u should use size_t instead of int... For i, n, s, w, e in convert tile map to poly map.

Is casting three slightly dispersed rays at eat intersection point more efficient than checking for each intersecting point whether the opposite points of both segments lie on the same side of the ray? (if so, then you know the triangle on the opposite side extends past the point.)

When you copy-and-pasted the code to make similar blocks of code just after 23:44 , would it be better to "abstract it away" with a function with some parameters, or would the function possibly be harder to read/understand, or harder to implement, or even perform worse than the direct but long approach?

you need more subs how have you only got 16k I could see you having 1 mill subs

If you can combine this effect with your Orthographic Dungeon code, this would be crazy

я не знаю английский язык, но мне интересно смотреть твои видео!

Instead of iterating through the whole array you can just check the newest block when its added. That should increase the performance in bigger maps.

Hey Javid, thanks for another great video. Is there any chance of doing a tutorial video on voxel game design at some point?

Hello sir, I was following your tutorial and implementing it in python, but got stuck at the point where you sorted the vector. I wanted to know how was it sorted ( I don't know C++ ), as t1 and t2 are float values while vecVisibilityPolygonPoints is a vector or list in python

To improve the raycasting, can't you create a new list with only the edges in a certain radius. That should make calculations faster (at least for larger maps)...

The sudden change in audio quality and volume made me audibly jump.

Can you please explain why is it faster when you set the realease mode?

Does anybody understand why the ray sweep optimization (not covered here) is faster and how it works???

> In this (long, sorry) video ... It explained everything clearly, so its okay.

can you just store the postion of each box... than check if there are shared edge, if yes delete them and sum the rest by checking the y or the x position so you know where to connect them ... if no share make all four bounds...

Hello, i love the way you are vast in your knowledge. I admire you... And also wants to learn. Please can you recommend good books in graphics physics and maths that are relevant to software development.

great demo. just wanted to point out that the mouse coordinates don't work for the Y axis using 2x2 pixel width/height on my laptop. it works using 1x1 pixels. this is likely due to the odd wide screen format of my display which is 1366x768. it works normally on another pc with a more standard display mode. i suspect it's due to a loss of precision in converting from float to int because a quick test showed me that 2.9 is being rounded down to 2 instead of rounding to 3 and we're off by an entire row.

Can you explain faster raycasting with tan and grid intersection in the next video?

Thought this video would talk about how to optimize which points to cast from when some are shadowed by other points :(

I watched this, looked at that site, and made my own version. It appears to behave perfectly but casting shadows at certain angles causes a glitch where ther radial order of the vertices changes. No clue what I'm doing wrong...

which video is "here" where you explained the edge grouping algorithm? XD

nice

There is nothing better then wake up an feed the brain.

How would the mechanics change if the edge geometry was planometrically isometric circular bodies w circular edges (or cylindrical if 3D) instead of square? E.G. Assume each cubed grid point embodied a scattered set of circular bodies contained with each isometric grid point...

@javidx9 don't you think this "int w = (y + sy) * pitch + (x + sx - 1); // Western Neighbour" has a potential to cause confusion for newbies like me as there is an argument with the same name "w" in the same function. I know it is local but considering someone trying this tutorial out for the first time. A GREAT TUTORIAL TO BE HONEST

I have never used or looked into your PixelEngine but doesn't it support texture mapping when drawing the triangle fan? If it does, showing the sprite would be just a matter of assigning proper texture coordinates to each vertex. At least that would be my first approach -.-

I have programmed a game i have a invertet version from your code and without rays(but im not finished)

Can you extend this project and add some antialiasing? That would be so awesome to see what the windows console can realy do and it would look so much better with that smoothing effect.

This is what was used in Diablo 2

There is a much simpler way doing the same thing and at the same time achieving global illumination: A 2D-Pathtracer

PGE

I would like to do this in 3d but how do you keep a pool of corners in 3d ?