Jump Point Search (JPS) アルゴリズムは、A* アルゴリズムを改良したもので、大規模な地図での探索効率を向上させます。

A* アルゴリズムは、拡張するノードのすべての隣接ノードを考慮しますが、地図が大きい場合、openList 中のノード数が多くなり、効率が低下します。

JPS アルゴリズムは、直線的なパスの場合、中間ノードを探索に含めません。探索が必要なのは、道のりを変えるための「拐点」（jump point）のみです。

実装前のルール確認

1. Forced Neighbors: ノード X の隣接ノード N が、X を通らないと到達できない場合、N は X の強制的な隣接ノードです。
2. Jump Points:
   1. 起点または終点。
   2. 強制的な隣接ノードを有する。
   3. 斜方向からの探索において、水平または垂直方向に強制的な隣接ノードを有する。

斜方向探索とは、(1,1)、(-1,1)、(1,-1)、(-1,-1) の4つの方向を指します。

JPS アルゴリズムの仕組み

1. openList を定義し、起点 S を openList に追加します。
2. openList が空でない限り、最小の f-スコアを持つノード A を取り出し、A が終点である場合に成功します。
3. 探索方向 dirList を決定します。起点の場合、8つの方向を探索します。
4. 各方向 dir について、直線的に探索します。探索途中で jump point を発見した場合、そのノードを openList に追加します。

探索方向 dirList の決定方法:

if (A に親がない) {
    dirList = {上、下、左、右、左上、右上、右下、左下};
} else {
    dirList = {水平方向、垂直方向、斜方向};
    // 親からの方向を分解し、dirList に追加
    if (horizontalDir != 0) {
        dirList.Add((horizontalDir, 0));
    }
    if (verticalDir != 0) {
        dirList.Add((0, verticalDir));
    }
    if (horizontalDir != 0 かつ verticalDir != 0) {
        dirList.Add((horizontalDir, verticalDir));
    }
}

jump point を発見するための直線探索:

foreach (方向 dir in dirList) {
    B = A
    while (true) {
        B += dir
        if (B が jump point) {
            B を openList に追加
            break;
        }
        if (B が障害物または地図境界) {
            break;
        }
    }
}

Python での JPS アルゴリズムの実装

以下に、JPS アルゴリズムを Python で実装した例を示します。

Node クラス:

class Node:
    def __init__(self, x, y, parent=None):
        self.x = x
        self.y = y
        self.parent = parent
        self.g = 0
        self.h = 0
        self.f = 0

優先度キュー (openList) を使用します:

import heapq

def jps_search(grid, start, end):
    open_list = []
    heapq.heappush(open_list, (0, start))
    closed_list = set()

    while open_list:
        current = heapq.heappop(open_list)[1]
        if current == end:
            return reconstruct_path(current)
        closed_list.add((current.x, current.y))

        # 探索方向を決定
        if current.parent is None:
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1),
                          (-1, 1), (1, 1), (1, -1), (-1, -1)]
        else:
            dx = current.x - current.parent.x
            dy = current.y - current.parent.y
            directions = []
            if dx != 0:
                directions.append((dx, 0))
            if dy != 0:
                directions.append((0, dy))
            if dx != 0 and dy != 0:
                directions.append((dx, dy))

        for dir in directions:
            x, y = current.x, current.y
            step = 1
            while True:
                x += dir[0]
                y += dir[1]
                if not is_valid(grid, x, y):
                    break
                # jump point を検出
                if is_jump_point(grid, x, y, current.parent):
                    # 前のノードを jump point として追加
                    x -= dir[0]
                    y -= dir[1]
                    next_node = Node(x, y, current)
                    next_node.g = current.g + step
                    next_node.h = heuristic(next_node, end)
                    next_node.f = next_node.g + next_node.h
                    if (next_node.x, next_node.y) not in closed_list:
                        heapq.heappush(open_list, (next_node.f, next_node))
                    break
                step += 1

有効性チェック:

def is_valid(grid, x, y):
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    if x < 0 or x >= rows or y < 0 or y >= cols:
        return False
    return grid[x][y] == 0  # 0 は通過可能、1 は障害物

Heuristic 関数:

def heuristic(node, end):
    return abs(node.x - end.x) + abs(node.y - end.y)

jump point 検出:

def is_jump_point(grid, x, y, parent):
    if parent is None:
        return True  # 起点は常に jump point
    # 強制的な隣接ノードを検出
    forced = get_forced_neighbors(grid, x, y, parent)
    return len(forced) > 0

def get_forced_neighbors(grid, x, y, parent):
    forced = []
    dx = x - parent.x
    dy = y - parent.y

    # 水平方向の強制的な隣接ノードを検出
    if dx != 0:
        # 上方向
        if is_valid(grid, x, y + 1):
            forced.append((x, y + 1))
        # 下方向
        if is_valid(grid, x, y - 1):
            forced.append((x, y - 1))
    # 垂直方向の強制的な隣接ノードを検出
    if dy != 0:
        # 右方向
        if is_valid(grid, x + 1, y):
            forced.append((x + 1, y))
        # 左方向
        if is_valid(grid, x - 1, y):
            forced.append((x - 1, y))
    return forced

パス再構築:

def reconstruct_path(node):
    path = []
    while node is not None:
        path.append((node.x, node.y))
        node = node.parent
    return path[::-1]  # 順序を逆転

注意点

• 起点の場合、8つの方向を探索します。
• 親ノードがある場合、親からの方向を分解し、水平、垂直、斜方向を探索します。
• 直線探索中に jump point を発見した場合、そのノードを openList に追加します。

この実装は、大規模な地図での探索効率を向上させます。障害物がない直線状のパスは、少数の jump point で済みます。