Jump to content

  • Log In with Google      Sign In   
  • Create Account

Allen Chou

Member Since 15 Jul 2010
Offline Last Active Jun 01 2016 01:11 PM

#5291166 A Brain Dump of What I Worked on for Uncharted 4

Posted by on 11 May 2016 - 11:11 AM

Awesome thanks for sharing.  Would be nice to see this posted as an article.

Yes please, make it an article!  At least an overview pointing to the original if nothing else.  This post will get lost in all the complaining about Unity.

Sure. I just submitted it as an article.

#5291078 A Brain Dump of What I Worked on for Uncharted 4

Posted by on 11 May 2016 - 12:36 AM

This post is part of My Career Series.
Now that Uncharted 4 is released, I am able to talk about what I worked on for the project. I mostly worked on AI for single-player buddies and multiplayer sidekicks, as well as some gameplay logic. I'm leaving out things that never went in to the final game and some minor things that are too verbose to elaborate on. So here it goes:
The Post System
Before I start, I'd like to mention the post system we used for NPCs. I did not work on the core logic of the system; I wrote client code that makes use of this system.Posts are discrete positions within navigable space, mostly generated from tools and some hand-placed by designers. Based on our needs, we created various post selectors that rate posts differently (e.g. stealth post selector, combat post selector), and we pick the highest-rated post to tell an NPC to go to.
Buddy Follow
The buddy follow system was derived from The Last of Us.The basic idea is that buddies pick positions around the player to follow. These potential positions are fanned out from the player, and must satisfy the following linear path clearance tests: player to position, position to a forward-projected position, forward-projected position to the player.
Climbing is something present in Uncharted 4 that is not in The Last of Us. To incorporate climbing into the follow system, I added the climb follow post selector that picks climb posts for buddies to move to when the player is climbing.
It turned out to be trickier than I thought. Simply telling buddies to use regular follow logic when the player is not climbing, and telling them to use climb posts when the player is climbing, is not enough. If the player quickly switch between climbing and non-climbing states, buddies would oscillate pretty badly between the two states. So I added some hysteresis, where the buddies only switch states when the player has switched states and moved far enough while maintaining in that state. In general, hysteresis is a good idea to avoid behavioral flickering.
Buddy Lead
In some scenarios in the game, we wanted buddies to lead the way for the player. I ported over and updated the lead system from The Last of Us, where designers used splines to mark down the general paths we wanted buddies to follow while leading the player.
In case of multiple lead paths through a level, designers would place multiple splines and turned them on and off via script.
The player's position is projected onto the spline, and a lead reference point is placed ahead by a distance adjustable by designers. When this lead reference point passes a spline control point marked as a wait point, the buddy would go to the next wait point. If the player backtracks, the buddy would only backtrack when the lead reference point gets too far away from the furthest wait point passed during last advancement. This, again, is hysteresis added to avoid behavioral flickering.
I also incorporated dynamic movement speed into the lead system. "Speed planes" are placed along the spline, based on the distance between the buddy and the player along the spline. There are three motion types NPCs can move in: walk, run, and sprint. Depending on which speed plane the player hits, the buddy picks an appropriate motion type to maintain distance away from the player. Designers can turn on and off speed planes as they see fit. Also, the buddy's locomotion animation speed is slightly scaled up or down based on the player's distance to minimize abrupt movement speed change when switching motion types.
Buddy Cover Share
In The Last of Us, the player is able to move past a buddy while both remain in cover. This is called cover share.
In The Last of Us, it makes sense for Joel to reach out to the cover wall over Ellie and Tess, who have smaller profile than Joel. But we thought that it wouldn't look as good for Nate, Sam, Sully, and Elena, as they all have similar profiles. Plus, Uncharted 4 is much faster-paced, and having Nate reach out his arms while moving in cover would break the fluidity of the movement. So instead, we decided to simply make buddies hunker against the cover wall and have Nate steer slightly around them.
The logic I used is very simple. If the projected player position based on velocity lands within a rectangular boundary around the buddy's cover post, the buddy aborts current in-cover behavior and quickly hunkers against the cover wall.
Medic Sidekicks
I was in charge of multiplayer sidekicks, and I'd say medics are the most special among all. Medic sidekicks in multiplayer require a whole new behavior that is not present in single-player: reviving downed allies and mirroring the player's cover behaviors.
Medics try to mimic the player's cover behavior, and stay as close to the player as possible, so when the player is downed, they are close by to revive the player. If a nearby ally is downed, they would also revive the ally, given that the player is not already downed. If the player is equipped with the RevivePak mod for medics, they would try to throw RevivePaks at revive targets before running to the targets for revival; throwing RevivePaks reuses the grenade logic for trajectory clearance test and animation playback, except that I swapped out the grenades with RevivePaks.
Stealth Grass
Crouch-moving in stealth grass is also something new in Uncharted 4. For it to work, we need to somehow mark the environment, so that the player gameplay logic knows whether the player is in stealth grass. Originally, we thought about making the background artists responsible of marking collision surfaces as stealth grass in Maya, but found out that necessary communication between artists and designers made iteration time too long. So we arrived at a different approach to mark down stealth grass regions. I added an extra stealth grass tag for designers in the editor, so they could mark the nav polys that they'd like the player to treat as stealth grass, with high precision. With this extra information, we can also rate stealth posts based on whether they are in stealth grass or not. This is useful for buddies moving with the player in stealth.
Since we don't have listen mode in Uncharted 4 like The Last of Us, we needed to do something to make the player aware of imminent threats, so the player doesn't feel overwhelmed by unknown enemy locations. Using the enemy perception data, I added the colored threat indicators that inform the player when an enemy is about to notice him/her as a distraction (white), to perceive a distraction (yellow), and to acquire full awareness (orange). I also made the threat indicator raise a buzzing background noise to build up tension and set off a loud stinger when an enemy becomes fully aware of the player, similar to The Last of Us.
This is the last major gameplay feature I worked on before going gold. I don't usually go to formal meetings at Naughty Dog, but for the last few months before gold, we had a at least one meeting per week driven by Bruce Straley or Neil Druckmann, focusing on the AI aspect of the game. Almost after every one of these meetings, there was something to be changed and iterated for the investigation system. I went through many iterations before arriving at what we shipped with the final game.
There are two things that create distractions and would cause enemies to investigate: player presence and dead bodies. When an enemy registers a distraction (distraction spotter), he would try to get a nearby ally to investigate with him as a pair. The closer one to the distraction becomes the investigator, and the other becomes the watcher. The distraction spotter can become an investigator or a watcher, and we set up different dialog sets for both scenarios ("There's something over there. I'll check it out." versus "There's something over there. You go check it out.").
In order to make the start and end of investigation look more natural, I staggered the timing of enemy movement and the fading of threat indicators, so the investigation pair don't perform the exact same action at the same time in a mechanical fashion.
If the distraction is a dead body, the investigator would be alerted of player presence and tell everyone else to start searching for the player, irreversibly leaving ambient/unaware state. The dead body discovered would also be highlighted, so the player gets a chance to know what gave him/her away.
Under certain difficulties, consecutive investigations would make enemies investigate more aggressively, having a better chance of spotting the player hidden in stealth grass. In crushing difficulty, enemies always investigate aggressively.
Dialog Looks
This is also among the last few things I worked on for this project.Dialog looks refers to the logic that makes characters react to conversations, such as looking at the other people and hand gestures. Previously in The Last of Us, people spent months annotating all in-game scripted dialogs with looks and gestures by hand. This was something we didn't want to do again. We had some scripted dialogs that are already annotated by hand, but we needed a default system that handles dialogs that are not annotated, which I put together. The animators are given parameters to adjust the head turn speed, max head turn angle, look duration, cool down time, etc.
Jeep Momentum Maintenance
One of the problems we had early on regarding the jeep driving section in the Madagascar city level, is that the player's jeep can easily spin out and lose momentum after hitting a wall or an enemy vehicle, throwing the player far behind the convoy and failing the level.
My solution was to temporarily cap the angular velocity and change of linear velocity direction upon impact against walls and enemy vehicles. This easy solution turns out pretty effective, making it much harder for players to fail the level due to spin-outs.
Vehicle Deaths
Driveable vehicles are first introduced in Uncharted 4. Previously, only NPCs can drive vehicles, and those vehicles are constrained to spline rails. I was in charge of handling vehicle deaths.There are multiple ways to kill enemy vehicles: kill the driver, shoot the vehicle enough times, bump into an enemy bike with your jeep, and ram your jeep into an enemy jeep to cause a spin-out. Based on various causes of death, a death animation is picked to play for the dead vehicle and all its passengers. The animation blends into physics-controlled ragdolls, so the death animation smoothly transitions into physically simulated wreckage.
For bumped deaths of enemy bikes, I used the bike's bounding box on the XZ plane and the contact position to determine which one of the four directional bump death animations to play.
As for jeep spin-outs, I test the jeep's rotational deviation from desired driving direction against a spin-out threshold.
When playing death animations, there's a chance that the dead vehicle can penetrate walls. I used a sphere cast, from the vehicle's ideal position along the rail if it weren't dead, to where the vehicle's body actually is. If a contact is generated from the sphere cast, I shifted the vehicle in the direction of the contact normal by a fraction of penetration amount, so the de-penetratiton happens gradually across multiple frames, avoiding positional pops.
I did a special type of vehicle death, called vehicle death hint. They are context-sensitive death animations that interact with environments. Animators and designers place these hints along the spline rail, and specify entry windows on the splines. If a vehicle is killed within an entry window, it starts playing the corresponding special death animation. This feature started off as a tool to implement the specific epic jeep kill in the 2015 E3 demo.
Bayer Matrix for Dithering
We wanted to eliminate geometry clipping the camera when the camera gets too close to environmental objects, mostly foliage. So we decided to fade out pixels in pixel shaders based on how close the pixels are to the camera. Using transparency was not an option, because transparency is not cheap, and there's just too much foliage. Instead, we went with dithering, combining a pixel's distance from the camera and a patterned Bayer matrix, some portion of the pixels are fully discarded, creating an illusion of transparency.
Our original Bayer matrix was an 8x8 matrix shown on this Wikipedia page. I thought it was too small and resulted in banding artifacts. I wanted to use a 16x16 Bayer matrix, but it was no where to be found on the internet. So I tried to reverse engineer the pattern of the 8x8 Bayer matrix and noticed a recursive pattern. I would have been able to just use pure inspection to write out a 16x16 matrix by hand, but I wanted to have more fun and wrote a tool that can generate Bayer matrices sized any powers of 2.
After switching to the 16x16 Bayer matrix, there was a noticeable improvement on banding artifacts.
Explosion Sound Delay
This is a really minor contribution, but I'd still like to mention it. A couple weeks before the 2015 E3 demo, I pointed out that the tower explosion was seen and heard simultaneously and that didn't make sense. Nate and Sully are very far away from the tower, they should have seen and explosion first and then heard it shortly after. The art team added a slight delay to the explosion sound into the final demo.
Traditional Chinese Localization
I didn't switch to Traditional Chinese text and subtitles until two weeks before we were locking down for gold, and I found some translation errors. Most of the errors were literal translations from English to Traditional Chinese and just did't work in the contexts. I did not think I would have time to play through the entire game myself and look out for translation errors simultaneously. So I asked multiple people from QA to play through different chapters of the game in Traditional Chinese, and I went over the recorded gameplay videos as they became available. This proved pretty efficient; I managed to log all the translation errors I found, and the localization team was able to correct them before the deadline.
That's It
These are pretty much the things I worked on for Uncharted 4 that are worth mentioning. I hope you enjoyed reading it. :)

