How to construct a closed dodecahedronal graph?

[nuderobmonkey]

I want to re-code the ancient game Hunt The Wumpus. Therefore I want to connect the rooms of the cave to a dodecahedronal graph with a room at each corner. Some idea, how I could write an algorithm which produces such a polyhedron?

[lastchance]

http://cplusplus.com/forum/general/231249/#msg1044390

Simplified version, without the OpenGL triangles. It gives coordinates of vertices, then the list of vertices for each pentagonal face.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

const double PI = 3.141592653589793;
const int NVERT = 20, NFACE = 12;   // For a dodecahedron

//================================================

struct Pt{ double x, y, z; };

Pt operator +( Pt p, Pt q ) { return { p.x + q.x, p.y + q.y, p.z + q.z }; }
Pt operator -( Pt p, Pt q ) { return { p.x - q.x, p.y - q.y, p.z - q.z }; }
Pt operator *( double r, Pt p ) { return { r * p.x, r * p.y, r * p.z }; }
Pt operator /( Pt p, double r ) { return { p.x / r, p.y / r, p.z / r }; }
double dot( Pt p, Pt q ) { return p.x * q.x + p.y * q.y + p.z * q.z; }
double abs( Pt p ) { return sqrt( dot( p, p ) ); }
Pt cross( Pt p, Pt q ) { return { p.y * q.z - p.z * q.y, p.z * q.x - p.x * q.z, p.x * q.y - p.y * q.x }; }

//================================================

Pt rotX( Pt p, double angle )       // Rotate about x axis
{
   double c = cos( angle ), s = sin( angle );
   return { p.x, p.y * c - p.z * s, p.y * s + p.z * c };
}

//================================================

Pt rotZ( Pt p, double angle )       // Rotate about z axis
{
   double c = cos( angle ), s = sin( angle );
   return { p.x * c - p.y * s, p.x * s + p.y * c, p.z };
}

//================================================

Pt reflectInPlane( Pt p, Pt norm, Pt ref )    // Reflect in plane defined by normal vector and reference point
{
   norm = norm / abs( norm );       // Make unit normal
   return p - 2.0 * dot( p - ref, norm ) * norm;
}

//================================================

void dodecahedron( Pt vertex[], int pentagon[][5] )
{
   double L = 4.0 / ( sqrt( 3.0 ) * ( 1.0 + sqrt( 5.0 ) ) );     // Length of side
   double d = 0.5 * L / sin( 0.2 * PI );                         // Circumradius of pentagonal face
   double ztop = sqrt( 1.0 - d * d );                            // z coordinate of flat top

   // Initially, dodecahedron with horizontal top, two rows of side pentagons, horizontal bottom
   // VERTICES: find a reference vertex in each of 4 tiers (z levels), then rotate in increments of 2 pi / 5
   vertex[0] = { 0, -d, ztop };
   for ( int i = 1; i <= 4; i++ ) vertex[i] = rotZ( vertex[0], 0.4 * PI * i );
   vertex[5] = rotX( vertex[0], 2.0 * asin( 0.5 * L ) );
   vertex[10] = reflectInPlane( vertex[1], vertex[0] - vertex[5], 0.5 * ( vertex[0] + vertex[5] ) );
   vertex[15] = { vertex[2].x, -vertex[2].y, -vertex[2].z };
   for ( int t = 1; t < 4; t++ )
   {
      for ( int i = 1; i <= 4; i++ ) vertex[5*t+i] = rotZ( vertex[5*t], 0.4 * PI * i );
   }

   // PENTAGONS (list of vertices; ANTICLOCKWISE when seen from OUTSIDE)
   int p = 0;
   for ( int i = 0; i < 5; i++ ) pentagon[p][i] = i;
   for ( p = 1; p <= 5; p++ )
   {
      int off1 = (p-1)%5;
      int off2 =  p   %5;
      pentagon[p][0] =      off1;
      pentagon[p][1] =  5 + off1;
      pentagon[p][2] = 10 + off1;
      pentagon[p][3] =  5 + off2;
      pentagon[p][4] =      off2;
   }
   for ( p = 6; p <= 10; p++ )
   {
      int off1 = (p-6)%5;
      int off2 = (p-2)%5;
      pentagon[p][0] =  5 + off1;
      pentagon[p][1] = 10 + off2;
      pentagon[p][2] = 15 + off2;
      pentagon[p][3] = 15 + off1;
      pentagon[p][4] = 10 + off1;
   }
   p = 11;
   for ( int i = 0; i < 5; i++ ) pentagon[p][i] = 19 - i;
}

