python-pathfinding/test/test_path.py at main · brean/python-pathfinding · GitHub

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
import json
import os

from pathfinding.core.diagonal_movement import DiagonalMovement
from pathfinding.core.grid import Grid
from pathfinding.finder.a_star import AStarFinder
from pathfinding.finder.best_first import BestFirst
from pathfinding.finder.bi_a_star import BiAStarFinder
from pathfinding.finder.bi_breadth_first import BiBreadthFirstFinder
from pathfinding.finder.bi_best_first import BiBestFirstFinder
from pathfinding.finder.bi_dijkstra import BiDijkstraFinder
from pathfinding.finder.breadth_first import BreadthFirstFinder
from pathfinding.finder.dijkstra import DijkstraFinder
from pathfinding.finder.finder import ExecutionRunsException
from pathfinding.finder.finder import ExecutionTimeException
from pathfinding.finder.ida_star import IDAStarFinder
from pathfinding.finder.msp import MinimumSpanningTree

import pytest


BASE_PATH = os.path.abspath(os.path.dirname(__file__))

# test scenarios from Pathfinding.JS
scenarios = os.path.join(BASE_PATH, 'path_test_scenarios.json')
data = json.load(open(scenarios, 'r', encoding='utf-8'))
finders = [AStarFinder, BestFirst, BiAStarFinder, BiBreadthFirstFinder,
           BiBestFirstFinder, BiDijkstraFinder, DijkstraFinder, IDAStarFinder,
           BreadthFirstFinder, MinimumSpanningTree]
TIME_LIMIT = 10  # give it a 10 second limit.


def grid_from_scenario(scenario):
    inverse = scenario['inverse'] if 'inverse' in scenario else True
    grid = Grid(matrix=scenario['matrix'], inverse=inverse)
    if scenario.get('passableLeftRightBorder'):
        grid.set_passable_left_right_border()
    if scenario.get('passableUpDownBorder'):
        grid.set_passable_up_down_border()
    start = grid.node(scenario['startX'], scenario['startY'])
    end = grid.node(scenario['endX'], scenario['endY'])
    return grid, start, end


def test_path():
    """
    test scenarios defined in json file
    """
    for scenario in data:
        grid, start, end = grid_from_scenario(scenario)
        for find in finders:
            grid.cleanup()
            finder = find(time_limit=TIME_LIMIT)
            weighted = False
            if 'weighted' in scenario:
                weighted = scenario['weighted']
            if weighted and not finder.weighted:
                continue
            path, _ = finder.find_path(start, end, grid)
            print(scenario['name'], find.__name__)
            print(grid.grid_str(path=path, start=start, end=end,
                                show_weight=weighted))
            print('path: {}'.format(path))
            assert len(path) == scenario['expectedLength']


def test_path_diagonal():
    # test diagonal movement
    for scenario in data:
        grid, start, end = grid_from_scenario(scenario)
        for find in finders:
            grid.cleanup()
            finder = find(diagonal_movement=DiagonalMovement.always,
                          time_limit=TIME_LIMIT)
            weighted = False
            if 'weighted' in scenario:
                weighted = scenario['weighted']
            if weighted and not finder.weighted:
                continue

            path, runs = finder.find_path(start, end, grid)
            print(scenario['name'], find.__name__, runs, len(path))
            print(grid.grid_str(start=start, end=end))
            print(grid.grid_str(path=path, start=start, end=end,
                                show_weight=weighted))
            print('path: {}'.format(path))
            assert len(path) == scenario['expectedDiagonalLength']


def test_unreachable_only_when_no_obstacle():
    # when the end is unreachable the open list can drain to only stale
    # entries, so pop_node() returns None; the finder should report an empty
    # path instead of crashing (issue #83)
    matrix = [
        [0, 0, 0, 0, 0, 1, 1],
        [0, 1, 1, 1, 0, 1, 1],
        [0, 1, 1, 1, 0, 1, 1],
        [0, 1, 1, 1, 0, 1, 1],
        [0, 1, 1, 1, 0, 1, 1],
        [0, 0, 0, 0, 0, 1, 1],
    ]
    grid = Grid(matrix=matrix)
    start = grid.node(1, 2)
    end = grid.node(6, 3)
    finder = AStarFinder(
        diagonal_movement=DiagonalMovement.only_when_no_obstacle)
    path, _ = finder.find_path(start, end, grid)
    assert path == []


def test_max_runs():
    grid, start, end = grid_from_scenario(data[1])
    for find in finders:
        grid.cleanup()
        finder = find(diagonal_movement=DiagonalMovement.always,
                      time_limit=TIME_LIMIT, max_runs=3)
        with pytest.raises(ExecutionRunsException):
            path, runs = finder.find_path(start, end, grid)
            print('{} finishes after {} runs without exception'.format(
                find.__name__, runs))
            print('path: {}'.format(path))
        msg = '{} needed to much iterations'.format(
            finder.__class__.__name__)
        assert finder.runs <= 3, msg


def test_time():
    grid, start, end = grid_from_scenario(data[1])
    for find in finders:
        grid.cleanup()
        finder = find(diagonal_movement=DiagonalMovement.always,
                      time_limit=-.1)
        with pytest.raises(ExecutionTimeException):
            path, runs = finder.find_path(start, end, grid)
            print('{} finishes after {} runs without exception'.format(
                find.__name__, runs))
            print('path: {}'.format(path))
        msg = '{} took to long'.format(finder.__class__.__name__)
        assert finder.runs == 1, msg


if __name__ == '__main__':
    test_path()
    test_path_diagonal()