Natural language dialog elements may be dynamically generated in a virtual world when an interaction is initiated between a user and a computer-controlled character. The dialog elements may be generated by combining abstract semantic representations from a knowledgebase of a computer-controlled character involved in the interaction, with abstract semantic representations from a current state of the virtual world. For example, the abstract semantic representations from the current state of the virtual world may describe the user's progress in accomplishing a set of interrelated goals. A program enables developers of games and other virtual worlds to provide dynamic dialog generation after simply entering natural language descriptions of potential game states and computer-controlled character knowledge. Compared to manually scripting dialog in advance, enabling a program to dynamically generate dialog elements provides for exponentially increasing variety, flexibility, and apparent intelligence in computer-controlled character dialog.