#5242536 DigiPen: The Game School I Went To

Posted by on 24 July 2015 - 08:14 PM

Original Blog Post


Disclaimer: This post is all about my personal experience with DigiPen and is in no way intended to represent anyone else’s experience or opinions.

I went to DigiPen Institute of Technology to learn how to make games in 2011, and graduated last year (2014). I graduated one year earlier than my fellow classmates in the same year, because I transferred in some credits I had already earned at my previous college in Taiwan.

I have written one post about my life at DigiPen every year on a game design forum in Taiwan. Also, many of my DigiPen friends just graduated and have started their jobs in the game industry. So I thought, why not write a dedicated post about my experience at DigiPen in English on my blog?


Finding & Choosing DigiPen

When I was almost done with my bachelor’s degree in Electrical Engineering at my first college in Taiwan, I blindly followed what most of my other peers did: looking for a master’s program in the US to advance further in academia. As I was combing through the overwhelming amount of resources on the internet over a few days, an idea deep in my mind struck me: I chose a program in Electrical Engineering because it had always been my dream to make games, and Electrical Engineering was the closest I could get in Taiwan (next to Computer Science). So why on earth was I blindly searching for a path confined within academia, just because everyone else was doing the same thing? After four years of college, I numbed my senses and got lost a little, forgetting my original dream. Hadn’t I played the Jak & Daxter trilogy and made Naughty Dog my dream company in high school? Stupid. Stupid. Stupid!

