Assignment To Go

[mamutas]

Couple of new programmers were asking about assignment which requires no specific graphic libraries knowledge. Here is one that came to my mind:

 

Globe coordinate description mechanizm

 

Your task is to create a technology to provide information about point on the globe. You will be given a pair of X and Y coordinates, and you must return an object which would describe that point. Following information is necessary (there will be definitely more in the future):

- is it possible to build a base here?

- what is the terrain at the point?

- what continent/country does it belongs to?

- what is the closest city to that point? how far it is?

 

As you see the data is static (will not change over time), so that would make sense to me that it will be stored somewhere, and your class would read it and returned to the caller.

 

Please, post only your suggestion/description on how you are going to implement it and whether you would like to work on it. The best idea will be chosen, and off you go with it!

[Wolfman]

Are there any constraints for some of that data?

 

Ie. For the closest city to a point, is that actual closest city or closest city to that point in the same country? Is the water counted as a whole, or is that split up into different oceans and seas, (rivers?)??

 

Secondly about the granularity of the data, is this going to be something like per pixel for the geoscape map? Or at a less fine resolution so that less memory is used up but the possibility of a wrong land type (or similar) being chosen at a border point like on a land/sea border?

 

Im sure I can come up with a possible design whatever the answers, but im sure it would change depending upon what those answers were!

 

-wolfman

[CptJackSparrow]

No time to do it myself, but some ideas.

Straight forward and probably not very

efficient, but maybe it'll help:

 

You could save a bitmap with about 16bit

per pixel. 9bit for the country/ocean, 6bit

for the terrain and an is_city bit.

 

If is_city==1 then the nearest city is at

this very pixel. Else you can determine

it with a spiral search pattern. The first

pixel with is_city==1 will be the nearest

city.

When you have the city's coordinates

you will still need a function which maps

these to its name...

 

base_possible = (terrain != water)

&& (!base_exists_here)

&& (!alien_base_exists_here)

&& (!is_city) ??

 

Maybe this model could be modified, so we could

reuse the bitmap as well as a visible globe texture,

so the player could switch between geographical

and political view...

 

Erm... anyway good night!

[[stewart]]

Someone mensioed pixelated surface or something? How are regions defined? With points and vectors or theta/phi matrix thingy? Or is that actually the assignment?

[Kreis]

Won't it be easier to use predefined region and surface matrix? and bases should be defined in separeted array - so when build check is on, just to check if any base already

built here...

[red knight]

Just make sure to decouple the logic part of it from the data representation, cause several representations came to my mind... like QuadTrees to specify terrain types and vectorized for Country Borders and Pairs of Coordinates for cities. I suggest to start with the highest level class layout design before write even a line of code, this is a task that has a lot to be though out...

 

Greetings

Red Knight

[[stewart]]

Easier said than done. How the data is to be stored is important when defining class members. Probably a large theta/phi (longitude latitude) matrix is best that way all data can be accessed via look-up table. THe data can be generated starting with vector/parametric equations of course. The question there would be do we generate the look-up table @ compile time or @ game initialization. If speed of initial start-up is the main concern then @ compile time is best but allowing for future game modibility (ie same game but played on a venus, arakis, middle earth, pangea map etc.) then @ game initialization is best.

 

Given this, data access about the location is a snap; look it up. Data generation is where the work is. Nearest city data then I believe it's positively curved space geometry equations, that will NOT be static or constant at least and the table entry is generated during run-time (if a base gets invaded then the "next base #5 is elsewhere so new value needed).

[Kreis]

Hey - let's forget about memory probs - it's no problem, 1 meg of memory to matrix - nothing - i know, it's primitive, but fast!!! and one question - coordinates gave related geoscape, or screen coords?

[[stewart]]

Now I'm starting to think maybe NOT a look-up table. The reason in later versions if we want to include axial tilt there /may/ be issues. Plus a rectangular matrix representing a globe creates a non-homgenous data density with respect to area on the globe (more data points per square mile, as it were, at the poles). Let me think about it.

[kurko]

- what is the terrain at the point?

