7 ms·

Interesting! How much more complicated would it be if the obstacles were not polygons but points on a grid? I've always been curious how the FoV was computed

Interesting! How much more complicated would it be if the obstacles were not polygons but points on a grid? I've always been curious how the FoV was computed so fast in the Baldur's Gate games given the complex grid-based map and the weak harder at the time. Example grid: http://aigamedev.com/static/tutorials/FPSB_bg_rsr.png http://aigamedev.com/static/tutorials/FPSB_bg_rsr.png And the FoV rendered: http://cdn.wegotthiscovered.com/wp-content/uploads/Baldurs-Gate-3.jpg http://cdn.wegotthiscovered.com/wp-content/uploads/Baldurs-G... (the rooms with no one in them are slightly darker)

willvarfar 10y ago
Permit me a "show HN" of my own ;) Here's a 3D view-shed calculation on a grid. http://williamedwardscoder.tumblr.com/post/13269950091/a-while-ago-i-was-playing-with-computing http://williamedwardscoder.tumblr.com/post/13269950091/a-whi...
- legends2k 10y ago
  This looks great! Are the calculations done in the GPU?
  - willvarfar 10y ago
    Not the example code I pasted into the blogpost. To be honest, its not an obvious candidate for offloading the the GPU. Its a light task, the result is probably wanted by the CPU, and these days we probably have spare CPU cores that could be utilized while the GPU is busy. However, with the move towards UMA for CPUs and GPUs - even the newly-announced ARM cores with Mali GPUs have coherent caches between CPU and GPU - and a move towards Vulkan, then the cost will change. As the cost of getting the result back to where its used for game logic diminishes, then this could increasingly be a candidate for GPU crunching :) (In my code there's a divide-per-grid-square that could be tackled using scaling perhaps.)
    - legends2k 10y ago
      > the result is probably wanted by the CPU -- I think this is a good reason to do it in the CPU. > its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind.
      - willvarfar 10y ago
        > its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind. I'm not following your meaning here ;) My blog post describes how to do it in a sweep rather than 'shooting lines', for the performance reasons given in the blog post. 'Shooting lines' is pretty poor for performance because of data locality and cache pressure. In general, locality is the big performance problem with 'ray tracing' in general. All attempts at speeding up ray tracing are about trying to make 'bundles' of adjacent rays flying in close formation that can be combined or computed together so as to try and give some locality to the problem. My scanline approach (line as in cache array of adjacent memory, not line as in line-of-sight between eye and obstacle) is good for CPUs and good for GPUs. If you want to offload viewshed computation to the GPU, you ought strive for a scanline approach rather than 'shooting a ray to every vertex' too. My code ought be straightforward to port to a shader.
        legends2k 10y ago
        My bad! Of course ray tracing in the GPU would be costly; I dunno where I got that. I think my mind is still stuck on 2D after this, need to go back to 3D :) When I had to do picking on a 3D terrain, I did a scanline approach too (https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terrain/Picking/ https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terra...)
      - PavlovsCat 10y ago
        I did something even worse with WebGL, shooting a ray from every light source and view point to every pixel on the screen in the pixel shader (so something has to be in LOS and and lit to be seen). http://i.imgur.com/ZJhr4Ll.png http://i.imgur.com/ZJhr4Ll.png The "player" is sitting on the "wall" of a room, to the right of it there are stairs going "downwards", it's all just a heightmap. Needless to say it's kinda slow, but I was surprised how neat it came out considering how little I put in. I'm sure someone who knows what they're doing (which isn't me) could do the same a lot faster and prettier, since I really did it in the most plump way possible.
legends2k 10y ago
> How much more complicated would it be if the obstacles were not polygons but points on a grid? I think with grids, one approach would be to go with a flood fill kind of an algorithm, but doing it cell-by-cell will be costly. An alternative way would be to unify cells together as a polygon and do intersection testing; with a hammer everything looks like a nail :P I think in games like Baldur's Gate, [Portal Visibility](http://playtechs.blogspot.in/2007/03/2d-portal-visibility-part-1.html http://playtechs.blogspot.in/2007/03/2d-portal-visibility-pa...) is commonly used.
marvin 10y ago
Looking at this with a decent understanding of how the computing world works today, I have an immense appreciation of all the work and care that went into the iconic classics such as Baldur's Gate. The combination of technical skill, ingenuity and also the (presumably) passionate creative focus and attention to detail when creating and integrating the artwork is just incredible.
a_e_k 10y ago
The roguelike development community has spent a lot of time thinking about this problem: http://www.roguebasin.com/index.php?title=Field_of_Vision http://www.roguebasin.com/index.php?title=Field_of_Vision

