Caspar Ant

俺也汇编一下：EMU8086

2008年6月9日 | 分类: Programming | 标签: asm, bug, deadcorner, emu8086

对不住各位看官了……这个EMU8086模拟器是Windows下的，还是破解的……我只是为了完成计组老师的作业而已。只是有道题比较有意思，我深深地想了好久，发现一些问题，估计老师不会认真改我的作业，我把它发上来发泄发泄，嗯。

话说EMU8086预先弄了几个PORT，其中PORT9就是实现了一个机器人的东东。具体描述如下：在一个9X6的地图内，有墙、灯、机器人三种东西。机器人碰到墙和灯都过不去，但是碰到灯的时候会自动改变灯的状态，也就是关灯或者开灯。
现在在地图上画一个地图，机器人使用给定的算法会产生死角，问怎么样消除死角。

话说原来给定的代码太弱了，一眼看出破绽：机器人碰墙只能单纯地朝一个方向转，那么碰到开了一口的闭合空间时，一旦进去就出不来了(如图)，必然得改进。改进的方法有两个，一个是把行走改成随机方向，那么机器人再怎么囧最后也能走出去，可是老师不提倡随机，那么只好接着改了。

在不使用随机走法的情况下，使用回溯法是更好的解决方案。回溯法用在走迷宫的时候比较实用，遵循“右手法则”地回溯搜索路径，最后走出死角。

然而一般“右手法则”下的回溯会产生另一个问题，就是在空白面积比较大的时候，会出现“绕某点打转”的现象，如下图：

这在机器人行走中是致命的。

我原计划采用的是“撒米标记法”解决此问题。但是由于对数组的使用不熟悉，没有解决这个问题。(关键在这，- -b)在这里仅写出思路：“撒米标记法”。使用一个数组来记录当前点是否已经被车子移到过，如果当前点在之前已经在同个方向上被访问过，则机器人不再继续前进，而是直接选择一个其他方向，继续按照右手法则行走。

第二个死角的产生比较麻烦，是软件本身产生的“副作用”。此“副作用”在如下情况下执行关灯/开灯操作时出现：
当程序员手动执行机器人转向操作时，软件会记录这一次转向。一次左转和一次右转会抵消。不连续的两次转向不相关。所以转向结束后，会有一个“净转向”值。此时机器人如果正好面对一盏灯，在执行关灯/开灯操作之后，机器人会自动逆着“净转向”的方向转动相应次数。例如下图：

机器人在两次右转之后，面对的是灯。在关完灯的同时，机器人会自动向左转两次，恢复到原来状态。
了解了转向的副作用，便可知下图会产生一个死角：

为了解决这个死角，可以采用“抵消副作用”法。对于以上右手法则，可以很容易获得其状态机：(其实这个状态机挺扯的，原谅我自动机课没学好T_T)

圈内数字表示当前状态下的净转向值。

具体解法可看附件的代码。

#MAKE_BIN#
#CS = 500#
#DS = 500#
#SS = 500#    ; stack is set
#SP = FFFF#   ; automatically.
#IP = 0#
R_PORT 		EQU 9
 
;BL	255: turned left
;	0: turned none
;	1: turned right
 
;BH	0: initial state
;	1: try right
;	2: try ahead
;	3: try left
;	4: try back
;	when it moves ahead, BH should be 0
 
eternal_loop:
	CALL	WAIT_ROBOT
	MOV	AL, 4
	OUT	R_PORT, AL
	CMP	BH, 0		; judge if initial state
	JE	first_step	; first_step
	CALL	WAIT_EXAM	; else judge how to move
	IN	AL, R_PORT + 1
	CMP	AL, 0		; nothing?
	JE	forward		; so, forward
	CMP	AL, 255 	; wall?
	JE	meet_wall	; so, turn right
	CMP	AL, 7		; switched-on lamp?
	JE	switch_off	; so, switch it off and do something
	CMP	AL, 8		; switched-off lamp?
	JE	switch_on	; so, switch it on and do something
 
first_step:
	ADD	BH, 1
	MOV	BL, 1
	JMP	turn_right
 
meet_wall:
	ADD	BH, 1
	SUB	BL, 1
	JMP	turn_left
 
meet_lamp:
	ADD	BH, 1
	CMP	BL, 255
	JE	turn_around
	SUB	BL, 1
	CMP	BL, 0
	JE	eternal_loop
	JMP	turn_left
 
turn_left:
	CALL	WAIT_ROBOT	; turn left operation
	MOV	AL, 2
	OUT	R_PORT, AL
	JMP	eternal_loop	; go again
 
forward:
	MOV	BH, 0		; when forward, back to initial state
	MOV	BL, 0		; no turn mark
	CALL	WAIT_ROBOT	; go ahead
	MOV	AL, 1
	OUT	R_PORT, AL
	JMP	eternal_loop	; go again!
 
switch_off:			
	CALL	WAIT_ROBOT	; turn off the lamp
	MOV	AL, 6
	OUT	R_PORT, AL
 
	JMP	meet_lamp
 
switch_on:
	CALL	WAIT_ROBOT	; turn on the lamp
	MOV	AL, 5
	OUT	R_PORT, AL
 
	JMP	meet_lamp
 
turn_right:
	CALL	WAIT_ROBOT	; turn right operation
	MOV	AL, 3
	OUT	R_PORT, AL
	JMP	eternal_loop	; go again
 
turn_around:
	CALL	WAIT_ROBOT	; turn right twice to turn around
	MOV	AL, 3
	OUT	R_PORT, AL
 
	CALL	WAIT_ROBOT
	MOV	AL, 3
	OUT	R_PORT, AL
 
	JMP	eternal_loop	; go again
 
WAIT_ROBOT	PROC
busy:
	IN	AL, R_PORT+2
	TEST	AL, 00000010b
	JNZ	busy ; busy, so wait.
	RET
WAIT_ROBOT	ENDP
 
WAIT_EXAM	PROC
busy2:
	IN	AL, R_PORT+2
	TEST	AL, 00000001b
	JZ	busy2 ; no new data, so wait.
	RET    
WAIT_EXAM	ENDP