Abstract: Traversing dense crowds can be challenging, but it is especially difficult in a virtual environment where the user is limited to simple input devices. Predicting near-future user movements with a hidden Markov model allows nearby autonomous agents to react politely, that is, to specifically avoid impeding the movement of the user. This predictive model and simple avoidance scheme are tested by six subjects in 360 short interactive games and by a 10-participant two-alternative forced choice questionnaire. Polite agents are found to significantly improve the player's ability to navigate quickly and without collision, and the resulting character movements showed increased naturalness for two of the three game scenarios.