Em có đang tìm hiểu game pikachu , nhưng chưa hiểu thuật toán mà nó áp dụng để nó hoạt động như thế nào mong mọi người giải đáp ?
Thuật toán được áp dụng trong game Pikachu là thuật toán như thế nào?
1 Like
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
7 Likes
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 ạ !
2 Likes
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
1 Like
Bạn nói chi tiết hơn đi bạn 
1 Like
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,
2 Likes
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ỉ
3 Likes
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.
1 Like
Đúng là kinh điển nhưng hiếm các bài nói về nó thật !!
1 Like
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?
1 Like
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
2 Likes
t cũng áp dụng thuật toán bfs giống b m sẽ dùng biến count[x][y] để cộng giá trị và gán nó tại vị trí x và y mà ta đang xet khi đường thay đổi và dùng một value [x][y] để lấy giá trị x và y để so sánh còn để kiểm tra thì ta sẽ kiểm tra các giá trị liền kề nó nếu cả hai giá trị x và y liền kề khác với giá trị value[x][y] x và y trung tâm thì ta sẽ cộng thêm count của vị trí liền kề với count vị trí trung tâm và gán giá trị value[x][y] x và y liền kề đang xét với giá trị x và y của gía trị trung tâm của nó còn chỉ có mỗi giá trị x hoặc y liền kề thay đổi thì ta sẽ gán giá trị count với giá trị trung tâm với giá trị liền kề và gán giá trị value[x][y] x và y cho giá trị value [x][y] x và y của giá trị trung tâm và đây và code của mình nếu bạn muốn hiểu rõ hơn:
bool visit[8][8];
int count1[8][8];
std::vector<std::vector<std::pair<int, int>>> value1(8, std::vector<std::pair<int, int>>(8));
int moveX[] = { 0,1,0,-1 };
int moveY[] = { 1,0,-1,0 };
bool bfs(vector<vector<int>>Pikachu, int x1, int y1, int x2, int y2) {
queue<pair<int, int>>q;
q.push({ x1,y1 });
visit[x1][y1] = true;
value[x1][y1] = { x1,y1 };
count1[x1][y1] = 1;
int x;
int y;
int cx;
int cy;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
cx = q.front().first;
cy = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
x = cx + moveX[i];
y = cy + moveY[i];
if (x > 7 || x < 0)continue;
if (y > 7 || y < 0)continue;
if (x != value[cx][cy].first && y != value[cx][cy].second) {
value[x][y] = { cx,cy };
count1[x][y] = count1[cx][cy] + 1;
if (count1[x][y] > 2) {
continue;
}
}
else {
value[x][y] = { value[cx][cy].first,value[cx][cy].second };
count1[x][y] = count1[cx][cy];
}
if (x == x2 && y == y2) {
if (Pikachu[x1][y1] == Pikachu[x2][y2]) {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
visit[i][j] = false;
}
}
return true;
}
}
if (Pikachu[x][y] != 0)continue;
if (!visit[x][y]) {
visit[x][y] = true;
q.push({ x,y });
}
}
}
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
visit[i][j] = false;
}
}
return false;
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?