cpp Jump Point Search算法

Jump Point Search算法是一种近年来提出的新型寻路算法，能够在路网数据中快速跳过大量的不可行区域，极大地提高了寻路效率。以下是一个简单的C++实现示例：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

const int MAXN = 100;
const int INF = 0x3f3f3f3f;

int n, m; // 路网数据的行列数
int sx, sy, ex, ey; // 起点和终点的坐标
int map[MAXN][MAXN]; // 路网数据
int dis[MAXN][MAXN]; // 距离起点的距离
bool vis[MAXN][MAXN]; // 是否已经访问过
int dir[8][2] = {{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}; // 方向数组

struct Node {
    int x, y, f, g, h; // 坐标、f值、g值、h值
    bool operator<(const Node& a) const {
        return f > a.f; // 优先队列为小根堆，f值小的优先级高
    }
};

bool is_valid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0;
}

vector<pair<int, int>> get_successors(int x, int y, int dx, int dy) {
    vector<pair<int, int>> successors;
    if (dx != 0 && dy != 0) {
        if (is_valid(x + dx, y + dy) && (!is_valid(x + dx, y) || !is_valid(x, y + dy))) {
            successors.push_back({x + dx, y + dy});
        }
        if (is_valid(x + dx, y) && !is_valid(x, y + dy)) {
            successors.push_back({x + dx, y});
            successors.push_back({x + dx, y + dy});
        }
        if (is_valid(x, y + dy) && !is_valid(x + dx, y)) {
            successors.push_back({x, y + dy});
            successors.push_back({x + dx, y + dy});
        }
    } else {
        if (dx == 0) {
            if (is_valid(x, y + dy)) {
                successors.push_back({x, y + dy});
                if (!is_valid(x + 1, y)) successors.push_back({x + 1, y + dy});
                if (!is_valid(x - 1, y)) successors.push_back({x - 1, y + dy});
            }
        } else {
            if (is_valid(x + dx, y)) {
                successors.push_back({x + dx, y});
                if (!is_valid(x, y + 1)) successors.push_back({x + dx, y + 1});
                if (!is_valid(x, y - 1)) successors.push_back({x + dx, y - 1});
            }
        }
    }
    return successors;
}

void jump(int x, int y, int dx, int dy) {
    int nx = x + dx, ny = y + dy;
    if (!is_valid(nx, ny)) return;
    if (nx == ex && ny == ey) {
        dis[nx][ny] = dis[x][y] + 1;
        return;
    }
    if (vis[nx][ny]) return;
    vis[nx][ny] = true;
    int g = dis[x][y] + 1;
    int h = abs(nx - ex) + abs(ny - ey);
    int f = g + h;
    priority_queue<Node> pq;
    pq.push({nx, ny, f, g, h});
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        int x = u.x, y = u.y;
        if (vis[x][y]) continue;
        vis[x][y] = true;
        dis[x][y] = u.g;
        vector<pair<int, int>> successors = get_successors(x, y, dx, dy);
        for (auto& s : successors) {
            int nx = s.first, ny = s.second;
            int g = dis[x][y] + 1;
            int h = abs(nx - ex) + abs(ny - ey);
            int f = g + h;
            pq.push({nx, ny, f, g, h});
        }
    }
}

void JPS() {
    memset(dis, INF, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[sx][sy] = 0;
    vis[sx][sy] = true;
    priority_queue<Node> pq;
    pq.push({sx, sy, abs(ex - sx) + abs(ey - sy), 0, abs(ex - sx) + abs(ey - sy)});
    while (!pq.empty()) {
        Node u = pq.top(); pq.pop();
        int x = u.x, y = u.y;
        if (x == ex && y == ey) return;
        for (int i = 0; i < 8; i++) {
            int dx = dir[i][0], dy = dir[i][1];
            if ((dx == 0 || dy == 0) || (is_valid(x + dx, y) && is_valid(x, y + dy))) {
                jump(x, y, dx, dy);
            }
        }
    }
}

int main() {
    cin >> n >> m >> sx >> sy >> ex >> ey;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }
    JPS();
    cout << dis[ex][ey] << endl;
    return 0;
}

这段代码实现了Jump Point Search算法的基本框架，包括预处理跳跃点、递归跳跃、状态转移和优先队列的使用。需要注意的是，Jump Point Search算法的预处理过程比较耗时，因此它更适用于需要多次寻路的场景。