Line Of Sight or Shadow Casting in 2D

In this (long, sorry) video I cover a variety of things to implement a classing line-of-sight mapping, or shadow casting depending on your perspective. It's also the first olc::PixelGameEngine project I've done a video for, so I spend some time showing you how to set up Visual Studio to use this engine. I'm quite pleased with the end result of these algorithms and I expect to use them quite a bit in more ambitious tile-based projects in the future.
These resources are excellent regarding the things seen in the video:
stackoverflow....
www.redblobgam...
ncase.me/sight...
Source: github.com/One...
/ discord
Blog: www.onelonecode...
Twitter: @javidx9
Twitch: javidx9

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_

[@5daydreams]

Wow, this is very organized! Thanks a lot :D

[@TheMadmaxster]

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

[@javidx9]

That's really pleasing to hear MadMaxster, thanks!

[@dewijones92]

+1

[@clodgozon3968]

It's true. I don't know why I do not enjoy Cherno and other people's programming videos, except this channel!

[@aimanal-eryani7809]

Yes indeed, dude's old-school

[@mothtolias]

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

[@javidx9]

Yeah, its a nice conclusion - always reduce a problem into things you can do, sounds obvious I know, but so very very true...

[@GermsOilCotten]

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.

[@clodgozon3968]

Duh, I love explanations too. You're not the only one, lmao.

[@harryfox4389]

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

[@javidx9]

Hey welcome to the community buddy!

[@stevea.b.9282]

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!

[@avirosenblum233]

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.

[@nilspin]

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!

[@javidx9]

Thanks nilspin, I'm pleased you are finding the videos accessible, and thanks for the feedback! I will!

[@kevinjad4506]

I LOVED HOW U EXPLAINED THE FAN of triangle CONCEPT

[@Otakutaru]

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).

[@videopsybeam7220]

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

[@SnakeEngine]

On Sega Saturn!

[@javidx9]

Yeah Psybeam a few comments have pointed this out - it looks like a great project from an experienced coder, one to watch for sure.

[@psyjax2]

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

[@javidx9]

dammit XD

[@mothtolias]

looks more like a map church symbol to me.

[@killereks]

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.

[@BlazertronGames]

I'm sure you could apply it to a different programming langauge.

[@BlazertronGames]

Also, if you're going to learn c++, make sure you get a good book. I've heard that free online beginner resources usually teach bad habits/techniques. And don't trust amazon reviews, make sure you research if you're going to buy one.

[@killereks]

hey, thanks for the help however i do code in C# and other languages for a long time so i have good understanding of private variables, friendly functions, destructors etc. I even learned how pointers work so I'm pretty sure i could learn c++ pretty quickly but I just don't know how to do graphics in it so I haven't tried yet. Also I don't like learning from books especially programming, I think it's better to go and try to code something or mess around with other people's code. Thanks again.

[@javidx9]

Hey Killereks, nice to have you on board!

[@mothtolias]

yes, most of what's described here is abstract and could be implemented in just about any language.

[@kepeb1]

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.

[@kepeb1]

Actually, it was a few things. A gap in my learning, majority of interesting KZbin tutorials seem to use it, and it is easier to follow for a beginner if it looks the same. I am not really skilled enough to argue the merits of either. But I can say VS was WAY easier to set up. There were a number of code:blocks specific hurdles that kept interrupting my progress. Before I was even introduced to all the fundamentals there were extra steps I had to figure out in order to simply follow along.

[@javidx9]

Hey Thanks Turncoat, I'm pleased it was useful to someone, its a question I get asked a lot.

[@laureven]

Absolutely Awesome Video

[@SamFisk]

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.

[@javidx9]

Sorry it was later than you needed Sam, oh well! At least you got it working and thanks for the support - its appreciated!

[@Jay-og4yb]

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

[@namless0o7]

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

[@javidx9]

Thanks namless!

[@KSG__]

perfect time for a javid video :D

[@javidx9]

lol, perhaps not in UK, it was 12:30am here :D

[@kubamaruszczyk4043]

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

[@javidx9]

Hey cheers Kuba!

[@Morphox]

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...

[@javidx9]

That's a nice approach Tomlow, and is probably valid in many situations, may be worth doing a performance comparison in the future!