So I threw away all my research on master’s programs, and simply started Googling “game school”. Several results turned up, and DigiPen was among them. I did some research and comparison on different curriculums and programs. As I learned about the vast number of various game-related courses there were, I became more and more convinced that a 2-year master’s program would not be long enough for what I wanted to learn. I ultimately chose DigiPen, which provides several 4-year undergrad programs, a learning environment exclusively for making games, and a large number of students in each year, which is a big enough pool to look for people to form a game team.

This wasn’t an easy decision to share with my parents. One stereotype about Chinese parents is unfortunately true: many Chinese parents expect successful academic progression from their kids, so they encourage – sometimes even force – kids to pursue higher degrees in academia. As far as I know, going for a second bachelor’s degree after already having earned one was unheard of in my circle. Fortunately for me, my parents are very reasonable people. After confirming with me for probably the fifth time that I was determined to do this, they finally said: “If going to this game school is really what you want, then you have our full support.” And I am forever grateful for their generous support.


DigiPen Is A Very Hard School

I will never forget the opening speech given by DigiPen’s president, Mr. Claude Comair, at the orientation.

“Look to your left. Look to your right. You won’t be seeing at least one of the people you just saw when you graduate…or not.”

This, as I learned later, is a very true statement, and he says it every year! Learning to make games at DigiPen is much more demanding than many people think. A quarter of freshmen can’t finish the first semester every year, and only about half of the students graduate on time; it’s worth mentioning, though, that some students choose to drop out because they have accepted job offers before finishing school.

Students are expected to attend classes and finish assignments just like regular college students do. However, on top of that, students need to use their own free time to work on game projects with a team. There are two game projects in the freshman year (one per semester), and one game project per year after that. Students can opt to intern at game companies instead of participating in student game projects in the final year.

Based on my experience, the things you learn from school, only account for 20% of the basic knowledge you need in the industry. What about the other 80%? You learn by forming study groups, conducting personal research and projects, attending club lectures, going to workshops, and last but not least, meeting with peers and professors. I learned about game physics and game engine architecture mostly through club lectures and research with peers.


Various Programs at DigiPen

When I started at DigiPen, there were 5 major undergrad programs, listed below. DigiPen has since added several new programs, including two sound & music programs for games.

  • Bachelor of Science in Real-Time Interactive Simulation (RTIS)
    This is basically a standard Computer Science program, plus extra courses focusing on game technology. The name of the program was changed during my sophomore year to Bachelor of Science in Computer Science in Real-Time Interactive Simulation, shortened BSCSRTIS, which is still quite a mouthful.
  • Bachelor of Science in Game Design (BSGD)
    Game design techniques, focusing more on the technical side of game design, e.g. scripting, gameplay programming.
  • Bachelor of Art in Game Design (BAGD)
    Similar to BSGD, but focusing more on the art side of game design, e.g. level design.
  • Bachelor of Fine Arts (BFA)
    As the name suggests, game arts.
  • Bachelor of Science in Computer Engineering (BSCE)
    Electrical engineering. Hardware stuff.

I was an RTIS student, so I have a better understanding of the RTIS program.



DigiPen is a 3-story building. On the first floor, there’s a cafeteria, some classrooms, including several bigger lecture halls, and a library (although not very large) full of books about making games (programming, art, game design, game history, you name it). You can also borrow games and various gaming hardwares from the library (for research purposes of course). On the second and third floors, there are more classrooms and the most important space of the school: the open lab.

The open lab consists of a big open space with tables and hundreds of computers. Students can use these computers to work on their assignments and game projects. Most game teams would stake out team spaces and use them throughout a game project cycle. In my first two years at DigiPen, I went to school at 9 in the morning and left around 11 at night almost every day. When I wasn’t in a class, I would be sitting in my team space, working on assignments, game projects, or conducting research. Good times.


Game Projects

Game projects account for special “game credits”. Throughout each project cycle, students have real milestones (Engine Proof, Prototype, First Playable, Alpha, Beta, and Gold), just like the industry. Upon each milestone, DigiPen’s game professors gather and sit through milestone presentations by every single team, usually non-stop throughout a couple days. Presentations are scored, and projects are also rated based on completion of Technical Certification Requirements (TCRs) and Design Certification Requirements (DCRs), all based on common industry standards.

These are very solid practices for presentation skills. During my first milestone presentation, I was so nervous that I sweated and trembled ridiculously. During my last presentation, not to brag, I was as calm as a pro.

We also learned to scope our games, as well as making the hard decision of cutting features before milestones.

In order to let students get a better taste of the industry, students are allowed to jump from one team to another; on the other hand, teams can hire or fire students. Students also have the option to go solo. If the game professors decide that a student has spent too much time without a team or a solo project, they can fail the student for game credits. A game team can also fail game credits if their game ends up incomplete.

