Devising the algorithm took around a month; did it in my free time. The implementation took a week, in HTML5 Canvas/JavaScript. Doing a 360°, not-bound-by-distance FoV would have been simpler, but FoV limited by both angle and distance took time.
The idea is to find the field of view of an observer on a map with blocking buildings (polygons) and also to service a line of sight query, to know if a given point is visible to the observer.
The code contains enough comments including citations and references to articles and books. Here's the actual repo from where the above page is served:
Well done!
It's almost the same algorithm I came up with in one sleepless night, 7 years ago. I used it in a game that was not finished: http://feiss.be/games/luxi (shameless Show HN)
Hah, thanks a lot. We always thought we had something cool in our hands, but our agendas didn't match and our budget was null.. The worst thing is that since then I lost faith in indie teams, and prefer the solo path, like a lone rider.. :/
Cool. Verifying the old Engineering adage about a month in the lab saving you a day in the library. Or 10 minutes on Google these days.
Still, sounds like a fun time. I have my own version of this sitting around on a floppy disk somewhere, done at a point in time where floppy disks existed (possibly even 5 1/4" ones).
Thanks! Spent quite some time searching for the algorithm in Google, DDG, what-have-you, but didn't find something that does exactly what I want and also none that explains it lucidly for anyone who wants to understand it.
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.)
> 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.
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 :)
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).
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.
Make ease of access (and how much it's wanted there, and so on) part of the fitness function, too :)
And future configurations could also take into account how many things you'd have to move, or whatnot (I have no idea about what you're doing, I just imagine that's not something you do once and never change, right?).
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.
The algorithm is called "recursive shadowcast" and has long been used in roguelike games. I once implemented a vector adaptation of this algorithm for the groundbreaking non-tile based roguelike Urban Warfare [1]
This is some interesting work! I was musing about another algorithm to achieve the same effect, as I was reading:
* First render the scene in 3D, from the viewer's position, using a perspective transformation with the right field-of-view to match the "bounding angle".
* Save the resulting Z-buffer into a texture.
* When rendering the 2D, top-down scene, you can consult the Z-buffer (now a texture) to see whether that pixel should be highlighted or not.
I think this is a technique that's already used, but almost complementarily, to calculate shadows from dynamic lights.
I found a bit of a weird 'bug', where I could get the POV to have a straight edge (rather than the curvature), if it's of any use: http://imgur.com/a/MPzGa
This is a floating-point comparison problem, I faced it frequently during development; need to play more with it to arrive at a better epsilon ε value.
This is new! I'd never hit it. But it seems the angular point sorting is off, can you please send the browser and its build you are on? I'm unable to reproduce it.
Good job OP. I personally found Eric Lippert's 6-part series (and playable Silverlight demo) on the subject fascinating. I didn't notice it referenced in your design document, so here it is.
It's fun when people share their work in a way others can play with and give feedback on. This is a classic Show HN—it's fine for such projects to be trinkets. Not everything, lord help us, must be an original contribution to computer science.
And the discussion upthread is superb, so this was an excellent post for HN in every way.
Even with a known algorithm, it can be cool to see a clean visualization of it.
OP was clever enough to figure it out, and that's great, but it bugs me some every time I see them say that they couldn't understand other people's explanations of how it works.
> it bugs me some every time I see them say that they couldn't understand other people's explanations of how it works.
I think I need to explain. Most of them explain their work well, but I cannot reuse them as they all have 360° FoV, not limited by distance, while I wanted something else, hence this mini project.
The ones which had what I wanted were closed source.
It's also interesting to some of the people who have been developers for almost two decades and haven't yet seen such an implementation in the browser before, or, you know, find it interesting to see people come up with solutions to things themselves. Good on OP for giving it a crack.
It's great on HN when people present things they've made for others to play with, and it's fine for such things to be toys, learning projects, and so on. Some of us are decades out from "learning javascript/programming/graphics for the first time" and still take pleasure in seeing projects like this.
What's not ok is to grouse about it. If you know more than others, share some of what you know. Superciliousness is a degrading spirit, and if you don't want to see HN degrade, that's the kind of thing you should help us cut back on.
https://bbcdn.githack.com/rmsundaram/tryouts/raw/e06259fffad...
Devising the algorithm took around a month; did it in my free time. The implementation took a week, in HTML5 Canvas/JavaScript. Doing a 360°, not-bound-by-distance FoV would have been simpler, but FoV limited by both angle and distance took time.
The idea is to find the field of view of an observer on a map with blocking buildings (polygons) and also to service a line of sight query, to know if a given point is visible to the observer.
The code contains enough comments including citations and references to articles and books. Here's the actual repo from where the above page is served:
http://bitbucket.org/rmsundaram/tryouts/src/master/CG/WebGL/...