Talk:Sphere
From Freeciv
Contents |
[edit] A Different Approach
[edit] Intro
It is not possible to cover a spherical surface in regular tiles apart from spherified platonic bodies (Tetrahedron, Hexahedron or Cube, Octahedron, Dodecahedron and Icosahedron - Picture of Platonic Solids ). All of those simply don't have enough tiles to allow decent playing on it. :)
While it is possible to cover a sphere in (almost-)identical tiles, there will always be a certain number of regions on the sphere where there will be tiles with a different number of neighbours. The number of these regions depends on the platonic body the tiling is based on.
Pathfinding and navigation on non-planar surfaces is without a doubt more difficult than on planar surfaces. In planar tiled surfaces, the position is defined by simple two-dimensional coordinates, and movement can be achieved by adding or subtracting natural numbers from those coordinates. All of this is not possible in 3d surfaces, and I can't see a simple way of mapping 3d surfaces onto planar maps. This means that there is no simple representation of map positions with arrays, for example, making calculations harder.
[edit] Proposal
I propose the following approach: Instead of trying to bend a planar surface into a spherical one, we redefine the basic principles of location and movement:
1) The possible unit positions are defined as nodes. These nodes are simply points in space (Vertices).
2) The nodes are connected by vectors representing possible movement paths. Movement is possible only along vectors. Vectors are directional and have a certain movement cost.
A map consists of a network made up of nodes and vectors. Usually, vectors come in pairs - where movement in one direction is possible, movement in the opposite direction is also possible, but not necessarily at the same cost.
The network is created at map generation. A standard civ-style map is a cylindrical structure of vertically and horizontally aligned nodes, connected by bidirectional vectors in eight directions (N,NE,E,SE,S,SW,W,NW), with southern and northern "border" nodes only connected in five directions.
A spherical map would be created as a geodesic sphere. each vertex is a node, and each edge is a bidirectional vector. That's it.
[edit] Major Differences
If this method is used, shape, size and arrangement of tiles becomes irrelevant in terms of programming. As long as there is a vector between a node A and a node B, you can move from A to B. This adds even more versatility than is apparent at first glance: since a vector has a direction, you need two vectors between A and B (A-->B and B-->A) to be able to move freely between them.
This allows unidirectional paths (swiftly flowing rivers, for example, where upstream movement is impossible) as well as unidirectional teleporters connecting non-adjacent nodes (i.e. airports). If a vector is assigned an additional value for movement cost, it is possible to make uphill movement slower than downhill movement, to implement ocean currents and persistent strong winds. With another value for unit restriction, the differentiation between land and sea units is implemented, and it also becomes possible to disallow tanks travelling through swamps or implement "mountaineer" units that can cross high mountains.
[edit] Backwards Compatibility & Advances
With this method it is still possible to play on flat, "standard" maps, with or without wraparound effects. At the same time it becomes entirely possible to create spherical maps (true planets) as well as multi-submap systems (several planets, moons, asteroids... travel between the submaps becoming possible with space flight). Another possible extra is allowing multiple-level oceans - allowing seafloor installations with ships passing overhead.
[edit] Graphics
For display purposes, the nodes should be "expanded" into tiles - the middle points between adjacent nodes and the center of each enclosed triangle are calculated and connected to form the border between neighboring tiles. This is, of course, the same as creating the geometric dual (turning "corners" into "sides" and vice versa).
Another nice thing is that any computer-generated 3d object can be played on - they all consist of nodes (vertices) connected to other nodes to form triangular faces. The actual visual representation of the playing field would, of course, be the geometric dual of the original object.
The camera could for simplicity's sake be always directed at the center of gravity of the map. For "closed" convex maps (spheres etc.), it can be calculated - for other types, it can be defined by the user. In the standard civ-style map, the center of gravity would be linear - the center line of the cylinder.
[edit] Troubles & Troubleshootings
Pathfinding is, of course, a little bit more complicated. The algorithms for it might be created analogous to internet package transfer - jumping from node to node along the fastest connections. Unfortunately, I don't know enough about how internet package transfer really works, so I need some help here :)
System resource usage will increase without a doubt. Where the standard grid map only needs to store two coordinates per tile (x and y) and simply adds or subtracts whole numbers to calculate the next position in movement, the node-net needs to store three-dimensional coordinates and outgoing vectors for each node.
Node identification could be done using their spatial coordinates, but it might be better to instead give each node a unique identifier instead. This allows for in-game modification of coordinates (sea level changes, tectonics, large-scale bombardment effects) without breaking the incoming vector connections. The easiest way of creating this unique identifier would probably be to number them in ascending order at the moment of creation... this creates two additional problems: It wil get very confusing for humans looking at the saved games, and we have to be careful to allow high numbers of nodes so that later we don't run into a wall of overflow errors.
Pathfinding might work something like this: first we look for a directly connecting vector. then the system checks whether the origin and destination nodes are on the same sub-net. then the nodes that are closest to a direct line between origin and destination are selected and the vectors connecting them are parsed. if this "direct" route contains vectors with high movement cost or unusable vectors (impassable for selected unit), the adjacent vectors are checked for a simple detour. once the fastest way is found, the system looks for nodes with connections to non-adjacent tiles within a radius reachable in less than the shortest time and looks for shorter paths from their destinations to the final destination.
In order to prevent enormous resource usage, we might also just disallow long-distance travel, instead implementing a waypoint-system. Instead of having to calculate one long path, the game then only has to deal with several short paths, probably decreasing the total possible paths greatly.
Keyboard movement commands are a problem... on a geodesic sphere-based node-net, we can superimpose the w-e-a-d-y-x movement keys on the adjacent tiles. If multiple levels and the like are involved, we need to find more creative solutions.
[edit] Conclusion
If we are not scared by an increase in resource usage, I think this might be the way to go. Of course, this will probably mean starting from scratch. I don't know enough about the code used in freeciv, but I guess it is different from this. or is it?
--moriarty 09:31, 26 Jun 2006 (PDT)
[edit] "different approach" - possible or not?
let me open this discussion page with a simple question for the programmers: is it possible to create a game system that uses the mechanics I proposed? If no, why not? --moriarty 10:52, 26 Jun 2006 (PDT)
I have a difficulty visualising what you are suggesting. Per 14:35, 26 Jun 2006 (PDT)
that's probably because I have difficulties expressing what I am visualizing :) I'll try to put it another way. The "node-net" would look like a simple mesh model (for example a "geosphere", or for simpler things, a flat plane of regularly arranged vertices like
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
the nodes / vertices (or "points") are possible unit positions, and the vectors (or "lines") are possible movement paths. if a unit wants to move from one node to another, the system checks for a vector that connects the two nodes, and if it exists, changes the unit position to the new node, subtracting the vector's movement cost from the unit's movement points. as simple as that. since the new position does not need to be exactly "one tile length" away from the previous position in this model, the arrangement, shape, size and everything of the tile is completely irrelevant.--moriarty 22:22, 26 Jun 2006 (PDT)
- I am not very experienced programmist, but i can surely say something about this: making boards for computer games based on nets is harder than arrays, and ai would be probably consuming so much energy, that it would be senseless to use it. Next problem is it will be unintuitive for a player to play on it. Better find good (for this game)sytem of positioning on sphere with 2 or 3 variables. Kshinji 05:24, 27 Jun 2006 (PDT)
I suspect that the programming needs to be a whole lot more clever to avoid needing too much computer power, true. I think this might be done by confining AI operations to small parts of the actual net. I think it might be possible to program it so that instead of trying to parse the whole net for movement paths or strategies, the AI looks at the immediate surroundings of the unit and then decides on an action, perhaps "influenced" by a global tactic that is calculated without looking at every detail. This might even make the AI more "human", sometimes overlooking small details.--moriarty 08:23, 27 Jun 2006 (PDT)
I do not see how the "different approach" model solves any problems. Instead, I see other problems that has to be solved, which is how to calculate which nodes are adjacent, and how to draw polygons the way the player would expect them for movement. Consider a grid which would yield a map of square tiles (numbers are nodes):
1 2 3
4 5 6
7 8 9
Movement in a square world, like in civ1, would be in 8 directions, but only 4 of those are strictly adjacent. Such a square has 4 edge neighbours and 4 additional vertex neighbours. This is simple for hex maps, and also combined hex/pentagon maps, where there are no vertex neighbours who are not also edge neighbours, but for a generalized topology system like what you suggest we do not know beforehand how this should play out. Notice how, if we only identified closest nodes as adjacent for polygon drawing and movement purposes, following the suggested drawing method, we would get a tilted square in the above example, drawn with vertices between (2,5), (4,5), (5,6) and (5,8), but movement would be expected to go across the tile's edges, not across its vertices. Notice, also, for spheres, you would still get some tiles as hexagons and some (12) as pentagons. A big problem for the basic sphere idea is that we all tiles in two variants. However, for the nodes idea, many more variants are needed, as we may not always get only hexagons or pentagons. Per 05:53, 30 Jun 2006 (PDT)
actually, I don't think adjacency should be an issue at all. The question whether a tile is connected to another is only defined by the vector(s) connecting the two tiles. whether there _is_ a vector is a problem of map creation. For that, there should be different possibilities, allowing eight-way connected tiles like in civ, or six-way connected tiles like in freeciv with hex grid, or any other kind of connection, really. and there is no problem with having different kinds of tiles in one map. of course, map creation should be done reasonably, unless we want to have utterly confusing and unplayable maps. that's why I think the map editor should start out by creating a "net" of nodes and vectors in the form of a convex 3d mesh, the kind we know from CAD programs.--moriarty 07:42, 4 Jul 2006 (PDT)