A typical student game team consists of programmers from the RTIS program, a couple game designers from the BSGD or BAGD programs, some artists from the BFA program, and a producer. Producers have weekly meetings with game professors to learn production skills and discuss progress on the game projects.

Game teams can schedule a “team-on-one” with one of the game professors. A team-on-one is a 4-hour session with a professor, where everyone sits down, eats snacks, and talks about the game project casually. This is sort of like a reality check for the game project and a good chance to fix communication problems within the team, utilizing various team exercises. After every session, I always felt like my mind had been refreshed and my motivation rebooted.



Unlike ordinary colleges, most of the clubs at DigiPen are either about playing games or making games: Board Game Club, Shooting Game Club, Fighting Game Club, Game Graphics Club, Game Physics Club, Game Engine Architecture Club, etc.

Among them is a special club called the Playtesting Club. They hold playtesting sessions twice a week in the afternoon, setting up games on the computers in the open lab. Game teams can participate by putting up their games and let other students play. Playtesting sessions are valuable time spent in getting precious feedback on your game from fellow classmates. By the way, you can get a voucher for a free entree from the cafeteria if you playtest three games. Why wouldn’t you participate?


Integration with Industry

DigiPen has a very tight relationship with the game industry. Many of the faculty are industry veterans; some are still in the industry and teaching at DigiPen part-time.

Spring breaks and fall breaks are always aligned with the Game Developer Conference (GDC) and the Electronic Entertainment Expo (E3), so students and faculty are free to attend these important industry events.

I cannot stress enough the importance of attending GDC. You can make professional connections there, and it is a great place for job hunting. My current job at Naughty Dog would not have been possible had I not run into Naughty Dog’s recruiter at GDC in 2013. I also write down some GDC social tips; if you’re interested, you can check them out here and here.


Career First

If there’s one thing at DigiPen that is more important than preparing students for the industry, it is putting them into the industry. This is a general consensus among faculty. A student’s opportunity to break into the industry takes top priority.

For instance, my on-site interview with Naughty Dog coincided with a midterm. My professor thought the interview was much more important than her midterm, so she let me go to the interview and take the midterm another day without penalty. I also missed some other classes that day, and all professors were totally fine with it.


Career Services Center

In my opinion, the Career Services Center is one of the best resources DigiPen provides.

You can schedule a meeting with a dedicated professional at the center. During the meeting, you can discuss how to write your resume, design your website and business cards, practice interviews, and so much more. I went to over 20 meetings before I finalized my resume, personal website, and business cards.

When I had my phone interviews with Naughty Dog, they kindly let me borrow a meeting room. They also helped me draft a very professional-looking turn-down letter to a Microsoft offer I received.

Almost every week, the Career Services Center would invite a game company over to the school’s biggest lecture hall for a “company day”. They would talk about the company and what they look for in job applicants. Sometimes, companies even hold interviews right on-campus!

The school holds various workshops, some designed for current events. For instance, most DigiPen students are quite shy; in one of my years at DigiPen, a few weeks before GDC, where people get socialized and make connections with people from the industry, they invited some people from the industry and held a miniature mixer to let students practice having conversations with professional game developers. Every now and then, they also hold workshops focusing on self-presentation, helping students understand how to appear more professional with their social skills, resumes, websites, business cards. I really learned a lot of great tips from these workshops, including how to tailor resumes to specific companies, and what to look out during interviews.

I recently learned that the school has started officially offering classes dedicated to professional communication taught by Sonia Michaels, including everything from resumes to business cards to professional networking and, of course, conference behavior.

The Career Services Center is also responsible for DigiPen’s annual career fair, which is famous for being quite different from regular colleges. Instead of having students walking around company booths, students set up booths and recruiters walk around to hunt for prospective hires. It is not uncommon for a student to end up with multiple job offers after the career fair.

The placement rate of the RTIS program in the past four years ranges from 84% to 90%, i.e. at least 8 out of 10 RTIS students graduated with a job offer already in hand in the past four years.


The End

These are the things I have to say about DigiPen off the top of my head.

I’ll end with a list of my friends from DigiPen, most of whom recently graduated and got jobs, in case you would like to follow them.

#5225609 Game Math: More on Numeric Springing

Posted by on 26 April 2015 - 02:39 AM

Original Blog Post with Pretty Equations
This post is part of my Game Math Series.  
Previously, I talked about numeric springing and provided some examples.  
I have been saving up miscellaneous topics I would like to discuss about numeric spring, and now I have enough to write another post. Here are the topics:  
1. Using The Semi-Implicit Euler Method  
2. Numeric Springing vs. Tweening  
3. Half-Life Parameterization  
Using The Semi-Implicit Euler Method
Recall the differential equation for a damped spring:  
(d^2 x)/(d t^2) + 2 zeta omega (d x)(d t) + omega^2 (x - x_t) = 0  
And the equations for simulating such system obtained by the implicit Euler method:  
x_{i+1} &= Delta_x / Delta  
v_{i+1} &= Delta_v / Delta  
Delta = (1 + 2 h zeta) + h^2 omega^2  
Delta_x = (1 + 2 h zeta omega) x_i + h v_i + h^2 omega^2 x_t  
Delta_v = v_i + h ^2 (x_t - x_i)  
I presented the equations obtained by the implicit Euler method, because they are always stable. We can obtain a different set of equations that can also be used to simulate a damped spring system by the semi-implicit Euler method[/b]:  
v_{i+1} = (1 - 2 h zeta omega) v_i + h omega^2 (x_t - x_i)  
x_{i+1} = x_i + h v_{i+1}  
The equations obtained by the semi-implicit Euler method involve much less arithmetic operations, compared to the equations obtained by the implicit Euler method. There is a catch: the equations obtained by the semi-implicit Euler method can be unstable under certain configurations and the simulation will blow up over time. This can happen when you have a large zeta and omega. However, the zeta and omega on most use cases are far from the breaking values. You would almost never use an overdamped spring, so zeta is usually kept under 1. Even if zeta is set to 1 (critically damped spring), omega can be safely set up to 10 pi (5Hz), which is a very fast oscillation you probably would never use on anything.  
So, if your choice of zeta and omega result in a stable simulation with the equations obtained by the semi-implicit Euler method, you can use them instead of the equations obtained by the implicit Euler method, making your simulation more efficient.  
Here's a sample implementation:  
      x     - value             (input/output)
      v     - velocity          (input/output)
      xt    - target value      (input)
      zeta  - damping ratio     (input)
      omega - angular frequency (input)
      h     - time step         (input)
    void SpringSemiImplicitEuler
      float &x, float &v, float xt, 
      float zeta, float omega, float h
      v += -2.0f * h * zeta * omega * v 
           + h * omega * omega * (xt - x);
      x += h * v;
