Implementing a Paging System for Coordinates

#1 I've started looking into this and eventually tabled it half a dozen times now. I built a simple test of a paging space sim back in the TGE days, but only for singleplayer (it's quite easy in singleplayer since you only have the one point of view to worry about!) Of course, I think pretty much everyone is hoping for a multiplayer solution.

The various times I've looked into it I've broken it down into 4 main issues (note that I was only ever looking at this in terms of a space sim, and never brought terrain into the equation). My focus here was to find ways to make the changes without needing to actually rewrite rendering code or core physics, so it all relies on keeping every object inside a cubic region around world origin and simply building logic to determine when they're allowed to actually interact.

1) Instead of rebuilding the scenegraph position system, have every moving object (at SceneObject level) warp around to -LIMIT whenever they reach LIMIT distance from root on any axis.

2) In a space sim, all collisions occur in the Vehicle class, which has a resolveCollision function that can easily be used to determine which things Vehicles collide with and which ones they totally ignore. This can be easily modified to allow only collisions between Vehicle objects which exist in the same X/Y/Z page.

3) Projectiles are the other remaining issue. Like Vehicles, it's fairly easy to modify them to only collide with objects in the same X/Y/Z page.

4) To support multiplayer, you need to "lie" to the clients when you send position updates for each type of object that will be part of the space sim. Each Client receives a picture of the world from the point of view of the page they currently occupy. An object that is 20 pages away from the Client's Control Object will be ghosted to that Client as actually being 400,000 units away (+/- due to actual positions of the 2 objs in their pages, and assuming page size of 20k cube). While that's far enough for the object to be in the "severe precision loss" zone, at that distance the jittering won't be visible even for very large objects. Establish a maximum page range after which objects go out of scope entirely, because the rendering engine will fail if you try to render something more than 1mil or so units away.

I consider all of those issues solved, at least at a theoretical level. In addition, here are the issues I haven't really looked into:

1) Planets and other large & distant objects realistically need to be rendered in a secondary, skybox-like scene because you can't have an object actually exist at the size of a planet and be rendered at a great distance. Making them part of a "background" scene allows them to actually be small and close to the camera while being rendered behind everything except an actual background starmap.

2) Objects can potentially interact with each other across page boundaries because the position of their origin determines which page they exist in. Larger Vehicle objects can potentially collide while they are each "anchored" in adjacent zones. This isn't an unsolvable issue, it simply requires more elaborate collision logic than my simple model of only allowing interactions between objects in the same zone. The same applies to projectiles, as part of a Vehicle could be over the line into another page and so projectiles would pass through it.

#1 seems very doable. The rendering code for skyboxes would probably give you enough code to build a new type of object that renders in the background.

#2 just requires some more advanced logic than "are they in the same page." Also not much of an issue if your objects are all fairly small.

I wish I could provide some actual concrete progress, but I kind of backed off of this when I came to the conclusion that -- in terms of the game I'm working on -- having full-scale solar systems to explore is actually incredibly boring. That doesn't mean I still wouldn't like to see it done, it just didn't end up being right for the gameplay style of my project.

#2 ive read about this large position/precision problem a few times as well. sounds like something which isn't related to torque in particular, but just numerical precision in the numbers.

it seems like the only real solution to the large coordinates problem is to readjust the relative positions of everything at some point in the code.

This sounds like a simple thing to do mathematically. the code would have to do 3 things. first, a new position must be designated as the new (0,0,0) reference point. second, the code would iterate through each object in the client and server lists modifying their transform for the new reference point, and lastly, this new reference point would be saved in a static variable in the matrix class and used in all further matrix transformations. if the math is done correctly, the transition could be seamless and unnoticeable.

#3 It's just an inherent issue with floating points, yeah.

You can definitely do as you suggested, actually modify the scenegraph to use a reference point. When I talk about "pages" I basically mean the same thing, but I'm trying to increase the amount of possible position data possible when only adding 3 32-bit values by storing the reference point as integers representing 1 "size of the viable physics region." (2,0,0) actualls means a reference point of (40000,0,0) if the size of that region is 20k on a side. Making this multiplayer is where things get complicated, because now each player has its own reference point, which is where I start to get into the whole thing about sending different data each client ghost.

