Subversion Repositories programming

Rev

Rev 424 | Show entire file | Ignore whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 424 Rev 429
Line 7... Line 7...
7 
from PyCompat import *
 7 
from PyCompat import *
8 
from Actions import *
 8 
from Actions import *
9 
from Menu import Menu
 9 
from Menu import Menu
10 
import sys
 10 
import sys
11 
import copy
 11 
import copy
- 
 
 12 
import random
12 
 
 13 
 
13 
(WALK, PUSH, CLIMB, GRAB) = ('Walk', 'Push', 'Climb', 'Grab')
 14 
(WALK, PUSH, CLIMB, GRAB) = ('Walk', 'Push', 'Climb', 'Grab')
14 
 
 15 
 
- 
 
 16 
class Possible:
- 
 
 17 
	def __init__ (self, action, arg1=None, arg2=None):
- 
 
 18 
		self.action = action
- 
 
 19 
		self.arg1 = arg1
- 
 
 20 
		self.arg2 = arg2
- 
 
 21 
 
15 
def findNextMove (State):
 22 
	def takeAction (self):
- 
 
 23 
		pass
- 
 
 24 
 
- 
 
 25 
	def __eq__ (self, rhs):
16 
	"""Prioritized Search for the best next move"""
 26 
		return (self.action == rhs.action) and (self.arg1 == rhs.arg1) \
- 
 
 27 
				and (self.arg2 == rhs.arg2)
- 
 
 28 
 
- 
 
 29 
	def __repr__ (self):
- 
 
 30 
		s = '(%s' % self.action
- 
 
 31 
		if self.arg1:
- 
 
 32 
			s += ', %s' % self.arg1
17 
 
 33 
 
18 
	monkeyPosition = Action(State).findMonkeyPosition ()
 34 
		if self.arg2:
19 
	boxPosition = Action(State).findBoxPosition ()
 35 
			s += ', %s' % self.arg2
20 
 
 36 
 
- 
 
 37 
		return '%s)' % s
- 
 
 38 
 
- 
 
 39 
def generatePossibleMoves (State):
- 
 
 40 
	moves = []
- 
 
 41 
 
21 
	# Try to Grab
 42 
	# Grab, Priority 1
22 
	if Grab(State).meetsPreconditions():
 43 
	if Grab(State).meetsPreconditions():
- 
 
 44 
		moves.append ((1, Possible(GRAB)))
- 
 
 45 
 
- 
 
 46 
	# Push, Priority 2
- 
 
 47 
	for f in LOCATIONS:
- 
 
 48 
		for t in LOCATIONS:
- 
 
 49 
			if Push(State, f, t).meetsPreconditions():
- 
 
 50 
				moves.append ((2, Possible(PUSH, f, t)))
- 
 
 51 
 
- 
 
 52 
	# Climb, Priority 2
- 
 
 53 
	for d in BOX_LOC:
- 
 
 54 
		if Climb(State, d).meetsPreconditions():
- 
 
 55 
			moves.append ((2, Possible(CLIMB, d)))
- 
 
 56 
 
- 
 
 57 
	# Walk, Priority 3
- 
 
 58 
	for f in LOCATIONS:
- 
 
 59 
		for t in LOCATIONS:
- 
 
 60 
			if Walk(State, f, t).meetsPreconditions():
- 
 
 61 
				moves.append ((3, Possible(WALK, f, t)))
- 
 
 62 
 
- 
 
 63 
	return moves
- 
 
 64 
 
- 
 
 65 
def chooseMove (moves, priority=None):
- 
 
 66 
	possible = []
- 
 
 67 
 
- 
 
 68 
	# If priority was not set, choose something from the highest
- 
 
 69 
	# priority that is available
- 
 
 70 
	if not priority:
- 
 
 71 
		if len(moves) > 0:
- 
 
 72 
			moves.sort()
- 
 
 73 
			priority = moves[0][0]
- 
 
 74 
 
- 
 
 75 
	for e in moves:
- 
 
 76 
		if e[0] == priority:
- 
 
 77 
			possible.append (e[1])
- 
 
 78 
 
- 
 
 79 
	# Make sure the list is not empty
- 
 
 80 
	if len(possible) < 1:
23 
		return (GRAB,)
 81 
		return False
- 
 
 82 
 
- 
 
 83 
	# Return a random choice from the possible moves of this priority
- 
 
 84 
	return random.choice (possible)
- 
 
 85 
 
- 
 
 86 
# Return (loop_length, first_instruction_in_loop)
- 
 
 87 
def loopDetector (plan_param):
- 
 
 88 
	plan = copy.deepcopy (plan_param)
- 
 
 89 
	plan.reverse()
- 
 
 90 
 
- 
 
 91 
	isloop = False
- 
 
 92 
 
- 
 
 93 
	for i in xrange(len(plan)):
- 
 
 94 
		cur = plan[:i]
- 
 
 95 
		rest= plan[i:]
- 
 
 96 
 
- 
 
 97 
		for i in xrange(len(cur)):
- 
 
 98 
			isloop = True
- 
 
 99 
			if cur[i] != rest[i]:
- 
 
 100 
				isloop = False
- 
 
 101 
				break
- 
 
 102 
 
- 
 
 103 
		if isloop:
- 
 
 104 
			return (len(cur), cur[0])
- 
 
 105 
 
- 
 
 106 
	return False
- 
 
 107
- 
 
 108 
 
- 
 
 109 
def findNextMove (State):
- 
 
 110 
	"""Prioritized Search for the best next move"""
- 
 
 111 
 
- 
 
 112 
	poss_moves = generatePossibleMoves(State)
- 
 
 113 
	chose_move = chooseMove (poss_moves)
- 
 
 114 
	#print 'POSSIBLE MOVES: ', poss_moves
- 
 
 115 
	#print 'CHOOSE MOVE: ', chose_move
24 
 
 116 
 
25 
	# Try to push box to middle
 - 
 
26 
	if Push(State, boxPosition, Push.MIDDLE).meetsPreconditions():
 - 
 
27 
		if boxPosition != Push.MIDDLE:
 - 
 
28 
			return (PUSH, boxPosition, Push.MIDDLE)
 - 
 
29 
 
 - 
 
30 
	# Try to walk to box
 - 
 
31 
	if Walk(State, monkeyPosition, boxPosition).meetsPreconditions():
 - 
 
32 
		if monkeyPosition != boxPosition:
 - 
 
33 
			return (WALK, monkeyPosition, boxPosition)
 - 
 
34 
 
 - 
 
35 
	# Try to climb the box
 - 
 
36 
	if Climb(State, Climb.UP).meetsPreconditions():
 - 
 
37 
		if not Action(State).monkeyOnBox ():
 - 
 
38 
			return (CLIMB, Climb.UP)
 117 
	return chose_move
39 
 
 - 
 
40 
	# Try to climb down from the box
 - 
 
41 
	if Climb(State, Climb.DOWN).meetsPreconditions():
 - 
 
42 
		if Action(State).monkeyOnBox ():
 - 
 
43 
			return (CLIMB, Climb.DOWN)
 - 
 
44 
 
 118 
 
45 
def isValidInitialState (State):
 119 
def isValidInitialState (State):
46 
	monkeyPos = Action(State).findMonkeyPosition()
 120 
	monkeyPos = Action(State).findMonkeyPosition()
47 
	boxPos = Action(State).findBoxPosition()
 121 
	boxPos = Action(State).findBoxPosition()
48 
	onBox = Action(State).monkeyOnBox()
 122 
	onBox = Action(State).monkeyOnBox()
Line 55... Line 129...
55 
def enter_initial_state ():
 129 
def enter_initial_state ():
56 
	State = set([])
 130 
	State = set([])
57 
 
 131 
 
58 
	# Get Monkey Position
 132 
	# Get Monkey Position