[@bryphi77]

Always such great content!

[@javidx9]

Cheers bryphi!

[@thePrinceOfPurpose]

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

[@mattpilot]

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 :-)

[@javidx9]

Thanks M P, I appreciate it, although I will say it is unlikely I'll do any javascript videos, but I will be doing some lua script pretty soon!

[@nivalius]

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

[@felixspeagel5915]

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 :).

[@up4life108]

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

[@javidx9]

Oh dang Up4Life, I hate it when stuff like that happens. Perhaps now its time to dig up those idea and give it another go?

[@up4life108]

it definetly is! Thank you for your respond, i will give it another try now!

[@skilz8098]

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!

[@alxklgn364]

A pleasure to watch. Thanks.

[@Revan727]

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!

[@fuanka1724]

Thanks for sharing this video. Lots to learn indeed.

[@rampage14x13]

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..

[@lucaxtal]

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

[@javidx9]

Cheers Luca, will do!

[@Plrang]

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

[@javidx9]

lol, yeah yeah, I get it, shorter videos :P Sleeping just stops you from doing cool stuff anyway...

[@Plrang]

@@javidx9 I got a fresh kid, don't sleep anyway;) And I know you have, watching that all the time

[@xeridea]

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.

[@marcusotter]

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

[@javidx9]

lol thanks Marcus!

[@beron_the_colossus]

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

[@javidx9]

Hey thanks Peki!

[@beron_the_colossus]

[@florianwicher]

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

[@GG-fj5er]

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

[@rockyrivermushrooms529]

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

[@javidx9]

Hi there FireFungi, hey thanks a lot buddy! As long as people enjoy the videos Im happy :D

[@jimboli9400]

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

[@thecrazyinstitute1680]

.

[@gatedrat6382]

KZbin is an algorithm that doesn't care about fairness

[@Valentyn90A]

This channel is amazing. Thank you for this!

[@javidx9]

Hey thanks Val, my pleasure!

[@patrickelliott2169]

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.

[@mypersonalvideos2786]

really good video thx

[@javidx9]

Thanks MPV!

[@James-uw4it]

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

[@javidx9]

Manuel, I really appreciate that, thanks buddy.

[@TomershalevMan]

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

[@nixonian1]

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.

[@javidx9]

lol, Im fairly certain youve told me this before XD - I'm just so set in my ways - It's like its built in "delete auto generated stuff"

[@unaigom]

New subscriber... instant follower!

[@javidx9]

Thank you Unai!

[@JoshRosario310]

The most visually satisfying first 1:30

[@focuseletronica]

Fantastic!!

[@javidx9]

Cheers friend!

[@erichenriquez3641]

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.

[@javidx9]

Glad it helped! Thanks Eric!

[@guy-dev]

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

[@bovineox1111]

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.

[@VictorQianYT]

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

[@guacamolen]

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]

Hi Micheal, thanks buddy. yes you can do both by adding fake edges in the shape you need around your light source before casting.

[@DamienFromPoison]

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 :)

[@javidx9]

Hi Damien, Its a perfectly valid approach. The only downside I can see is the redundancy in drawing multiple "shadow" quads that may be redundant (say an edge lies within the shadow of another edge) - certainly worth experimenting with anyway.

[@Thoracius]

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.)

[@jakubsebek]

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

[@javidx9]

Hi Jacob, in debug mode, the compiler adds all sorts of additional code behind the scenes so you can debug your program, i.e. hooks and variable information that the debugger can display. Other things it checks for is going out of bounds on arrays, stuff like that. In release mode, it will not do any of these things, so its much higher performance

[@jakubsebek]

@@javidx9 thx

[@michaeljones3448]

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

[@kalejaneth2457]

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?

[@AndreasEDM]

best channel.

[@jsflood]

Excellent! :-D

[@javidx9]

Thanks John!

[@botteu]

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?

[@beyondcatastrophe_]

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)...

[@javidx9]

You are correct! There are several ways to optimise this, but certainly this is one of the simpler ones. Checking if points are within a radius can be fiddly to though (obviously the check is simple, but you dont want to have to check all points)

[@PierreSoubourou]

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

