NPC States

10-10-2011

I am going to try and post a basic topic of interest each week.  While my topics will generally be geared toward application for gaming, the topics should be of interest to programmers in general.  I will use psuedo-code in most cases, but will also try to include Basic code for any specifics.  I normally code in Purebasic or DarkBasic but also do some coding in C/C++, PHP and Perl (of which I hate C/C++ the most).

Stateful-NPC

The first topic I want to address is "Stateful"-NPCs.  A "Stateful"-NPC is a computer controlled actor that can recognize different "States" of the game.  For example, each NPC monster might have a "State" of Hunger.  If they are hungry ("Hunger state = 1"), they may be allowed to wonder further than normal from their spawn point.  If they are not hungry ("Hunger state = 0") then they stay closer to their spawn point, and/or return.  If an NPC monster has a Hunger state = "1" and there is a nearby NPC Mob that is smaller then it can attack and eat.  This would allow for a wondering adventurer to hear/see "natural" activities.

For example suppose we want to define the following states of an NPC:

  • Does the NPC currently have a quest to hand out?
  • Does the NPC have a magical item for reward?
  • Does the NPC have a normal item for reward?
  • Does the NPC have a monetary reward?

We can set this up in several ways

[+] Code Snippet

npc_quest=.t.
npc_magic_reward=.t.
npc_normal_reward=.t.
npc_money_reward=.t.
 
Suppose that the adventurer has completed his quest and wants to get all of his rewards.  In order to do this we would have to check each and everyone fo the reward states.  Not difficult but if we had more than the above three states could become quite cumbersome. For example suppose we have the following states for a woodland monster;
 
  • Is monster awake?
  • Is monster hungry?
  • Is monster enraged?
  • Is monster poisoned?
  • Is monster trapped?
  • Is monster crippled?
  • Is monster confused?
  • Is monster scared?

Would you want to run code that checks all eight (8) states on every single monster in a scene?

An easier way might be to assign numerical values to each state so that we can just check the value of the monster state against another value.  Using the above example what if we had this code:

[+] Code Snippet

#mob_awake=1        ; note # means Constant in Purebasic
#mob_hungry=2
#mob_enrage=3
#mob_poisoned=4
#mob_trapped=5
#mob_crippled=6
#mob_confused=7
#mob_scared=8
 
Now if we do a check in our code like this
 

[+] Code Snippet

If current_monster_state=6
 
Unfortuantely, the above introduces a problem. Does the current_monster_state = 6 mean we have a monster that is #mob_crippled (6), or do we have a monster that is #mob_poisoned (4) and #mob_hungry (2) (4+2=6)?
 
 So is there another, easier way that can give us what we need to know exactly?

The answer is of course YES, (otherwise I would have nothing else to write).

In order to understand how to implement something like this that can be easy and specific you really need to understand the binary numbering system and the application of "Bitwise Operators".  So for the rest of todays discussion we will make sure everyone is on the same page by starting off with an introduction to Binary.

The Basics of Binary

"0" or "1" that is it.  Leasson over. NOT! 

Why "0" Why "1"

Well a computer is an electrical system that can only register if the power flow is "Off" ("0") or "On" ("1"). Each "register" of memory is therefore either charged or not charged.  (By the way, as a side note, take a look at the power button on most electronic items, you will notice it is a line inside of a circle, a "1" inside of a "0" which is "On/Off" shorthand that has evolved due to computers).

A computer can check the state of memory locations or "registers". It will determine if it is charged "1" or not charged "0".  individually these numbers mean nothing, but standards have evolved to bring meaning to these two simple states.  Depending on the "place" of the "0" or "1" determines how they are converted to different representations whether that is a decimal number, hexadecimal or even Letters. For now, we are going to wory with conversion between Binary and Decimal.

In computers we work with Bit's which are individual "0" and "1". 

The next step above a Bit is a Nibble which is 4 bytes together represented in groups of 4 such as "0000" or "0010". 

The step above a Nibble is a Byte. Bytes are 2 Nibbles or 8 Bits and typically represented in the formate of  two sets of Nibbles together such as "0000 0000" (notice the spacing to make it easier to read). 

A Word is 2 Bytes, 4 Nibbles or 16 Bits and is represented as "0000 0000 0000 0000" . 

