FOV shader/algorithm optimization

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
Post Reply
pauls313
Citizen
Posts: 50
Joined: Tue Aug 02, 2016 3:07 am

FOV shader/algorithm optimization

Post by pauls313 »

First of all, there is very little content on the internet regarding 2D shaders optimization and using it for FOV algorithms, so if you do understand (even if only a little) about this stuff, I'll be immensely thankful for your help.

My algorithm works like this: I cast a ray towards all 4 vertices of all solid tiles on the map. When a ray hits, I cast 2 more with a 0.001 angle displacement so I can hit the walls behind it too. Once all rays are cast, I organize them by order of angle, and finally I generate an array of triangles from all collisions. Anything inside this polygon gets rendered. My algorithm is quite literally the same as the ones in these websites, which contain great explanations:

https://www.redblobgames.com/articles/visibility/
https://ncase.me/sight-and-light/

Right now the algorithm is working, but with two issues:

First: It runs like shit
Second: all walls, even those behind other walls, are rendered

I'm VERY new to shaders, I only began to learn them for this FOV thing. I have experimented a little, but my greatest issue right now is with iteration. It's scaringly expensive for the GPU to iterate through an array, and like I said my algorithm generates an array of triangles, therefore each fragment has to read this array. This reduces the FPS to 15 or less with just a little more than 20 solid tiles. Would it be faster to draw the triangles onto a Canvas and then use it as a stencil?

Second, how would I render close solid tiles in their entirety, but only render part of the solid tiles behind them?

I uploaded a .LOVE file. WASD moves the player, left click instantiates/deletes solid tiles, right click turns on/off the shader.
Attachments
FOVtest.love
(4.86 KiB) Downloaded 143 times
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

Re: FOV shader/algorithm optimization

Post by ReFreezed »

I get an error while running the program. It may be because my graphics card is a bit old. I got it running by changing triangles[1000] to triangles[300] (until I click to add a new solid tile).

Code: Select all

Error

Cannot link shader program object:
Fragment info
-------------
(0) : error C6020: Constant register limit exceeded at love_ScreenSize; more than 1024 registers needed to compile program
(0) : error C6020: Constant register limit exceeded at MainTex; more than 1024 registers needed to compile program
(0) : error C6020: Constant register limit exceeded at num_triangles; more than 1024 registers needed to compile program

Traceback
[C]: in function 'newShader'
main.lua:54: in function 'load'
[C]: in function 'xpcall'
[C]: in function 'xpcall'
Anyway, drawing the triangles to a canvas, as you say, should be a whole lot faster - then you can use the canvas to determine how tiles and stuff should render in the shader. It's faster to render a few solid triangles once instead of looping though all triangles for every single fragment (which gets more crazy if MSAA is enabled). You can also use a mesh to draw all triangles in one go, which is faster than drawing each triangle individually (though I'm guessing this probably doesn't makes much difference in the game at this point).

I'm not sure what you mean by only rendering "part of solid tiles" behind other solid tiles. If you just want to not render them then the code to determine that should be in Lua and not in the shader. You already have rays that hit visible tiles that you can use.
Tools: Hot Particles, LuaPreprocess, InputField, (more) Games: Momento Temporis
"If each mistake being made is a new one, then progress is being made."
St. Cosmo
Prole
Posts: 8
Joined: Wed Nov 07, 2018 6:53 pm

Re: FOV shader/algorithm optimization

Post by St. Cosmo »

1. As you already said, render the triangles to a canvas, effectively creating a black and white texture that you send to the shader

2. Consider using physics shapes and the love.physics raycasting which is probably going to be faster than a pure lua implementation
Post Reply

Who is online

Users browsing this forum: No registered users and 44 guests