[@stonekase]

@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

[@javidx9]

Hey Akawo, you are correct in this regard - a bit lazy of me to not use a different name, to be fair, I just didnt notice :D

[@sirknight1291]

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.

[@javidx9]

Absolutely Sir Knight, in fact there are many additional optimizations one can perform here. Block removal gets a bit more complex though!

[@mutated__donkey5840]

even though i have Clear(olc::BLACK); in my OnUserUpdate, i see a white screen. i have even tried FillRect(0, 0, nWorldWidth * fBlockWidth, nWorldHEight * fBlockWidth, olc::BLACK); and it still doesn't work pls help

[@user-vv5sn6gf1f]

Pal, try to change "Solution platform" on x64 in main toolbar (the default is x86), if you have x64 operation system. In my case it worked.

[@lovecastle7154]

Was this based on gamehut's 16bit pubs video from last week?

[@lovecastle7154]

Pubg

[@javidx9]

No, its an algorithm that has been around for at least 30 years. Though I saw GameHuts video today after a few people left comments about it, and it looks like an exciting project!

[@chris_burrows]

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

[@alegh4008]

Excuse me for the stupid question. Do i need to download the entire github library or just the header file?

[@javidx9]

Just the header will do

[@alegh4008]

@@javidx9 thanks man. I'll be following along your video now

[@phynx-victumterra652]

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?

[@Bunny99s]

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 -.-

[@EvilStreaks]

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...

[@EvilStreaks]

Fixed. The coordinates of the vertices had to be floats

[@prajjwalpathak2718]

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

[@francescopiazza4882]

Very nice !

[@cheako91155]

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.

[@OneShot_cest_mieux]

Thank you for this content. I have tried your c++ code on Github but the right button on the mouse don't work to display the light, am I wrong ? Sorry for my bad english I am french

[@javidx9]

Are you linux or windows? Up until recently right click and middle click were swapped on linux.

[@seanwiiik]

@@javidx9 I'm on Windows, and I have the same problem.

[@seanwiiik]

I found the solution. You also have to drag the light.png from the same GitHub into your project folder, where you dropped the ShadowCasting file.

[@OneShot_cest_mieux]

I am on windows too, thank you Sean Wiik it work ! Sorry for this stupid mistake

[@TheVersatilefungus]

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

[@javidx9]

Hi Versatil Fungus and thanks! Im not interested in doing voxels the expected/conventional(?) way (i.e. yet another minecraft clone) so if I can think of a more interesting vehicle to demonstrate them then I will. After all, voxels have been around waaaay longer than minecraft so it shouldn't be too difficult ;)

[@TheVersatilefungus]

@@javidx9 I wasn't thinking so much like a Minecraft clone. More in a sense to make destructible objects with physics. Something similar to this perhaps: kzbin.info/www/bejne/iqeumYx-brd3fsk

[@flobuilds]

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.

[@javidx9]

Hi Bluestroker, just to avoid confusion, this is not rendering using a windows command prompt anymore (though the code could be ported to ConsoleGameEngine quite easily). I hope to do a video about various image processing techniques soon - I have already experimented with blurring algorithms for soft shadows and they look awesome.

[@flobuilds]

@@javidx9 ok that's awesome. I love this c++ code

[@MacShrike]

Hi Javid, I'm a bit confused; Isn't it actually a Light-cast algorithm and not a shadow cast? You only draw visible light triangles. Might be semantics only but the only things you actually don't draw are the shadows =) Anyhoe, although I like it, I can imagine a tiled colourful playfield background in which case you would only have to erase the shadow parts. So an actual shadow triangle drawing routine seems more useful. Still loving your vids afcourse, Kind regards, Mac

[@javidx9]

Hi Machiel and thanks! Light and Shadow casting are the same thing, they are just inverse. Obviously where there is light, there is no shadow and vice versa, so by calculating one you get the other for free! No need to draw shadows, because you know they have not been touched by light.

[@MacShrike]

@@javidx9 ooo, that's deep 🤔🤗🖖

[@javidx9]

😂

[@unveil7762]

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...

[@cheako91155]

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.

[@user-kf1xn1dq9t]

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

[@mrferret980]

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

[@davidkozak9959]

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...

