Bagaimana saya bisa secara bertahap menghasilkan grafik?

8

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).

Grafik dunia pemain A

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:

Grafik dunia pemain B

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.

Ben Blank
sumber
Mengapa grafik yang terhubung tidak cocok dengan ini? mathworld.wolfram.com/ConnectedGraph.html Saya mungkin kehilangan intinya. Jika pengguna ingin pergi dari satu lokasi ke lokasi lain dan mereka semua terhubung, beri mereka daftar lokasi dan pindahkan posisi mereka di peta dunia ke lokasi baru.
brandon
@brandon - "Connected" adalah daftar properti I kedua. :-)
Ben Blank
maksud saya adalah, jika Anda dapat beralih dari satu node ke node lainnya. Ketika mereka mengunjungi seorang teleporter, berikan mereka daftar semua node yang telah mereka kunjungi kecuali yang ini. Tidak perlu memiliki grafik, Anda menyimpan daftar semua node yang dikunjungi dan lokasi mereka dan Anda hanya teleport ke lokasi yang mereka pilih. Apakah saya salah paham?
brandon
hampir semua deskripsi Anda tentang istilah-istilah itu benar, kecuali untuk "siklik" dan "terbatas secara lokal". Yang pertama membatasi grafik Anda menjadi seperti apa itu - sebuah lingkaran. Suatu istilah yang dapat Anda gunakan untuk persyaratan bahwa ada lebih dari satu jalur dari satu titik ke titik lainnya adalah "2-connected". "Lokal terbatas" hanya berarti bahwa setiap simpul memiliki jumlah tepi terbatas.
Harry Stern
@ Harry Stern - Pemahaman saya adalah bahwa grafik siklik adalah grafik yang mengandung setidaknya satu siklus grafik . Sepertinya Anda berbicara tentang grafik siklus , yang merupakan grafik yang terdiri dari satu siklus grafik dan tidak ada yang lain. Saya secara khusus tidak mencari grafik yang "2-terhubung" (lihat "sederhana"). Dan ya, itulah yang saya maksud dengan "terbatas lokal".
Ben Blank

Jawaban:

6

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".

Grafik 1 Grafik 2

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.

Chumby Gumball
sumber
Anda memahami persis apa yang saya maksudkan dengan "tak terbatas" dan poin Anda tentang "terluar" diambil dengan baik - saya telah mengubah kata-kata dalam pertanyaan saya. Namun, entah saya tidak memahami generator Anda dengan benar atau saya menjelaskan kebutuhan saya dengan buruk, karena sepertinya ini tidak akan menghasilkan benih yang sama untuk jalur yang berbeda ke titik yang sama. Saya telah menambahkan beberapa ilustrasi pada pertanyaan saya yang diharapkan akan memperjelas apa yang ingin saya capai. :-)
Ben Blank
Saya mengerti maksud Anda sekarang. Itu agak sulit. Apa yang perlu Anda lakukan adalah mengubah panggilan genRandomNumbers ke fungsi yang selalu mengembalikan set angka yang sama untuk inputnya, dan menggunakan seed node sebagai argumen. Ini akan menjamin bahwa Anda akan mendapatkan koneksi dan benih yang sama tidak peduli jalur mana yang Anda ambil atau simpul mana yang Anda mulai. Anda harus berhati-hati bahwa himpunan angka untuk simpul B yang A terhubung juga berisi A sehingga Anda mendapatkan properti grafik yang tidak terarah. Jika Anda tidak melakukan ini, maka Anda mendapatkan grafik yang diarahkan.
Chewy Gumball
1

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.

Jiahua Wang
sumber