Bagaimana cara membuat karakter saya menjadi halus saat berjalan di jalan (daftar koordinat)?

Saya memiliki daftar dengan koordinat - output dari algoritma A * - dan saya ingin membuat karakter saya dengan lancar mengikuti jalur ini dengan rotasi.

Jadi saya punya sesuatu seperti A dan saya ingin mendapatkan C

Bagaimana saya bisa melakukan ini?

EDIT

Untuk membuat diri saya sedikit lebih jelas:

Saya lebih tertarik pada perputaran yang lancar karena saya sudah tahu cara berjalan dari satu simpul ke simpul lainnya.

EDIT

Karena banyak orang menganggap ini berguna (saya juga) saya memposting tautan ke "Sifat kode" Daniel Shiffman di mana ia membahas banyak masalah AI (dan fisika) permainan, misalnya perilaku kemudi. Http://natureofcode.com/book/chapter- 6-autonomous-agents / # chapter06_section8

Jika Anda ingin lintasan yang mulus di lingkungan berbasis ubin, tidak ada jalan lain untuk menerapkan lintasan-lintasan pada titik arah A * Anda. Dalam bukunya tentang pemrograman game AI, Matt Buckland menjelaskan algoritma sederhana dan cepat untuk memperlancar jalur (pada dasarnya menghapus semua tepi yang dapat dihapus tanpa menyebabkan persimpangan dengan hambatan Anda).

Setelah Anda menghapus tepi yang tidak perlu seperti ini, kasing pertama Anda ( A -> B ) terpecahkan. Menghaluskan tepi pada grafik Anda dapat dilakukan dengan beberapa cara. Kemungkinan besar, spline Hermite akan bekerja (tergantung sedikit pada kepadatan hambatan dan ukuran ubin Anda). Opsi lain bisa berupa perilaku menyetir, di mana Anda mulai mengarahkan ke titik jalan berikutnya, segera setelah Anda tinggal setengah langkah dari target saat ini (ini benar-benar tergantung pada seberapa cepat "agen" Anda bergerak / berbelok).

Seperti yang telah disebutkan orang lain, untuk kasus kedua Anda harus menerapkan semacam spline atau (sebenarnya lebih cocok untuk contoh Anda) memberikan unit semacam perilaku kemudi.

Namun, untuk kasus pertama, ada solusi yang lebih sederhana dan memberikan hasil yang lebih baik daripada pemulusan jalur. Ini disebut Theta * , dan merupakan ekstensi A * pada grid yang sederhana (dan relatif baru) yang memungkinkan unit bergerak ke arah mana pun di antara titik-titik grid.

Ada artikel bagus yang menjelaskan Theta * (dari mana saya mencuri gambar di atas) di sini

Untuk gerakan realistis yang lebih manusiawi, coba integrasikan dengan Steering Behaviors. (Versi C # dari OpenSteer klasik http://sharpsteer.codeplex.com/ ) Anda mendapatkan output AStar dan membiarkan perilaku kemudi peduli tentang movimentasi (Salah satu sampel menunjukkan dengan tepat bagaimana melakukan ini, navigasikan mengikuti jalur)

Dalam hal navigasi dari titik ke titik, saya menggunakan perbedaan sudut (arah pemain saat ini vs arah dari titik saat ini ke titik berikutnya) dan kemudian secara bertahap mengubah sudut ke sudut akhir saat gerakan terjadi. Lihat permainan ini di sini di mana pesawat terbang bergerak dari satu titik ke titik lain, tetapi belokannya tidak tiba-tiba tetapi dengan memperhatikan dengan seksama orang dapat mengidentifikasi titik-titik jalur. (Gim ini hanya berfungsi di ponsel meskipun lebih disukai iPhone / iPad).

Saya sudah beruntung dengan splines Catmull (sejenis spline kubik seperti yang juga direkomendasikan oleh @bummzack). Bagian yang baik tentang itu adalah bahwa spline akan selalu melewati titik kontrol, banyak yang tidak. Terapkan sesuatu seperti ini:

t    = <time*>
t12  = t + 1.0
t23  = t
t34  = t - 1.0
t123 = (t + 1.0) / 2.0
t234 = t / 2

c1 = controlpoint[0];
c2 = controlpoint[1];
c3 = controlpoint[2];
c4 = controlpoint[3];

l12 = lerp(c1, c2, t12);
l23 = lerp(c2, c3, t23);
l34 = lerp(c3, c4, t34);
position = lerp(lerp(l12, l23, t123), lerp(l23, l34, t234), t);

* waktu adalah nilai [0,1] antara titik kontrol 1 dan 2.

A-> B dapat dipecahkan dengan menggunakan jerat navigasi bukan kisi. Ini menyiratkan perubahan besar dalam pembuatan data pathfinding.

Kasus seperti C dan D hanya memotong sudut: jika karakter bergerak di jalur dan di dalam "sudut" (sel di mana sebelumnya, saat ini, sel berikutnya tidak pada garis lurus), dorong ke arah sel sebelumnya dan berikutnya . Satu-satunya masalah adalah menentukan jarak dari posisi nyata (jarak dorong). Itu mungkin akan membutuhkan jarak dari sel saat ini sebagai input. Sesuatu seperti ini:

push_dir = average( prevcell.pos, nextcell.pos ) - curcell.pos;
push_dist = cell_half_width - distance( char.pos, curcell.pos );
char.pos += push_dir * push_dist;