[@davep7176]

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

[@EvilStreaks]

Instead of hardcoding the edges to be filled cells, why not hardcode four polygon lines to the map boundaries?

[@javidx9]

of course you can do this

[@beaconofwierd1883]

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

[@SketchpunkLabs]

great job. i likey

[@javidx9]

Thanks Sketchpunk!

[@jackpret4547]

Neat!

[@javidx9]

Thanks Jack!

[@CJBurkey]

This might be a bit out of the scope of this channel, but is there any chance you could talk about/demonstrate the fortune's algorithm for generating a set of edges in a voronoi diagram? I know of a few libraries that do this, but the math behind it is a bit complex and would love to see someone as good as yourself explain it in ways that I can understand :)

[@javidx9]

Hi CJ, Ok I'll add it to the list - I do have a plan to look at voronoi, but from a slightly different, potentially highly parallel perspective so I'll see if I can fit something in.

[@CJBurkey]

Oh, cool, thanks!

[@conandoyle1859]

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

[@cvabds]

you rock! Um abraço brasileiro!

[@javidx9]

Aww, thanks cvabds!

[@androth1502]

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.

[@javidx9]

Hi androth, rounding down in this instance is actually desirable. The mouse coordinates become inaccurate if you resize the window, or use a window manager that resizes it for you. Are you running on linux?

[@androth1502]

@@javidx9 i'm running windows 10 on both systems. the same code works on my desktop, but not on my laptop. the only thing different between these two is the display resolution. i'm trying to figure out why i'm losing more rows precision the further down i click in the window, and why if i switch to 1x1 pixels, the problem goes away. sorry, i'm coming from C#/WPF. haven't looked at C++ in over 10 years :) edit: i think it's because windows is resizing my window. the program needs 800 pixel screen height and my laptop maxes out at 768. i figured windows would just create the full size window and allow it to extend beyond the screen.

[@javidx9]

What size window are you creating?

[@androth1502]

@@javidx9 same as in your program, 640x400, but with 2x2 pixels, it's really 1280x800. i think that is the issue, it just didn't register in my brain. i guess i'm getting slow in my old age. anyway, i appreciate what you're doing here. i made something very similar (win32/linux gui library) in assembly language over a decade ago, but never took it beyond demo.

[@javidx9]

Lol its ok androth. Sometimes just need a fresh pair of eyes! I currently dont support normalised coordinates so resizing the screen introduces mouse weirdness.

[@anonymoussloth6687]

Great Video! I just don't understand why you are drawing and updating it every frame. Wouldn't the performance be much better if you just draw/update only when there is user input (otherwise there will be no change to the application)?

[@javidx9]

Thanks Ayush, I draw every frame primarily because it's representative of how such a technique would actually be used (in a game for example). This way performance remains an objective, because if it doesn't perform well, it's pretty worthless.

[@anonymoussloth6687]

@@javidx9 I see. I also had a question about the border. You mentioned in the video that the rays needed something to intersect which is why you drew the border. Is there no way to make it work without the border?

[@javidx9]

Sure, just specify a maximum length for the ray.

[@anonymoussloth6687]

@@javidx9 OK, but I am sti confused as to why this is needed in the first place. At 42:35 you mention that they need to intersect with something. Could you elaborate on why that is?

[@javidx9]

Normally the shadow/light that is cast needs to be physically represented. An infinitely long polygon isnt that easy to work with, so it needs to be terminated at some point

[@haudiweg]

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

[@amankaushik5833]

this is awesome!!

[@tacticolfire]

This is my first introduction to making games thanks for the clear tutorial sir. How can I obtain the Sprite.png file?

[@javidx9]

It should be in the github repo, but feel free to use almost any png file

[@tacticolfire]

@@javidx9 Thanks :)

[@stonekase]

@javidx9 , why is "j" capped at 4 in the loop---does the 4 cover for 4 sides of the square? "// Clear "PolyMap" vecEdges.clear(); for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) for (int j = 0; j < 4; j++) { world[(y + sy) * pitch + (x + sx)].edge_exist[j] = false; world[(y + sy) * pitch + (x + sx)].edge_id[j] = 0; }"

[@javidx9]

This is correct