The "Theory of Special Relativity" is widely regarded as a difficult topic for learners in physics to grasp, as it reformulates fundamental conceptions of space, time and motion, and predominantly deals with situations outside of everyday experience. In this paper, we describe embedding the physics of relativity into a computer game, and present the results of a study on its effectiveness for learning. The game, which is based on "Asteroids", enables learners to interact with the physics, and observe and contrast their effect with Newtonian mechanics. The principal relativistic effects of length contraction, mass dilation and time dilation are each portrayed, and key with the learning outcomes of the Australian Higher School Certificate (HSC) high school physics course. Key findings from the study conducted with both students studying HSC physics, and participants without physics training, show that the game on its own serves as a powerful introduction for building up accurate qualitative descriptions of relativistic physics effects; in addition, learners generally reported finding the game accessible and interesting. However, establishing deeper understanding of the physics requires further reflection on the part of the learners than the game itself tends to facilitate. We conclude by discussing implications for design and integration of game-based learning with traditional teaching in relation to the topic of special relativity. (Contains 6 figures and 7 tables.)