Numeric Springing vs. Tweening
Numeric springing and tweening (usually used with the famous Robert Penner's easing equations[\url] might seem very similar at first, as they are both techniques to procedurally animate a numeric value towards a target value; however, they are actually fundamentally different. Tweening requires a pre-determined duration; numeric springing, on the other hand, does not have such requirement: numeric springing provides a simulation that goes on indefinitely. If you were to interrupt a procedural numeric animation and give it a new target value, numeric springing would handle this gracefully and the animation would still look very natural and smooth; it is a non-trivial task to interrupt a tweened animation, set up a new tween animation towards the new target value, and prevent the animation from looking visually jarring.  
Don't get me wrong. I'm not saying numeric springing is absolutely superior over tweening. They both have their uses. If your target value can change dynamically and you still want your animation to look nice, use numeric springing. If your animation has a fixed duration with no interruption, then tweening seems to be a better choice; in addition, there are a lot of different easing equations you can choose from that look visually interesting and not necessarily have a springy feel (e.g. sine, circ, bounce, slow-mo).  
Half-Life Parameterization
Previously, I proposed a parameterization for numeric springing that consisted of 3 parameters: the oscillation frequency f in Hz, and the fraction of oscillation magnitude reduced p_d over a specific duration t_d due to damping.  
I have received various feedback from forum comments, private messages, friends, and colleagues. The most suggested alternative parameterizatoin was the half-life parameterization, i.e. you specify the duration when the oscillation magnitude is reduced by 50%. This seems like a fair suggestion; thus, I'll to show you how to derive zeta to plug into numeric springing simulations, based on a given half-life.  
I'll use lambda to denote half-life. And yes, it is the same symbol from both Chemistry and the game.  
As previously discussed, the curve representing the oscillation magnitude decreases exponentially with this curve:  
x(t) = e^ {-zeta omega t}  
By definition, half-life is the duration of reduction by 50%:  
x(lambda) = e^ {-zeta omega lambda} = 0.5  
So we have:  
zeta omega = -ln(0.5) / lambda  
Once we decide the desired lambda, we lock in omega and compute zeta:  
zeta = -ln(0.5) / (omega lambda)  
And here's a sample implementation:  
    void SpringByHalfLife
      float &x, float &v, float xt, 
      float omega, float h, float lambda
      const float zeta = (-lambda / omega) * ln(0.5f);
      Spring(x, v, xt, zeta, omega, h);
Here's a graph showing lambda = 0.5 and omega = 4 pi (2Hz). You can clearly see that the oscillation magnitude is reduced by 50% every half second, i.e. 25% every second.  
I've discussed how to implement numeric springing using the faster but less stable semi-implicit Euler method, the difference between numeric springing versus tweening, and the half-life parameterization of numeric springing.  
I hope this post has given you a better understanding of various aspects and applications of numeric springing.

#5222628 Game Math: Numeric Springing Examples

Posted by on 11 April 2015 - 11:52 AM

This post is part of my Game Math Series.  
So, you have seen how to precisely control numeric springing in my previous post.  
I showed this animation as an example.  
Letting artists manually fine-tune the animation with animation curves probably will give better results, if it's fixed animation, that is.  
One big advantage of numeric springing over animation curves is that it can be dynamic and interactive. I will show you several examples in this post.  
Before that, let's quickly review the spring function presented in my previous post.  
      x     - value             (input/output)
      v     - velocity          (input/output)
      xt    - target value      (input)
      zeta  - damping ratio     (input)
      omega - angular frequency (input)
      h     - time step         (input)
    void Spring
      float &x, float &v, float xt, 
      float zeta, float omega, float h
      const float f = 1.0f + 2.0f * h * zeta * omega;
      const float oo = omega * omega;
      const float hoo = h * oo;
      const float hhoo = h * hoo;
      const float detInv = 1.0f / (f + hhoo);
      const float detX = f * x + h * v + hhoo * xt;
      const float detV = v + hoo * (xt - x);
      x = detX * detInv;
      v = detV * detInv;
Positional Springing  
We can dynamically set the target position based on user input and have object spring to the target position accordingly.  
Here's the code for this example:
    void OnButonClicked(int buttonIndex)
      obj.targetY = buttons[buttonIndex].positionY;
      obj.velocityY = 0.0f;
    void Update(float timeStep)
        obj.positionY, obj.velocityY, obj.targetY, 
        zeta, omega, timeStep
Rotational Springing  
Numeric springing can also be used to make a pointer try align itself to the mouse cursor.  
Here's the code for this example:  
    void Init()
      obj.angle = 0.0f;
      obj.angularVelocity = 0.0f;
    void Update(float timeStep)
      obj.targetAngle = 
        Atan2(obj.positionY - mouse.y, obj.positionX - mouse.x);
        obj.angle, obj.angularVelocity, obj.targetAngle, 
        zeta, omega, timeStep
Animation Springing  
We can even apply numeric springing to the frame number of an animation, creating a dynamic animation that has a springy feel.  
Giving this animation below:  
If we apply numeric springing to the frame number shown based on the mouse position, we get this effect:  
Pretty neat, huh?  
And here's the code for this example:  
    void Init()
      x = 0.0f;
      v = 0.0f;
    void Update(float timeStep)
      xt = mouse.x;
        x, v, xt, 
        zeta, omega, timeStep
      obj.frame = int(obj.numFrames * (x / window.width));
Orientational Springing  
Lastly, let's bring numeric springing to the third dimension.  
Here's the code for this example:  
    void Init()
      angle = 0.0f;
      angularVelocity = 0.0f;
      targetAngle = 0.0f;
      tiltDirection.Set(0.0f, 0.0f, 0.0f);
    void Update(float timeStep)
      if (mouse.isPressed) // true for one frame pressed
        pressPosition.x = mouse.x;
        pressPosition.y = mouse.y;
      if (mouse.isDown) // true when held down
        const float dx = mouse.x - pressPosition.x;
        const float dy = mouse.y - pressPosition.y;
        tiltDirection.Set(dx, 0.0f, dy);
        targetAngle = Sqrt(dx * dx + dy * dy);
        angle, angularVelocity, targetAngle, 
        zeta, omega, timeStep
      const Vector axis = Cross(yAxis, tiltDirection);
      obj.orientation = OrientationFromAxisAngle(axis, angle);
End of Numeric Springing Examples  
That's it!  
I hope these examples have inspired you to get creative with numeric springing. :)  

