I have my students play almost exactly this game at the start of a course in College Geometry, through GeoGebra. Of course, it lacks the video game style interface you're describing (and which, I agree, would be awesome), so I would be excited to see something like this polished up nicely.
I'll tell you briefly what I do in class and a little about how you could spice it up. Be sure to sign me up as a $\beta$ tester!
First, GeoGebra is heavily customizable in terms of what tools are available. So on the first day of class I have them open a blank GeoGebra worksheet where the only tools are available are the minimal compass and straight-edge constructions: Create a point, connect two points through a line, and draw a circle given its center and a second point. The next very handy point of GeoGebra is that you can make tools (or, "unlock abilities") which allow you to write macros to accomplish repetitive tasks. For example, students quickly tire of manually bisecting each line segment and are motivated to construct a tool that can do it more quickly. Incidentally, the challenge that students are trying to accomplish is to develop a set of tools that minimizes the number of mouse clicks they need to use to accomplish a series of geometric constructions. Hartshorne's Geometry is a good source for such problems, including some rather challenging ones (boss battles?)
This typically goes over really well, but I agree that for the casual audience we'd like to jazz it up some more. Okay, so how do you jazz it up? Well, the third great feature of GeoGebra you can exploit is its ability to embed itself in HTML, and in particular interface with javascript code. The things I do by hand for the class (pre-ordaining a set of tools) can be implemented as HTML/javascript buttons outside of the main geogebra panel. So as your picture suggests, you could, for example, give a player a scrollable inventory of clickable tools (Daggerfall in particular is entering my visual consciousness at the moment) for use in their constructions. This also embeds the entire game in a more robust and convenient programming framework, as keeping track of a bunch of counters and complicated global structure is somewhat non-intuitive using GeoGebraScript.
Best Answer
When I started delving in to The Elements I had the same issue. Euclid's propositions are somewhat unusual especially due to the translations. I actually did a whole blog post on this that was geared towards new students trying to learn and understand geometry. I go over the propositions in it if you are interested: http://mathhelpblog.com/geometry-for-dummies-how-to-do-geometry-and-understand-it/. Perhaps this could serve as an example on how to show it it more modern terms.
It's a challenging read, but I figure since it was the go-to math text for over 2000 years, that it still has its relevance. Euclid is a personal hero of mine. I know its been a while since you wrote this post, but I am interested in what you came up with.