Structuring enemy behavior

Discuss technical or other issues relating to programming the Nintendo Entertainment System, Famicom, or compatible systems. See the NESdev wiki for more information.

Moderator: Moderators

Post Reply
Zorg
Posts: 6
Joined: Sun Dec 19, 2021 3:22 am

Structuring enemy behavior

Post by Zorg »

Hello,

I have been asking myself: How is the enemy behavior in games typically programmed?

Games like Mega Man or Contra III have a lot of different enemies who all act differently. In what way is this done?

Did they program one function for each enemy?
And this function might call some generic functions, like gravity calculation for a jump, or collision detection with the player's projectiles, but overall each enemy function is individually implemented.

Or did they program one function that is for all enemies?
Like a script interpreter. It implements everything that any enemy could ever do (walking, jumping, flying, being invincible, spawning a new object...).
And the enemies are assigned a bunch of arrays that describe their behavior:
Byte 1 = next pattern.
If byte 1 = walking, then byte 2 = length of pixels min, byte 3 = length of pixels max.
If byte 1 = jumping, then byte 2 = high of jumping.


If each enemy is programmed individually, with only the most basic stuff shared (like collision detection or gravity), this would be a huge number of functions. The first Mega Man has more than 20 regular enemies alone, plus the bosses. Do these games really have ProcessSniperJoe, ProcessScrewBomber, ProcessFireCutMan functions?


But if there's a generic function with script interpretation, the question is whether this can even be generelized into a single function.
A Wizzrobe and an Octorok from Legend of Zelda might be able to share the same basic functions. You need the patterns "walking" (with direction and variable speed), "spawning a projectile", "flickering" and "teleporting". And then you can control those two enemy types with the same function by giving some pattern arrays to each character. And the teleport can even be reused for Ganon.

But I don't know how in Contra III a regular foot soldier and that wall-walking thing from level 3, or the giant turtle boss could ever be controlled by the same function with reusable patterns.


What is typically the go-to way for NES games with a non-trivial number of enemies?
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Structuring enemy behavior

Post by Dwedit »

MC Kids programmer Gregg Tavares had some elaborate system where they used flags to determine whether an object should have physics on the X or Y axis, and so on.
He said that instead, objects should have been calling the functions for what they needed, rather than the object system itself doing that.

A script interpreter isn't necessary and will just slow things down. The enemies should just be written in ASM code.

---

One thing that can help is a "yield" system, where you can put in code to break out of an enemy subroutine, and resume in that position the next time it is called.
This can be done either with a real code address (simpler, but can crash if the value is out of range), or with a jump table (safer if you limit the range with a mask first, then pad the table with dummy destinations)

(more to come)
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
tokumaru
Posts: 12427
Joined: Sat Feb 12, 2005 9:43 pm
Location: Rio de Janeiro - Brazil

Re: Structuring enemy behavior

Post by tokumaru »

What I personally like to do, not only for enemies, but for all objects, even player characters, is give each one a set of handler subroutines, which the engine calls at specific moments to make them function and interact with each other.

Each object has at least one initialization handler, which takes care of organizing the object's memory and getting it ready to function. Since objects can come to life in different ways (e.g. created from nothing, loaded from a list or transformed from another object), it's possible for a single object to have multiple initialization handlers. The proper one will be called by the engine or by another object as needed.

Then there's the logic handler, which gets called once per frame. This is where the behavior for each object is defined, and usually consists of several calls to functions shared between all objects for things like walking, colliding, hurting players, and so on. In most cases, handling all behaviors of an object in a single function gets very hectic, so I usually break up the logic into multiple states, and give each state its own logic subroutine. Each of these handlers first tests for the need to transition to other states (e.g. in the "falling" state, a collision with the floor will cause a transition to the "standing" state), and then handles the logic.

Next is the graphics handler, which's also called once per frame and basically takes care of drawing the object. Most objects are drawn with sprites, so there's a generic function that can be used by all objects that draws a metasprite according to the frame of animation the object is currently using. This function also takes care of making objects flicker when they're hurt, by using their invulnerability countdown values to alternate between drawing or not drawing the objects. Objects can also be drawn using background tiles, in which case the graphics handler may need to request background updates.

The last type of handler subroutine I use is the interaction handler. It receives messages from other objects that are initiating interactions (e.g. a bullet notifying an enemy that it was hit). The interaction handler is responsible for appropriately reacting to the message, assuming that the message is relevant to the object at all (messages can be ignored).

So yeah, I basically have several logic handlers for each object, one for each state that objects can be in, and they make use of many shared subroutines in order to execute common tasks, but can also contain code that's exclusively used by an specific object or state.