59 
	m = Menu(autorun=True, name='Enter Monkey Position')
 133 
	m = Menu(autorun=True, name='Enter Monkey Position')
60 
	m.add_entry ('1', 'Window', lambda: Walk.WINDOW)
 134 
	m.add_entry ('1', 'Window', lambda: WINDOW)
61 
	m.add_entry ('2', 'Door', lambda: Walk.DOOR)
 135 
	m.add_entry ('2', 'Door', lambda: DOOR)
62 
	m.add_entry ('3', 'Middle', lambda: Walk.MIDDLE)
 136 
	m.add_entry ('3', 'Middle', lambda: MIDDLE)
63 
	m.add_entry ('Q', 'Quit', sys.exit)
 137 
	m.add_entry ('Q', 'Quit', sys.exit)
64 
 
 138 
 
65 
	pos = m.run_menu()[1]
 139 
	pos = m.run_menu()[1]
66 
	State.add ('At(Monkey,%s)' % pos)
 140 
	State.add ('At(Monkey,%s)' % pos)
67 
 
 141 
 
68 
	# Get Box Position
 142 
	# Get Box Position
69 
	m = Menu(autorun=True, name='Enter Box Position')
 143 
	m = Menu(autorun=True, name='Enter Box Position')
70 
	m.add_entry ('1', 'Window', lambda: Push.WINDOW)
 144 
	m.add_entry ('1', 'Window', lambda: WINDOW)
71 
	m.add_entry ('2', 'Door', lambda: Push.DOOR)
 145 
	m.add_entry ('2', 'Door', lambda: DOOR)
72 
	m.add_entry ('3', 'Middle', lambda: Push.MIDDLE)
 146 
	m.add_entry ('3', 'Middle', lambda: MIDDLE)
73 
	m.add_entry ('Q', 'Quit', sys.exit)
 147 
	m.add_entry ('Q', 'Quit', sys.exit)
74 
 
 148 
 
75 
	pos = m.run_menu()[1]
 149 
	pos = m.run_menu()[1]
76 
	State.add ('At(Box,%s)' % pos)
 150 
	State.add ('At(Box,%s)' % pos)
77 
 
 151 
 
Line 104... Line 178...
104 
 
 178 
 
105 
	print 'Plan:'
 179 
	print 'Plan:'
106 
	while not Action(State).isGoal():
 180 
	while not Action(State).isGoal():
107 
 
 181 
 
108 
		next = findNextMove (State)
 182 
		next = findNextMove (State)
109 
		action = next[0]
 183 
		action = next.action
- 
 
 184 
		arg1 = next.arg1
- 
 
 185 
		arg2 = next.arg2
110 
 
 186 
 
111 
		if action == WALK:
 187 
		if action == WALK:
112 
			print '%s from %s to %s' % next
 188 
			print '%s from %s to %s' % (action, arg1, arg2)
113 
			State = Walk(State, next[1], next[2]).takeAction()
 189 
			State = Walk(State, arg1, arg2).takeAction()
114 
		elif action == PUSH:
 190 
		elif action == PUSH:
115 
			print '%s Box from %s to %s' % next
 191 
			print '%s Box from %s to %s' % (action, arg1, arg2)
116 
			State = Push(State, next[1], next[2]).takeAction()
 192 
			State = Push(State, arg1, arg2).takeAction ()
117 
		elif action == CLIMB:
 193 
		elif action == CLIMB:
118 
			print '%s %s' % next
 194 
			print '%s %s' % (action, arg1)
119 
			State = Climb(State, next[1]).takeAction()
 195 
			State = Climb(State, arg1).takeAction()
120 
		elif action == GRAB:
 196 
		elif action == GRAB:
121 
			print '%s Banana' % next
 197 
			print '%s Banana' % action
122 
			State = Grab(State).takeAction()
 198 
			State = Grab(State).takeAction()
123 
		else:
 199 
		else:
124 
			print 'BAD STATE'
 200 
			print 'BAD STATE'
125 
			return
 201 
			return
126 
 
 202