Klon PyGame QIX, area pengisian

Saya bermain-main dengan PyGame.

Sekarang saya mencoba menerapkan klon QIX .

Saya memiliki loop permainan saya, dan saya dapat memindahkan pemain (kursor) di layar.

Di QIX, pergerakan pemain meninggalkan jejak (ekor) di layar, membuat polyline.

Jika polyline dengan batas layar membuat poligon, area tersebut terisi.

Bagaimana saya bisa menyelesaikan perilaku ini?

Bagaimana cara menyimpan ekornya di memori?

Bagaimana mendeteksi ketika itu membangun bentuk tertutup yang harus diisi?

Saya tidak membutuhkan solusi kerja yang tepat, beberapa petunjuk, nama algo akan keren.

Pada awal, hanya ada batas abu-abu, di mana pemain dapat menggerakkan kursornya.

• Skenario pertama:

Pengguna memindahkan kursornya dari titik A melalui titik B, menggambar multiline merah hingga titik C. Pada titik ini, karena melintasi perbatasan, titik A harus dihubungkan dengan titik C secara otomatis, membuat poligon, yang harus diisi ( hal oranye pada gambar saya). Mengisi poligon sangat sederhana di PyGame, karena saya memberikan urutan poin, dan PyGame peduli sisanya.

• Skenario kedua:

Pengguna bergerak di perbatasan ke titik D, dari mana ia menggambar garis ke titik E. Karena ia melintasi garis poligon sebelumnya, dan dengan garis dan perbatasannya poligon lain dapat dibuat, itu harus diisi juga. (yang hijau).

• Skenario ketiga:

Pemain bergerak lebih jauh pada poligon (dia bisa bergerak pada garis poligon yang ada), dan menggambar garis dari titik G ke titik F. Di sini sekali lagi, karena perbatasan dan garis yang ada, poligon lain harus diisi (yang biru) .

Inilah cara saya mendekatinya:

1. Selalu ada area terbuka tunggal, yang diwakili oleh poligon. Semua area lain tidak relevan.
2. Garis dimulai ketika Anda bergerak dari perimeter poligon ke interior poligon.
3. Sebuah garis berhenti ketika Anda bergerak dari bagian belakang poligon ke perimeter.
4. Ketika Anda menghentikan garis, Anda telah membagi poligon menjadi dua poligon.
5. Anda kemudian memutuskan mana dari dua poligon yang akan diisi, dan mana yang harus disimpan sebagai area terbuka. Di Qix, sisi tempat Qix (musuh) berada tetap terbuka dan sisi lainnya terisi.

Bagaimana Anda membagi poligon? Anda menggunakan titik akhir dari garis Anda untuk membagi perimeter poligon menjadi dua bagian, kemudian gunakan baris baru untuk menyelesaikan dua bagian itu menjadi poligon baru.

Sebagai contoh, katakanlah area terbuka Anda adalah sebuah poligon dengan poin [p0, p1, p2, p3, p4, p5]. Titik awal Anda Aterjadi antara p1dan p2, dan titik akhir Anda Bterjadi antara p3dan p4. Baris baru yang ditarik adalah [A, s, t, u, v, B]. Kami pertama-tama membagi poligon menjadi dua segmen [A, p2, p3, B]dan [B, p4, p5, p0, p1, A]. Kedua segmen ini bersama-sama membentuk poligon asli. Kemudian kami merekatkan baris baru ke masing-masing (sekali ke depan, sekali ke belakang), membentuk [A, p2, p3, B, v, u, t, s]dan [B, p4, p5, p0, p1, A, s, t, u, v]. Anda mengisi salah satu poligon ini dan menyimpan yang lain sebagai area terbuka baru Anda.

Saya belum menerapkan ini dan tidak tahu pasti apakah itu akan berhasil, tapi itulah pendekatan yang akan saya gunakan: subdivisi poligon bukan pengisian poligon.

Ini adalah masalah yang melibatkan beberapa subteps diskrit. Berikut adalah garis besar dari apa yang saya sarankan:

• Tunggu sampai pemain membentuk persimpangan beberapa garis
• Dapatkan piksel dari setiap sisi persimpangan
• Pathfind untuk melihat apakah mereka dapat terhubung satu sama lain
• Piksel yang tidak dapat terhubung satu sama lain adalah area yang terpisah
• Lakukan pengisian banjir untuk mendapatkan semua piksel di area tersebut

Saya akan menyimpan status piksel game dalam array Numpy (numpy dot scipy dot org). Warna bisa menjadi tiga array terpisah untuk RGB, tetapi array yang akan saya fokuskan adalah line / no line array. Inisialisasi saja dengan nol dan atur sesuai ukuran bidang permainan Anda, dan setiap kali pemain melewati piksel, atur item yang sesuai dalam array ke 1. Anda ingin menampilkannya di layar sebagai warna berbeda , karena mereka baris Anda!

Setiap kali pixel pemain bergerak, saya akan memeriksa untuk melihat apakah itu melewati (dan menggambar garis di sebelah) garis yang ada. Jika demikian, saya akan mendapatkan piksel dari setiap divisi yang mungkin:

. . . | . 
. . . | . 
. . . | x 
. . x < -

Titik adalah piksel kosong, garis adalah garis (jelas), dan X adalah piksel kosong yang ingin kita pilih. Kita dapat melakukannya dengan cara berikut:

• Tambahkan semua piksel kosong di sebelah pemutar / persimpangan ke daftar.
• Ulangi daftar menghapus piksel jika item berikutnya dalam daftar berdekatan (di bidang game) dengan yang Anda aktifkan.

Setelah Anda memiliki piksel dari semua sisi yang mungkin dari persimpangan, jalankan A * pada setiap pasangan yang memungkinkan. (Lihat http://www-cs-students.stanford.edu/~amitp/gameprog.html#paths atau Google bintang-bintang untuk informasi lebih lanjut.) Jika jalur dapat ditemukan di antara sepasang, hapus salah satu piksel yang terhubung dari daftar.

Setelah looping dan pathing untuk semua pasangan, piksel yang tersisa harus masing-masing berada di area yang terpisah dan tertutup! Untuk mendapatkan semua piksel di setiap area, lakukan pengisian banjir dari piksel area itu. Lihat http://en.wikipedia.org/wiki/Flood_fill .

Semoga berhasil!

Area Anda hanyalah serangkaian poin. Kerja kerasnya datang dengan mengambil serangkaian titik yang membentuk (biasanya) poligon cekung dan melakukan triangulasi sehingga Anda dapat membuat dan mungkin memproyeksikan tekstur pada mereka. Lihat http://en.wikipedia.org/wiki/Polygon_triangulation untuk lebih jelasnya