Bagaimana saya bisa secara bertahap menghasilkan grafik?

Saya baru saja memulai proyek baru di mana saya ingin dunia game terdiri dari lokasi yang dihasilkan secara prosedural yang terhubung oleh para teleporter. Setelah sedikit riset, saya menemukan ini disebut "teori grafik" atau "rumit berdarah", tergantung pada siapa yang membahasnya. Sayangnya, saya menemukan sangat sedikit informasi tentang menghasilkan grafik; sebagian besar alat yang saya lihat diarahkan untuk memeriksa grafik yang ada.

Dengan asumsi saya memiliki terminologi yang diurutkan dengan benar, persyaratan saya adalah bahwa grafiknya adalah:

• sederhana - tidak ada lokasi (vertex) harus memiliki teleporter (tepi) yang menghubungkan kembali ke dirinya sendiri, juga dua simpul tidak memiliki banyak tepi yang menghubungkannya
• terhubung - harus mungkin untuk melakukan perjalanan antara dua simpul dalam grafik (meskipun saya tidak melihat pernah perlu menemukan jalan; hanya mengetahui pemain bisa menemukan satu jika mereka memilih cukup)
• siklik - harus ada lebih dari satu jalur antara dua simpul
• tidak diarahkan - semua sisi dapat dilalui ke arah mana pun
• infinite - jika pemain menginginkannya, mereka harus dapat melakukan perjalanan tanpa batas, dengan grafik terus bertambah secara bertahap ketika mereka mendekati simpul tereksplorasi yang paling luar.
• terbatas secara lokal - gelar vertex tidak boleh berubah setelah pemain mengunjunginya
• diberi label secara stabil - setiap titik mewakili lokasi yang akan dihasilkan secara prosedural dari sebuah benih; seed yang sama harus ditugaskan ke vertex tanpa memandang jalur apa yang digunakan pemain untuk melakukan perjalanan ke sana atau seberapa besar grafik ketika mereka melakukannya

Saya sudah memiliki beberapa ide (yang belum saya coba terapkan) mengenai penggunaan maxima lokal 2D noise perlin sebagai simpul (input x dan y kemudian dapat digunakan sebagai labelnya), tetapi itu terasa kikuk dan rumit.

Apakah ada cara yang lebih baik untuk menghasilkan grafik seperti ini? Saya sedang mengembangkan di Python 2.6 menggunakan Panda3D dan numpy, dan tentu saja mau melihat termasuk perpustakaan lain jika mereka akan membantu dengan masalah ini!

Edit

Saya pikir saya telah melakukan pekerjaan yang buruk dengan menjelaskan beberapa persyaratan saya, jadi sekarang saatnya ilustrasi! Semoga ini bisa menyelesaikan semuanya.

Yang saya maksud dengan memiliki label stabil adalah bahwa saya ingin, misalnya, Pemain A untuk dapat melakukan banyak penjelajahan dan menemukan, antara lain, jalur siklik kembali ke lokasi awal mereka dan gunung yang terlihat seperti kucing. Game-nya sekarang terlihat seperti berikut ini (simpul diberi nomor dengan seed dan edge-nya dengan urutan pemain melewati mereka). Dia mulai pada titik 8329 (hijau) dan Gunung Happycat berada di puncak 6745 (biru).

Teman baik Player A, Player B adalah penggemar kucing, jadi dia ingin menunjukkannya padanya. Dia memberinya benih akar untuk dunianya dan arah di sepanjang rute yang lebih pendek ke gunung yang menarik. Game-nya sekarang akan terlihat seperti ini:

Masalah saya saat ini yang paling sulit adalah "Bagaimana cara menghasilkan benih yang sama untuk Player B ketika eksplorasi belum mengikuti jalur yang sama?" Itulah yang mengarahkan saya pada ide untuk menggunakan Perlin noise - selama seed root yang sama digunakan, maxima tidak akan bergerak, sehingga koordinat mereka dapat digunakan sebagai seed vertex yang stabil.

