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

31–40 of 47 posts

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

#31

Post by highCs »

Nice article. However I think there's a better algorithm: the one actually used in Doom from Id Software.

First the scene must be put into a 2d bsp (that requires slicing some edge). After that, the bsp must be traversed front-to-back and that gives the edges in the right order. Just keep track of which angles are occluded then while traversing. During the process, when an edge is proccessed, cast/create the shadow accordingly. The algorithm stop when the field of vision is fully occluded - and not farther.

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

#32

Post by Trufa »

shurcooL wrote: post #30

Very cool article. Providing actual working demos for each step makes the technique a lot easier to explain to others. I had fun implementing this effect a long time, in a pre-graphics-shader era [1]. [1] https://github.com/shurcooL/eX0#screenshots

Honestly, I haven't even read it because I'm tired and I'll leave it for tomorrow, but this is the reason I check HN, I've gotten good enough at skimming through and article and the comments to know when an post is worth it and this looks awesome, not much of a point, just happy to see quality material in HN (not a rant, just happy to find a great post).

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

#33

Post by kevingadd »

ahoge wrote: post #29
ANTSANTS wrote: post #28

I'm kinda tired of the "cone-of-vision" mechanic and associated visual effect common in modern 2D games. In traditional 2D games, being able to see things that are not visible to the player's avatar is, IMO, a significant part of the charm. Not being restricted to a realistic viewpoint lets you become the larger-than-life hero of cartoons and cheesy action movies that does impossible things like leaping into a room f…

Well, it's not like the unlit parts must be completely black. Having some dynamic lighting does not mean that you must make it part of your game's mechanics. It's perfectly fine to do that kind of thing just for polish.

It's usually quite important if you want to create AI that behaves convincingly in a 2D world. The previous game I built using a 2D lighting system used it explicitly for this (other than making the environments look cool, of course) - the same geometry and light source data that lit the environments and produced shadows also determined whether enemies could see objects at given locations and whether you had hidden yourself by vanishing into the shadows or behind a given surface.

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

#34

Post by kevingadd »

ANTSANTS wrote: post #28

I'm kinda tired of the "cone-of-vision" mechanic and associated visual effect common in modern 2D games. In traditional 2D games, being able to see things that are not visible to the player's avatar is, IMO, a significant part of the charm. Not being restricted to a realistic viewpoint lets you become the larger-than-life hero of cartoons and cheesy action movies that does impossible things like leaping into a room f…

You seem to have an unnecessarily narrow view of games and how they're constructed.

Try out Mark of the Ninja and tell me they were 'just trying to make an FPS'.

Picking an appropriate perspective for a game involves a lot of tradeoffs. While certain mechanics are most appropriate for certain perspectives (top-down 2d, isometric, first-person 3d...) a general approach to 'visibility' is not one of them. Visibility (or an approximation of it) applies to AI in almost every action game type, regardless of perspective. Whether they can see you or not is an essential consideration for creating convincing enemies, and AI allies need to know whether they can see foes.

You can also extensively use vision cone mechanics without having anything to do with an FPS. Classic games of the Rogue variety (i.e. nethack, angband...) all leverage vision cones and line-of-sight despite the fact that they predated 3D games of any kind.

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

#35

Post by kevingadd »

awj wrote: post #26
dllu wrote: post #17

Earlier quoted context omitted.

Yes, with calculus you can find all the tangent lines from a point to any kind of curve. The exact equations vary based on what kind of curve it is (sine, parabola, cubic splines, Bezier curves, non-uniform rational B-splines, etc) and are kinda complicated.

At that point you're no longer dealing with rays and the math gets way more expensive for a goal of 1/60th of a second per render loop.

Any of this is absurdly trivial on modern graphics hardware, you can literally do all of the geometric math to compute your shadow volumes on the GPU and it will be a miniscule portion of your frame time.

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

#36

Post by eru »

jianshen wrote: post #25
tjaerv wrote: post #10

You, sir, must be from the future, what with the uncopyrighted, bitcoin-based crowdfunding campaign. Backing this effort is a no-brainer. https://back.nothingtohide.cc/

A bit OT but what are some of the most successful open source game titles out there? I'm writing a game server backend right now and didn't find very many projects where I could read good quality game code. (I come from the JS web app world where everything is out in the open so I'm super biased)

I found Battle for Wesnoth to be entertaining as a game. It's open source, but I don't know about code quality. If you are willing to read code from when dinosaurs roamed the land and sea, try Nethack.

If you only care about reading code, open source or not, I think the first Deus Ex's in game scripting code was visible in the game's editor. (And the rest was the first Unreal engine, whose might also be available for reading nowadays. Or you just read the source of the various Quakes.)

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

#37

Post by vlasev »

dllu wrote: post #17
Mithaldu wrote: post #14

Earlier quoted context omitted.

I'm not too strong with trig. Would this also work with curves that have more than one bump? (sine, etc.)

Yes, with calculus you can find all the tangent lines from a point to any kind of curve. The exact equations vary based on what kind of curve it is (sine, parabola, cubic splines, Bezier curves, non-uniform rational B-splines, etc) and are kinda complicated.

Let P be the point (a,b) and let Q be the point (x(t),y(t)) of a curve for some parameter t. The tangent vector to that curve is (x'(t),y'(t)) and the ray PQ is just (a-x(t),b-y(t)). You need to make sure these vectors are the same (up to a constant multiple) in order to have a tangent ray. That is you are led to two equations

cx'(t) = a-x(t) cy'(x) = b-y(t)

You need to solve these two equations for values of c and t. The difficulty of this task depends mostly on the difficulty of the curve itself.

If the curve has equation y = f(x) (or in other words a simple representation x(t) = t and y(t) = f(x(t)) = f(t)), then you have

c = a-x cf'(x) = b-f(x)

Therefore (a-x)f'(x) = b-f(x). If f(x) is a polynomial of degree n, the problem is reduced to root-finding of a polynomial of degree n so you'll have at most n roots to deal with. So in general it won't be easy. This reduces to the code in the post if you use line segments.

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

#38

Post by frownie »

a1k0n wrote: post #9
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 ki…

I think this particular idea of storing information in the BSP leaves was the big innovation brought to us by Id Software. Now, the elephant in the room is : how to build a well balanced BSP tree... But well, that's an entirely different question (I was a computer geometry researcher years ago... :-) )
Post reply on HN