python-pathfinding/pathfinding/finder/a_star.py at python2 · brean/python-pathfinding · GitHub

History

94 lines (84 loc) · 3.71 KB

Raw

# -*- coding: utf-8 -*-

import heapq # used for the so colled "open list" that stores known nodes

from .finder import BY_END, Finder, MAX_RUNS, TIME_LIMIT

from ..core.diagonal_movement import DiagonalMovement

from ..core.heuristic import manhattan, octile

from ..core.util import backtrace, bi_backtrace

class AStarFinder(Finder):

def __init__(self, heuristic=None, weight=1,

diagonal_movement=DiagonalMovement.never,

time_limit=TIME_LIMIT,

max_runs=MAX_RUNS):

"""

find shortest path using A* algorithm

:param heuristic: heuristic used to calculate distance of 2 points

(defaults to manhattan)

:param weight: weight for the edges

:param diagonal_movement: if diagonal movement is allowed

(see enum in diagonal_movement)

:param time_limit: max. runtime in seconds

:param max_runs: max. amount of tries until we abort the search

(optional, only if we enter huge grids and have time constrains)

<=0 means there are no constrains and the code might run on any

large map.

"""

super(AStarFinder, self).__init__(

heuristic=heuristic,

weight=weight,

diagonal_movement=diagonal_movement,

time_limit=time_limit,

max_runs=max_runs)

if not heuristic:

if diagonal_movement == DiagonalMovement.never:

self.heuristic = manhattan

else:

# When diagonal movement is allowed the manhattan heuristic is

# not admissible it should be octile instead

self.heuristic = octile

def check_neighbors(self, start, end, grid, open_list,

open_value=True, backtrace_by=None):

"""

find next path segment based on given node

(or return path if we found the end)

:param start: start node

:param end: end node

:param grid: grid that stores all possible steps/tiles as 2D-list

:param open_list: stores nodes that will be processed next

"""

# pop node with minimum 'f' value

node = heapq.nsmallest(1, open_list)[0]

open_list.remove(node)

node.closed = True

# if reached the end position, construct the path and return it

# (ignored for bi-directional a*, there we look for a neighbor that is

# part of the oncoming path)

if not backtrace_by and node == end:

return backtrace(end)

# get neighbors of the current node

neighbors = self.find_neighbors(grid, node)

for neighbor in neighbors:

if neighbor.closed:

# already visited last minimum f value

continue

if backtrace_by and neighbor.opened == backtrace_by:

# found the oncoming path

if backtrace_by == BY_END:

return bi_backtrace(node, neighbor)

else:

return bi_backtrace(neighbor, node)

# check if the neighbor has not been inspected yet, or

# can be reached with smaller cost from the current node

self.process_node(neighbor, node, end, open_list, open_value)

# the end has not been reached (yet) keep the find_path loop running

return None

def find_path(self, start, end, grid):

"""

find a path from start to end node on grid using the A* algorithm

:param start: start node

:param end: end node

:param grid: grid that stores all possible steps/tiles as 2D-list

:return:

"""

start.g = 0

start.f = 0

return super(AStarFinder, self).find_path(start, end, grid)

python-pathfinding/pathfinding/finder/a_star.py at python2 · brean/python-pathfinding · GitHub

Expand file tree

Breadcrumbs

a_star.py

Latest commit

History

Breadcrumbs

a_star.py

File metadata and controls