There are also Double Words (32 Bits, 4 Bytes, 2 Words) and Long (also known as Long Integer or Long Int, which is 64 bits, 8 Bytes, 4 Words).

             (Did you notice the sub-contextual references to food? No wonder programmers are always snacking).

     (O.K. back on topic, had to grab a quick piece of Pizza).

Binary->Decimal

In today's society we think in Decimal numbers and not Binary numbers. Therefore, how do we convert between the two different systems? The basic mathematical formula for converting Binary to Decimal is as follows:

(pn x 2^8) + (pn x 2^7) + (pn x 2^6) + (pn x 2^5) + (pn x 2^4)+ (pn x 2^3) + + (pn x 2^2)+ (pn x 2^1)+ (pn x 2^0)

where pn = Positional Number, either the "0" or "1" in that position.  Let us look at an example:

to convert 0101 0010 we would have the following formula

0 1 0 1 0 0 1 0
(0 x 2^7) (1 x 2^6)  (0 x 2^5) (1 x 2^4) (0 x 2^3) (0 x 2^2) (1 x 2^1) (0 x 2^0)
0x128 1x64 0x32 1x16 0x8 0x4 1x2 0x1
0 64 0 16 0 0 2 0
 
adding the bottom row of numbers together 0+64+0+16+0+0+2+0=64+16+2 = 82
 
Remember that any number raised to the zero'th power = 1
 
Here is a quick reference table for the numbers 0 to 17
 
Decimal Binary Decimal Binary
0 0000 0000 9 0000 1001
1 0000 0001 10 0000 1010
2 0000 0010 11 0000 1011
3 0000 0011 12 0000 1100
4 0000 0100 13 0000 1101
5 0000 0101 14 0000 1110
6 0000 0110 15 0000 1111
7 0000 0111 16 0001 0000
8 0000 1000 17 0001 0001

Here are a few more numbers

Decimal Binary
32 0010 0000
64 0100 0000
128 1000 0000

 

Setting States

So how do we use this for a game?  It is really simple. Going back to our first example the following states are needed to be tracked for an NPC that hands out quests.

  • Does the NPC currently have a quest to hand out?
  • Does the NPC have a magical item for reward?
  • Does the NPC have a normal item for reward?
  • Does the NPC have a monetary reward?

The idea here is that as adventurer's interact with the NPC they will have to give hime specific items in order to indicate that they succesfully completed a quest.  You might be familiar with these types of quest.  "Go kill 10 bears and bring me 10 bearskins". Well, with those 10 bearskin hides the NPC makes a Leather Armor Jerkin, that he can use as a reward for the next quest he hands out.  Therefore, the rewards are dynamic (changing) and not always static (10 gold pieces, everytime you bring him 10 hides).

In order to show what he has on hand at any given time we set up a variable called npc_quest.  This variable will be typed as a byte (.b) or character (.c) depending on your programming language.  A type byte (.b) allows for values from -127 to +128, whereas a character (.c) allows for values from 0 to +255.  We will use a type character (.c) in this example since all values will be positive.

Our binary number is 4 digits long "0000" each digit represents 1 question. 

0 0 0 0
¦ ¦ ¦ ¦
¦ ¦ ¦ Monetary Reward
¦ ¦ Normal Item Reward
¦ Magical Item Reward
Quest available

Thus

"1000" represents Quest available but no rewards

"1100" represents Quest available and a Magical Item reward

"1010" represent Quest available and a Normal Item reward

"1001" represents Quest available and a Monetary reward

"1101" represents Quest available and a Magical Item along with a Monetart reward are available

Coding this in Purebasic is pretty straight forward.

[+] Code Snippet

npc_quest.c=%1101

Again, this code "1101" would be interpreted as follows:

  • Does the NPC currently have a quest to hand out? 1 = Yes
  • Does the NPC have a magical item for reward? 1 = Yes
  • Does the NPC have a normal item for reward? 0 = No
  • Does the NPC have a monetary reward? 1 = Yes

WAIT! Why did you spend so much time on how to convert Binary to Decimal if we are going to be working in Binary, you ask.  Well because it is easier for us to think in decimal than it is to think in binary. When it comes right down to it, we will probably code our States into some constants anyway.