Use a texture and check the pixel at that particular point. If you want arbitrary complexity I see no other way, and you need it if you want to render it over the globe.

 

- is it possible to build a base here?

Terrain at point != water...?

 

- what continent/country does it belongs to?

Use another texture, with less detail if you want.

 

- what is the closest city to that point? how far it is?

Having a list of cities, check the distance to the point for every city... cities could be sorted along longitude and skip for cities far away, but there is no point, how much time does it take to do 100, 200 or 1000 sqrt's ?? how many queries are needed per second ?

 

if you are worried with varying densities along latitude you could use a Mercator projection, or study non-euclidean geometry it depends on how much interested in detail you are.

Edited November 23, 2003 by kurko

[red knight]

Well you can down the memory requirements an order of magnitude if you encode (the most simple information) like water or not in a QuadTree...

 

Thats why I said to decouple the representation from the logic. In that way we can change after a simple implementation to another more efficient and complex representation without changing a line of game logic code.

 

Dont worry about the screen space cause to get the coordinate you need to shoot a ray from the pixel to the model (for now a sphere, a geosphere could be interesting if someone wants to figure the math of it - that means find a good book that have it defined mathematically and find the geodesic constants for the earth) and then resolve the ray equation to find the point in the model. After that you can use a [u,V] coordinate system (like a matrix ), so if you can make it work in a planar way then the rest is easy.

 

For the country for instance the quadtree is excelent and can be generated from an image, the other solution is to use a border vector (but if we think to have more or less accurate country borders then it becomes a little more inefficient) on the other hand that representation is lighting fast for rendering the borders... The other nasty thing is to get the data anyone with GIS background will be required to find that data or generate an approximation but ourselves.

 

The important here is to give a standarized (assume what you need to assume) way to access that information regardless of the real representation...

 

We need to know: Locations of the cities, country borders, what country a [u,V] coordinate pair is associated, type of the terrain for a [u,V] pair (that includes water), you can have extra information if you want but that is not required (like population estimates) to put or not houses in there, humidity to select likely weather conditions, but that is far more complex and not needed for a good game... (That is like of an all the time easter egg).

 

If anyone is seriously interested we can arrange a network meeting to design in real time, just PM me to arrange when...

 

Greetings

Red Knight

[[stewart]]

I'll see if I can dig-up te "flat" geometry equations for the surface of a sphere so we can see how much of a headache it might or might not be.

[exio82]

We have to consider also where we find all the data we need. For example cities are a lot and it is not possible to assign to someone the work of inserting them in a big table with GIS coordinates. The same for countries.

And how many cities are we going to consider? I hope not only capital cities..

 

I really like the quadtree idea for regions and I've found something interesting here for image2quadtree convertion.

 

About the data granularity, how big is a base? 200 meters? 1 Km ? If we divide the Earth in 1Km2 squares we have approx 2 billion squares.

If we divide in 100Km2 squares we have approx 20 millions of them.

I think we can divide it in 100Km2 squares and search if someone compiled a big table with terrain informations...

We cannot base on a texture cause it's mapped on a sphere and near the poles we loose pixels.

Or we can also get a pixel color using coordinates and getting it from the graphic engine?

 

About the high level interface I think we can query a point with coordinates, find which square it is into and return that square informations. We can assume bases are placed with a minimum distance of for example 100Km (one square).

We can use also hexagons instead of squares.

 

A square data can be as follow:

Bool isTerrain
Real averageAltitude (in meters, in oceans may be the deepness)
String countryName (or UInt32 countryID)
UInt32 baseID (our base or an invalid value if not present)

 

A possible interface could be:

SquareData getTerrainInformation(Real latitude, Real longitude)
Bool addBase(Real lat, Real lon, UInt32 newBaseID)
A function to update terrain ownership of countries (if we are going to put some story about it)
Bool removeBase(baseID) and an overloaded with lat/lon

 

RK is this what you intended with decouple logic part and data representation?

 

I've found some lists about

Nuclear implants all around the world (alien can strike at these)

