Hacker News new | past | comments | ask | show | jobs | submit login
Show HN: 2D field of view demo (jsfiddle.net)
333 points by legends2k on June 7, 2016 | hide | past | web | favorite | 76 comments



In case someone is interested in the design:

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


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)


Wow, the visuals look stunning, I like the noir theme!


Thanks! :) It's a shame we didn't finished it..


It's beautiful.


This looks like something that could do well comercially today, you guys should pick it back up.


I second this.


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



Thanks! Seems to be a failing corner case, will look into it.


Pun fully intended? :)


The code is very well commented! Great learning resource for anybody interested.


I've also done something similar about 10 years ago. I'm curious if you've ever seen my (unfinished) project:

https://vimeo.com/62844255

https://github.com/shurcooL/eX0


No, I have not come across it until now but from the screenshot it looks nice.


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.


Similar technique used for a nice website background: https://web.archive.org/web/20140429043206/http://www.goodga...


That looked like a very cool site and nice set of games. Time is a harsh mistress.


It's not bad, not sure what the potential for inducing seizures in some people is though.


It's also vaguely related to the raycasting used by classic 2.5D games like Doom.


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

And the FoV rendered: http://cdn.wegotthiscovered.com/wp-content/uploads/Baldurs-G... (the rooms with no one in them are slightly darker)


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


This looks great! Are the calculations done in the GPU?


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


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


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

When I had to do picking on a 3D terrain, I did a scanline approach too (https://bitbucket.org/rmsundaram/tryouts/src/master/CG/Terra...)


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

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.


Me too. Though it's just rendered as a 2D raster: http://monkeybrains.net/viewshed

I'm trying to build something that can be used across the DSM we have of SF for better planning our wireless links.


Oh, interesting!

Shouldn't it be possible to then feed that into a fitness function and randomly "evolve" the "perfect" distribution, or is that silly?


Totally possible. Though getting data out of WebGL can be hairy. And actually getting on the rooftops of the ideal buildings is a whole nother story.


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


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


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.


> 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-pa...) is commonly used.


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]

[1] https://common-lisp.net/project/lifp/uwar.htm


Very nice. Did you look at http://ncase.me/sight-and-light/ at all?


This too is a reference that I'd cited in the design document I'd linked :)

See the References section.


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.


Yes, it is very similar to shadow mapping.


This brings back memories of playing Commandos: Behind Enemy Lines: http://store.steampowered.com/app/6800/


Huge fan of Commandos series and the Desperados series. In fact this was inspired by it :) Thanks for bringing up its name!


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


Thanks for reporting this ;)

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.


I found different bug. Might it be the same issue? https://imgur.com/Rxaq72M


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.


Google Chrome - Version 49.0.2623.110 m (64-bit)


Thanks, will check when I get time.


No problem :) Glad I could help! :D But other than that, I don't know much about what you're doing, but seems very cool anyway :D


Here's an interesting approach to do this from a game worked on by Shamus Young, http://www.shamusyoung.com/twentysidedtale/?p=20777


Seems to be a great article at first glance, will read it. Thanks!


Great read, thanks! The same effect was used brilliantly in Monaco.


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.

https://blogs.msdn.microsoft.com/ericlippert/tag/shadowcasti...


Actually I've not read it, will read it some time, bookmarked :)


This is really cool, appreciate the demo, source and the writeup.

The debug view is beautiful. Great work.


Thanks for your kind words.


Old (June 2012), but still interesting related article: http://www.redblobgames.com/articles/visibility/


This is one of the references I'd cited, see the References section in the design document link I'd shared.


Whoops, so you did.


On a tangent, this reminded of this 2D shadow mapping technique.

https://github.com/mattdesl/lwjgl-basics/wiki/2D-Pixel-Perfe...


Thanks! The original inspiration cited in this (Catalin's article) did come up during development.


Here's a fairly detailed blog entry about some similar explorations : http://barradeau.com/blog/?p=194


Great link! It seems to have an in-depth treatment of the subject, thanks!


I found a bug http://imgur.com/VDQOT7o



Thanks will look at it when I find time.


We used to do it on coding interviews, but with rectangles only.


This looks great. Loved reading the writeup!


Thank you!


So... Can anyone explain what is so special or interesting about this?

Both the idea and the algorithms are decades old and were already used in the 80s and 90s computer games like Wolf3D and Doom.


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.


Most of them are closed, at least I couldn't find one which fit my needs and also none explain what they do very well.

But hey, I can't answer your question, since I cannot upvote on my own post, so I'm not the one calling it interesting ;)


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.


Thanks!

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


[flagged]


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 an honored tradition on HN for people to present things they've made for others to play with, and it's absolutely ok 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 in one's knowledge is a wrong spirit in which to comment here, and if you don't want to see HN degrade, that's the kind of thing you should help us cut back on.




Registration is open for Startup School 2019. Classes start July 22nd.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: