Abstract:Crowd animation has been researched and applied in many domains in recent years, such as robotics, movies, games, and so on. But the traditional technologies for creating crowd animation all need complex calculating for motion planning or collision avoidance, the computing efficience is low. This paper presents a new algorithm for generating motion trajectory based on Markov Decision Processes (MDPs) for crowd animation, it can generate all agents' collision-free motion trajectories without any collision detecting. At the same time, this paper presents a new improved value iteration algorithm for solving the state-values of MDPs. We test the performance of the new improved value iteration algorithm on grid maps, the experimental results show that the new alogithm outperforms the value iteration algorithm using Euclidean distance as heuristics and Dijkstra algorithm. The results of crowd animation simulating experiments using the motion trajectory generating algorithm in three-dimensional (3D) scenes show that the proposed motion generating algorithm can make all agents move to the goal position without any collision, meanwhile, agents' motion trajectories are different when we run the algorithm at different time and this effect makes the crowd animation much more alive.