AI_PROJECT/BFS.py

268 lines
9.5 KiB
Python

import random
import pygame
import Node
from displayControler import NUM_X, NUM_Y
from Pole import stoneList
def goalTest1(hIndex):
for i in list(hIndex.values()):
if i == 0:
return False
return True
def succ1(state):
resp = []
hIndex = state["hydradeIndex"].copy()
if state["direction"] == "N":
if state["y"] > 0:
if hIndex[state["x"], state["y"]-1] == 0:
hIndex[state["x"], state["y"] - 1] = 1
resp.append(["forward", {'x': state["x"], 'y': state["y"]-1, 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "E", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "W", 'hydradeIndex': state["hydradeIndex"].copy()}])
elif state["direction"] == "S":
if state["y"] < NUM_Y-1:
if hIndex[state["x"], state["y"]+1] == 0:
hIndex[state["x"], state["y"] + 1] = 1
resp.append(["forward", {'x': state["x"], 'y': state["y"]+1, 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "W", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "E", 'hydradeIndex': state["hydradeIndex"].copy()}])
elif state["direction"] == "E":
if state["x"] < NUM_X-1:
if hIndex[state["x"]+1, state["y"]] == 0:
hIndex[state["x"] + 1, state["y"]] = 1
resp.append(["forward", {'x': state["x"]+1, 'y': state["y"], 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "S", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "N", 'hydradeIndex': state["hydradeIndex"].copy()}])
else: #state["zwrot"] == "W"
if state["x"] > 0:
if hIndex[state["x"]-1, state["y"]] == 0:
hIndex[state["x"] - 1, state["y"]] = 1
resp.append(["forward", {'x': state["x"]-1, 'y': state["y"], 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "N", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "S", 'hydradeIndex': state["hydradeIndex"].copy()}])
return resp
def check1(tab, state):
for i in tab:
if i.state == state:
return False
return True
def BFS1(istate):
fringe = []
explored = []
x = Node.Node(istate)
fringe.append(x)
while True:
if fringe == []:
return False
elem = fringe.pop(0)
if goalTest1(elem.state["hydradeIndex"]):
x = elem
tab = []
while x.parent != None:
tab.append([x.parent, x.action])
x = x.parent
return tab
explored.append(elem)
for resp in succ1(elem.state):
if check1(fringe, resp[1]) and check1(explored, resp[1]):
x = Node.Node(resp[1])
x.parent = elem
x.action = resp[0]
fringe.append(x)
for event in pygame.event.get():
if event.type == pygame.QUIT:
quit()
def goalTest3(state, goalTreassure):
if state["x"] == goalTreassure[0] and state["y"] == goalTreassure[1]:
return True
return False
def succ3(state):
resp = []
if state["direction"] == "N":
if state["y"] > 0 and (state['x'], state["y"] - 1) not in stoneList:
resp.append(["forward", {'x': state["x"], 'y': state["y"]-1, 'direction': state["direction"]}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "E"}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "W"}])
elif state["direction"] == "S":
if state["y"] < NUM_Y - 1 and (state['x'], state["y"] + 1) not in stoneList:
resp.append(["forward", {'x': state["x"], 'y': state["y"]+1, 'direction': state["direction"]}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "W"}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "E"}])
elif state["direction"] == "E":
if state["x"] < NUM_X - 1 and (state['x'] + 1, state["y"]) not in stoneList:
resp.append(["forward", {'x': state["x"]+1, 'y': state["y"], 'direction': state["direction"]}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "S"}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "N"}])
else: #state["zwrot"] == "W"
if state["x"] > 0 and (state['x'] - 1, state["y"]) not in stoneList:
resp.append(["forward", {'x': state["x"]-1, 'y': state["y"], 'direction': state["direction"]}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "N"}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "S"}])
return resp
def check3(tab, state):
for i in tab:
if i.state == state:
return False
return True
def BFS3(istate,GT):
randomGT=False
if(randomGT==True):
goalTreassuere = (random.randint(0,NUM_X-1), random.randint(0,NUM_Y-1))
else:
goalTreassuere=GT
print(goalTreassuere)
fringe = []
explored = []
x = Node.Node(istate)
fringe.append(x)
while True:
if fringe == []:
return False
elem = fringe.pop(0)
if goalTest3(elem.state, goalTreassuere):
x = elem
tab = []
while x.parent != None:
tab.append([x.parent, x.action])
x = x.parent
return tab
explored.append(elem)
for resp in succ3(elem.state):
if check3(fringe, resp[1]) and check3(explored, resp[1]):
x = Node.Node(resp[1])
x.parent = elem
x.action = resp[0]
fringe.append(x)
for event in pygame.event.get():
if event.type == pygame.QUIT:
quit()
"""
def goalTest(hIndex):
for i in list(hIndex.values()):
if i == 0:
return False
return True
def succ(state):
resp = []
hIndex = state["hydradeIndex"].copy()
if state["direction"] == "N":
if state["y"] > 0:
if hIndex[state["x"], state["y"]-1] == 0:
hIndex[state["x"], state["y"] - 1] = 1
resp.append(["forward", {'x': state["x"], 'y': state["y"]-1, 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "E", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "W", 'hydradeIndex': state["hydradeIndex"].copy()}])
elif state["direction"] == "S":
if state["y"] < dCon.NUM_Y-1:
if hIndex[state["x"], state["y"]+1] == 0:
hIndex[state["x"], state["y"] + 1] = 1
resp.append(["forward", {'x': state["x"], 'y': state["y"]+1, 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "W", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "E", 'hydradeIndex': state["hydradeIndex"].copy()}])
elif state["direction"] == "E":
if state["x"] < dCon.NUM_X-1:
if hIndex[state["x"]+1, state["y"]] == 0:
hIndex[state["x"] + 1, state["y"]] = 1
resp.append(["forward", {'x': state["x"]+1, 'y': state["y"], 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "S", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "N", 'hydradeIndex': state["hydradeIndex"].copy()}])
else: #state["direction"] == "W"
if state["x"] > 0:
if hIndex[state["x"]-1, state["y"]] == 0:
hIndex[state["x"] - 1, state["y"]] = 1
resp.append(["forward", {'x': state["x"]-1, 'y': state["y"], 'direction': state["direction"], 'hydradeIndex': hIndex}])
resp.append(["right", {'x': state["x"], 'y': state["y"], 'direction': "N", 'hydradeIndex': state["hydradeIndex"].copy()}])
resp.append(["left", {'x': state["x"], 'y': state["y"], 'direction': "S", 'hydradeIndex': state["hydradeIndex"].copy()}])
return resp
def check(tab, state):
for i in tab:
if i.state == state:
return False
return True
def BFS(istate):
fringe = []
explored = []
x = Node.Node(istate)
fringe.append(x)
while True:
if fringe == []:
return False
elem = fringe.pop(0)
if goalTest(elem.state["hydradeIndex"]):
x = elem
tab = []
while x.parent != None:
tab.append(x.action)
x = x.parent
return tab
explored.append(elem)
for resp in succ(elem.state):
if check(fringe, resp[1]) and check(explored, resp[1]):
x = Node.Node(resp[1])
x.parent = elem
x.action = resp[0]
fringe.append(x)
"""