Ok, there hasn’t been a Part 1 – really – and ‘Stellar Cartography’ is from Star Trek, and no – I won’t be using that name in the game – it’s just for the blog and continuing the UI,UI post of last week 🙂

So, it’s been an up and down week – it looks like my mystery illness is not quite done with me and it’s flared up a couple of times – the last nearly took me off my feet (literally) – but back on increased med’s and all is well again.

Anyway – personal woe’s aside – progress! This past week, any spare minutes I have (which is not much) have been spent on the Galaxy Map, in my quest to turn it from the original ‘make it look like it works’ to shiny new, production oriented ‘it works’ code. A spot of refactoring here, and some bug-hunting deep within the 666 engine has resulted in exactly what I wanted to achieve! Hurrah!

I’ve yet to test the system performs to an acceptable level with a fully populated galactic database of 200,000 stars, but it’s set up with that in mind. This has all been ‘under-the-hood’ work, so little has changed visually – though I may do a little video to show WIP. I’ve yet to plumb the System Map back in – but I have plans which mean that is now a separate UI element so it’ll need refactoring out of the present Galaxy Map code anyway. I’m not sure how many of you are interested in the ‘techy’ elements involved even though this is a Dev Blog post, so I’ve decided to split “Tech Talk” into a separate section of each post – so you only have to read it if you really want to 🙂 And look at the pictures 🙂

Tech-wise, the Galaxy Map is an interactive, ‘all-inclusive’ map of the galactic cluster, in real-time, overlaid over your view of ‘the real world’. What do I mean? Basically you can rotate and zoom in/out of a map of all the stars in the galaxy, and select any of them at any time – there’s no ‘here is your tiny window to play in instead of the massive galaxy’ – you get the whole enchilada to enjoy at all times. Filters whittle the massive data-set down to useful levels (like stars which have stations orbiting, and so on). You still see the rest of the stars which do not qualify, but they are dimmed down so they don’t clutter your view. The reason for this is aesthetic mainly, but also certain drive systems (like g-drive) have to interact with stellar gravitational fields – so a route from one system to another might weave it’s way between several other stars to get you there. It would look a little screwy if your route appeared to wander around galactic space at random if the stars it traversed were not visible in some form!

Selecting a star focuses the map on it, and it becomes the focal point which you rotate the cluster around. You can then zoom in to see the star system itself with it’s satellites (if any), and interact with the System Map in the same manner.

 Tech Talk

Octrees. You’ve seen me mention them before. Check the link for details but in brief they are a tree structure for partitioning 3D space in such a way that you can search for just the objects of interest for a given position (or ray, or volume) instead of searching against everything in the 3D space your objects exist in.

This then is an optimisation – which allows you to do all the expensive stuff (like collision testing) against just the relevant nearby objects – instead of one’s the other side of the game world that would not need to be checked.

They are also used for visibility testing – as it’s far easier to check if a octree node (which is just an axis aligned cube) is present in the view frustum, than checking every single object which is within that cube. Is the cube entirely in the view frustum? Yes? Then ergo – every single object within that cube must also be in the view frustum. If the cube is entirely outside, then so is every object within it. This neatly splits a huge number of objects into ‘visible’ and ‘not visible’ in one foul swoop, and we only need to check the objects within cubes that intersect the frustum to see if each individual object is visible or not.

So – that preamble leads me to the application for the Galaxy Map. When I create ‘the galaxy’ – all 200,000 stars are inserted into an octree. This is then used to render the stars in the game scene into the backdrop textures (which are then rendered onto a skysphere). Ray intersection testing is used through the octree to ‘pick’ a star with the Auto Pilot so you can simply aim your vessel at a star and say “fly there”.

The Galaxy Octree

This same octree is then used in the Galaxy Map – but now with visibility testing to only render nodes (and their stars) which are visible to the viewer. Again I employ the Ray intersection testing by casting a ray from the camera, through the mouse position (in world space). This gives me the nodes in the octree that the ray intersects, that contain stars.

I then whittle this list down even further by doing a conical projection around the ray to get just stars ‘near’ the ray itself (ones within the cone). Why a cone? Because of perspective. You (the user) will be interacting with the 3D star positions in screen space, not 3D space. So, to you – you’ll be hovering over a 2D point – with no idea how far away it really is. A star that is very near the mouse screen position and very near the camera could be light-minutes away from that 3D ray used to intersect the galaxy. But, a star that is very near the mouse position, but very far away from the camera could be tens of light years away from the ray itself. If I just said “find all stars within 5 light years of the ray” – chances are you’d be unable to select a star which to you looks to be right under the mouse position. So the cone broadens out away from the camera and gets wider in the far distance, to catch all “candidate” stars. A thought just occured to me whilst writing this explanation – this is why I love explaining things, because usually I realise it could be done better… I could project all the candidate stars into an orthographic plane aligned perpendicular to the ray and just do radius testing… not sure if that gains any performance wins though. I’ll have to have a tinker at some point 🙂

So – all that ‘whittling’ is for a reason. Now we need to decide which stars are closest to the mouse in screen space. And that’s costly. After you’ve finished zooming in/out and rotating the galaxy all over the place, we have to “unproject” every single 3D star position to a 2D screen space position. Doing that for thousands of stars (let alone hundreds of thousands) is really, really expensive on the old (or new!) CPU. So with our heavily reduced list of possible ‘nearest’ stars, we can now finally find the one closest to the mouse position, and voila – we have our winner (shown with the tiny little green circle around it just left of the mouse cursor!).

And that ladies and gentles all – is what took all the time this week 🙂

Stay tuned folks!