Lately, I have been working on a video-game called DobadoBots. This game is about programming a robot’s articial intelligence to solve mazes.

The robot is materialized by a white triangle. The goal is to reach the objective (orange square) while avoiding several obstacles.

Instead of using a standard embeddable script language such as LUA, I went the custom way and wrote my own language.

Specifying the Language

I had only one idea in mind when started to specify this language: keep it as simple as possible. I started wondering, what do we really need to program this kind of artificial intelligence? What is the smallest set of operations the language needs to support?

I decided to specify the language as a decision tree. Each condition being a node, each robot movement being a leaf. No loops, no variable assignments, no functions. We do not want to embarrass the player with unnecessary concepts.

Basically, the language structure looks like this.

  IF [sensor]
       [action or nested condition]
  ELSE
       [action or nested condition]

The sensor statement is a boolean expression. It is evaluated in order to decide which subtree should be next executed.

Every sensor evaluation results either in an action token, which gives the robot a movement instruction, or in a nested condition, which gives us a way to refine the behaviour.

In the end, a robot’s AI will be defined by something like this:

IF laserDistance > 20
  moveForward
ELSE
  IF laserScan = objective
    moveForward
  ELSE
   IF laserScan = obstacle
       turnLeft
   ELSE faceObjectives

Sensors and Actions

We then needed to determine the minimal operations subset required to control the robot though the maze.

We finally end up with the following sensors list:

• laserDistance: checks the distance between the robot and the nearest object.
• laserScan: checks what kind of object is facing the robot. It can be an obstacle, a wall, another robot or the objective.
• objectiveDistance: checks the distance between the robot and the objective.

ObjectiveDistance was not necessary but makes solutions less confusing in some cases.

Regarding the actions, we ended up keeping 4 of them:

• moveForward: the robot moves one step ahead.
• turnLeft: the robot rotates counterclockwise.
• turnRight: the robot rotates clockwise.
• faceObjective: the robot faces the objective.

Implementing the Abstract Syntax Tree (AST)

Now we specified the language, we still need to implement its AST. We will use the Haskell programming language for this part.

We start specifying data structures for both actions and sensors tokens. This problem is quite straightforward, we just need to use Haskell’s algebraic data types.

data ActionToken = MoveForward
                 | TurnLeft
                 | TurnRight
                 | FaceObjective
                 | ChangeObjective
                 deriving (Show, Eq)

data SensorToken = LaserDistance
                 | LaserScan
                 | ObjectiveDistance
                 deriving (Show, Eq)

We then need to specify the logic expression data type. We need to keep in mind that comparing a laser distance with an integer is quite different from comparing a laserScan with a Collider.

In order to simplify both the parser and the interpreter, we restricted as much as possible the type definition for both of these kind of logic expression.

data LogicExpr = CmpCollider SensorToken Collider
               | CmpLogicInt (CmpInteger SensorToken)
               deriving (Show, Eq)

data CmpInteger a = Sup a Integer
                  | Inf a Integer
                  | Eq a Integer
                 deriving (Show, Eq)

data Collider = Obstacle
              | Objective
              | Wall
              | Robot
              deriving (Show, Eq)

Now we have implemented all the basic data types, we just need to compose them in order to build the actual tree.

To do so, we use a recursive data type.

data Cond = Token ActionToken
          | Cond { sensor    :: LogicExpr
                 , ifValid   :: Cond
                 , ifInvalid :: Cond
                 } deriving (Show, Eq)

We now successfully implemented our AST, Cond being its root.

In next article, we will dive in the associated parser’s implementation.