This is very flexible, but can also consume more ROM space than a simpler system where you can toggle behaviors on and off for each object using flags and whatnot. What will work best for you depends on what kind of game you're making and what resources you can afford to spend on this.
coto
Posts: 102
Joined: Wed Mar 06, 2019 6:00 pm
Location: Chile

Re: Structuring enemy behavior

Post by coto »

as systems gets more sophisticated there's actually decision-making algorithms (such as in billiard where things like trajectory, collision is calculated from the main object the player controls (cue ball), and overwrites its current status by performing further algorithms surrounding whatever object the main object the player controls).

But since the NES CPU is slow, you could hardcode behaviour per enemy, so it performs preset actions through a tree-based solution for handling ticks per second, multiple entities and actions made by the object itself affecting the rest. The idea is that you spawn entities regardless if it's enemy or the main object character.
Zorg
Posts: 6
Joined: Sun Dec 19, 2021 3:22 am

Re: Structuring enemy behavior

Post by Zorg »

Dwedit wrote: Sun Dec 19, 2021 9:51 am MC Kids programmer Gregg Tavares had some elaborate system where they used flags to determine whether an object should have physics on the X or Y axis, and so on.
He said that instead, objects should have been calling the functions for what they needed, rather than the object system itself doing that.
I assume this means the ProcessSoldier function calls the Walk, the Shoot and the Jump function, but processes the conditions for when to call each function itself, right?
Dwedit wrote: Sun Dec 19, 2021 9:51 amOne thing that can help is a "yield" system, where you can put in code to break out of an enemy subroutine, and resume in that position the next time it is called.
I'm not sure I understood this right. Do you mean things like function pointers?
tokumaru wrote: Sun Dec 19, 2021 4:43 pm Then there's the logic handler, which gets called once per frame. This is where the behavior for each object is defined, and usually consists of several calls to functions shared between all objects for things like walking, colliding, hurting players, and so on. In most cases, handling all behaviors of an object in a single function gets very hectic, so I usually break up the logic into multiple states, and give each state its own logic subroutine. Each of these handlers first tests for the need to transition to other states (e.g. in the "falling" state, a collision with the floor will cause a transition to the "standing" state), and then handles the logic.
Shared functions make sense of course. A jump arc is probably the same logic for each character that can jump. And a regular horizontal movement/walking logic only needs the pixels per frame, the direction and when to switch the animation frame.

