Belajar Menyelesaikan Labirin dengan Python

Building a maze solver (Membangun pemecah labirin)


Mari gunakan algoritma A * untuk memecahkan labirin. Perhatikan gambar berikut:


Simbol # menunjukkan rintangan. Simbol o melambangkan titik awal dan x mewakili tujuan. Tujuannya yakni menemukan jalur terpendek dari titik awal hingga titik akhir. Ayo dilihat bagaimana melakukannya dengan Python.

 1. Buat file Python baru dan ketik kode berikut:

import math
from simpleai.search import SearchProblem, astar

# Class containing the methods to solve the maze
class MazeSolver(SearchProblem):
# Initialize the class
def __init__(self, board):
self.board = board
self.goal = (0, 0)

for y in range(len(self.board)):
for x in range(len(self.board[y])):
if self.board[y][x].lower() == "o":
self.initial = (x, y)
elif self.board[y][x].lower() == "x":
self.goal = (x, y)

super(MazeSolver, self).__init__(initial_state=self.initial)

# Define the method that takes actions
# to arrive at the solution
def actions(self, state):
actions = []
for action in COSTS.keys():
newx, newy = self.result(state, action)
if self.board[newy][newx] != "#":
actions.append(action)

return actions

# Update the state based on the action
def result(self, state, action):
x, y = state

if action.count("up"):
y -= 1
if action.count("down"):
y += 1
if action.count("left"):
x -= 1
if action.count("right"):
x += 1

new_state = (x, y)

return new_state

# Check if we have reached the goal
def is_goal(self, state):
return state == self.goal

# Compute the cost of taking an action
def cost(self, state, action, state2):
return COSTS[action]

# Heuristic that we use to arrive at the solution
def heuristic(self, state):
x, y = state
gx, gy = self.goal

return math.sqrt((x - gx) ** 2 + (y - gy) ** 2)

if __name__ == "__main__":
# Define the map
MAP = """
##############################
# # # #
# #### ######## # #
# o # # # #
# ### ##### ###### #
# # ### # #
# # # # # # ###
# ##### # # # x #
# # # #
##############################
"""

# Convert map to a list
print(MAP)
MAP = [list(x) for x in MAP.split("\n") if x]

# Define cost of moving around the map
cost_regular = 1.0
cost_diagonal = 1.7

# Create the cost dictionary
COSTS = {
"up": cost_regular,
"down": cost_regular,
"left": cost_regular,
"right": cost_regular,
"up left": cost_diagonal,
"up right": cost_diagonal,
"down left": cost_diagonal,
"down right": cost_diagonal,
}

# Create maze solver object
problem = MazeSolver(MAP)

# Run the solver
result = astar(problem, graph_search=True)

# Extract the path
path = [x[1] for x in result.path()]

# Print the result
print()
for y in range(len(MAP)):
for x in range(len(MAP[y])):
if (x, y) == problem.initial:
print('o', end='')
elif (x, y) == problem.goal:
print('x', end='')
elif (x, y) in path:
print('·', end='')
else:
print(MAP[y][x], end='')

print()

 2. Hasil output akan nampak pada terminal;

3. Saya perbesar, biar lebih kelihatan


  Referensi:

  • Prateek Joshi. 2017. Artificial Intelligence with Python-Build real-world Artificial Intelligence applications with Python to intelligently interact with the world around you. Birmingham, Mumbai.

0 Komentar