FilesExpand file tree

bubble_sort

/

astar.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

150 lines (131 loc) · 4.1 KB

bubble_sort

/

astar.py

Copy path

Top

File metadata and controls

• Code
• Blame

150 lines (131 loc) · 4.1 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

"""

The A* algorithm combines features of uniform-cost search and pure

heuristic search to efficiently compute optimal solutions.

A* algorithm is a best-first search algorithm in which the cost

associated with a node is f(n) = g(n) + h(n),

where g(n) is the cost of the path from the initial state to node n and

h(n) is the heuristic estimate or the cost or a path

from node n to a goal.A* algorithm introduces a heuristic into a

regular graph-searching algorithm,

essentially planning ahead at each step so a more optimal decision

is made.A* also known as the algorithm with brains

"""

import numpy as np

class Cell:

"""

Class cell represents a cell in the world which have the property

position : The position of the represented by tupleof x and y

coordinates initially set to (0,0)

parent : This contains the parent cell object which we visited

before arrinving this cell

g,h,f : The parameters for constructing the heuristic function

which can be any function. for simplicity used line

distance

"""

def __init__(self):

self.position = (0, 0)

self.parent = None

self.g = 0

self.h = 0

self.f = 0

"""

overrides equals method because otherwise cell assign will give

wrong results

"""

def __eq__(self, cell):

return self.position == cell.position

def showcell(self):

print(self.position)

class Gridworld:

"""

Gridworld class represents the external world here a grid M*M

matrix

world_size: create a numpy array with the given world_size default is 5

"""

def __init__(self, world_size=(5, 5)):

self.w = np.zeros(world_size)

self.world_x_limit = world_size[0]

self.world_y_limit = world_size[1]

def show(self):

print(self.w)

def get_neigbours(self, cell):

"""

Return the neighbours of cell

"""

neughbour_cord = [

(-1, -1),

(-1, 0),

(-1, 1),

(0, -1),

(0, 1),

(1, -1),

(1, 0),

(1, 1),

]

current_x = cell.position[0]

current_y = cell.position[1]

neighbours = []

for n in neughbour_cord:

x = current_x + n[0]

y = current_y + n[1]

if 0 <= x < self.world_x_limit and 0 <= y < self.world_y_limit:

c = Cell()

c.position = (x, y)

c.parent = cell

neighbours.append(c)

return neighbours

def astar(world, start, goal):

"""

Implementation of a start algorithm

world : Object of the world object

start : Object of the cell as start position

stop : Object of the cell as goal position

>>> p = Gridworld()

>>> start = Cell()

>>> start.position = (0,0)

>>> goal = Cell()

>>> goal.position = (4,4)

>>> astar(p, start, goal)

[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4)]

"""

_open = []

_closed = []

_open.append(start)

while _open:

min_f = np.argmin([n.f for n in _open])

current = _open[min_f]

_closed.append(_open.pop(min_f))

if current == goal:

break

for n in world.get_neigbours(current):

for c in _closed:

if c == n:

continue

n.g = current.g + 1

x1, y1 = n.position

x2, y2 = goal.position

n.h = (y2 - y1) ** 2 + (x2 - x1) ** 2

n.f = n.h + n.g

for c in _open:

if c == n and c.f < n.f:

continue

_open.append(n)

path = []

while current.parent is not None:

path.append(current.position)

current = current.parent

path.append(current.position)

return path[::-1]

if __name__ == "__main__":

world = Gridworld()

# stat position and Goal

start = Cell()

start.position = (0, 0)

goal = Cell()

goal.position = (4, 4)

print(f"path from {start.position} to {goal.position}")

s = astar(world, start, goal)

# Just for visual reasons

for i in s:

world.w[i] = 1

print(world.w)