Loading ...
Sorry, an error occurred while loading the content.

addressing on a icosahedron

Expand Messages
  • Brandon J. Van Every
    Oh the trials and tribulations of the 4X wargame designer. After watching far too many sci-fi movies and contemplating how to sell a storyline, I came to
    Message 1 of 15 , Jun 7, 2001
    • 0 Attachment
      Oh the trials and tribulations of the 4X wargame designer. After watching
      far too many sci-fi movies and contemplating how to "sell" a storyline, I
      came to the inescapable conclusion that gorgeous planetary landscapes from
      space are the way to go. Toroids, no matter how analytically elegant for
      gridding purposes, just don't cut it. Topologically, I've settled on an
      icosahedron with hexes covering the triangular faces. This implies that the
      "hexes" at the 12 vertices will in fact have to be pentagons. A wrinkle in
      the topological elegance, and not something I wanted, but the guys on
      sci.math tell me it's impossible to cover a sphere with only hexes. Even
      oddly shaped hexes. Has to do with Euler's rule.

      So, given what I'm going to do, has anyone already thought up a preferred
      addressing scheme for the icosahedron I've described? Not that this is
      hard, just that I'm happy to borrow people's previously used brain cells.
      Chasing elegance does consume hours.

      Also, my current opinion is that the map is inherently 3D and there is no
      purpose whatsoever in ever doing any kind of 2D display (aside from local
      zooming). It would just cause people to make mistakes about what's next to
      what. Can't see the whole planet at once? Well, that's how planets
      fundamentally are, so they should be kept that way. Anyone want to gainsay
      this opinion?


      Cheers, www.3DProgrammer.com
      Brandon Van Every Seattle, WA

      20% of the world is real.
      80% is gobbledygook we make up inside our own heads.
    • Brandon J. Van Every
      ... BTW by addressing scheme I don t mean how to pack the stuff into memory. I mean how to assign numerical coordinates to the hexes so that we can easily
      Message 2 of 15 , Jun 7, 2001
      • 0 Attachment
        > So, given what I'm going to do, has anyone already thought up a preferred
        > addressing scheme for the icosahedron I've described?

        BTW by "addressing scheme" I don't mean how to pack the stuff into memory.
        I mean how to assign numerical coordinates to the hexes so that we can
        easily make mathematical statements about the relationships between hexes.
        Such as distances, or where a hex is upon the globe.

        Peter made a good point in private e-mail: as far as explaining spherical
        locations to the user is concerned, it would be easiest to simply use
        (latitude, longitude) like we do for Earth. That's great for users
        intuitively grasping global position. Doesn't do anything as far as making
        it easy to figure out how far away something is, though.


        Cheers, www.3DProgrammer.com
        Brandon Van Every Seattle, WA

        20% of the world is real.
        80% is gobbledygook we make up inside our own heads.
      • Adam Baratz
        ... making ... GPSes calculate distance using longitude and latitude. Get both of the points and find the delta for longitude and latitude. You then know how
        Message 3 of 15 , Jun 7, 2001
        • 0 Attachment
          > Peter made a good point in private e-mail: as far as explaining spherical
          > locations to the user is concerned, it would be easiest to simply use
          > (latitude, longitude) like we do for Earth. That's great for users
          > intuitively grasping global position. Doesn't do anything as far as
          making
          > it easy to figure out how far away something is, though.

          GPSes calculate distance using longitude and latitude. Get both of the
          points and find the delta for longitude and latitude. You then know how
          many degrees out of 360 you have for each direction. You can then use the
          proportion of that to get the actual distance using a known circumference of
          your map. Then use the good old Pythagorean Theorem to get the distance.

          [this is wonderful if you have a "continuous" sphere, but Brandon doesn't, it's discrete hexes'n'pents - Peter]

          -Adam
        • Gerry Quinn
          ... the ... It s easy to make tesselations on a plane, but a sphere is more difficult because it doesn t map easily to an array. After a little thought, I came
          Message 4 of 15 , Jun 8, 2001
          • 0 Attachment
            >Oh the trials and tribulations of the 4X wargame designer. After watching
            >far too many sci-fi movies and contemplating how to "sell" a storyline, I
            >came to the inescapable conclusion that gorgeous planetary landscapes from
            >space are the way to go. Toroids, no matter how analytically elegant for
            >gridding purposes, just don't cut it. Topologically, I've settled on an
            >icosahedron with hexes covering the triangular faces. This implies that
            the
            >"hexes" at the 12 vertices will in fact have to be pentagons. A wrinkle in
            >the topological elegance, and not something I wanted, but the guys on
            >sci.math tell me it's impossible to cover a sphere with only hexes. Even
            >oddly shaped hexes. Has to do with Euler's rule.
            >
            >So, given what I'm going to do, has anyone already thought up a preferred
            >addressing scheme for the icosahedron I've described? Not that this is
            >hard, just that I'm happy to borrow people's previously used brain cells.
            >Chasing elegance does consume hours.

            It's easy to make tesselations on a plane, but a sphere is more difficult
            because it doesn't map easily to an array.

            After a little thought, I came up with this:

            class MapNode
            {
            // Pointers to 6 neighbours (one may be null)
            MapNode* m_Neighbours[6];
            // Exact coordinate values of map node
            double m_Latitude;
            double m_Longitude;
            };

            // Array of nodes (some will not exist on map)
            MapNode m_Map[NODES_ALONG_EQUATOR][NODES_ALONG_MERIDIAN];

            // This allows calculations based on direction etc.
            MapNode* GetMapNode( double latVal, double longVal )
            {
            // I can't be bothered to do the math in detail
            // x is easy to get from the longitude
            // make a guess at y from the latitude
            // then find the nearest, and test that and its nearest neighbours
            // one of them will be the node you want
            // maybe you can get an exact formula, but you may have to skip over a
            few non-nodes before you find the nearest which is actually valid.
            }

            For plotting directions, a Mercator transformation might be useful.

            Gerry Quinn
            --
            http://bindweed.com
            Puzzles, Strategy Games, Kaleidoscope Screensaver
            Download evaluation versions free - no time limits
            New puzzle challenge: "Dragon Scales"











            >
            >Also, my current opinion is that the map is inherently 3D and there is no
            >purpose whatsoever in ever doing any kind of 2D display (aside from local
            >zooming). It would just cause people to make mistakes about what's next to
            >what. Can't see the whole planet at once? Well, that's how planets
            >fundamentally are, so they should be kept that way. Anyone want to gainsay
            >this opinion?
            >
            >
            >Cheers, www.3DProgrammer.com
            >Brandon Van Every Seattle, WA
            >
            >20% of the world is real.
            >80% is gobbledygook we make up inside our own heads.
            >
            >
            >
            >To unsubscribe send an email to:
            >gamedesign-l-unsubscribe@egroups.com
            >
            >
            >
            >Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
            >
            >
            >
          • Brandon J. Van Every
            ... I ve now got a scheme that exhibits a high degree of coordinate symmetry. Imagine the 20 triangular faces as 10 groups of 2 triangles. 2 triangles
            Message 5 of 15 , Jun 8, 2001
            • 0 Attachment
              > So, given what I'm going to do, has anyone already thought up a preferred
              > addressing scheme for the icosahedron I've described?

              I've now got a scheme that exhibits a high degree of coordinate symmetry.
              Imagine the 20 triangular faces as 10 groups of 2 triangles. 2 triangles
              together form a "square," in the sense that their hexes are easy to number
              by rows and columns. The 5 groups touching the north pole are the "Northern
              Hemisphere" and the 5 groups touching the south pole are the "Southern
              Hemisphere." Of course that's only my choice of verbiage, they aren't
              hemispheres at all, actually they look like 5-pointed flowers turned
              downwards or upwards, respectively.

              10 of the vertices belong to the 10 groups of 2 triangles. You have to
              ignore the north and south pole, they're 2 extra vertices and don't belong
              to anything. Maybe the north pole should have the most positive coordinate
              and the south pole the most negative coordinate. All of the "Northern
              Hemisphere" hexes would be positive, and the "Southern Hemisphere" hexes
              would be negative.

              It seems that all the edges are shared properly. Each group of 2 triangles
              "owns" 2 edges that are shared with other groups, and has 1 edge that's
              completely internal to the group. 10 * (2 + 1) = 30 edges, which is what an
              icosahedron has got. That said, the devil is in the details. I can't quite
              visualize if I've got this correct on paper. I might be double counting
              something, I'm not sure if I've got ownership correct.

              If this addressing scheme is correct, then the various groups would have
              coordinates (well, an ordinate) like:
              [-321],
              [-320..-257], [-256..-193], [-192..-129], [-128..-65], [-64..-1],
              [0..63], [64..127], [128..191], [192..255], [256..319],
              [320].

              If so, then distances and directions may have some useful properties.

              > Also, my current opinion is that the map is inherently 3D and there is no
              > purpose whatsoever in ever doing any kind of 2D display (aside from local
              > zooming).

              Actually I've discovered that you can view the entire icosahedron unfolded
              in a pentagonal arrangement. The "Northern Hemisphere" becomes a central
              flower shape, and the "Southern Hemisphere" fills in the gaps around the
              central flower shape. The overall effect is that with respect to the north
              pole, the closest hexes are closest, and the farthest hexes are farthest
              away at the edge of the pentagon. The player would have to remember that
              everything wraps around at the outside, but in the interior, everything is
              quite intuitive. Such a 2D map could have a lot of strategic value, you
              could plan things in terms of what's closest or farthest away. And of
              course you can center this map on any vertex, not just the north pole.

              On a spherical map this would be analogous to showing the northern
              hemisphere, then showing the southern hemisphere as peripheral shredded
              triangles. But because we're dealing with a hex-gridded icosahedron, we
              actually get to see 3/4 of the "globe" for nuthin' without distortion, and
              the remaining 5 triangles rip neatly away in a pretty pattern! Cool huh.


              Cheers, www.3DProgrammer.com
              Brandon Van Every Seattle, WA

              20% of the world is real.
              80% is gobbledygook we make up inside our own heads.
            • Brandon J. Van Every
              ... Unfortunately, this doesn t provide any mathematical relations between hexagonal nodes on an icosahedron. ... On a hexagonally tiled icosahedron, latitudes
              Message 6 of 15 , Jun 8, 2001
              • 0 Attachment
                > class MapNode
                > {
                > // Pointers to 6 neighbours (one may be null)
                > MapNode* m_Neighbours[6];
                > // Exact coordinate values of map node
                > double m_Latitude;
                > double m_Longitude;
                > };

                Unfortunately, this doesn't provide any mathematical relations between
                hexagonal nodes on an icosahedron.

                > // Array of nodes (some will not exist on map)
                > MapNode m_Map[NODES_ALONG_EQUATOR][NODES_ALONG_MERIDIAN];

                On a hexagonally tiled icosahedron, latitudes are easy. Longitude in the
                middle half of the icosahedron is easy, since the middle half is a
                wraparound 10 triangle strip. Basically, a cylinder, so you can associate a
                unique longitude in that region. But at the northern and southern polar
                caps, all the longitudes converge. Thus longitude doesn't exist over the
                entire icosahedron in any quantized sense.

                I wonder if some notion of "spread" is possible instead, using some kind of
                truncated ceil(x) floor(x) math. Don't know if that would be
                computationally desireable though.

                Hmm I wonder if some method of half-cylinders is possible. First an
                orientation to establish a given half-cylinder. That's simply naming a
                vertex, or more exactly, an axis between opposite poles. There are 10
                half-cylinders possible, assuming you don't care about positive or negative
                orientation. Of course, whatever hexes these cylinders name, the names are
                not going to be unique. Might be useful idea for certain algorithms though.


                Cheers, www.3DProgrammer.com
                Brandon Van Every Seattle, WA

                20% of the world is real.
                80% is gobbledygook we make up inside our own heads.
              • Gerry Quinn
                ... It s not meant to. For local pathfinding, you use the network connections. For distant destinations, you calculate a direction. Come to think of it, you
                Message 7 of 15 , Jun 8, 2001
                • 0 Attachment
                  >> class MapNode
                  >> {
                  >> // Pointers to 6 neighbours (one may be null)
                  >> MapNode* m_Neighbours[6];
                  >> // Exact coordinate values of map node
                  >> double m_Latitude;
                  >> double m_Longitude;
                  >> };
                  >
                  >Unfortunately, this doesn't provide any mathematical relations between
                  >hexagonal nodes on an icosahedron.

                  It's not meant to. For local pathfinding, you use the network connections.
                  For distant destinations, you calculate a direction. Come to think of it,
                  you don't really often need to find a given distant node, just the direction
                  to it! Why do you want a mathematical relation? The whole point of a map
                  is that it represents a particular configuration of the world, which need
                  not obey any simple mathematical rules.

                  Example: I want my tank to go to City A. A has longitude +30 degrees,
                  latitude +25 degrees. The exact direction involves a more complicated
                  calculation, but if I want a heuristic for pathfinding, north-east will do.
                  The six(five) neighbours each have an approximate direction.

                  >
                  >> // Array of nodes (some will not exist on map)
                  >> MapNode m_Map[NODES_ALONG_EQUATOR][NODES_ALONG_MERIDIAN];
                  >
                  >On a hexagonally tiled icosahedron, latitudes are easy. Longitude in the
                  >middle half of the icosahedron is easy, since the middle half is a
                  >wraparound 10 triangle strip. Basically, a cylinder, so you can associate
                  a
                  >unique longitude in that region. But at the northern and southern polar
                  >caps, all the longitudes converge. Thus longitude doesn't exist over the
                  >entire icosahedron in any quantized sense.

                  Yes, some nodes are null, but we have a grid which approximately implements
                  cylindrical coordinates.


                  Gerry Quinn
                  --
                  http://bindweed.com
                  Puzzles, Strategy Games, Kaleidoscope Screensaver
                  Download evaluation versions free - no time limits
                  New puzzle challenge: "Dragon Scales"
                • Brandon J. Van Every
                  [Regarding the pure nodal approach] ... Really, you don t want to know exactly how far away Moscow is from a particular missile silo in Kansas? If you want to
                  Message 8 of 15 , Jun 8, 2001
                  • 0 Attachment
                    [Regarding the pure nodal approach]

                    > For distant destinations, you calculate a direction. Come to think of it,
                    > you don't really often need to find a given distant node,

                    Really, you don't want to know exactly how far away Moscow is from a
                    particular missile silo in Kansas? If you want to know the distance, you
                    need a mathematically well defined addressing scheme. Otherwise you're
                    going to have to search for Moscow every time you want to know that
                    distance. Why make this a O(N) operation when a O(1) operation would do?

                    Now admittedly, any reasonable ordering of the hexes will result in a O(1)
                    distance operation. The math might be hairy and special cased but it would
                    still be O(1). It's just that all things being equal, I'd rather make it
                    simple and elegant. I'd like the ordering to impart intuitive information
                    to the user/programmer. And for all I know, from an AI standpoint it might
                    be better to have the ordering based on simple maths. Maybe it is possible
                    to do analytic computations on sets of hexes if you have the right system.
                    For example, what about the convergence of multiple missile silos upon
                    Moscow? Whereas in a "pure node" system, you'll have to manually search
                    through all the nodes that are N hexes away from a given hex.

                    > Yes, some nodes are null, but we have a grid which approximately
                    > implements cylindrical coordinates.

                    It doesn't approximately implement cylindrical coordinates. It implements
                    them around the middle of the icosahedron and completely fails to implement
                    them at the poles. There's no value in using cylindrical coordinates if
                    it's going to be half-assed. I can just see all the AI bugs that players
                    would exploit. "Stupid computer, thinks it's on a cylinder!"

                    Now, I realized early in the a.m. that you could have unique "twist"
                    coordinates. Instead of emanating the longitudes from the poles, you'd
                    emanate them from the spines around the poles. In other words, see the
                    icosahedron as 5 groups of 4 triangles in a strip. This might be an
                    improvement over my 10 groups of 2 triangles in "squares."

                    But in either case I'm still having trouble with how to number the poles.
                    It would be nice to have all vertices have a common property, like all being
                    multiples of 64 (or 2^n more generally). That way, you'd easily know where
                    your pentagons are. Problem is you've got 10 blocks of hexes and 12
                    vertices, so there's a numerical gap. i.e.

                    [0..63], [64..127], [128..191], [192..255], [256..319], [320..383],
                    [384..447], [448..511], [512..575], [576..639], [640..ack!], [704]

                    If you do this in a linearly ascending order there will always be this gap
                    somewhere, since you can't put 12 things around 10 things. I could make
                    zero a null value and fiddle the positives and negatives:

                    [-321],
                    [-320..-257], [-256..-193], [-192..-129], [-128..-65], [-64..-1],
                    [0],
                    [1..64], [65..128], [129..192], [193..256], [257..320],
                    [321]

                    So, now all addresses are contiguous except for the zero gap. The vertices
                    all have the form i*2^n + 1, which is an easy enough bit pattern to test
                    for, if not as cool as just i*2^n. What I don't like about this is now I've
                    got to do everything in terms of absolute values, and nothing starts from 0.
                    Well, maybe that's not such a big deal in the real world, I dunno.


                    Cheers, www.3DProgrammer.com
                    Brandon Van Every Seattle, WA

                    20% of the world is real.
                    80% is gobbledygook we make up inside our own heads.
                  • Scott Le Grand
                    ... Yep, does NASA or NORAD think this way? I liked this idea at first (loved that scene in ST II with the Reliant and the Enterprise on opposite sides of the
                    Message 9 of 15 , Jun 8, 2001
                    • 0 Attachment
                      At 04:18 PM 6/7/2001 -0700, you wrote:
                      >Also, my current opinion is that the map is inherently 3D and there is no
                      >purpose whatsoever in ever doing any kind of 2D display (aside from local
                      >zooming). It would just cause people to make mistakes about what's next to
                      >what. Can't see the whole planet at once? Well, that's how planets
                      >fundamentally are, so they should be kept that way. Anyone want to gainsay
                      >this opinion?

                      Yep, does NASA or NORAD think this way? I liked this idea at first (loved
                      that scene in ST II with the Reliant and the Enterprise on opposite sides
                      of the planetoid), but thinking strategically, I'd tell you to get stuffed
                      if you threw an interface like that at me. Make it an option, sure, but
                      give me a Mercator projection or give me death!

                      Have you looked into whether the military is considering 3D display
                      technology for this sort of thing? They usually have some pretty cool
                      ideas about this kind of information...

                      Scott
                    • Brandon J. Van Every
                      ... Why Mercator, specifically? It s rather nasty around the poles if your goal is to play your game on a proper sphere. If you just want to play a game on a
                      Message 10 of 15 , Jun 8, 2001
                      • 0 Attachment
                        > Yep, does NASA or NORAD think this way? I liked this idea at
                        > first (loved
                        > that scene in ST II with the Reliant and the Enterprise on opposite sides
                        > of the planetoid), but thinking strategically, I'd tell you to
                        > get stuffed
                        > if you threw an interface like that at me.

                        > Make it an option, sure, but
                        > give me a Mercator projection or give me death!

                        Why Mercator, specifically? It's rather nasty around the poles if your goal
                        is to play your game on a proper sphere. If you just want to play a game on
                        a cylinder and pretend it's a sphere, I'd agree with you, but you're not
                        playing the same game. Anyways, I think the "pentagonal foldout" I
                        described in another post is a better 2D projection than Mercator. It tells
                        you whether things are close or far away in every direction, which is the
                        most important thing. An easy trick with polyhedrons, not so easy a trick
                        with spheres.

                        > Have you looked into whether the military is considering 3D display
                        > technology for this sort of thing? They usually have some pretty cool
                        > ideas about this kind of information...

                        Not really. sci.math is about as far as I felt I needed to go. The CIA
                        world database is drawn with vector splines that are probably proper 3D
                        entities, and that's way more math intensive than would be useful for a
                        game.


                        Cheers, www.3DProgrammer.com
                        Brandon Van Every Seattle, WA

                        20% of the world is real.
                        80% is gobbledygook we make up inside our own heads.
                      • Gerry Quinn
                        ... From: Brandon J. Van Every To: gamedesign-l@yahoogroups.com Date: 08 June 2001 22:24 Subject:
                        Message 11 of 15 , Jun 9, 2001
                        • 0 Attachment
                          -----Original Message-----
                          From: Brandon J. Van Every <vanevery@...>
                          To: gamedesign-l@yahoogroups.com <gamedesign-l@yahoogroups.com>
                          Date: 08 June 2001 22:24
                          Subject: RE: [gamedesign-l] addressing on a icosahedron


                          >[Regarding the pure nodal approach]
                          >
                          >> For distant destinations, you calculate a direction. Come to think of
                          it,
                          >> you don't really often need to find a given distant node,
                          >
                          >Really, you don't want to know exactly how far away Moscow is from a
                          >particular missile silo in Kansas? If you want to know the distance, you
                          >need a mathematically well defined addressing scheme. Otherwise you're
                          >going to have to search for Moscow every time you want to know that
                          >distance. Why make this a O(N) operation when a O(1) operation would do?

                          Moscow is in the city list. And a spotted enemy tank is in the current
                          target list. So your problem, as I see it, is only to decide how far it is
                          away. In traditional Civs, this is handled by making you count along the
                          missile path, with the missile taking a detour around any tanks in the way,
                          because the crude user interface cannot distinguish between passing over an
                          enemy and destroying it. Time to think out of the box! Missiles go directly
                          to their destinations, and possible targets will glow as the mouse passes
                          over them (or they all glow when you click on the missile). Missile
                          performance degrades at maximum distance, dropping from normal to zero over
                          a certain range (can be impemented as performance loss or percentage
                          failure). Distance is based on the latitude and longitude of the node
                          centres, not on the number of nodes traversed.

                          The AI will handle this okay especially if implemented as a percentage
                          failure. AIs are not demoralised by wasting occasional missiles - this sort
                          of fuzziness will be good for the AI. If players don't like it, they can
                          wait until the target gets in range.

                          >> Yes, some nodes are null, but we have a grid which approximately
                          >> implements cylindrical coordinates.
                          >
                          >It doesn't approximately implement cylindrical coordinates. It implements
                          >them around the middle of the icosahedron and completely fails to implement
                          >them at the poles. There's no value in using cylindrical coordinates if
                          >it's going to be half-assed. I can just see all the AI bugs that players
                          >would exploit. "Stupid computer, thinks it's on a cylinder!"
                          >

                          Maybe so, but I don't know *what* it will think it's on with your system!
                          One advantage of the nodes is that they are blind to anything of this kind.
                          Node pathfinding logic will have no discontinuities, no 'edge longitude' and
                          no poles. Combine this with a geometric representation, and implement
                          switching between representations in any ugly but efficient manner you
                          desire, and surely you get the best of both worlds?

                          >Now, I realized early in the a.m. that you could have unique "twist"
                          >coordinates. Instead of emanating the longitudes from the poles, you'd
                          >emanate them from the spines around the poles. In other words, see the
                          >icosahedron as 5 groups of 4 triangles in a strip. This might be an
                          >improvement over my 10 groups of 2 triangles in "squares."

                          It might be worth trying to find out what Populous 3 did - I only played the
                          demo but it had a nice spherical implementation.


                          Gerry Quinn
                          --
                          http://bindweed.com
                          Puzzles, Strategy Games, Kaleidoscope Screensaver
                          Download evaluation versions free - no time limits
                          New puzzle challenge: "Dragon Scales"
                        • philar@hotmail.com
                          ... I knew that (deep, deep down) you really loved spheres. Welcome aboard. :-) ... Sadly, much as I tried to prove them otherwise, it seems that the sci.math
                          Message 12 of 15 , Jun 18, 2001
                          • 0 Attachment
                            --- In gamedesign-l@y..., "Brandon J. Van Every" <vanevery@3...>
                            wrote:
                            > Oh the trials and tribulations of the 4X wargame designer. After
                            > watching far too many sci-fi movies and contemplating how to "sell"
                            > a storyline, I came to the inescapable conclusion that gorgeous
                            > planetary landscapes from space are the way to go. Toroids, no
                            > matter how analytically elegant for gridding purposes, just don't
                            > cut it.

                            I knew that (deep, deep down) you really loved spheres. Welcome
                            aboard. :-)

                            > Topologically, I've settled on an icosahedron with hexes covering
                            > the triangular faces. This implies that the "hexes" at the 12
                            > vertices will in fact have to be pentagons. A wrinkle in the
                            > topological elegance, and not something I wanted, but the guys on
                            > sci.math tell me it's impossible to cover a sphere with only hexes.
                            > Even oddly shaped hexes. Has to do with Euler's rule.

                            Sadly, much as I tried to prove them otherwise, it seems that the
                            sci.math fellows are correct.

                            > So, given what I'm going to do, has anyone already thought up a
                            > preferred addressing scheme for the icosahedron I've described?

                            I gave up on 20-sided solids due to the difficulty of mapping between
                            the internal representaion, lattitude/longitude, and 3D space. My
                            preferred model is an eight-sided polyhedron (I can't recall the
                            technical name for this creature off the top of my head).

                            Positioning this solid on the origin with the verticies all lying
                            along the 3D axies gives you nice clean end-point co-ordinates, and
                            you have one face per 3D 'octant' around the origin (or whatever
                            they're called in 3D-speak). You can easily tell which major triangle
                            a 3D point belongs in by checking the sign of its co-ordinates.

                            For internal addressing I divide the figure into four square quadrants
                            of two triangles each (one north, one south). (0,0) and (1,1) in each
                            quadrant lie on the equator, (0,1) is the north pole and (1,0) is the
                            south pole.

                            Using one method of hexifying the triangular grids gives you 6 squares
                            (at the verticies) joining the hexagon meshes together. Since two of
                            these lie on the poles you're only really stuck with the inelegance of
                            the four around the equator. At least you know which points are
                            inelegant - they're the (0,0) [== (1,1)] ones.

                            Using another method of hexifying the triangular grid you end up with
                            6 pentagon pairs joining the hexagon meshes (again at the verticies).
                            Although you have a larger number of non-hexagon regions this way it
                            appears to be more asthetically pleasing - the joining squares in the
                            above method are noticably smaller than the other hexagons, while the
                            joining pentagons in the second method seem to cover about the same
                            area.

                            I don't want to go into more technical detail on the internal
                            implementation here - it's straying a bit far from game design. If
                            anyone is interested in viewing an implementation of the first method
                            described above drop me a line and I'll send you an old DOS.exe I
                            compiled many moons ago. It shows a sphere covered in about 4 million
                            hexagons, connected together with 6 squares.

                            > Also, my current opinion is that the map is inherently 3D and there
                            > is no purpose whatsoever in ever doing any kind of 2D display (aside
                            > from local zooming). It would just cause people to make mistakes
                            > about what's next to what. Can't see the whole planet at once?
                            > Well, that's how planets fundamentally are, so they should be kept
                            > that way. Anyone want to gainsay this opinion?

                            I agree in general, but a 2D whole-world map (however much distorted)
                            at least allows the player to spot something and zoom to it quickly. I
                            couldn't play Populous 3 because of the difficulty in locating
                            hotspots.

                            Getting back to Euclid, if you WERE going to do a 2D display (to
                            support lower-spec machines, too?) then using an 8-sided solid means
                            you can display the whole planet as a single square - albeit with
                            significant distortion/misrepresentation on the opposing hemisphere
                            (outer corner) portions. Of course (as with a 20-sided polyhedron) you
                            can always move the centre of projection to another of the connecting
                            points as you go.

                            The main advantage of an 8-sided over a 20-sided object here is that
                            the flat projection is a square. The vertical and horizonal lines look
                            cleaner on raster displays and you don't waste any screen space in
                            non-map void.

                            ---

                            Back to game design, the inelegant connecting points pose interesting
                            problems (regardless of the number of sides in your polyhedra).

                            Since the connecting points have fewer borders than a hexagon, units
                            within them can be surrounded by fewer units than normal. Depending on
                            your conflict resolution mechanic this could be either a good or a bad
                            thing.

                            You might want to place the players' starting cities in these
                            positions to ensure that the players are evenly spaced (with an
                            eight-sided world you only have 4 starting positions, though, unless
                            the polar caps are also viable). A favourable combat mechanic could
                            also make these starting cities more defendable.

                            You might want to place special resources in these positions
                            (especially in a fantasy setting where you could place mana reserves
                            here). This makes these areas - already special because of their
                            topology - into specific and valuable strategic considerations.

                            Alternatively you may not want these areas used, in which case you
                            would have to ensure that the terrain at these points is mostly
                            unusable (e.g.: water, ice) or that there are other reasons that
                            players will want to avoid these areas.

                            Hope I've provided a little food for thought.

                            -Phil
                          • Brandon J. Van Every
                            ... Hmm I forgot about both the octahedron and the cube. You have a point regarding coordinate systems. On the other hand, I ve gone so far with analyzing the
                            Message 13 of 15 , Jun 18, 2001
                            • 0 Attachment
                              > I gave up on 20-sided solids due to the difficulty of mapping between
                              > the internal representaion, lattitude/longitude, and 3D space. My
                              > preferred model is an eight-sided polyhedron (I can't recall the
                              > technical name for this creature off the top of my head).

                              Hmm I forgot about both the octahedron and the cube. You have a point
                              regarding coordinate systems.

                              On the other hand, I've gone so far with analyzing the icosahedron that I'm
                              not ready to turn back yet. I've found that the hexes on the icosahedron
                              can be evenly packed in the form 10n(n-1) + 12, where n(n-1) is a "square"
                              of 2 triangles, and 12 are the extra pentagonal vertices. Each "square"
                              only owns 2 of its 4 edges, hence the (n-1). So the memory layout is
                              spiffy, and I'm still trying to decide upon coordinates. In the above model
                              there are of course 10 natural regions of n(n-1) "square" addressing. So
                              worst case, 10 different regions + 12 special names for the vertices. I'm
                              hoping to do better than that, to find a numbering of vertices such that a
                              vertex + all its neighbors always adds up to a constant value. But my
                              number crunching programs got deleted in some idiot snafu in VC++ on Friday,
                              and I haven't had time to reconstruct them.

                              Oh, and in case it isn't clear the 10n(n-1) + 12 arrangment means that the
                              10 "squares" do not own the vertices at all. They are a completely separate
                              set. All the "squares" (well, rectangles really) just slide and fit right
                              around the vertices. So clearly when you make up a coordinate system, you
                              can always know exactly which the 12 special pentagonal "hexes" are. The
                              downside is this coordinate system may not be continuous, it may have to be
                              segmented. I'm still working on that.

                              > Getting back to Euclid, if you WERE going to do a 2D display (to
                              > support lower-spec machines, too?)

                              Personally I could care less about "low spec" machines. It's going to be
                              awhile before my project is finished. I bought a new box in December 2000
                              with a GeForce2 and now we're on to GeForce3. Who knows what we'll be on to
                              by December 2001. I don't really see a point in making a slick sexy 3D
                              version of a movie and then a grungy 2D version of a movie. Either make the
                              movie in 2D or 3D to begin with. Computationally I'm hoping the AI will
                              bring most machines to their knees anyways. :-)

                              > The main advantage of an 8-sided over a 20-sided object here is that
                              > the flat projection is a square. The vertical and horizonal lines look
                              > cleaner on raster displays and you don't waste any screen space in
                              > non-map void.

                              As I realized in a later post, you can display any polyhedron flatly by
                              folding out the backside. There will be distortion but it's easy to do. In
                              the case of an icosahedron you'll get a pentagon. Wasted space but heh, so
                              what, fill it up with something cute.

                              > You might want to place the players' starting cities in these
                              > positions to ensure that the players are evenly spaced (with an
                              > eight-sided world you only have 4 starting positions, though, unless
                              > the polar caps are also viable). A favourable combat mechanic could
                              > also make these starting cities more defendable.

                              I'm not in favor of this. IMHO it is important to handle asymmetry in 4X
                              start conditions. Also I see no reason to limit a game to 6 players.

                              > Alternatively you may not want these areas used, in which case you
                              > would have to ensure that the terrain at these points is mostly
                              > unusable (e.g.: water, ice) or that there are other reasons that
                              > players will want to avoid these areas.

                              If you make the 4-sided "hex" absolutely impassable, then all you've done is
                              rearrange your topology so that there are now 4 5-sided "hexes" surrounding
                              the vertices. You haven't eliminated the defensive advantages of having
                              only 5 sides, you've only spread the problem out.


                              Cheers, www.3DProgrammer.com
                              Brandon Van Every Seattle, WA

                              20% of the world is real.
                              80% is gobbledygook we make up inside our own heads.
                            • philar@hotmail.com
                              ... You get 4n^2 + 2 for an Octohedral world. Other benefits include: 1) Each of the four quadrants uses identical addressing and transformation functions
                              Message 14 of 15 , Jun 27, 2001
                              • 0 Attachment
                                --- In gamedesign-l@y..., "Brandon J. Van Every" <vanevery@3...>
                                wrote:
                                > > I gave up on 20-sided solids due to the difficulty of mapping
                                > > between the internal representaion, lattitude/longitude, and 3D
                                > > space. My preferred model is an eight-sided polyhedron (I can't
                                > > recall the technical name for this creature off the top of my
                                > > head).
                                >
                                > Hmm I forgot about both the octahedron and the cube. You have a
                                > point regarding coordinate systems.
                                >
                                > On the other hand, I've gone so far with analyzing the icosahedron
                                > that I'm not ready to turn back yet. I've found that the hexes on
                                > the icosahedron can be evenly packed in the form 10n(n-1) + 12,
                                > where n(n-1) is a "square" of 2 triangles, and 12 are the extra
                                > pentagonal vertices. Each "square" only owns 2 of its 4 edges,
                                > hence the (n-1). So the memory layout is spiffy, and I'm still
                                > trying to decide upon coordinates. In the above model there are
                                > of course 10 natural regions of n(n-1) "square" addressing. So
                                > worst case, 10 different regions + 12 special names for the
                                > vertices.

                                You get 4n^2 + 2 for an Octohedral world.

                                Other benefits include:

                                1) Each of the four quadrants uses identical addressing and
                                transformation functions (rotated 0/90/180/270 degrees around the
                                polar axis).

                                2) The equator can be defined as those regions where x = y (regardless
                                of the quadrant).

                                3) You can tell when a region is in the Northern Hemisphere by
                                checking if y > x (& v.v. for the S.H.).

                                4) Because of distortion the lattitude of a region isn't exactly a
                                direct function of y - x... but you could use it as such depending on
                                the amount of distortion you're willing to accept.

                                These calculations are fairly simple; their equivalents on other
                                polyhedra are not quite so.


                                > > Alternatively you may not want these areas used, in which case you
                                > > would have to ensure that the terrain at these points is mostly
                                > > unusable (e.g.: water, ice) or that there are other reasons that
                                > > players will want to avoid these areas.
                                >
                                > If you make the 4-sided "hex" absolutely impassable, then all
                                > you've done is rearrange your topology so that there are now 4
                                > 5-sided "hexes" surrounding the vertices. You haven't eliminated
                                > the defensive advantages of having only 5 sides, you've only
                                > spread the problem out.

                                I didn't say to remove these areas from play by making them
                                impassable, but to make their contents less desirable/useful so that
                                they have less of an impact during normal play. e.g.: low resource
                                terrain and/or [the equivalent of] water.

                                Players will then visit these specific areas less often and so the
                                rather minor problem their unique topology inflicts can be minimised
                                without having to resort to any of the other special cases I offered.

                                ---

                                If you were really intent on retaining full hexagonal movement across
                                the whole map you could remove the vertex squares from play and
                                allocate their map space to the surrounding hexagons. Visually these
                                hexagons would now look like pentagons all touching a common point
                                (the vertex itself). Allowing units to "cross the diagonal" of the
                                vertex in question would ensure that every region on the map has six
                                full movement directions.

                                -Phil
                              • Brandon J. Van Every
                                ... This is equivalent to keeping the hexagons + square arrangement, and saying that anytime the square is moved into, the unit is immediately moved out the
                                Message 15 of 15 , Jun 27, 2001
                                • 0 Attachment
                                  > If you were really intent on retaining full hexagonal movement across
                                  > the whole map you could remove the vertex squares from play and
                                  > allocate their map space to the surrounding hexagons. Visually these
                                  > hexagons would now look like pentagons all touching a common point
                                  > (the vertex itself). Allowing units to "cross the diagonal" of the
                                  > vertex in question would ensure that every region on the map has six
                                  > full movement directions.

                                  This is equivalent to keeping the hexagons + square arrangement, and saying
                                  that anytime the square is moved into, the unit is immediately moved out the
                                  other side of the square. It should be noted that you're messing up
                                  distance relationships by doing so. It might be easier to implement it this
                                  way than the other way. It might be better to allow squares to be occupied.
                                  At least when moving into a square on an octahedron, your orientation
                                  remains well defined.

                                  I hate the idea of abandoning all my work on icosahedrons just because of
                                  those pesky pentagonal poles, but I have to concede that the octahedron is
                                  simpler. I'll need to think about it a few days.


                                  Cheers, www.3DProgrammer.com
                                  Brandon Van Every Seattle, WA

                                  20% of the world is real.
                                  80% is gobbledygook we make up inside our own heads.
                                Your message has been successfully submitted and would be delivered to recipients shortly.