A huge list of cities with coordinates. I'm a lucky men!

Geographical data resources online

[mamutas]

Exio,

 

Those are very valuable resources.

 

I really had no ideas when I started this thread on how would we store the data and return it to the caller. Wow! I did not expected such hot discussion.

 

Anyway, lots of good suggestions. I 100% agree with RK, that we need to separate the data representation from the logic. However, I really can hardly imagine how would we be able to achieve that. The problem is that class must return specific data which we must store. Other thing is when a calculation is performed. In that case the calculation must be separated.

 

After all, I think that the very first thing we need to do is to decide what exactly we need to know about given coordinate (which, I think will be passed either in pixels coordinate relative to texture we use for the globe or in magnitude/latitude dimensions). Many of mentioned parameters could be easily randomized without significant gameplay implications.

 

So, here is the start.

 

1) Terrain (includes oceans/deserts/urban/etc.)

2) Country (will be used to alternated appeareance of urban terrains. For instance, european houses vs. middle-east buildings. Also, banners on stores could be localized: Coffee/Cafe/Kava/Kawa etc.)

3) Distance from nearest city (this will affect how urban terrain will look like: more downtown style vs. suburbs).

 

Note, that this is information about the coordinates. In order to get it, there could be many ways to calculated it from the data stored. Data could be stored as vectors or rasters, but in the end each coordinate pair will have predetermined characteristics.

[Wolfman]

About Citys and Countries, will the information on them be used to display on the geoscape as well as be returned as in this project? For instance in the original UFO I think that when the map zoomed in for an intercept you could see the borders for the countries and also the city names. There could even be an option to have this on all the time on the geoscape??

 

If this is the case then we need to think about the best format for storing the city/country information that is going to suit both drawing and for retrieving at high speed. Perhaps this should infact be handled by a different class to seperate the data storage for these, so infact when drawing its something like

 

for(cities in view)
cityclass->draw();

for(countries in view)
countryclass->drawBorder();

 

And then when retrieving the data for the (x,y) something like:

 

citylist = cityclass->getCityList();
countrylist = countryclass->getCountryList();
city = searchListForNearest(citylist);
country = searchListForNearest(countrylist);

 

That way the city & country data is seperated and used for multiple purposes.

 

Also then some cool things could be done when drawing countries if the data is seperate, like drawing on the geoscape things such as alien activity (blue = not much, red = lots), then its easy to see where to put bases to cut down activity.

 

For the terrain, I assume that the quad tree could be pre generated, and then simply loaded from a file? Perhaps we could build a small tool that generates a quad tree file from a simple texture, that way it would be easy to allow more planets/different starting planet, and easy to mod.

 

As for the (x,y) coords for the globe, how about using long/lat coords? It seems to me that is the standard when talking about coords in the real world over the globe?

 

Anyway, just a few suggestions.

 

-wolfman

[[stewart]]

The "calculate nearest city" is a snap! THe nearest city accross the surface is also the nearest city in free space. So calculate distances as though earth wasn't there at all (distance going through the ground) nearest of those IS nearest also by surface. Since the actual distance is not important to but only the comparative distances this works.

[exio82]

Stewart you're right !! So calculating distances is simpler... but we cannot give the user a free space distance if he needs to know how far two cities are.. we may need both calculations

[[stewart]]

Nope because we NEVER need to know actual ground distances EVER. And if somehow in the future we somehow need it (perhaps using "estimated time to interception" or something like that for more game "atmosphere"; pardon the pun) then we simply find the forumula for distance on a globe using spherical coodinates and we write the 5 lines of code and we're done, for now don't worry about it.

[Kreis]

BTW can anyone explain me what is QuadTree(the structure), cause i can't find proper translation into russian...

[CptJackSparrow]

@Kreis:

Try this link

[[stewart]]

So that's what it is. Hmm? Has anyone apllied a quadtree to non-euclidian space though. You still get the non-homogenaity of data density at the poles and equator, unless we adjust the "grainyness" of quad trees at different latitudes.

 

