Thuật toán và game
Thuật toán là gì ? Nó có mục đích gì trong game ?
Thuật toán (algorithm) là gì? Có khá nhiều định nghĩa về thuật toán, nhưng chúng ta có thể hiểu, thuật toán là từng bước một để hoàn thành một nhiệm vụ nào đó (task).
Chẳng hạn như bạn muốn hoàn thành task đi từ Đà Nẵng => Sài Gòn. Bạn sẽ cần “thuật toán” mua vé -> bắt grab ra sân bay -> đi máy bay. Một trường hợp khác chẳng hạn bạn muốn tìm kiếm tên “Phúc” trong bảng điểm của trường bạn sẽ tìm đến vần P -> tìm đến chữ Ph -> và cứ thế.
Trong khoa học máy tính, algorithm là từng bước để hoàn thành một task, việc tìm ra một thuật toán tốt rất quan trọng đối với chương trình.
Các loại thuật toán trong game
Cuộc sống cũng chứa đầy thuật toán
- Một số thuật toán được sử dụng trong game lẫn trong các chương trình khác chẳng hạn như thuật toán nén (compression algorithm) để nén một lượng dữ liệu lớn qua internet một cách nhanh chóng, hoặc nén một âm thanh để giảm tải dung lượng cài đặt trên điện thoại.
- Một thuật toán khác cũng rất phổ biến là thuật toán tìm đường (route finding), không chỉ áp dụng cho trí thông minh nhân tạo của các nhân vật game. Nó còn sử dụng rộng rộng rãi trong google map. Có rất nhiều thuật toán tìm đường khác nhau chẳng hạn như Djikstra, A star...
- Một số thuật toán khác phải kể ra như MinMax dùng trong trò chơi cờ, spatial partitioning trong đồ họa, numerical integration cho vật lý cơ bản để mô phỏng lò xo,và chuyển động trong giao diện người dùng, Sorting algorithms khi bạn muốn làm một túi đồ cho nhân vật …nếu bạn biết về các thuật toán, bạn có thể tiết kiệm nhiều công sức và tối ưu hóa cho mỗi trường hợp cụ thể.
Không phải mọi thuật toán của danh sách trên đều được sử dụng khi muốn phát triển game, một số thuật toán chỉ là toán học cơ bản,do đó bạn cần có kiến thức về toán như vector, góc, nội suy tuyến tính. Tùy vào trò chơi mà bạn muốn phát triển, sẽ có hàng tấn thuật toán khác nhau. Tuy nhiên đây là một bước quan trọng khi bạn muốn bắt đầu. Khi bạn làm việc với nhiều khía cạnh lớn khác nhau của trò chơi, việc thiết kế để quản lý cấu trúc dữ liệu là bắt buộc.
Nếu bạn đã biết rõ về các thuật toán., bạn có thể biết được những hạn chế và ưu điểm của mỗi thuật toán tìm đường khác nhau, nó có thể ảnh hưởng đến thiết kế trò chơi. Đôi khi bạn có thể phải thiết kế lại trò chơi.
Việc thiết kế các thuật toán bị ảnh hưởng bởi hai yếu tố chính là chính xác và hiệu quả. Chẳng hạn như khi tôi muốn tạo một thuật toán xác định va chạm giữa 2 hình tròn. Tôi có thể sử dụng thuật toán mô phỏng vật lý có sẵn hoặc lựa chọn tự viết cho mình một thuật toán mới đơn giản hơn. Tương tự đối với mỗi yêu cầu trò chơi khác nhau, bạn sẽ cần viết rất nhiều thuật toán khác nhau để tìm kiếm, mô phỏng, tập hợp, trí thông minh, toán học, đồ họa …
Điều gì tạo nên một thuật toán tốt ?
Có 2 tiêu chí của một thuật toán tốt, đó là tính chính xác và hiệu suất. Hầu hết các trường hợp chúng ta chỉ quan tâm đến tính chính xác. Đôi khi chúng ta không thể có một kết quả chính xác cho kết quả và nó mất nhiều thời gian. Một số thuật toán hiệu suất cao hơn những thuật toán khác. Nếu muốn tìm hiểu thêm về thuật toán bạn có thể tham khảo, bạn có thể đọc cuốn Introduction to Algorithms của tác giả Thomas H. Cormen.
Kết luận
Tùy thuộc vào vấn đề mà chúng ta muốn xử lý, sẽ có nhiều thuật toán khác nhau, thuật toán bản thân nó chỉ là một công thức để giải quyết vấn đề. Đôi khi cả một chương trình cũng được coi là một thuật toán phức tạp.
Bài viết gốc: https://kipalog.com/posts/Thuat-toan-va-game