【游戏算法】 - 寻路算法-JPS算法（跳点搜索）

宋 游戏开发
  2022-11-18 19:07:05 2022-11-18 19:07:05 创建   2023-04-15 19:20:09 2023-04-15 19:20:09 更新      3.3k 字  18 分钟

跳点搜索

优化方式

跳点搜索（JPS Jump point search）是对A Star搜索算法的优化。

传统A*算法通过启发式搜索（F = G + H）在网格地图中寻找最短路径，但其核心问题在于：

  • 搜索空间过大：在均匀代价的网格中，A*需要遍历大量中间节点，导致计算开销高。
  • 对称性冗余：在无权重网格中，存在大量对称路径（如绕圈），A*无法自动剪枝。

JPS通过以下策略优化A*：

  • 剪枝对称路径：直接跳过中间无意义的节点，仅关注关键的“跳点”。
  • 跳跃搜索：沿直线或斜线方向一次性移动多格，直到遇到障碍或跳点。
  • 强迫邻居检测：通过判断节点的“强制邻居”快速识别跳点，减少搜索次数。

JPS的核心概念

强制邻居（Forced Neighbor）

节点X的邻居节点有障碍物，且X的父节点P经过X到达N的距离代价，比不经过X到大N的任一路径的距离代价都小，则称N是X的强迫邻居
强制邻居是指当前节点的某个邻居节点必须被检查，否则会遗漏潜在的最优路径。
强制邻居

跳点（Jump Point）

跳点是路径上的关键节点，满足以下条件之一

  • 路径转折点：跳点的下一个节点需要改变方向（如绕过障碍物）。
  • 强制邻居：跳点的某个邻居节点是唯一可行路径（如障碍物边缘）。

跳跃搜索

跳跃搜索分为直线方向和斜方向两种情况

直线方向搜索（上下左右）

沿当前方向一直移动，直到满足以下条件之一：

  • 遇到障碍物或边界：当前节点是跳点。
  • 发现强制邻居：当前节点是跳点。
  • 到达终点：直接返回路径。
斜方向搜索（对角线）

斜方向搜索需同时检查水平和垂直分量：

  • 沿斜方向前进一步，检查水平和垂直方向是否存在强制邻居。
  • 如果存在强制邻居或到达终点，则当前节点为跳点。
  • 否则继续沿斜方向跳跃。

算法流程概述

JPS保留了A*的基本框架，但通过以下步骤优化后继节点的扩展：
初始化：将起点加入OpenList，设置F值。
主循环：

  • 从OpenList中取出F值最小的节点。
  • 沿当前节点的8个方向进行跳跃搜索，找到所有跳点。
  • 将跳点加入OpenList，并记录父节点。
    终止条件：当终点被加入OpenList时，回溯父节点生成路径。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <vector>
#include <queue>
#include <cmath>
#include <limits>
#include <unordered_map>

using namespace std;

enum class Heuristic {
    MANHATTAN,
    EUCLIDEAN,
    CHEBYSHEV
};

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    bool operator==(const Point& other) const { return x == other.x && y == other.y; }
};

struct Node {
    Point pos;
    int g, h;
    Node* parent;
    
    Node(Point p, int g_cost, int h_cost, Node* parent_node)
        : pos(p), g(g_cost), h(h_cost), parent(parent_node) {}
    
    int f() const { return g + h; }
    
    bool operator<(const Node& other) const {
        return f() > other.f(); // Min-heap
    }
};

class JPS {
public:
    JPS(vector<vector<int>>& grid) : grid(grid) {}
    