Considering we have to keep in mind base-locations, landing sites, and aircraft positions as they fly across a sphere. This may require on-the-fly calculations rather than a look-up table.

 

Base placement isn't a problem as the game "stops" while you select a location so there won't be playability time issues.

 

Aircraft location isn't really one either as we can fudge it. We calculate the location of the aircraft 5 seconds from now (in a free space interception) and then readjust the rho coordinate. Not 100% accurate but more than good enough I think.

 

The tricky part is the alien landing sites. Since some will occur on the "back" of the world and without our knowledge you can't use screen coordinate to cheat, and in this case you can't throw up an "Alien Craft has Landed Window" to stall for time while calculations are made (yep multithread-o-rama).

 

We might just have to calculate on the fly. We'll need to instrument that code and profile the heck out it. Anouther thought though, the calculation can just come late. The unknown crash site can't be discovered until the math is done. We might be able to fake it also. We'll know the location, craft type, race, and mission before the landing site terrain is determined. We can pop-up a window that says these things (but not terrain type, which I believe the REAL Xcom does anyway). While you acknowledge the window manually anouther thread is busy making the calculation.

 

Just some ideas.

[Wolfman]

A good question at this point would be - Are we aiming for non-euclidian space or not??

 

-wolfman

[kurko]

for distance we could use this http://www.uottawa.ca/academic/arts/geogra...greatcircle.htm

[[stewart]]

I wouldn't recommend that for aircraft flight but rather the approxiamte algorythm I just outlined; there's a LOT less calculations and it's good enough.

[Kreis]

Sorry, but it's no cute - but i think the best representation is simple matrix - if we could place texture over globe, so why we couldn' place matrix over globe, but colors must be objects that represent terrain properties(and cities and etc.).... so what about predefined wolrd matrix - on my opinion it is the easiest way. Why to make thought algorithms, when there are no borders to use others!

 

P.S. Pls, send your critics!

Edited November 27, 2003 by Kreis

[[stewart]]

Actually I don't think it will be that bad to calculate (ie slow), it all depends on how the boundries between regions are defined. The benifit of calculating on the fly is that your "grid" has infinite fineness along with it being homogenously distributed throughout the surface of the globe. If we go to a matrix representation of the surface of the world it will also make dealing with axial tilt for later versions of Xenocide much more difficult.

 

Besides as I outlined before there are ways around any "speed" problems that may show themselves as a result of not putting a grid over the whole world.

 

Don't worry I'm workin' on it.

[Wolfman]

I dont see why, like Kreis says, we dont use a matrix. Axial tilt doesnt come into it as it is the job of the UI to return the proper x,y coords that have been clicked on/selected rather than this classes job to adjust for the axial tilt.

 

Assume that the adjusted coords have been given and then it is just a simple look-up in a table.

 

The only disadvantage as I see of a matrix representation is the fact that at the equator the granularity of the data is better than at the poles.

 

-wolfman

[[stewart]]

As I said we're doing more than just placing bases down. There are UFO landing sites whose terrain must be known as well, for example. These can occur on the side of the planet NOT visible to the gamer. Or can occur on the visible side and yet not be seen. So using screen coordiante won't help. By calucualting on-the-fly we can avoid pixelization or inconsistancies when zooming in for example.

 

The idea behind using a matrix is for one of speed. However since the game stops anyway while you decide where to put your base speed is irrelevent if we don't use a matrix of longitude/latitude terrain types or what have you.

 

That being said what I'm think about is rather than a matrix describing the whole surface of the planet, I'm thinking of a table containing the coordinates of the endpoints of straight lines dividing regions on the globe. The coordinates of the endpoints, of course, are stored in a table. Data represented in this way i think would be easier to manipulate for axial tilt calculations.

 

I'll try to work-up some algorythms over the weekend.

[mamutas]

I think guys you are going in wrong direction. Can we get some simple table lookup first? And add sophisticated algorithms later?

[[stewart]]

We should have at least some idea of how we are going to represent the surface of the world, either storing the whole surface for look-up speed purposes, a table with coordinates for the verticies of regions, or even some heretofore undescribed method.

 

