俺也汇编一下: 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

写完了。反正问题就在，会绕圈……

等考完事再来看。估计也就是几个 register 的问题。

最后附上一个可启动的小东东：打字训练——所谓的“操作系统”作业，Orz。专门为某打字不按指法的家伙准备的。

谢帆说还要把 Loader 和 Kernel 分开写，我继续 Orz 了，这个小东西填 MBR 的牙缝都不够呢，还分开……

Ant-Veil

Caspar Blog

俺也汇编一下: EMU8086

Comments