Lets look at this example (again this is Purebasic)

[+] Code Snippet

#has_quest = 8                 ; binary %1000
#has_reward_magic=4   ; binary %0100
#has_reward_normal=2  ; binary %0010
#has_reward_money=1  ; binary %0001

npc_quest.c= #has_quest + #has_reward_magic + #has_reward_money

Debug Rset(bin(npc_quest),8,"0")      ;Rset is used to "0" fill  upto 8 characters.
; I am using Debug for a quick show of results
 
In this instance we know that npc_quest=13 because we know 8+4+1 = 13.  We can do this math qucikly in our head, but could you have told me that "1101"=13? Quickly?
 

Gameplay using Binary

So how do we use this to drive game play?

Simple with Bitwise Operators AND (& in Purebasic) OR (¦ in Purebasic) along with XOR.

Bitwise AND (&)

    0 & 0 = 0   
    0 & 1 = 0
    1 & 0 = 0
    1 & 1 = 1
Bitwise OR (¦)

0 ¦ 0 = 0
0 ¦ 1 = 1
1 ¦ 0 = 1
1 ¦ 1 = 1
Bitwise XOR (!)

0 ! 0 = 0
0 ! 1 = 1
1 ! 0 = 1
1 ! 1 = 0
 
Bitwise NOT (~)
 
~0  = 1
~1 = 0
 
 
 

So in code we could do this to check it there is a quest to be done.

[+] Code Snippet

#has_quest = 8                 ; binary %1000
#has_reward_magic=4   ; binary %0100
#has_reward_normal=2  ; binary %0010
#has_reward_money=1  ; binary %0001

npc_quest.c= #has_quest + #has_reward_magic + #has_reward_money

IF npc_quest & #has_quest       ; alternative you could code IF npc_quest&%1000
    Debug "Has Quest"
    ; do quest functions here
Else
    Debug "No Quest available at this time"
Endif
 
But what about the problem with the monster in the second example was it #mob_crippled or was it #mob_poisoned and #mob_hungry?  Have we eliminated the problem of multiple possible results?
 
Going back, remember we had the following States:
 
  • Is monster awake?
  • Is monster hungry?
  • Is monster enraged?
  • Is monster poisoned?
  • Is monster trapped?
  • Is monster crippled?
  • Is monster confused?
  • Is monster scared?
These states would be represented using a Byte ("0000 0000")
 
128 64 32 16 8 4 2 1
0 0 0 0 0 0 0 0
¦ ¦ ¦ ¦ ¦ ¦ ¦ scared
¦ ¦ ¦ ¦ ¦ ¦ confused
¦ ¦ ¦ ¦ ¦ crippled
¦ ¦ ¦ ¦ trapped
¦ ¦ ¦ poisoned
¦ ¦ enraged
¦ hungry
awake

Therefore, if our current_monster_state variable = 6, our monster would in fact be #mob_crippled and #mob_confused because there is only one way in which we can have a total of 6 and that is "0000 0110" which is 4+2=6.

In practice we can now get very direct answers in code

[+] Code Snippet

#mob_awake=128
#mob_hungry=64
#mob_enraged=32
#mob_poisoned=16
#mob_trapped=8
#mob_crippled=4
#mob_confused=2
#mob_scarred=1

current_mob_state=6
 
IF current_mob_state & #mob_crippled
    Debug "Monster appears to have a crippled right forepaw"
ELSE
    Debug "Monster appears healthy"
ENDIF
 
Even though we have defined our current_mob_state as being Crippled and Confused, the above If statement is only checking to see if the Crippled portion of our variable is set to true (true = 1).  We only have to check the portion of our state that is pertinent to what we are coding for.  We could check every single state if we wanted, and even check for multiple states, or we can check for a single specific state.
 
It is so much easier, and memory efficient to lookup the value of current_mob_state versus having current_mob_state_awake, current_mob_state_hungry, current_mob_state_enraged, etc.  One variable to tell us 8 states versus having to have 8 variables in memory for each monster in the area.
 
Finally a Bitwise OR example
 
Well FUCK!  This damn blog software keeps cutting off my hard work, sorry but I am too pissed to finish this now.