Relationships between people who meet in virtual worlds are common and these relationships can be long term, in some cases lasting a life-time. Although relationships formed in virtual worlds have invited a lot of recent interest, surprisingly little work has been done on developing computer agents and non-player characters that can actively participate in such relationships. The focus of this review is relational agents, agents that can build long term socioemotional relationships with users. In virtual worlds, such agents are just starting to emerge; they are more common in other environments but remain few and far between. This review critically assesses the progress of relational agent development and research since their inception in 2005, proposes new areas of research and considers the potential for their exploitation in virtual worlds.