Thuật toán được áp dụng trong game Pikachu là thuật toán như thế nào?

Mình nghĩ chắc là thuật toán tìm đường đi ngắn nhất đó bạn.
Ma trận pikachu sẽ có dạng như thế này:

0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 2 4 2 3 5 1 2 3 4 1 0
0 1 2 3 1 2 3 2 3 1 3 1 2 0
0 4 3 2 4 1 2 3 1 2 3 1 2 0 
0 2 1 3 1 2 3 4 1 2 3 1 2 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0

Trong đó thì 1, 2, 3… là các loại pokemon khác nhau.
Số 0 là những ô trống mà có thể tìm đường đi được.
Sẽ có một viền số 0 để nối các pokemon ở vòng ngoài.

Nhưng làm sao để kiểm tra đường đi có phải rẽ quá 2 lần không thì mình cũng chưa rõ lắm.

Đây là blog của @nguyenvanquan7826 có nói về thuật toán

Distance Learning – 25 Mar 14

Algorithm pokemon game (pikachu) - Distance Learning

In cases where the content is located on a row or column horizontally Where to go, vertical within the rectangle At extend horizontally, Code along the main function Update: 13/06/2014: Game Pokemon completed, you see here. Before writing this...

Các số giống nhau sẽ tượng trưng cho 2 con pikachu giống nhau có khả năng ăn được đúng không ạ !

Nhưng làm sao để kiểm tra đường đi có phải rẽ quá 2 lần không thì mình cũng chưa rõ lắm.

Dùng nhánh cận để kiểm tra là được.
Còn thuật toán của nguyenvanquan hình như là chia ra các pattern cho đương đi

Bạn nói chi tiết hơn đi bạn

Bạn có thể sử dụng thêm một biến đếm mỗi khi khi trọn hướng đi rẽ trái và rẽ phải thì tăng biến đếm và kiểm tra. nhưng nếu sử dụng như thế thì khi ko có đương đi sẽ kiểm tra hơi lâu
Mình thấy thuật toán của nguyenvamquan vẫn hay vì lợi dụng cái viền ở bên ngoài để xác định đương,

Khó tìm thật, không biết tên của loại game này là gì nhỉ? em tìm mãi mà không thấy có bài viết nào về thuật toán của nó tưởng game này lâu rồi phải có rất nhiều clone rồi chứ nhỉ

Thuật toán A* để tìm đường đi ngắn nhất xem sao. Từng nghe loáng thoáng ở đâu là phải dùng cái này đấy.

Đúng là kinh điển nhưng hiếm các bài nói về nó thật !!

hình như còn phải kiểm tra xem có đường đi ko nữa? Nếu ko có thì phải xáo trộn lại?

Tui thấy nó đơn giản mà. Có thể không đúng như thuật toán của nó nhưng không khó để giải quyết vấn đề đó lắm.

Kiểm tra ma trận 2 lần theo 2 hướng x,y là ra. Ngại viết code nên miêu tả vậy

Con Pikachu 1 có tọa độ (x1,y1). Con Pikachu2 có tọa độ (x2,y2).

Lần 1 quét hướng X.
Quét từ xi=x1 đến xi=x2.
Nếu tổng số pikachu trên 3 nhánh : 
- x1,y1 đến xi,y1 
- xi,y1 đến xi,y2
- xi,y2 đến x2,y2
 mà bằng 0 thì ăn được. Khác không thì duyệt theo chiều Y.

Lần 2 quét hướng Y.
Quét từ yi=y1 đến yi=y2.
Nếu tổng số pikachu trên 3 nhánh : 
- x1,y1 đến x1,yi 
- x1yi đến x2,yi
- x2,yi đến x2,y2
 mà bằng 0 thì ăn được. Nếu tổng bằng 0 thì ăn được. Khác không thì 2 con pikachu không ăn được.
PS : Nếu 2 con có x1==x2 hoặc y1==y2 thì duyệt xi và yi từ 0 đến hết bảng (tính cả 4 đường viền xung quanh).

Xong