Nonplayer characters (NPCs) in today's computer games lack the ability to adapt to situations that were not envisaged by the artificial intelligence (AI) programmer. This lack of adaptation produces lifeless characters that are prone to repetitive and predictable behavior. In this article, we present our work towards the development of an online learning and adaptation architecture for NPCs in first-person shooter (FPS) computer games. Our architecture builds upon incremental case-based approaches to modelling an observed entity, and makes a number of novel contributions. In particular, we develop a dual state representation to enhance case matching, and use adaptive k-d tree-based techniques to improve case storage and retrieval. The dual state representation allows more game features to be represented in the system, which enables observed behavior to be more accurately recorded and actions predicted. The system is applied to the Unreal Tournament using the GameBots API and evaluated in a number of different game scenarios. Our results show that the adaptation system can accurately predict a human player's actions and that our dual state representation enhances prediction. We also demonstrate that an adaptive k-d tree-based technique can be used online to maintain a balanced tree of observed cases.