Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How to create 2D visibility/shadow effects for your game

ncase.github.io

Post reply on HN
Print view View original

1–10 of 47 posts

Re: How to create 2D visibility/shadow effects for your game

#2

Post by dllu »

Related:

1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/

2) a public domain Javascript visibility polygon library that runs in O(n log n), which is actually used in the Nothing to Hide game: https://code.google.com/p/visibility-polygon-js/

3) a blog post by author of said library discussing the algorithm: http://byronknoll.blogspot.ca/2013/05/on-log-n.html

Shooting a ray to every vertex and then naively computing intersections takes O(n^2) since there are n rays with up to O(n) intersections each. It is interesting to read and think about O(n log n) algorithms for computing the visibility polygon.

Re: How to create 2D visibility/shadow effects for your game

#3

Post by Osmium »

Really cool tutorial. It also looks like the author has a pledge drive ending today, and he/she is really close to hitting their funding goal. Would be a shame to miss it while being so close, especially for something that looks so promising.

(Note: I have no connection to this developer. Just thought it was worth mentioning.)

Re: How to create 2D visibility/shadow effects for your game

#7

Post by forrestthewoods »

Mithaldu wrote: post #5

He uses a nice trick to approximate the real thing, however this algorithm wouldn't be able to deal with curved objects.

I'm downvoting your comment because on technical posts the top rated comment is damn near always of zero value and only serves to make the commenter try to sound smarter than the post author. The more in-depth and complicated the post the more those type of comments appear.

This is a nice little post that reasonably describes a technique that has been used by a fair number of professional, commercial products. That anyone would try to downplay it to make themselves feel superior is silly.

To provide some actual value, most of the the images in the post are actually interactive. It's pretty cool. I somehow read the whole thing and didn't notice.

Re: How to create 2D visibility/shadow effects for your game

#8

Post by sartakdotorg »

forrestthewoods wrote: post #7
Mithaldu wrote: post #5

He uses a nice trick to approximate the real thing, however this algorithm wouldn't be able to deal with curved objects.

I'm downvoting your comment because on technical posts the top rated comment is damn near always of zero value and only serves to make the commenter try to sound smarter than the post author. The more in-depth and complicated the post the more those type of comments appear. This is a nice little post that reasonably describes a technique that has been used by a fair number of professional, commercial products. That a…

You didn't read very carefully if you missed that everything was interactive.

"Today, I will show you how to make something like this: (move your mouse around in the box below)"

"The demo below just draws a bunch of line segments and tracks your mouse position."

"Here's what all that math looks like: (move your mouse over the box)"

Re: How to create 2D visibility/shadow effects for your game

#9

Post by a1k0n »

dllu wrote: post #2

Related: 1) a tutorial on the same topic by Red Blob Games: http://www.redblobgames.com/articles/visibility/ 2) a public domain Javascript visibility polygon library that runs in O(n log n), which is actually used in the Nothing to Hide game: https://code.google.com/p/visibility-polygon-js/ 3) a blog post by author of said library discussing the algorithm: http://byronknoll.blogspot.ca/2013/05/on-log-n.html Shooting…

I didn't see this mentioned in those articles, so I figured I'd mention it: If the level has a lot of geometry, you could also make a BSP tree, and then at runtime you'd just have an O(log n) lookup, plus an O(m log m) running of the same algorithm on a pruned subset of m vertices stored in the BSP node. Each BSP node would contain only the edges which can possibly be seen from a particular area. The tree might be kind of big, though.
Post reply on HN