If you just want singleplayer, it's actually amazingly easy. In fact, I basically do exactly what you suggest, only I do it the cheap/hacky way -- At SceneObject level you do a pacman style warp to the other side of the world thing, then you iterate the entire list of objects in the scene and move them to compensate for the warp. I've tested this, it works just fine, but obviously a space sim without multiplayer is kind of old news these days. :P

#4 The system I have ultimately begun implementing is basically the same as the idea you just laid out, Henry. When you reach the edges of the mission area, you and all other moving objects get warped to the opposite side of the mission area, like in a game of Asteroids. When you get warped, you get placed on a new page. Only objects in the same page can interact, and clients only are ghosted objects that are on their own page.

There's a few problems with this method, here is how those are fixed. First, so you can see beyond the edge of the page, the terrain objects in all adjacent pages are also ghosted to clients.

Second, an opponent or projectile flying out of your page would disappear as he gets warped around, so we will offset the position of ghosted opponents and projectiles in adjacent pages as +PAGESIZE until you enter their page, then they are snapped back to their proper position as you get warped around. This should look more or less seamless.

In reality, nothing is ever moving that far away from origin, so is never subject to the precision issues. On the server, everything is stacked up on top of each other, but on the clients, they only see what is ghosted to them.

@Sean, in theory modifying MatrixF and the positioning system of the game to support paging is the best way to do this, but unfortunately, I do not have the wherewithal to make a change so extensive to the engine.

Not to say I didn't try, but I can barely understand how RenderInstance works at all, let alone make changes to how interprets the MatrixF data from the game objects.

#5 Im the middle of this modification now, it is going well enough. One unforseen issue is that you need to deal with container raycasts and searches, projectiles bog the engine down to a crawl when passing through objects they cannot hit that are on different pages, so I had to make separate containers for all pages only using gServerContainer for things that don't actually use the containers (such as skyboxes, etc). That approach should work fine, but it isn't fully complete yet.

#6 If you don't care about the size of a terrain then you could get away with making more room by decreasing the size and rate that things travel.

#7 The same problems that arise in the 10K+ coordinate area would probably occur all the time if you "shrunk the world" down several tens or hundreds of times. Youd go from the problem of having too few numbers on the right of the float to the problem of their being too little distance between objects for the engine to properly run.

This isn't a torque problem, every game engine out today except maybe one made for an MMO uses F32s to store position. It's just not made for large, single environment situations. A paging system is really the best and only way to go with this.

#8 A couple of useful links related to this:

1) Game Programming Gems, Vol. 4, chapter 2.3 covers a nice solution for handling large coordinates (it's effectively a paging system similar to that described above).

2) www.gamasutra.com/view/feature/1965/visualizing_floats.php?print=1

#9 My system is largely implemented, here is how it works.

Pages - A "page" is a virtual zone that basically behaves like another space for the purposes of interaction. Each game object has page coordinates, and only objects that are in the same page are scoped to eachother or are able to interact with eachother.

When a game object reaches the edge of the page (which I just made the edge of the mission area), I move it to the opposite side of the mission area, and alter its page according to which side of the mission area it left. Now it no longer scopes gameplay objects in its old page and only scopes guys in its new page.

Additionally, the server keeps each active page up and each page has its own container. This container is used for hitscans and searches, so objects in different pages do not test for collisions or raycasts against objects in other pages. I just made the server contain a vector of page objects and each page object creates its own container.

The main challenge with this approach is your levels. In my game, you can see beyond your page into other pages, so I also have to scope objects in adjacent pages and then offset their transforms on the client as per what page they are on. I also have to see enviromental objects in adjacent pages as well, so I scope and offset those too. When crossing pages, there is a little bauble as the client regenerates the level info in a different location but it is not a big deal.

If you wanted to do a lighter approach, you could do what I think Konrad is doing in his game which is just to teleport players to entirely different areas where they cannot see into the next zone, from a gameplay perspective, that works fine too. Alot of people also just use entirely different servers to run the different pages, which is basically the same as having a paging system and separate containers.