#5222083 Game Math: Precise Control over Numeric Springing

Posted by on 08 April 2015 - 10:11 AM

This post is part of my Game Math Series.
Numeric springing is a very powerful tool for procedural animation. You specify the initial value, initial velocity, target value, and some spring-related parameters; the result is a smooth springing effect. You can apply this technique to all sorts of numeric properties, some common ones being position, rotation, and scale of an object.
The Common But Designer-Unfriendly Way
Here is a common, yet designer-unfriendly, implementation of numeric springing. Let x_i and v_i denote the numeric value and velocity, respectively, at frame i; and let k, d, h, x_t, denote the spring stiffness, damping factor, time step between frames, and target value, respectively.   
    v_{i+1} = d * v_i + h * k * (x_t - x_i)  
    x_{i+1} = x_i + h * v_{i+1}  
Let's dissect this implementation.  
The difference between the target value and the current value (x_t - x_i) contributes to the velocity change after multiplied by the spring stiffness k. The larger the difference and spring stiffness, the larger the change in velocity.  
The new velocity v_{i+1} inherits the value from the old velocity v_i scaled by the damping factor d, which should be a value between zero and one. If the damping factor is equal to one, then no scaling happens, and the new velocity completely inherits the value from the old velocity. If the damping factor is a fraction of one, then the magnitude of oscillation will decrease gradually.  
That seems all reasonable and good, but just what exactly are the values for k and d do we need to achieve a specific springing effect, say an oscillation at 5Hz frequency and the oscillation magnitude decreases 90% every one second? Many people just decide to bite the bullet and spend a large amount of time hand-tweaking the values for k and d, until the result is acceptably close to the desired effect.  
We Can Be Exact
Now let's take a look at the differential equation for a damped spring system centered around x = x_t.  
    x'' + 2 * zeta * omega * x' + omega^2 * (x - x_t) = 0,   
I won't go into details as to how this equation is derived. All you really need to know is that omega and governs how the system behaves and what they mean.  
Omega is the angular frequency of the oscillation. An angular frequency of 2 pi (radians per second) means the oscillation completes one full period over one second, i.e. 1Hz.  
Zeta is the damping ratio. A damping ratio of zero means there is no damping at all, and the oscillation just continues indefinitely. A damping ratio between zero and one means the spring system is underdamped; oscillation happens, and the magnitude of oscillation decreases exponentially over time. A damping ratio of 1 signifies a critically damped system, where this is the point the system stops showing oscillation, but only converging to the target value exponentially. Any damping ratio above 1 means the system is overdamped, and the effect of springing becomes more draggy as the damping ratio increases.  
Here's a figure I borrowed form Erin Catto's presentation on soft constraints, to show you the comparison of undamped, underdamped, critically damped, and overdamped systems.  
Below are the equations for simulating a damped spring system using the implicit Euler method.  
    x_{i+1} = x_i + h * v_{i+1}  
    v_{i+1} = v_i - h * (2 * zeta * omega v_{i+1}) - h omega^2 * (x_{i + 1} - x_t)  
Solving x_{i+1} and v_{i+1} in terms of x_i and v_i using Cramer's rule, we get:  
    x_{i+1} = Delta_x / Delta  
    v_{i+1} = Delta_v / Delta  
    Delta = (1 + 2 * h * zeta * omega) + h^2 * omega^2  
    Delta_x = (1 + 2 h * zeta * omega) x_i + h * v_i + h^2 * omega^2 * x_t  
    Delta_v = v_i + h * omega^2 * (x_t - x_i)  
Below is a sample implementation in C++. The variables x and v are initialized once and then passed into the function by reference every frame, where the function keeps updating their values every time it's called.  
      x     - value             (input/output)
      v     - velocity          (input/output)
      xt    - target value      (input)
      zeta  - damping ratio     (input)
      omega - angular frequency (input)
      h     - time step         (input)
    void Spring  
      float &x, float &v, float xt, 
      float zeta, float omega, float h  
      const float f = 1.0f + 2.0f * h * zeta * omega;  
      const float oo = omega * omega;  
      const float hoo = h * oo;  
      const float hhoo = h * hoo;  
      const float detInv = 1.0f / (f + hhoo);  
      const float detX = f * x + h * v + hhoo * xt;  
      const float detV = v + hoo * (xt - x);  
      x = detX * detInv;  
      v = detV * detInv;  
Designer-Friendly Parameters
Now we have our formula and implementation all worked out, what parameters should we expose to the designers from our spring system so that they can easily tweak the system?  
Inspired by the aforementioned presentation by Erin Catto, I propose exposing the oscillation frequency f in Hz, and the fraction of oscillation magnitude reduced p_d over a specific duration t_d due to damping.  
Mapping f to omega is easy, you just multiply it by 2 pi:  
    omega = 2 * pi * f  