I know OOD likes to ignore data but in this case how we approach it will have implications on the final game.

 

Don't worry M we're making progress here.

[Wolfman]

So using screen coordiante won't help.  By calucualting on-the-fly we can avoid pixelization or inconsistancies when zooming in for example.

 

Sorry,

 

I didnt explain myself very well, when I say adjusted coords I meant relative to the texturemap of the geosphere, ie they wrap around the whole sphere, and are not screen coords.

 

What I mean is, have an array that is the same shape & size as the geoscape texture. Then it doesnt matter about axial tilt etc because the coords returned are relative to the texture, not relative to the sphere - this means that it works on user clicks (the ui has to find out the coords by some method of tracing a line onto the sphere, then looking up the texture x,y at that point), and it also works for the "nightside" of the planet that cannot be seen.

 

I havnt found the discussion about axial tilt, but I imagine it to be a simple case of rotating the sphere a little according to the time of year. When the spehere rotates so does the texturemap, so anything that is based upon the texturemap will automatically ignore the rotation if you see what I mean?

 

Im not very good at explaining myself am I? :-/

 

-wolfman

[red knight]

Axial tilt is a no brainer (cause you dont tilt the earth), the sun movement is the one that use a diferent orbit (and nobody will notice a linear displacement, that is for sure, so you can easily fake the effect)...

 

About all the decitions of using or not matrix or quadtrees and all that... Now it is irrelevant I will outline what we need the Xenocide Simulation Engine to have in an easy to use interface, the internals (if we are using non euclidian or euclidian geometry, quadtrees or matrix, or anything else)...

 

For the simulation engine we need a simple to use representation... That involves:

 

[*] An entity can be translated with a given velocity from point A in direction B so we need the new coordinate in planar coordinates (so we get where we should be)...

[*] A simple planar representation to easy the calculations and interface of the module (nasty stuff inside, that includes the coordinate transformation to a suitable representation)...

[*] Given a point A in that representation get the points MetaData (like terrain type, demographics, nearest city, weather condition if you like, etc).

[*] For dynamic entities like UFOs, Aircrafts, Bases, Landing sites, etc... there is no metadata at this stage cause this system do not integrate dynamic entities (is more of a static lookup database, than a dynamic one).

 

The reason to use planar coordinates is that it is pretty easy for us to use a 2D representation of the globe in most of the places, except when things move arround. In that case go to point one of the coordinate system to know how you should move.

 

There is already enough information in here to start working on a design draft without ever assuming that you are going to use this or the other representation.

 

So let's get our hands dirty

 

Greetings

Red Knight

Edited November 28, 2003 by red knight

[Kreis]

One more question - could we determine on sphere wich polygon is concretly selected while pointing on it (its id or somthing, i'm bad in graphics programming)?

[red knight]

Just to easy your heart, you dont only can select (and find) the polygon... You can find the exact point of the sphere you are clicking, it is already done in Xenocide code, though not used in the demo ...

 

Stewart had mentioned off the forum that we can really rotate a little the earth instead of calculating the sun's diferent orbit given the axial tilt (it is even simplier) so I think we will try it and see how it goes in that way... So we can call the Axial Tilt issue of this thread closed with 2 simple solutions proposed to the problem, if none of those works in practice then we find a new one but it is not the time right now...

 

Greetings

Red Knight

[LordT]

Stewart had mentioned off the forum that we can really rotate a little the earth instead of calculating the sun's diferent orbit given the axial tilt (it is even simplier) so I think we will try it and see how it goes in that way...

Wouldn't that require the camera to rotate too? :/

[red knight]

No I thought that too, but it is not required to do so...

 

Greetings

Red Knight

[thejer]

well from the description this sounded like something I could contribute to! simpler programming task but I haven't gotten through all the responses posted yet...

[mamutas]

The discussion is continueing in SF.net programming mailing list. I recommend you to subscribe to it and read it as well.

 

Wolfman took that assignment and had some work done. If you would like to help on that task, read his postings in the list first and then see what would be the most of interest for you.