    vector<Point> findPath(Point start, Point end, Heuristic heuristic) {
        if (grid[end.x][end.y] == 1) return {};
        
        priority_queue<Node> openList;
        unordered_map<Point, Node*, PointHash> closed;
        Node* startNode = new Node(start, 0, calculateHeuristic(start, end, heuristic), nullptr);
        openList.push(*startNode);
        
        while (!openList.empty()) {
            Node current = openList.top();
            openList.pop();
            
            if (current.pos == end) {
                return reconstructPath(current);
            }
            
            closed[Point(current.pos.x, current.pos.y)] = &current;
            
            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) continue;
                    
                    Point jumpPos(current.pos.x + dx, current.pos.y + dy);
                    if (isValid(jumpPos) && grid[jumpPos.x][jumpPos.y] != 1) {
                        Point jumpResult = jump(jumpPos, dx, dy, end);
                        if (jumpResult != Point(-1, -1)) {
                            Node* neighbor = new Node(jumpResult, current.g + 1, 
                                                     calculateHeuristic(jumpResult, end, heuristic), &current);
                            if (!contains(closed, neighbor->pos)) {
                                openList.push(*neighbor);
                            }
                        }
                    }
                }
            }
        }
        return {};
    }
    
private:
    vector<vector<int>> grid;
    
    struct PointHash {
        size_t operator()(const Point& p) const {
            return p.x * 1000000 + p.y;
        }
    };
    
    bool isValid(Point p) {
        return p.x >= 0 && p.x < grid.size() && p.y >= 0 && p.y < grid[0].size();
    }
    
    Point jump(Point p, int dx, int dy, Point end) {
        if (p == end) return p;
        
        if (!isValid(p) || grid[p.x][p.y] == 1) return Point(-1, -1);
        
        // Check for forced neighbors in straight directions
        if (dx != 0 && dy != 0) {
            if ((grid[p.x - dx][p.y] == 1) || (grid[p.x][p.y - dy] == 1)) {
                return p;
            }
        }
        
        // Check diagonal jumps
        if (dx != 0 && dy != 0) {
            if ((grid[p.x - dx][p.y + dy] == 1) || (grid[p.x + dx][p.y - dy] == 1)) {
                return p;
            }
        }
        
        // Continue straight if no obstacles
        if (dx != 0 && dy == 0) {
            if ((grid[p.x + dx][p.y + 1] == 1) || (grid[p.x + dx][p.y - 1] == 1)) {
                return p;
            }
            return jump(Point(p.x + dx, p.y), dx, dy, end);
        } else if (dy != 0 && dx == 0) {
            if ((grid[p.x + 1][p.y + dy] == 1) || (grid[p.x - 1][p.y + dy] == 1)) {
                return p;
            }
            return jump(Point(p.x, p.y + dy), dx, dy, end);
        } else {
            return jump(Point(p.x + dx, p.y + dy), dx, dy, end);
        }
    }
    
    int calculateHeuristic(Point a, Point b, Heuristic h) {
        int dx = abs(a.x - b.x);
        int dy = abs(a.y - b.y);
        
        switch (h) {
            case Heuristic::MANHATTAN: return dx + dy;
            case Heuristic::EUCLIDEAN: return static_cast<int>(sqrt(dx*dx + dy*dy));
            case Heuristic::CHEBYSHEV: return max(dx, dy);
            default: return 0;
        }
    }
    
    vector<Point> reconstructPath(Node& node) {
        vector<Point> path;
        Node* current = &node;
        while (current != nullptr) {
            path.push_back(current->pos);
            current = current->parent;
        }
        reverse(path.begin(), path.end());
        return path;
    }
    
    bool contains(unordered_map<Point, Node*, PointHash>& map, Point key) {
        return map.find(key) != map.end();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
using System;
using System.Collections.Generic;

namespace JPSAlgorithm
{
    public enum Heuristic
    {
        Manhattan,
        Euclidean,
        Chebyshev
    }

    public class Point
    {
        public int X { get; }
        public int Y { get; }
        public Point(int x, int y)
        {
            X = x;
            Y = y;
        }
        
        public override bool Equals(object obj)
        {
            if (obj is Point p)
                return X == p.X && Y == p.Y;
            return false;
        }
        
        public override int GetHashCode()
        {
            return X * 1000000 + Y;
        }
    }

    public class Node : IComparable<Node>
    {
        public Point Position { get; }
        public int G { get; }
        public int H { get; }
        public Node Parent { get; }
        
        public int F => G + H;
        
        public Node(Point position, int g, int h, Node parent)
        {
            Position = position;
            G = g;
            H = h;
            Parent = parent;
        }
        
        public int CompareTo(Node other)
        {
            return F.CompareTo(other.F);
        }
    }

    public class JPS
    {
        private int[,] _grid;
        
        public JPS(int[,] grid)
        {
            _grid = grid;
        }
        
        public List<Point> FindPath(Point start, Point end, Heuristic heuristic)
        {
            if (_grid[end.X, end.Y] == 1) return new List<Point>();
            
            var openSet = new SortedSet<Node>(new NodeComparer());
            var closedSet = new HashSet<Point>();
            var startNode = new Node(start, 0, CalculateHeuristic(start, end, heuristic), null);
            openSet.Add(startNode);
            
            while (openSet.Count > 0)
            {
                var current = openSet.Min;
                openSet.Remove(current);
                
                if (current.Position.Equals(end))
                {
                    return ReconstructPath(current);
                }
                
                closedSet.Add(current.Position);
                
                for (int dx = -1; dx <= 1; dx++)
                {
                    for (int dy = -1; dy <= 1; dy++)
                    {
                        if (dx == 0 && dy == 0) continue;
                        
                        var jumpPos = new Point(current.Position.X + dx, current.Position.Y + dy);
                        if (IsValid(jumpPos) && _grid[jumpPos.X, jumpPos.Y] != 1)
                        {
                            var jumpResult = Jump(jumpPos, dx, dy, end);
                            if (jumpResult != null)
                            {
                                var neighbor = new Node(jumpResult, current.G + 1, 
                                                       CalculateHeuristic(jumpResult, end, heuristic), current);
                                if (!closedSet.Contains(neighbor.Position) && !openSet.Contains(neighbor))
                                {
                                    openSet.Add(neighbor);
                                }
                            }
                        }
                    }
                }
            }
            return new List<Point>();
        }
        
        private bool IsValid(Point p)
        {
            return p.X >= 0 && p.X < _grid.GetLength(0) && p.Y >= 0 && p.Y < _grid.GetLength(1);
        }
        
        private Point Jump(Point p, int dx, int dy, Point end)
        {
            if (p.Equals(end)) return p;
            
            if (!IsValid(p) || _grid[p.X, p.Y] == 1) return null;
            
            // Check for forced neighbors in straight directions
            if (dx != 0 && dy != 0)
            {
                if ((_grid[p.X - dx, p.Y] == 1) || (_grid[p.X, p.Y - dy] == 1))
                {
                    return p;
                }
            }
            
            // Check diagonal jumps
            if (dx != 0 && dy != 0)
            {
                if ((_grid[p.X - dx, p.Y + dy] == 1) || (_grid[p.X + dx, p.Y - dy] == 1))
                {
                    return p;
                }
            }
            
            // Continue straight if no obstacles
            if (dx != 0 && dy == 0)
            {
                if ((_grid[p.X + dx, p.Y + 1] == 1) || (_grid[p.X + dx, p.Y - 1] == 1))
                {
                    return p;
                }
                return Jump(new Point(p.X + dx, p.Y), dx, dy, end);
            } 
            else if (dy != 0 && dx == 0)
            {
                if ((_grid[p.X + 1, p.Y + dy] == 1) || (_grid[p.X - 1, p.Y + dy] == 1))
                {
                    return p;
                }
                return Jump(new Point(p.X, p.Y + dy), dx, dy, end);
            }
            else
            {
                return Jump(new Point(p.X + dx, p.Y + dy), dx, dy, end);
            }
        }
        
        private int CalculateHeuristic(Point a, Point b, Heuristic h)
        {
            int dx = Math.Abs(a.X - b.X);
            int dy = Math.Abs(a.Y - b.Y);
            
            switch (h)
            {
                case Heuristic.Manhattan: return dx + dy;
                case Heuristic.Euclidean: return (int)Math.Sqrt(dx * dx + dy * dy);
                case Heuristic.Chebyshev: return Math.Max(dx, dy);
                default: return 0;
            }
        }
        
        private List<Point> ReconstructPath(Node node)
        {
            var path = new List<Point>();
            var current = node;
            while (current != null)
            {
                path.Add(current.Position);
                current = current.Parent;
            }
            path.Reverse();
            return path;
        }
    }
    
    class NodeComparer : IComparer<Node>
    {
        public int Compare(Node x, Node y)
        {
            if (x == null || y == null)
                return 0;
            return x.F.CompareTo(y.F);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
type Heuristic = 'manhattan' | 'euclidean' | 'chebyshev';

class Point {
    constructor(public x: number, public y: number) {}
    
    equals(other: Point): boolean {
        return this.x === other.x && this.y === other.y;
    }
}

class Node implements Comparable<Node> {
    constructor(
        public pos: Point,
        public g: number,
        public h: number,
        public parent: Node | null
    ) {}
    
    get f(): number {
        return this.g + this.h;
    }
    
    compare(other: Node): number {
        return this.f - other.f;
    }
}

class JPS {
    private grid: number[][];
    
    constructor(grid: number[][]) {
        this.grid = grid;
    }
    
    findPath(start: Point, end: Point, heuristic: Heuristic): Point[] {
        if (this.grid[end.x][end.y] === 1) return [];
        
        const openSet = new PriorityQueue<Node>((a, b) => a.f - b.f);
        const closedSet = new Set<string>();
        const startNode = new Node(start, 0, this.calculateHeuristic(start, end, heuristic), null);
        openSet.enqueue(startNode);
        
        while (!openSet.isEmpty()) {
            const current = openSet.dequeue()!;
            
            if (current.pos.equals(end)) {
                return this.reconstructPath(current);
            }
            
            closedSet.add(`${current.pos.x},${current.pos.y}`);
            
            for (let dx = -1; dx <= 1; dx++) {
                for (let dy = -1; dy <= 1; dy++) {
                    if (dx === 0 && dy === 0) continue;
                    
                    const jumpPos = new Point(current.pos.x + dx, current.pos.y + dy);
                    if (this.isValid(jumpPos) && this.grid[jumpPos.x][jumpPos.y] !== 1) {
                        const jumpResult = this.jump(jumpPos, dx, dy, end);
                        if (jumpResult) {
                            const neighbor = new Node(jumpResult, current.g + 1, 
                                                     this.calculateHeuristic(jumpResult, end, heuristic), current);
                            const key = `${neighbor.pos.x},${neighbor.pos.y}`;
                            if (!closedSet.has(key) && !openSet.contains(neighbor)) {
                                openSet.enqueue(neighbor);
                            }
                        }
                    }
                }
            }
        }
        return [];
    }
    
    private isValid(p: Point): boolean {
        return p.x >= 0 && p.x < this.grid.length && p.y >= 0 && p.y < this.grid[0].length;
    }
    
    private jump(p: Point, dx: number, dy: number, end: Point): Point | null {
        if (p.equals(end)) return p;
        
        if (!this.isValid(p) || this.grid[p.x][p.y] === 1) return null;
        
        // Check for forced neighbors in straight directions
        if (dx !== 0 && dy !== 0) {
            if ((this.grid[p.x - dx]?.[p.y] === 1) || (this.grid[p.x]?.[p.y - dy] === 1)) {
                return p;
            }
        }
        
        // Check diagonal jumps
        if (dx !== 0 && dy !== 0) {
            if ((this.grid[p.x - dx]?.[p.y + dy] === 1) || (this.grid[p.x + dx]?.[p.y - dy] === 1)) {
                return p;
            }
        }
        
        // Continue straight if no obstacles
        if (dx !== 0 && dy === 0) {
            if ((this.grid[p.x + dx]?.[p.y + 1] === 1) || (this.grid[p.x + dx]?.[p.y - 1] === 1)) {
                return p;
            }
            return this.jump(new Point(p.x + dx, p.y), dx, dy, end);
        } else if (dy !== 0 && dx === 0) {
            if ((this.grid[p.x + 1]?.[p.y + dy] === 1) || (this.grid[p.x - 1]?.[p.y + dy] === 1)) {
                return p;
            }
            return this.jump(new Point(p.x, p.y + dy), dx, dy, end);
        } else {
            return this.jump(new Point(p.x + dx, p.y + dy), dx, dy, end);
        }
    }
    
    private calculateHeuristic(a: Point, b: Point, h: Heuristic): number {
        const dx = Math.abs(a.x - b.x);
        const dy = Math.abs(a.y - b.y);
        
        switch (h) {
            case 'manhattan': return dx + dy;
            case 'euclidean': return Math.sqrt(dx * dx + dy * dy);
            case 'chebyshev': return Math.max(dx, dy);
            default: return 0;
        }
    }
    
    private reconstructPath(node: Node): Point[] {
        const path: Point[] = [];
        let current: Node | null = node;
        while (current) {
            path.push(current.pos);
            current = current.parent;
        }
        return path.reverse();
    }
}

// Helper classes
interface Comparable<T> {
    compare(other: T): number;
}

class PriorityQueue<T> {
    private heap: T[];
    private compareFn: (a: T, b: T) => number;
    
    constructor(private comparator: (a: T, b: T) => number) {
        this.heap = [];
        this.compareFn = comparator;
    }
    
    enqueue(item: T): void {
        this.heap.push(item);
        this.bubbleUp(this.heap.length - 1);
    }
    
    dequeue(): T | undefined {
        const count = this.heap.length;
        if (count === 0) return undefined;
        
        const top = this.heap[0];
        const last = this.heap.pop()!;
        if (count > 1) {
            this.heap[0] = last;
            this.bubbleDown(0);
        }
        return top;
    }
    
    isEmpty(): boolean {
        return this.heap.length === 0;
    }
    
    contains(item: T): boolean {
        return this.heap.some(x => this.compareFn(x, item) === 0);
    }
    
    private bubbleUp(index: number): void {
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.compareFn(this.heap[index], this.heap[parentIndex]) >= 0) break;
            
            [this.heap[index], this.heap[parentIndex]] = 
                [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }
    
    private bubbleDown(index: number): void {
        const count = this.heap.length;
        while (true) {
            const leftChildIndex = 2 * index + 1;
            const rightChildIndex = 2 * index + 2;
            let smallest = index;
            
            if (leftChildIndex < count && 
                this.compareFn(this.heap[leftChildIndex], this.heap[smallest]) < 0) {
                smallest = leftChildIndex;
            }
            
            if (rightChildIndex < count && 
                this.compareFn(this.heap[rightChildIndex], this.heap[smallest]) < 0) {
                smallest = rightChildIndex;
            }
            
            if (smallest === index) break;
            
            [this.heap[index], this.heap[smallest]] = 
                [this.heap[smallest], this.heap[index]];
            index = smallest;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
Heuristic = {
    MANHATTAN = 1,
    EUCLIDEAN = 2,
    CHEBYSHEV = 3
}

Point = {}
Point.__index = Point

function Point:new(x, y)
    local self = setmetatable({}, Point)
    self.x = x
    self.y = y
    return self
end

function Point:equals(other)
    return self.x == other.x and self.y == other.y
end

Node = {}
Node.__index = Node

function Node:new(pos, g, h, parent)
    local self = setmetatable({}, Node)
    self.pos = pos
    self.g = g
    self.h = h
    self.parent = parent
    return self
end

function Node:getF()
    return self.g + self.h
end

JPS = {}
JPS.__index = JPS

function JPS:new(grid)
    local self = setmetatable({}, JPS)
    self.grid = grid
    self.height = #grid
    self.width = #grid[1]
    return self
end

function JPS:findPath(start, endPt, heuristic)
    if self.grid[endPt.x+1][endPt.y+1] == 1 then return {} end
    
    local openSet = {}
    local closedSet = {}
    local startNode = Node:new(start, 0, self:calculateHeuristic(start, endPt, heuristic), nil)
    table.insert(openSet, startNode)
    
    while #openSet > 0 do
        table.sort(openSet, function(a, b) return a:getF() < b:getF() end)
        local current = table.remove(openSet, 1)
        
        if current.pos:equals(endPt) then
            return self:reconstructPath(current)
        end
        
        closedSet[current.x.."-"..current.y] = true
        
        for dx = -1, 1 do
            for dy = -1, 1 do
                if dx == 0 and dy == 0 then continue end
                
                local jumpPos = Point:new(current.pos.x + dx, current.pos.y + dy)
                if self:isValid(jumpPos) and self.grid[jumpPos.x+1][jumpPos.y+1] ~= 1 then
                    local jumpResult = self:jump(jumpPos, dx, dy, endPt)
                    if jumpResult then
                        local neighbor = Node:new(jumpResult, current.g + 1, 
                                                 self:calculateHeuristic(jumpResult, endPt, heuristic), current)
                        local key = neighbor.pos.x.."-"..neighbor.pos.y
                        if not closedSet[key] then
                            table.insert(openSet, neighbor)
                        end
                    end
                end
            end
        end
    end
    return {}
end

function JPS:isValid(p)
    return p.x >= 0 and p.x < self.height and p.y >= 0 and p.y < self.width
end

function JPS:jump(p, dx, dy, endPt)
    if p:equals(endPt) then return p end
    
    if not self:isValid(p) or self.grid[p.x+1][p.y+1] == 1 then return nil end
    
    -- Check for forced neighbors in straight directions
    if dx ~= 0 and dy ~= 0 then
        if (self.grid[p.x - dx + 1][p.y + 1] == 1 or self.grid[p.x + 1][p.y - dy + 1] == 1) then
            return p
        end
    end
    
    -- Check diagonal jumps
    if dx ~= 0 and dy ~= 0 then
        if (self.grid[p.x - dx + 1][p.y + dy + 1] == 1 or self.grid[p.x + dx + 1][p.y - dy + 1] == 1) then
            return p
        end
    end
    
    -- Continue straight if no obstacles
    if dx ~= 0 and dy == 0 then
        if (self.grid[p.x + dx + 1][p.y + 1 + 1] == 1 or self.grid[p.x + dx + 1][p.y - 1 + 1] == 1) then
            return p
        end
        return self:jump(Point:new(p.x + dx, p.y), dx, dy, endPt)
    elseif dy ~= 0 and dx == 0 then
        if (self.grid[p.x + 1 + 1][p.y + dy + 1] == 1 or self.grid[p.x - 1 + 1][p.y + dy + 1] == 1) then
            return p
        end
        return self:jump(Point:new(p.x, p.y + dy), dx, dy, endPt)
    else
        return self:jump(Point:new(p.x + dx, p.y + dy), dx, dy, endPt)
    end
end

function JPS:calculateHeuristic(a, b, h)
    local dx = math.abs(a.x - b.x)
    local dy = math.abs(a.y - b.y)
    
    if h == Heuristic.MANHATTAN then
        return dx + dy
    elseif h == Heuristic.EUCLIDEAN then
        return math.sqrt(dx*dx + dy*dy)
    elseif h == Heuristic.CHEBYSHEV then
        return math.max(dx, dy)
    else
        return 0
    end
end

function JPS:reconstructPath(node)
    local path = {}
    local current = node
    while current do
        table.insert(path, 1, {x = current.pos.x, y = current.pos.y})
        current = current.parent
    end
    return path
end
  • 标题: 【游戏算法】 - 寻路算法-JPS算法（跳点搜索）
  • 作者: 宋
  • 创建于 : 2022-11-18 19:07:05
  • 更新于 : 2023-04-15 19:20:09
  • 链接: https://sxl-space.tk/2022/11/18/002_Find-Path-3-JPS/
  • 版权声明: 版权所有 © 宋，禁止转载。
目录
【游戏算法】 - 寻路算法-JPS算法（跳点搜索）
  1. 1. 跳点搜索
    1. 1.1. 优化方式
    2. 1.2. JPS的核心概念
      1. 1.2.1. 强制邻居（Forced Neighbor）
      2. 1.2.2. 跳点（Jump Point）
      3. 1.2.3. 跳跃搜索
        1. 1.2.3.1. 直线方向搜索（上下左右）
        2. 1.2.3.2. 斜方向搜索（对角线）
      4. 1.2.4. 算法流程概述
      5. 1.2.5. 代码实现