willvarfar 10y ago

Permit me a "show HN" of my own ;) Here's a 3D view-shed calculation on a grid. http://williamedwardscoder.tumblr.com/post/13269950091/a-while-ago-i-was-playing-with-computing http://williamedwardscoder.tumblr.com/post/13269950091/a-whi...

legends2k 10y ago
This looks great! Are the calculations done in the GPU?
- willvarfar 10y ago
  Not the example code I pasted into the blogpost. To be honest, its not an obvious candidate for offloading the the GPU. Its a light task, the result is probably wanted by the CPU, and these days we probably have spare CPU cores that could be utilized while the GPU is busy. However, with the move towards UMA for CPUs and GPUs - even the newly-announced ARM cores with Mali GPUs have coherent caches between CPU and GPU - and a move towards Vulkan, then the cost will change. As the cost of getting the result back to where its used for game logic diminishes, then this could increasingly be a candidate for GPU crunching :) (In my code there's a divide-per-grid-square that could be tackled using scaling perhaps.)
  - legends2k 10y ago
    > the result is probably wanted by the CPU -- I think this is a good reason to do it in the CPU. > its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind.
    - willvarfar 10y ago
      > its not an obvious candidate for offloading the the GPU -- How? Shooting a ray to every vertex comes to my mind. I'm not following your meaning here ;) My blog post describes how to do it in a sweep rather than 'shooting lines', for the performance reasons given in the blog post. 'Shooting lines' is pretty poor for performance because of data locality and cache pressure. In general, locality is the big performance problem with 'ray tracing' in general. All attempts at speeding up ray tracing are about trying to make 'bundles' of adjacent rays flying in close formation that can be combined or computed together so as to try and give some locality to the problem. My scanline approach (line as in cache array of adjacent memory, not line as in line-of-sight between eye and obstacle) is good for CPUs and good for GPUs. If you want to offload viewshed computation to the GPU, you ought strive for a scanline approach rather than 'shooting a ray to every vertex' too. My code ought be straightforward to port to a shader.
      - legends2k 10y ago
        My bad! Of course ray tracing in the GPU would be costly; I dunno where I got that. I think my mind is still stuck on 2D after this, need to go back to 3D :) When I had to do picking on a 3D terrain, I did a scanline approach too (https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terrain/Picking/ https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terra...)
    - PavlovsCat 10y ago
      I did something even worse with WebGL, shooting a ray from every light source and view point to every pixel on the screen in the pixel shader (so something has to be in LOS and and lit to be seen). http://i.imgur.com/ZJhr4Ll.png http://i.imgur.com/ZJhr4Ll.png The "player" is sitting on the "wall" of a room, to the right of it there are stairs going "downwards", it's all just a heightmap. Needless to say it's kinda slow, but I was surprised how neat it came out considering how little I put in. I'm sure someone who knows what they're doing (which isn't me) could do the same a lot faster and prettier, since I really did it in the most plump way possible.

legends2k 10y ago

> How much more complicated would it be if the obstacles were not polygons but points on a grid? I think with grids, one approach would be to go with a flood fill kind of an algorithm, but doing it cell-by-cell will be costly. An alternative way would be to unify cells together as a polygon and do intersection testing; with a hammer everything looks like a nail :P I think in games like Baldur's Gate, [Portal Visibility](http://playtechs.blogspot.in/2007/03/2d-portal-visibility-part-1.html http://playtechs.blogspot.in/2007/03/2d-portal-visibility-pa...) is commonly used.

marvin 10y ago

Looking at this with a decent understanding of how the computing world works today, I have an immense appreciation of all the work and care that went into the iconic classics such as Baldur's Gate. The combination of technical skill, ingenuity and also the (presumably) passionate creative focus and attention to detail when creating and integrating the artwork is just incredible.

a_e_k 10y ago

The roguelike development community has spent a lot of time thinking about this problem: http://www.roguebasin.com/index.php?title=Field_of_Vision http://www.roguebasin.com/index.php?title=Field_of_Vision