Anda tidak dapat membuat grafik tanpa batas. Memori Anda terbatas, sehingga jumlah simpul dan tepi juga terbatas. Yang dapat Anda lakukan adalah membuat grafik hingga kemudian menambahkan lebih banyak ke dalamnya. Anda tampaknya telah menyadari hal ini tetapi saya pikir ini penting untuk dinyatakan secara eksplisit sehingga Anda tidak menemui jalan buntu.

Anda harus sangat berhati-hati ketika berbicara tentang "simpul terluar". Grafik adalah satu set simpul, satu set tepi, dan fungsi yang menghubungkan keduanya. Tidak ada set interpretasi geometris kecuali Anda menerapkannya. Sebagai contoh: kedua gambar ini menunjukkan grafik yang sama persis. Pada gambar pertama, simpul 2 dapat dianggap sebagai simpul "terluar", namun pada gambar kedua, simpul 2 tidak akan dianggap "terluar". Jika Anda mempertimbangkan tiga dimensi, Anda bisa mengatakan semua simpul "paling luar".

Ini berarti Anda harus memiliki beberapa informasi lain agar Anda dapat mengetahui apa itu vertex "paling luar". Anda dapat menggunakan pasangan (x, y) karena itu akan memberi Anda kemudahan untuk memvisualisasikan representasi geometris, namun saya tidak berpikir Anda perlu melangkah sejauh itu. Dari apa yang Anda katakan, yang perlu Anda ketahui hanyalah simpul apa yang ada dalam grafik.

Jika Anda menjalankan ini setiap kali Anda mengunjungi titik:

if(this.needsNeighbours)
{
    List<int> connections = genRandomNumbers(n);
    foreach (int connection in connections)
    {
        //Simple graph
        if(connection == this.seed || this.hasNeighbour(connection))
        {
            continue;
        }
        //Connections to already existing, unvisited vertices
        else if(nodeMap.containsKey(connection) && 
                nodeMap.getByKey(connection).needsNeighbours)
        {
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
        //Grow graph with new vertices
        else
        {
            nodeMap.add(connection, new Node(connection));
            nodeMap.getByKey(connection).addNeighbour(this.seed);
            this.addNeighbour(connection);
        }
    }
    this.needsNeighbours = false;
}

grafik Anda akan memenuhi semua kebutuhan Anda kecuali menjadi siklus. Saya tidak tahu apakah Anda benar-benar membutuhkan jaminan. Jika Anda melakukannya maka Anda dapat secara khusus memilih simpul yang belum dikunjungi dan membuat koneksi, yang akan menjamin jalur antara simpul saat ini dan simpul yang sudah dikunjungi karena semua node yang belum dikunjungi terhubung ke setidaknya satu simpul yang dikunjungi dan karena Anda harus mengunjungi simpul yang dikunjungi untuk sampai ke tempat Anda sekarang setidaknya ada dua jalur.

Ini sederhana karena ada pemeriksaan eksplisit untuk itu, terhubung karena semua node baru mendapatkan setidaknya satu koneksi, terbatas secara lokal karena tepi hanya ditambahkan sebelum Anda mengunjungi atau pada kunjungan pertama Anda, dan hanya ke node yang belum dikunjungi. Secara teknis itu tidak terarah, tetapi secara fungsional itu sama seperti Anda membuat tepi terarah di kedua arah. Anda dapat memberi label pada simpul apa pun yang Anda inginkan, saya menggunakan nomor acak yang dihasilkan, tetapi Anda dapat menambahkan parameter lain ke konstruktor, satu menjadi unggulan Anda.

Satu metode:

init:
  root = generateLocation using random seed
  store root's seed
  place player in root location

when the player enters a new location:
  release the memory used by locations that are further than 1 edge away, but keep their seeds
  generate some neighbors for the new location. for every neighbor n:
    gen.seed(getSeed(n))
    n = generateLocation using n's random seed
    numCyclicEdges = gen.randint(0, 1)
    create numCycleEdges edges to existing locations

getSeed(n):
  if(n already has a seed) return n's seed
  else return randomSeed()

Ada banyak detail yang saya tinggalkan, tetapi ini harus menangkap ide umum. Anda mungkin ingin menjaga tetangga di memori yang lebih jauh dari lokasi saat ini, tergantung pada seberapa jauh jarak antar portal, banyak memori yang tersedia, dll.