Analysis

Some problems in computer science have well-established, solid solutions. The intricacies of such problems are completely understood, and optimal algorithms have been found. As anyone familiar with algorithm theory knows, sorting a list of N numbers needs at most N*log(N) comparisons, and no algorithm can perform better than that (in a worst-case scenario). Sorting algorithms is thus a great example of these "silver bullets." But most problems are a bit more complicated, and each solution has some downsides, so evaluating and selecting the right option is far from trivial. Character animation is one of these tricky problems. Many different approaches have been devised through the years, but all of them have potential pitfalls. Generally, we will be able to choose between CPU-intensive methods (which use little memory) or memory-hungry methods (which in turn use little CPU resources). In this chapter, I will expose many different methods, trying to make evident the advantages and shortcomings of each technique. This way you will be able to select the algorithm that best suits your needs.