Annotated code: Circles bouncing off lines

http://annotated-code.maryrosecook.com/circles-bouncing-off-lines/index.html

by danso • 11 years ago

238 65 11 years ago

annotated-code.maryrosecook.com

+1 vote for a "raw raw code" link, all comments stripped.

capex2• 11 years ago

Very cool. Interesting bit: The outcomes of the falling balls seem to differ every time, which corroborates the fact that any minor change in initial state results in vastly different outcomes.

Edit: Or am I just imagining it?

jsprogrammer2• 11 years ago

~~The simulation clock is based on the actual frame rate achieved via requestAnimationFrame().~~

Edit: Actually, it looks like the physics portion takes constant (but implicit) time steps each frame, but the time that a circle enters the simulation is based on the actual frame rate, which means when a given circle appears, the lines could be in a different location from previous runs.

capex2• 11 years ago

Thank you.

taeric• 11 years ago

Trying to keep the narrative of explanation in the same linear order as the code makes for a surprisingly difficult to understand item. Would be neat to see more "traditional" literate programming techniques applied here.

All of that said, really cool, and seriously thank you for sharing!!

eru2• 11 years ago

I wonder if the weaving in literate code is one of the things that could only have been invented to deal with Pascal. It is useful to be able to rearrange the presentation even in JavaScript, but I doubt it would be enough of a pain point for people to invent weaving in an alternate history were literate programming was born on more flexible languages.

jostylr• 11 years ago

I wrote a literate-programming compiler to deal with JavaScript programming (any language works, but js is the one I use the most); it use markdown as the language in which the code is embedded.

For me, prototype setup and async stuff seemed to naturally lead me to want to differ in the ordering between how I write and how the program is laid out. I find it quite liberating to not care what order I write the code in, dashing off a substitution section to deal with later.

I know functions can be used to chunk out code in different orders, but I like the interplay of having it ordered in the writing in a sensible fashion while still getting the compiled view of it in the programmatic ordering.

Plus my version allows for a lot of finely tuned hacking on the language. That is, one can reduce a lot of boiler-plate setup with processing small chunks of code.

Having said all that, I would not use Knuth's original version for js. I think what was particularly attractive was a simple language like markdown for embedding code in a natural and simple way.

My main repo is https://github.com/jostylr/literate-programming though I am currently rewriting the engine behind it to allow for more asynchronous compiling https://github.com/jostylr/literate-programming-lib

hartror• 11 years ago

Neat!

Is the code annotation page a library?

mxtopher2• 11 years ago

Indeed. It's using docco, most likely: http://jashkenas.github.io/docco/

danso• 11 years ago

I believe the OP is using Docco.js (which has been ported to many languages, e.g. Rocco for Ruby, Shocco for Shell, Pycco for Python, Gocco for Go, etc.)

http://jashkenas.github.io/docco/

There's different ways to configure the output and layout...the Docco homepage uses a single-column format, whereas the OP uses the double-column format.

falcor84• 11 years ago

The manual function signatures are a bit annoying. In particular, why don't the author's comments include the parameters? I wonder if docco has an extension to create these automatically. I much prefer the docstrings, and the new type annotations in python, which make this much nicer.

mxtopher2• 11 years ago

so tick calls requestAnimationFrame that calls tick that... Doesn't it create an ever growing stack? Isn't there a way to do it with a while loop?

zerocrates• 11 years ago

It doesn't create an ever-growing stack.

tick calls requestAnimationFrame, tick returns, the browser waits for the next frame and calls tick...

Rusky• 11 years ago

requestAnimationFrame just queues up the callback for later, it doesn't actually call into it. There's no stack growth.

spullara• 11 years ago

Really useful if you want to play around with their code and share it with your kids, etc.

http://jsfiddle.net/yr64fy2o/1/

It is nice to be able to show someone directly how changing the various parameters affects the simulation.

hcarvalhoalves• 11 years ago

That's pretty educational.

