[epiar-devel] Infinite Canvas

[Matthew Zweig]

On Jan 19, 2010, at 4:53 PM, Christopher Thielen wrote:

> Hey Matt,
> 	This weekend (23-24) we should work together on this. Anybody else reading this in the Northern California area is welcome to join; just mail me privately.
> 
>> 1)  Doubles and Floats lose precision as they get bigger.  The Pysics may work fine near (0,0) but might work really badly at (10E24,10E24).  I don't know how big we plan on making our universe, but I don't like the idea of things falling apart at the edges.  I would like to have each Quadrant maintain it's own Coordinate system. That way, the Coordinates never lose precision as you move between quadrants since you can't travel more than R before moving into the next Quadrant.  Unfortunately, I haven't figured out a good, clean way of doing this yet.  Another bonus to this idea is that we could define 
> 
> This is a good idea. It would scale much more so. In 0.5.0, we didn't really have a problem with a galaxy of about 30 planets: the largest ones were only about 50,000 units away from the origin, so it is and isn't a problem.
> 
> I don't entirely understand how the quadtree handling works to help you with this. Could you go into detail what a quadtree is again and how it helps in this situation vs just a list of planets with Cartesian coordinates? Is it that a quadtree helps you find the next nearest planet without doing it in O(n) time?

I try to answer this in a separate email.  In short, the QuadTree is not the right structure for finding planets.  The QuadTree is a good structure for finding generic Sprites.  The QuadTree simply provides a clean distinction between two different areas of space.

>> 2)  How long do we need to keep track of Sprites?  If a ship is 10 quadrants away from the player, do we really need to run the full AI loop for that ship?  Alternatively, we need to keep the AI loops running for ships in nearby Quadrants so that the player can't just hop into the next quadrant for a while and then.  Could we just delete ships as they cross quadrant boundaries?  One idea would be to add a screen flash every time the player enters a quadrant, then delete all sprites in the old quadrant and create sprites in the new quadrant.  Also, how should ships be removed?  Simply blink them away?  Make them land on a planet?  Make sure ships are outside of the players' views before deleting them?
> 
> We don't need to have a real running universe unless it's computationally easy. One idea is to have AI sprites very far away simply updated 1/2x as often or 1/16 as often as sprites on screen.

I think that this is possible, I'll look into it.  The idea of just freezing distant systems rather than deleting them is appealing, but I bet that it would cause memory issues down the road.

> I'd keep all the sprites in a quadrant (a star system?) working fine. The sprites in the nearby quadrant can be generated as the player approaches that quadrant. I don't think ships should blink off screen; just wait until they're far enough away.

> It's important to note a few sprites would need to exist regardless of distance: if I take a mission to hunt a pirate who's known to be a few systems away, we would generate that ship in those systems, far away, and just run it (or would we? what would it have to shoot in an empty galaxy? hm)

We could add a state flag or getter for Sprites that shouldn't be 'cleaned up' when they go too far out of range.  For example, Planets should never be 'cleaned up' regardless of distance.  We may not want to put planets in the QuadTree at all actually, since they are vastly outnumbered by ships and projectiles and don't need the same sort of searching or culling guarantees.

> The flashing between quadrants is no good. We should simply ensure planets aren't visible at the edge of quadrants and if any ships are on-screen when the player switches quadrants, we'll switch the sprites to the new quadtree too. This requires the quadtrees allow for some sprites somewhat outside its coordinates temporarily. Does that make sense?

I agree, no flashing between quadrants.  I don't think we need it anyway.  The current infinity branch has planets and ships at the edge of a quadrant and it works just fine.  I think that we can do can do visibility based removal.

The QuadTree becomes useless if there are sprites outside of it since it can't reasonably cull out of searches.  The current infinity branch implementation doesn't need this though, since the range checking crosses Quadrant boundaries 'seemlessly'.

>> 3)  How Should we handle creating more Ships?  Escape Velocity handled this by having ships warp in, but with an infinite canvas, they can only to be created at some point that is theoretically reachable by the player.  The current method is to create them occasionally around the planets as if they were launching off of that planet, but it still looks dirty.
> 
> There should be a few methods, imo. Some planets have defense fleets that patrol, that would simply be generated as you get near. Other ships should be generated by a "traffic generator", which is an attribute of a planet that we can use, e.g. if a certain planet is supposed to be a hub of activity, we can give it a high traffic value so when the player is near, a lot of traffic is generated. Whether or not all those ships have purposes doesn't matter. It simply has to appear, for all purposes, like it's full of ships. Once a ship flies by and is numerous 'screen lengths' away, or perhaps off the quadrant quadtree, we can delete it. This way, we never really have more than 100 ships at once in the game. Ships with jump engines could still jump in, but this still sounds like something the traffic generator can handle.
> 
> Additionally, some missions may dictate, depending on how we could handle the pirate mission above, generate a pirate in a given area, e.g. a mission says a pirate will be in 1 of 6 systems; when the player is in that system, there's simply a 1/6 (or less, we can play with it) chance that the pirate will be generated and available to progress the mission.
> 
> - Chris
> 
> 
> _______________________________________________
> epiar-devel mailing list
> epiar-devel at epiar.net
> http://epiar.net/mailman/listinfo/epiar-devel