6 ms·
Show HN: 2D field of view demo
- almightysmudge 10y agoVery nice. Did you look at http://ncase.me/sight-and-light/ http://ncase.me/sight-and-light/ at all?
- legends2k 10y agoThis too is a reference that I'd cited in the design document I'd linked :) See the References section.
- MasterScrat 10y agoInteresting! 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 agoPermit 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 agoThis looks great! Are the calculations done in the GPU?
- willvarfar 10y agoNot 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.
- 10y ago
- 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 agoLooking 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 agoThe 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
- deleted 10y ago[deleted]
- mrmattyboy 10y agoI 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 http://imgur.com/a/MPzGa
- legends2k 10y agoThanks 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.
- mrmattyboy 10y agoNo 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
- Scea91 10y agoI found different bug. Might it be the same issue? https://imgur.com/Rxaq72M https://imgur.com/Rxaq72M
- legends2k 10y agoIn case someone is interested in the design: https://bbcdn.githack.com/rmsundaram/tryouts/raw/e06259fffad9231172a65b66ed99406df4e051d1/CG/WebGL/FoV/design.html 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/FoV http://bitbucket.org/rmsundaram/tryouts/src/master/CG/WebGL/...
- Eun 10y agoGot a bug here: http://pasteboard.co/1vhAc3yM.png http://pasteboard.co/1vhAc3yM.png
- legends2k 10y agoThanks! Seems to be a failing corner case, will look into it.
- peter-slovak 10y agoPun fully intended? :)
- feiss 10y agoWell 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 http://feiss.be/games/luxi (shameless Show HN)
- legends2k 10y agoWow, the visuals look stunning, I like the noir theme!
- xabi 10y agoOld (June 2012), but still interesting related article: http://www.redblobgames.com/articles/visibility/ http://www.redblobgames.com/articles/visibility/
- legends2k 10y agoThis is one of the references I'd cited, see the References section in the design document link I'd shared.
- almightysmudge 10y agoWhoops, so you did.
- intruder 10y agoThis is really cool, appreciate the demo, source and the writeup. The debug view is beautiful. Great work.
- legends2k 10y agoThanks for your kind words.
- foota 10y agoHere's an interesting approach to do this from a game worked on by Shamus Young, http://www.shamusyoung.com/twentysidedtale/?p=20777 http://www.shamusyoung.com/twentysidedtale/?p=20777
- manuelflara 10y agoThis brings back memories of playing Commandos: Behind Enemy Lines: http://store.steampowered.com/app/6800/ http://store.steampowered.com/app/6800/
- legends2k 10y agoHuge fan of Commandos series and the Desperados series. In fact this was inspired by it :) Thanks for bringing up its name!
- asQuirreL 10y agoThis 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.
- Chilinot 10y agoYes, it is very similar to shadow mapping.
- thomasjonas 10y agoSimilar technique used for a nice website background: https://web.archive.org/web/20140429043206/http://www.goodgameclub.com/ https://web.archive.org/web/20140429043206/http://www.goodga...
- jdironman 10y agoIt's not bad, not sure what the potential for inducing seizures in some people is though.
- nitrogen 10y agoIt's also vaguely related to the raycasting used by classic 2.5D games like Doom.
- partisan 10y agoThat looked like a very cool site and nice set of games. Time is a harsh mistress.
- Artlav 10y agoSo... 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.
- legends2k 10y agoMost 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 ;)
- carb 10y agoIts not. We've been in the Eternal September of Hacker News for a bit now. This is interesting to all the people learning javascript/programming/graphics for the first time and they're a sizable portion of the users.
- King-Aaron 10y agoIt'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.
- deleted 10y ago[deleted]
- dang 10y agoIt'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 in one's knowledge 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.
- damptowel 10y agoOn a tangent, this reminded of this 2D shadow mapping technique. https://github.com/mattdesl/lwjgl-basics/wiki/2D-Pixel-Perfect-Shadows https://github.com/mattdesl/lwjgl-basics/wiki/2D-Pixel-Perfe...
- legends2k 10y agoThanks! The original inspiration cited in this (Catalin's article) did come up during development.
- sakri 10y agoHere's a fairly detailed blog entry about some similar explorations : http://barradeau.com/blog/?p=194 http://barradeau.com/blog/?p=194
- legends2k 10y agoGreat link! It seems to have an in-depth treatment of the subject, thanks!
- mar_tin 10y agoThis looks great. Loved reading the writeup!
- legends2k 10y agoThank you!
- sclangdon 10y agoGood 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/shadowcasting/ https://blogs.msdn.microsoft.com/ericlippert/tag/shadowcasti...
- legends2k 10y agoActually I've not read it, will read it some time, bookmarked :)
- Grue3 10y agoThe 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 https://common-lisp.net/project/lifp/uwar.htm
- achikin 10y agoWe used to do it on coding interviews, but with rectangles only.
- blastseld 10y agoI found a bug http://imgur.com/VDQOT7o http://imgur.com/VDQOT7o