OT: I'm not a game developer. What are the other patterns - besides the global state and mutation functions - that one can use for a game loop?

hemdawgz• 11 years ago

I don't have a specific answer for your question, but I know this site was written specifically for game programming patterns: http://gameprogrammingpatterns.com/contents.html

sago5• 11 years ago

Mostly modern game engines use an entity system[1], which is a form of database (global data, I guess, in as much as any database is).

The main loop then steps through each component (of which physics would be one) and lets it update the entity data for all entities.

This pattern took over from class/inheritance based architectures about 10 years ago.

There have been some suggestions that Functional Reactive Programming is a better approach. I've used it in some prototypes, but I couldn't scale it to engine-size, and I'm not aware of it having been used successfully for a full game engine.

So, this approach is pretty much it. You keep a database of state, then you run a system (the physics system, say) to update that database.

[1] http://t-machine.org/index.php/2007/09/03/entity-systems-are...

t3hprogrammer• 11 years ago

One of the "not good" explanations of this was probably mine (and I agree!) written many years ago [1]. I wish I could remember why my code ended up so much more complex.

[1] http://ericleong.me/research/circle-line

e0m2• 11 years ago

Wow great learning resource. I wish docco let you click functions to jump to their definition.

e0m2• 11 years ago

Uncle Bob would be proud!

moe2• 11 years ago

I hate this left/right code documentation fad with passion.

Making my eyes jump horizontally across the page every few lines is about the worst you can possibly do for readability.

Just keep the damn comments inline and use colors/font-faces/fold markers to make it readable.

seanmcdirmid4• 11 years ago

Do you also prefer footnotes and sidebars inline when reading articles?

These are standard typographical practices. I do set my comment color to super light so comments don't distract me too much when reading code, but I wish there was a better way.

wingerlang3• 11 years ago

How about toggle-able comments?

moe2• 11 years ago

Do you also prefer footnotes and sidebars inline when reading articles?

No. I prefer them at the bottom (that's why they're called footnote) and with a tooltip for convenience.

I don't see how that relates to the idiotic idea of scattering comments/code over two wide columns.

swhipple2• 11 years ago

Not the parent, but I prefer footnotes/sidenotes when reading physical texts, but prefer inline commentary when reading on the computer screen. Jumping up and down to read a footnote (either manually scrolling or with a hyperlink) or having the sidenotes take up a large percentage of the screen is disorienting for me.

It helps if the inline commentary is differently colored or in a separate box.

I also use light colors for comments when reading source code, but I personally prefer this over having them as footnotes or sidenotes.

clay_to_n• 11 years ago

I find it far more readable. Anyway, next to where you clicked Annotated Code there's a link for Raw Code which has the comments in-line if you prefer that. You can use an IDE or web editor to get the font colors nice.

mikeboydbrowne• 11 years ago

I think this is awesome but I think it's a little too spaced out. I like the side-by-side display (gives the code an approachable narrative) but I wish I had to scroll up and down (to remind myself of what's going on) less.

glhaynes• 11 years ago

On mobile it combines the sides together in a way that I find an appealing option. Screenshot: http://imgur.com/xRvDubc

Anybody know if there's an easy way to get something like the mobile view on desktop (without spoofing user agents, etc)?

Cogito• 11 years ago

The view will switch to this layout if you make the display window narrow enough (320px)

doco.css:202