Mapping p_d and t_d to zeta is a little bit more tricky.  
First you need to understand that the oscillation magnitude decreases exponentially with this curve:  
    y(t) = e^{-zeta * omega * t}  
After plugging in p_d and t_d, we get:  
    y(t_d) = e^{-zeta * omega * t_d} = p_d  
So we can solve for zeta:  
    zeta = ln(p_d)} / (-omega * t_d)  
For example, if we want the oscillation to reduce 90% (p_d = 0.1) every 0.5 second (t_d = 0.5) with oscillation frequency 2Hz (omega = 4 pi), then we get:  
    zeta = ln(0.1)} / (-4 * pi * 0.5) = 0.367  
Numeric springing is a very powerful tool for procedural animation, and now you know how to precisely control it. Given the desired oscillation frequency and percentage of oscillation magnitude reduction over a specific duration, you can now compute the exact angular frequency omega and damping ratio zeta necessary to create the desired springing effect.  
By the way, let's look at the animated example shown above again:  
This animation was created with omega = 8 pi (4 full oscillation periods per second) and zeta = 0.23 (oscillation magnitude reduces 99.7% every second).  

#5206519 GDC Social Tips

Posted by on 25 January 2015 - 04:24 AM

Hi, all:
I wrote some GDC social tips on my blog. I hope you find this useful smile.png
Blog Post Link
I wrote some tips on meeting people at GDC a while ago. It was the GDC that lead me to my current job (more on this here). Recently, I got some friends asking me for advice on breaking into the game industry, how to present yourself, and how to meet people at GDC. So I decided to write another post about it. This will be a collection of what I learned from the Career Service Center and the career workshops at DigiPen, plus my own experience.
These tips worked for me, but they might not suit everyone. Feel free to disregard any of them at your discretion.
Email, Twitter, Domain Name
Before doing anything else, you should have a professional-looking email address. Don't use random internet names like AwesomeDude7345; that makes your address look unprofessional. Make sure the only thing present in the name part of the address is your name. The email address I share with people is MingLun.Chou[at]gmail.com.
Applying the same rule to your Twitter handle and domain name can help them appear more professional as well. My Twitter handle is TheAllenChou, and my domain name is AllenChou.net. Of course, you can always throw in some variation if that helps express more about yourself, such as JasonGameDev.net or AmysArt.net.
Get a LinkedIn account, period. LinkedIn is a professional social network where you can build online professional connections. You can join groups and follow companies on LinkedIn. Your profile page is the place to show people your professional side; maintain it well. Many recruiters actively look for potential hires on LinkedIn by going through his/her 1st, 2st, and 3rd degree connections. It is important that you build connections with people in the industry on LinkedIn. I constantly receive messages on LinkedIn from recruiters in the game industry and software engineering industry.
You can customize your LinkedIn profile page's URL. Choose one that follows the aforementioned rule for your email address. My LinkedIn profile page URL is linkedin.com/in/MingLunChou.
Business Cards
Always keep a stack of business cards with you, so you are prepared when the time has come for you to exchange contact information, or when you just want to present yourself to others. To make yourself appear more professional, use a card holder. It looks much more professional to pull out business cards from a card holder than from a jeans pocket.
After you give someone your business card and leave, that person might want to write down some notes about you on your business card, so they can still remember you after meeting many other people at GDC. Choosing a material that is easy to write on for your business card would make this process easier, as well as using a light color on the back of your card and leaving some writing space.
Make sure your name is the most noticeable text element on your business card. If you want to, just use a few stand-alone words to describe your profession. Don't try to squeeze a wall of text that describes every positive thing you have to say about yourself. Once I received a card with a wall of text, saying how passionate a designer the person is and his many holy life goals as a designer. I read the first few sentences and put the card away, never bothering finishing it. This is a business card, not a cover letter.
Below is my current business card design. My name is the largest text element and is at the direct center. I put down four of my primary professional skills (Physics, Graphics, Procedural Animation, and Visuals) below my name. My contact information is at the bottom, including my website URL, email address, LinkedIn profile URL, Twitter handle, and Google+ handle.
Most recruiters prefer resumes with only one page, but some recruiters prefer two pages. So I just keep my resume one-page.
If you want to send a resume to a company that you are applying for, always tailor the resume to fit the company. One company, one specific resume. Look for the requirements for the position you are applying for on the company's website, and make sure they are the first things on your resume. Also, do not forget to include an objective line that states the position you intend to apply for.
In addition, prepare a generic version of the resume. This way, you can show it on your website, and present it at the company booths in the expo hall at GDC.
Personal Branding
Personal branding is optional, but it is a powerful tool if done right.
I put down Long Bunny, a little character I designed, on my business cards, resumes, and this website.
At first, I designed Long Bunny just for fun, because I love bunnies. Then, I thought I could fill it in the extra space on my business cards and resumes. This turned out to be the right thing to do, and Long Bunny became my personal branding.
On a Sucker Punch company day at DigiPen, I gave the recruiter my business card and resume. The next time I talked to her at another company day one year later, she did not recognize me at first. But after I showed her my business card, she instantly remembered me, saying it's because of the Long Bunny. Also, in all my follow-up emails (a separate tip that will be covered later), I start with "Hi, I'm Allen Chou. My business card has a long bunny on it." Most people would remember me because of my personal branding.
The W Hotel Lobby
At GDC, it is well known that many attendees who want to socialize and do not have a party to go to will hang out at the lobby bar of The W Hotel. If you want to meet people from the game industry at GDC and have no party on your list, then The W Hotel is the place to go. My friends and I usually come back from the afternoon GDC activities to our hotel and chill out until 8pm. Then we would head out to The W Hotel's lobby bar. That is where we meet new people from the industry and introduce ourselves. We usually stay there at least until 11pm, and would stay longer if we are in a long conversation.
Starting A Conversation
The hardest part to meeting people is to start a conversation. The first time I went to GDC, I was too shy to walk up to a stranger and start talking. This is a skill you must practice if you want to meet people.
There is really nothing scary about opening a conversation. Almost everyone at The W Hotel's lobby bar during GDC is in the game industry, very laid back, and welcomes conversations. Just pick someone that does not seem to be occupied, say hi, and introduce yourself. I usually start with what I do and then ask what the other person does, and then at some point casually ask for a business card exchange, either by saying "here's my business card" or "hey, do you have a business card?" It's that simple.
If you feel like the conversation needs to be ended, either because the other person appears to be not interested in talking any more, or you are running out of things to say, say "nice meeting/talking to you", "I'm gonna take off", and leave. No hassle.
Following up with an email is very important after obtaining contact information. After the person that has given you his/her business card leaves, write down notes about the conversation you had and reminders for sending the person your work or resumes (if asked). Within 48 hours, write an email to re-introduce yourself, make comments on the conversation, and thank the person for talking to you. This shows that you care. Also, be sure to connect with the person on LinkedIn if you can find his/her page.
I always bring a tablet with me to GDC, loaded with demo reels. I actively look for opportunity during a conversation to pull out my tablet and demonstrate my work. I also upload the demo reels to my phone, just in case my tablet runs out of battery.
Notepads & Pens
It's convenient to carry a mini notepad and a pen with you at all times. GDC is quite a busy event, and people can quickly run out of business cards. When you give someone your business card and the person is out of cards, you can ask the person to write down contact information on your notepad with your pen.
That's It
I hope these tips will help you prepare for the upcoming GDC this year. Go meet people and have fun!