//================================================

void output( Pt vertex[], int pentagon[][5] )
{
   #define SF << fixed << setprecision( 6 ) << setw( 10 ) <<
   #define SI << setw( 2 ) <<

   cout << "VERTICES:\n";
   for ( int v = 0; v < NVERT; v++ ) cout SF vertex[v].x << ", " SF vertex[v].y << ", " SF vertex[v].z << '\n';

   cout << "\nPENTAGONS:\n";
   for ( int p = 0; p < NFACE; p++ ) 
   {
      for ( int i = 0; i < 5; i++ ) cout SI pentagon[p][i] << " ";
      cout << '\n';
   }
}

//================================================

int main()
{
   Pt vertex[NVERT];
   int pentagon[NFACE][5];

   dodecahedron( vertex, pentagon );
   output( vertex, pentagon );
}

//================================================  

VERTICES:
  0.000000,  -0.607062,   0.794654
  0.577350,  -0.187592,   0.794654
  0.356822,   0.491123,   0.794654
 -0.356822,   0.491123,   0.794654
 -0.577350,  -0.187592,   0.794654
  0.000000,  -0.982247,   0.187592
  0.934172,  -0.303531,   0.187592
  0.577350,   0.794654,   0.187592
 -0.577350,   0.794654,   0.187592
 -0.934172,  -0.303531,   0.187592
  0.577350,  -0.794654,  -0.187592
  0.934172,   0.303531,  -0.187592
  0.000000,   0.982247,  -0.187592
 -0.934172,   0.303531,  -0.187592
 -0.577350,  -0.794654,  -0.187592
  0.356822,  -0.491123,  -0.794654
  0.577350,   0.187592,  -0.794654
  0.000000,   0.607062,  -0.794654
 -0.577350,   0.187592,  -0.794654
 -0.356822,  -0.491123,  -0.794654

PENTAGONS:
 0  1  2  3  4 
 0  5 10  6  1 
 1  6 11  7  2 
 2  7 12  8  3 
 3  8 13  9  4 
 4  9 14  5  0 
 5 14 19 15 10 
 6 10 15 16 11 
 7 11 16 17 12 
 8 12 17 18 13 
 9 13 18 19 14 
19 18 17 16 15 

