Issue with robot exploration in Assembly (emu8086)

2k Views Asked by At

I'm working on an assembly program using the emu8086. The program uses the built-in robot device to emulate a virtual robot on a simulated 6x9 map. The map will contain unknown amounts of walls and lamps(lit/unlit) in which the robot is to traverse through the map and located all the unlit lamps and light them. The robot itself, can only take data from adjacent squares in which the robot is facing, and also can rotate in only 90 degree turns. The project suggests that the upper-left hand corner will be the origin of the coordinate system (0,0).

http://www.emu8086.com/assembler_tutorial/robot.gif

I understand how to interface the robot with my code to move and examine data, however, I'm not sure of how to efficiently travel through and check for all lamps on the entire map, without falling into an infinite loop or dead end.

I've read about using several search algorithm such as the breadth-first and depth-first search algorithms, but I am unsure of how to implement such concepts in assembly (as most of the example/psuedocode is written in c++/c#/etc).

I'm not asking for any specific coding, but insight on how to implement those search functions. Since the problem mentions an origin for a coordinate system, I made a 2d array in which to take values for objects at certain coordinates. Not sure how important the array is for the problem, but any help would be appreciated.

1

There are 1 best solutions below

1
On
  1. Place tiles you discover in an unvisitedNodes list (your starting tile for now).
  2. Grab a tile from unvisitedNodes and examine it.
  3. After examination, move a tile from unvisitedNodes to a visitedNodes list.
  4. When examining a tile, check if each of it's neighbouring tiles is present in one of your lists.
  5. If not, the neighbour in question is a new finding; append it to your unvisitedNodes list.
  6. Repeat from point 2 until unvisitedNodes becomes empty

For this, I'd recommend to create a nice little collection (list/queue/set) library to start with.