#5148054 Interpolating Quaternions with Circular Blending

Posted by on 18 April 2014 - 09:37 PM


A bisector of a line segment connecting two points on a circle always goes through the center of the circle.

My comment was regarding the length of n1 and n2, not their direction. The illustration implies that the lengths of n1 and n2 are each equal to the distance between the respective midpoints and the center of the circle. E.g., ||n1|| == ||m1 - C||. If that were true (which I believe it is not), then finding the center would be trivial.


I'm just commenting that the illustration is misleading in that regard. Showing shorter vectors n1 and n2 (i.e., an unknown distance between the vectors heads and the center) would better highlight the need for the parameterized bisectors. Something like the following:





Ah, I see what you're talking about now.

You are right. n1 and n2 should not have the exact distance from the midpoint to the center of the circle C.

The figure is kind of misleading.

My bad tongue.png

#5147989 Interpolating Quaternions with Circular Blending

Posted by on 18 April 2014 - 02:52 PM

Hi, all:


I wrote a post on interpolating quaternions with circular blending.




Circular blending is an interpolation technique that produces "quaternion curves" with C1 continuity, as opposed to the commonly used piece-wise slerp technique that has only C0 continuity.


Here's a video comparing the two techniques.



#5147972 I gave a lecture on constraint-based physics, and here are the slides.

Posted by on 18 April 2014 - 01:27 PM

Nice work Allen, I'm pretty sure you're not going to have a problem getting a job after graduation.


Actually, I already did. I'm going to work at Naughty Dog laugh.png

#5147825 I gave a lecture on constraint-based physics, and here are the slides.

Posted by on 18 April 2014 - 12:51 AM

Hi, all:

This is my last semester at DigiPen Institute of Technology, so I decided to give a lecture to my fellow schoolmates on constraint-based physics to pass down a few things I know about implementing game physics.

Here are the slides I used:

Below are the main points I went over in this lecture:

  • The flow chart of a typical physics engine.
  • How to derive velocity constraints.
  • Contact constraints, including normal and tangential resolutions.
  • Solving multiple constraints simultaneously (block-solving).

You don't really need to implement a full-blown physics engine with narrow phase, broad phase, and other fancy stability features like contact caching and warm starting, just in order to get something cool. In the end, I presented a simple constraint, the mouse constraint, as an exercise homework.

I encourage anyone who hasn't done any physics-related stuff to try implementing mouse constraints with a simple semi-implicit Euler integrator; you will end up with something you can drag around, reacting and looking physically "correct".

If you are not familiar with motion dynamics, I also wrote two posts on its fundamentals and implementation examples, please do check them out:

Lastly, here's a full list of the posts I have written on game physics:

As always, please tell me if you think I've got something wrong. Thanks smile.png

#5132832 Misc. Polyhedon-Related Posts for Game Physics

Posted by on 19 February 2014 - 08:04 PM

Hi, everyone:


I wrote a couple of miscellaneous posts on polyhedron-related stuff for my game physics series on my blog.


The first post explains how you can use the half edge data structure to implement a better support function for polyhedrons utilizing a hill-climbing approach, as opposed to the most obvious brute-force approach. It also shows an example implementation of dynamic half edge data structure.



The second post demonstrates 3 options for updating the AABBs of polyhedrons, namely the brute-force approach, approximation by local AABB, and the support function approach. This posts also touches on their pros and cons.



Here's a list of all posts of the game physics series that lead up to these two posts.



I hope you like it smile.png

#5119276 Blog Series on Game Physics

Posted by on 26 December 2013 - 04:46 AM

Hi, all:


My name is Allen Chou.

I am a student from DigiPen Institute of Technology.

I've been working on my junior game project as a physics programmer for over half a year now.


I felt like starting a series on my blog about game physics, 

so that I can share what I have learned throughout my studies.


The series is still on-going.

Have a look if you are interested, 

and please DO point out anything that seems wrong smile.png


Here's a list of completed posts and planned topics:





Motion Dynamics Fundamentals



Motion Dynamics Implementations



Broadphase - Overview



Collision Detection - CSOs & Support Functions



Collision Detection - GJK



Contact Generation - EPA



Resolution - Constraints & Sequential Impulse



Resolution - Contact Constraints



Stability - Slops



(Planned) Persistent Contacts


(Planned) Islanding & Sleeping


(Planned) Broadphase - Dynamic AABB Tree



I will update the links as I finish writing more posts.

I hope you guys like it smile.png