See also:
https://en.wikipedia.org/wiki/Regular_dodecahedron#Cartesian_coordinates
(but I didn't use that particular scale or orientation).

[nuderobmonkey]

Maybe there is a misunderstanding. The 'rooms' and the whole cave should have no spatial dimensions. They should be logically connected, represented by a graph, where the nodes represent rooms, and their edges represent doors. So each room should have three doors, leading to other neighbored rooms.
I ask me, if there exists an algorithm which could produce such a dodecahedron. If not, I need to connect the nodes by hand.

[lastchance]

You asked for a polyhedron: that's what I gave you.

The list of "PENTAGONS" above connects 20 vertices ("rooms"). For example, 0 appears in pentagons (0,1,2,3,4), (0,5,10,6,1), (4,9,14,5,0). Treating those as circular lists, 0 connects to the three vertices 1, 4 and 5.

Similarly for all your other graph connections.

You don't need an algorithm, you could just use that table.

There are, of course, plenty of other orders to label the 20 vertices of a dodecahedron.

[Duthomhas]

OP is not asking for pictures.

You could write anything to create a maze structure. IIRC, Hunt the Wumpus did some kind of randomization on the rooms as it was. All you need to do is generate any graph and randomly populate it.

But, I think it worth your time to write a level editor, of sorts. Draw your graph on paper, then just code it in. It is easy enough since there does not need to exist any correlation between spatial reality and the drawing (though it would help your players if there did).

If each room has three doors, then just create three links and store the graph in a std::map.

Here's something to play with that might get your ideas flowing:

#include <algorithm>
#include <cctype>
#include <ciso646>
#include <iostream>
#include <string>
#include <unordered_map>

using Room_Name = std::string;

// Doors must be listed clockwise, 1 <= N <= 3
using Doors = Room_Name[ 3 ];

struct Room
{
  bool  has_widget;
  Doors doors;
};

std::unordered_map <Room_Name, Room> rooms =
{
  { "Entry", { false, { "A",     "B", "C"     } }},
  { "A",     { false, { "Q",     "B", "Entry" } }},
  { "B",     { false, { "A",     "D", "Entry" } }},
  { "C",     { false, { "Entry", "D", ""      } }},
  { "D",     { true,  { "B",     "",  "C"     } }},
  { "Q",     { false, { "A",     "",  ""      } }},
};

int back_door_index( const Room_Name& this_room_name, const Room_Name& last_room_name )
{
  for (int n = 0; n < 3; n++)
    if (rooms[this_room_name].doors[n] == last_room_name)
      return n;
  return 0;  // or -1 to indicate not found if you set your map up for it
}

int main()
{
  std::cout << "Find the Widget and Escape!\n";
  
  Room_Name this_room_name = "Entry";
  Room_Name last_room_name = "Entry";
  
  bool has_found_widget = false;
  while (!(has_found_widget and (this_room_name == "Entry")))
  {
    has_found_widget |= rooms[this_room_name].has_widget;
    
    std::cout << "\n(" << this_room_name << ")\n";
    if (has_found_widget) std::cout << "You found the Widget.\n";
    else                  std::cout << "No Widget here.\n";
    
    std::unordered_map <std::string, Room_Name> go_direction;
    
    int n = back_door_index( this_room_name, last_room_name );
    go_direction["back" ] = last_room_name;
    go_direction["left" ] = rooms[this_room_name].doors[ (n + 1) % 3 ];
    go_direction["right"] = rooms[this_room_name].doors[ (n + 2) % 3 ];

    while (true)
    {
      std::cout << "go (";
      for (auto kv : go_direction)
        if (!kv.second.empty())
          std::cout << kv.first << " ";
      std::cout << "\b)? ";
    
      std::string which_direction;
      getline( std::cin, which_direction );
      if (go_direction[which_direction].empty()) continue;
      
      last_room_name = this_room_name;
      this_room_name = go_direction[which_direction];
      break;
    }
  }
  std::cout << "\nYou escaped with the Widget!\n";
}

Enjoy!

[lastchance]

#include <iostream>
#include <map>
#include <set>
using namespace std;

const int NFACE = 12;   // For a dodecahedron


void dodecahedron( int pentagon[NFACE][5] )       // Set vertex numbers on the faces of a dodecahedron
{
   // PENTAGONS (list of vertices; ANTICLOCKWISE when seen from OUTSIDE)
   int p = 0;
   for ( int i = 0; i < 5; i++ ) pentagon[p][i] = i;
   for ( p = 1; p <= 5; p++ )
   {
      int off1 = (p-1)%5;
      int off2 =  p   %5;
      pentagon[p][0] =      off1;
      pentagon[p][1] =  5 + off1;
      pentagon[p][2] = 10 + off1;
      pentagon[p][3] =  5 + off2;
      pentagon[p][4] =      off2;
   }
   for ( p = 6; p <= 10; p++ )
   {
      int off1 = (p-6)%5;
      int off2 = (p-2)%5;
      pentagon[p][0] =  5 + off1;
      pentagon[p][1] = 10 + off2;
      pentagon[p][2] = 15 + off2;
      pentagon[p][3] = 15 + off1;
      pentagon[p][4] = 10 + off1;
   }
   p = 11;
   for ( int i = 0; i < 5; i++ ) pentagon[p][i] = 19 - i;
}

//================================================

int main()
{
   int pentagon[NFACE][5];
   dodecahedron( pentagon );

   map<int,set<int>> graph;
   for ( int face = 0; face < NFACE; face++ )
   {
      for ( int vert = 0; vert < 5; vert++ )
      {
         int a = pentagon[face][vert], b = pentagon[face][(vert+1)%5];
         graph[a].insert( b );
         graph[b].insert( a );
      }    
   }   

   cout << "Graph: room ===> exits to:\n";
   for ( auto node : graph )
   {
      cout << node.first << " ===> ";
      for ( auto target : node.second ) cout << target << ' ';
      cout << '\n';
   }
}

//================================================  

Graph: room ===> exits to:
0 ===> 1 4 5 
1 ===> 0 2 6 
2 ===> 1 3 7 
3 ===> 2 4 8 
4 ===> 0 3 9 
5 ===> 0 10 14 
6 ===> 1 10 11 
7 ===> 2 11 12 
8 ===> 3 12 13 
9 ===> 4 13 14 
10 ===> 5 6 15 
11 ===> 6 7 16 
12 ===> 7 8 17 
13 ===> 8 9 18 
14 ===> 5 9 19 
15 ===> 10 16 19 
16 ===> 11 15 17 
17 ===> 12 16 18 
18 ===> 13 17 19 
19 ===> 14 15 18

If you want randomisation then just permute the numbers 0-19.