/* ---------------------- Low resolutions (> 320px) --------------------- */
@media only screen and (min-width: 320px) {

wingerlang3• 11 years ago

Reminds me of a simple physics system I wrote a couple of years ago [0]. After writing a cloth simulation [1] I figured that all I needed to make them into collidable boxes was to have each dot collide with each line. I went in very very small steps, iterating each thing to ensure I understood it. The code was super verbose and I learned a lot from this about linear algebra, cross products, vector projection etc. I always planned to straighten the code out and do a proper writeup.

[0] https://www.youtube.com/watch?v=ud8NirjyLAA

[1] https://www.youtube.com/watch?v=G05M_Y6NQVM

thisjepisje• 11 years ago

The tearing is awesome, haven't seen that before in cloth simulations.

wingerlang3• 11 years ago

Thanks. If you find it enjoyable to watch I'd recommend you to do a youtube search because there's actually a lot of it.

As for the implementation, it is extremely simple. For anyone interested just do a search for "verlet cloth".

EDIT: I'd specifically recommend this one [0]. It looks quite simpler than many on youtube but it feels more real.

[0] http://web.media.mit.edu/~bandy/cloth/

choward• 11 years ago

Mostly useful, however a lot of the comments are unnecessary noise. And some could be eliminated with better naming, intermediate variables and refactoring.

chuckledog• 11 years ago

Nice code. Thank you. Are those ball-to-line collisions energy preserving? I believe they are... However it seems there might be an edge case, where moving a colliding circle until it no longer intersects the line, might cause it to skip past another line. Because of this, the lines should not intersect each other. Sorry to ramble but I love this sort of stuff. Collision detection is covered well in many game development texts.

cronin101• 11 years ago

circle.velocity.x -= 2 * dot * bounceLineNormal.x; circle.velocity.y -= 2 * dot * bounceLineNormal.y;

The collisions currently reverse the velocity of the circle relative to the line by subtracting to cancel and then subtracting again to negate.

I found a slightly nicer-looking effect can be gained by making the factor ~1.8 to simulate 20% energy loss in collisions.

Obviously, any magic numbers in the code are not relevant for its purpose of demonstrating a simple mathematical concept in a literary style. I'd love to see more examples of this kind around HN as it's a quick way to learn/refresh the odd concept.

rehevkor52• 11 years ago

Yeah he should be getting the starting & ending position of the ball during the tick, and determining whether that line intersects the other line. If it does, the intersection point should be found and the segment that goes past the line should be reflected over the normal, and the ball placed at the new endpoint of the reflected segment. And, of course, the velocity vector needs to be changed as well.

But... I guess this won't be the first time someone posts bad physics code on the internet and poses it as a good example.

jconley• 11 years ago

The challenge of the more accurate method you describe is balancing how much CPU is used to find the point in game time where a collision occurs because it is almost certainly at some point between your tick times. You have to perform the calculation at many units of time across the tick delta with the significance level you care about, with more calculations necessary as velocities of bodies increases.

Of course, this is what physics engines do, and why you should probably use one instead of reinventing the wheel.

In terms of showing how a game loop and really basic game physics works, however, this is a pretty clean and understandable example.

sago5• 11 years ago

Hmmm, you appear to have a high opinion of your ability to determne 'good physics code'. Unfortunately, just a high opinion, not a high ability.

The OPs code is fine. And was written by a she, not a he.

Your suggestion is what is sometimes called 'continuous' collision detection. It is needed in some cases, particular when the OP approach might miss collisions (less often for when knock-on-collisions are missed, since those are rarer). But that approach is not 'better' - it is far more time consuming (vastly more for 3d rigid bodies with angular velocity), and has a visual benefit in some cases (not in the OPs case - or at least you wouldn't see the difference).

But, of course, both approaches are very approximate and only intended to give the right feel. If you wanted to be even more accurate you would process your collisions by subdividing updates around the collision (a good pool-ball simulation does this, to model proper breaks). And you'd have to use different integrators than the 1st degree Newton update.

This process can keep going as far as you like. For physics systems I've worked on for modelling the behavior of rigid components in MotoGP bikes, the kinds of approximations you allow are very different to the physics engines I've built for commercial games. Neither are 'better' or 'worse' - a good programmer understands the requirements of their domain . To that extent, the OP's approach is fine, and powers the vast majority of the physics in current generation video games (most engines do support continuous collision detection, but it will be switched off for most rigid bodies in a scene, for performance).

zifnab06• 11 years ago

Just have to say, it gets more amusing with more balls and lines: https://zifnab.net/circles-bouncing-off-lines/

amolgupta• 11 years ago

would be interesting to plot the probability of a ball going to the right direction against the number of lines, when lines are moving clockwise or vice-versa.

dubya• 11 years ago

This looks glitchier than the original for some reason, probably just sheer numbers. Balls bouncing off the bottom of lines that are moving away appear to jump.

MarcScott• 11 years ago

I could have really done with this a few months ago. I was trying to make animations of electrons flowing through wires of variable thickness, and really struggled trying to find examples online. I ended up having a three hour maths lesson with my brother over irc, to get my head around vector maths.

ahoge• 11 years ago

In case anyone wonders about that reverse-for loop in updateCircles():

Iterating over an array in reverse allows you to remove items in the same iteration (at the very end of the loop). If you delete an item, the items which follow are downshifted by one which means that their indices also change.

However, this isn't a problem if you iterate in reverse, because you already took care of those items in previous iterations. The item you'll handle next will stay where it is.

This also works nice with unordered lists (or "bags").

Flow• 11 years ago

Here's a similar effect, from a 1994 C64 demo.

https://www.youtube.com/watch?v=SUQb_Oepa6o

graemian• 11 years ago

I assume the side-by-side view is rendered from the raw file with comments inline? Is this using some kind of comment markup language?

Where can I find out more about cool ways to render comments like this?

hey_lu• 11 years ago

It's generated using http://jashkenas.github.io/docco/. I think it's possible to use comments, but often it's "literate" source code, e.g. markup & code blocks.

tombh• 11 years ago

Same person that wrote gitlet[1], as seen on HN a few weeks ago. Personally I'm extremely happy to see HN so supportive of well commented and documented code.

[1] https://github.com/maryrosecook/gitlet

sago5• 11 years ago

I don't know if the OP reads this, but one very minor note about the core of the update loop. From the POV of the circles, it is effectively:

  for each circle:
    if circle is penetrating:
      apply collision impulse
      remove penetration
    integrate forces (gravity) to update velocity
    integrate velocity to update position
  for each circle:
    render circle

Because interpenetration is resolved before integration, the integration step can cause further interpenetration before rendering.

For this case, the effect of this is probably invisible (I couldn't see it). With slower moving objects, higher gravity, or less elastic collisions, this can cause objects to 'sag' or appear springy. A simple change in order helps:

  for each circle:
    integrate forces (gravity) to update velocity
    integrate velocity to update position
    if circle is penetrating:
      apply collision impulse
      remove penetration
  for each circle:
    render circle

A very minor thing, but something to remember when doing physics animations.

qznc2• 11 years ago

I do not understand. Since this is executed in a loop, for the circle it looks like ...-penetration-integration-penetration-integration-penetration-integration-... in either version. Why does it matter between which steps the circle is rendered?

sago5• 11 years ago

(Edit: I can be clearer, using your approach - more verbose explanation trimmed)

In the linked version we are doing

... move, draw, de-overlap, move, draw, de-overlap ...

So the move might cause an overlap, which we'd draw on screen. Having objects routinely interpenetrating a little (by a frame's worth) can appear springy, as if they aren't made of rigid material.

Better would be

... move, de-overlap, draw, move, de-overlap, draw ...

nightcracker• 11 years ago

In the original version it's possible that a penetrating object gets drawn, in the modified version penetrating objects are always resolved before the drawing happens.

adam-f• 11 years ago

I did the same thing a few years ago (scroll down past the tutorial/examples for the annotated code) http://sparecycles.github.io/litijs?template

(but litijs itself is an undocumented hack) http://sparecycles.github.io/litijs?litijs

pc86• 11 years ago

I love the look of the annotated code. I think it would be particularly useful for documentation.

Are there any tools that can generate this from comments, or perhaps an Eclipse or Visual Studio plugin that shows this type of documentation along with the code?

JeremyBanks• 11 years ago

This page was generated from comments using Docco: http://jashkenas.github.io/docco/

Annotated code: Circles bouncing off lines

Related Stories