But do you still have separate main processing functions for each enemy? What if the game has 30-50 different enemy types? Does this make 30-50 functions who decide when to call the more generic functions?
(Let's only talk about the logic handler here. Initialization and graphics output are secondary to my concern.)


That's why I was thinking of data arrays. For example:
Every enemy has up to four regular pattern arrays that are chosen randomly whenever an old pattern has come to its end.
Plus an array for "if close to the player".
One array for "what to do after getting hit".
And one array for "what to do if low on energy".

The arrays for a boss could then look like follows:
Array 1: Move right, 16-120 pixels. Move left, 16-120 pixels. Shoot 3 times. Jump and stomp.
Array 2: Jump towards player for 5-7 seconds.
Array 3: Fly to x/y positon 128/64. Repeat 3-5 times: { Shoot down left. Shoot straight down. Shoot down right. }
Array 4: Do array 1.
Array "close to the player": Unused.
Array "after getting hit": Do array 3.
Array "low on energy": Activate invincibility shield. Run towards player for 5-7 seconds while shooting. Deactivate shield. Wait 2 seconds.

This way you only have one main function for the enemy movement. The function takes the corresponding array of your enemy type, reads the current value and lets the character act accordingly.

But I fear that while this might work in a game like NES Zelda where the game physics are pretty limited, it would pose an issue for a game like Contra III where you have stuff like robotic legs that climb up a wall, and their center weapon sporadically shoots at you. Because all those enemies behave so differently from each other that the movement logic of one enemy can barely be reused for another. Even Link's Awakening could make problems here: How could the first boss, Moldorm, ever be done with those kind of reusable patterns?


Is there any information on how games like Mega Man, Contra or Ninja Gaiden structured their enemy behavior? Or stuff like Link's Awakening?
User avatar
never-obsolete
Posts: 411
Joined: Wed Sep 07, 2005 9:55 am
Location: Phoenix, AZ
Contact:

Re: Structuring enemy behavior

Post by never-obsolete »

Ninja Gaiden enemies use a state machine that calls shared functions.
. That's just like, your opinion, man .
Zorg
Posts: 6
Joined: Sun Dec 19, 2021 3:22 am

Re: Structuring enemy behavior

Post by Zorg »

never-obsolete wrote: Tue Dec 21, 2021 4:33 am Ninja Gaiden enemies use a state machine that calls shared functions.
Is there a place on the internet where I can read more on this?
User avatar
Dwedit
Posts: 4924
Joined: Fri Nov 19, 2004 7:35 pm
Contact:

Re: Structuring enemy behavior

Post by Dwedit »

A "Yield" system is basically equivalent to a state machine.

Yield is like returning from the function, but you are saving your prior address. The next time you enter the function, you immediately jump there.

Saving the prior address does not necessarily mean literally saving a 16-bit code address, it could just be encoded as a single byte.

---

Psuedocode example of an object handler that uses YIELD. Not a great example, as it doesn't do any collision checking or anything, but just to demonstrate what YIELD means.


MyObjectHandler:

movingLeft:
HitTest(this.x - 1, this.y + 15)
if not a wall
- this.x -= 1
- YIELD
- goto movingLeft
else
- for this.i = 0 to 100
- - YIELD
- next
- goto movingRight

movingRight:
HitTest(this.x + 17, this.y + 15)
if not a wall
- this.x += 1
- YIELD
- goto movingRight
else
- for this.var1 = 0 to 100
- - YIELD
- next
- goto movingLeft

This guy moves left and right, and stops for 100 frames when it hits a wall.

---

Example of how to implement YIELD:

Beginning of the handler function: (psuedo 6502 ASM, register X is your object number)

MyObjectHandler:

LDA objectState,X
CMP #MyObjectStateLimit
BCS MyObjectState0
TAY
LDA objectStateLowBytes,Y
STA myIndirectJump + 0
LDA objectStateHighBytes,Y
STA myIndirectJump + 1
JMP (myIndirectJump)

Remaining code of toy example (psuedo 6502 ASM)

MyObjectState0:
movingLeft:
;HitTest(this.x - 1, this.y + 15)
LDA objectXCoordinate,X
SEC
SBC #1
STA hitTestArgX
LDA objectYCoordinate,X
CLC
ADC #15
STA hitTestArgY
JSR HitTest
;if not a wall
BNE movingLeftHitWall
movingLeftNotWall:
;this.x -= 1
DEC objectXCoordinate,X
;YIELD
LDA #1
STA objectState,X
RTS
MyObjectState1:
JMP movingLeft
movingLeftHitWall:
;else
;for this.var1 = 0 to 100
LDA #0
STA objectVar1,X
myForLoop1:
;YIELD
LDA #2
STA objectState,X
RTS
MyObjectState2:
;next
INC objectVar1,X
LDA #100
CMP objectVar1,X
BNE myForLoop1
;goto movingRight
JMP movingRight

I'll leave out the second half of this example (moving right)...
Then elsewhere you need to define these:

MyObjectStateLimit = 5 (the total number of states for the object)
objectStateLowBytes:
.db <MyObjectState0
.db <MyObjectState1
.db <MyObjectState2
.db <MyObjectState3
.db <MyObjectState4
objectStateHighBytes:
.db >MyObjectState0
.db >MyObjectState1
.db >MyObjectState2
.db >MyObjectState3
.db >MyObjectState4

But the idea here is that YIELD becomes this:
LDA #N
STA objectState,X
RTS
MyObjectStateN:

So you can resume your code the next time the handler is called.
Here come the fortune cookies! Here come the fortune cookies! They're wearing paper hats!
User avatar
never-obsolete
Posts: 411
Joined: Wed Sep 07, 2005 9:55 am
Location: Phoenix, AZ
Contact:

Re: Structuring enemy behavior

Post by never-obsolete »

Zorg wrote: Tue Dec 21, 2021 4:39 am Is there a place on the internet where I can read more on this?
About Ninja Gaiden specifically? Probably not. I re'd parts of it a while back for a rom hacking project, and have since lost the notes with the AI code commented. I do have an older copy with much less comments if you are interested.

If you want to read about state machines and AI in a more general sense, there's this that goes over the idea in a HLL.
. That's just like, your opinion, man .
User avatar
dougeff
Posts: 3079
Joined: Fri May 08, 2015 7:17 pm

Re: Structuring enemy behavior

Post by dougeff »

When I looked at the source code of Galaga, it didn't work at all like I thought. Every enemy object is assigned a function pointer, and that function pointer was changed every time they needed a swarm to come down, and changed back when it needed to hover.

There are a series of flags and decision trees to decide what to do next.

The functions themselves were mostly of the "add a little to x speed or to y speed" variety.
nesdoug.com -- blog/tutorial on programming for the NES
Post Reply