Translations/Project X

Konstantin Dronov on AI in Project X, excerpt from Inferno #2 [1]

Some words about AI

Artificial intelligence is an important part of a game, be it a typical action game or nerdy strategy, and its design haven't changed highly since 80's. The cause is that it's very hard to do. For example, make a monster turn a corner, that seems simple. But what's a corner? How to describe it? How to describe an enemy for a monster? Regular way that is called "artificial intelligence" will take too much time to do. You should write an enormous subroutine in which you understand all the actions. I can't even imagine everything needed for this, because humans evolutioned for tens thousands, maybe hundreds thousands years. How you can repeat this in a few days? However, the nature itself suggests the way - from simple to complex. An alternative to artificial intelligence is developed now actively - artificial life (AL). What life, you will ask? Here it is, its approach:

1. Instead of writing a cumbersome routine, we write several little routines, each of them to accomplish just one task. Enumerate them, for example:

• 0 - NOP, no command
• 1 - MOVE, move forward
• 2 - STEP LEFT, one step to the left
• 3 - STEP RIGHT, one step to the right
• 4 - TURN LEFT, turn left 90 degrees
• 5 - TURN RIGHT, turn right 90 degrees

etc.

2. Write a routine, an interpreter, that will interpret codes under a pointer and move the pointer in memory. Interpreting a code is calling a subroutine for that specific code. The routine must contain variables to exchange data between subroutines. This is a programming language, in fact.

3. That's all !!!

Isn't this simple? To program the behaviour of monsters in PROJECT X, I used just 15 commands and one register (one byte of memory!). The monsters are simple there, of course, although even these 15 commands are enough for modelling a very complex behaviour.

Here are the commands used:

• 00 RANGE - check if the player is in sight. Returns 0 (yes) or 1 (no). This command was used in the game to check if the monster is on screen.
• 01 MOVE - move one step forward.
• 02 TURN LEFT - turn left by certain angle
• 03 TURN RIGHT - turn right
• 04 SEARCH - check if the way ahead is blocked. Returns 0 (yes) or 1 (no).
• 05 SEARCH LEFT - the same for the way to the left
• 06 SEARCH RIGHT - the same for the way to the right
• 07 FIRE - shoot (not used in the game)
• 08 HALT - tells the interpreter that he must interrupt and return to the main program.
• 09 VERIFY L - check if the player is to the left (or else to the right) of the monster. Returns 0 (yes) or 1 (no).
• 10 VERIFY F - the same but ahead or behind
• 11 TYPE - checks if the player and the monster are on one line that is along the player's movement (?). Returns 0 (ahead) or 1 (behind).
• 12 JUMPIF 0 adress - checks the register. If it is 0, jump to adress.
• 13 JUMPIF 1 adress - the same, but 1.
• 14 JUMP adress - unconditional jump.

That's all!!!

An example of a program written using this code:

   the adress
┌──────────────────
│
01 SEARCH
02 JUMPIF 1 4
03 TURN LEFT
04 VERIFY L
05 JUMPIF 0 9
06 VERIFY F
07 JUMPIF 0 15
08 JUMP 19
09 TYPE
10 JUMPIF 0 13
11 TURN RIGHT
12 JUMP 19
13 TURN LEFT
14 JUMP 1
15 TYPE
16 JUMPIF 0 19
17 TURN LEFT
18 TURN LEFT
19 MOVE
20 HALT
21 JUMP 1

This is just a test program practically unusable because it returns once, by HALT at line 20. To work in normal conditions you should use HALT before every JUMP or JUMPIF.

So, think of commands you need and add them to the list. You can even write self-learning monsters, this only needs writing new commands by the monster's program.