ID:37966
 
Keywords: ai, design, intermediate
Many thanks to DarkView and Deadron for suggestions and improvements.

 

Binary

On or off. The revolution started with two states. Either on or off. From that, we can now use technology that people living 100 years ago would see as utter magic. Of course you know what I am talking about. The world of computers!

When something can be either on or off, nothing in between, it is said to be in a binary state. Of course, computers prefer the terms 1 and 0 instead of on and off. Binary states are excellent for storing, encoding, encrypting and modifying information. The information is very hard to disrupt and can be reconstructed quite easily.

What binary states provide is a very sharp border. It seems to work in many cases. Lights on, lights off. Fridge closed, fridge open. But does it work in all cases? A person is having his 26th birthday. A comment from someone is "you're not young anymore'. So what happened here? Did the person catapult into being middleaged overnight? Other people would still say that the person is young. What is the correct answer? Seems a bit fuzzy doesn't it? Maybe the person is both young and middleaged? Older than most young people, and a small bit into middleage.

Fuzzy

The answer seems a bit fuzzy as said, so we need to find a way of getting the facts straight. The person is young and middleaged, how do we picture that? We could plot a graph of age, and divide it into areas of young and middleaged. Lets see how it would look like:


Fig 1. A binary jump in age groups

There is that instant jump again. A clear binary state, either young or middleaged. That is not good enough. Since the person could be both young and middleaged, we need a way for those states to overlap. We could overlap the rectangles in the diagram. Then the person would be young and middleage in the same time, but still the introduction to this new age group would be as sudden as overnight. The solution is to use not rectangles, but triangles! We can use the triangles slope to gradually slide away from the young ages into middleage. That sounds a bit better, doesn't it? Lets make a graph of it.


Fig 2. Gradual changes between age groups

Much better! Now when a person is going into his 20's, the young triangle is gradually being replaced by the middleage one. And during those years between 20 and 30, you could say that the person is both young and old. I generalized here and defined that after 30 years of age a person isn't young anymore. Of course, setting the limit where one triangle ends is up to you, as you will see later in this article.

To complete this graph, we add one more age group, old. With some adjustments of the slopes, the final graph looks like this:


Fig 3. The complete age group graph

Now we can determine to what age group(s) a person belongs. There are some properties of this graph that is worth noting:

  • The graph is ranged over a specific interval. In this case, only ages from 0-100 are interesting. If someone is over 100 years old, that person will be counted for as being 100 years, the maximum value.
  • The three triangles peak at the same height. Therefore we can assume that the height is 1. This is very convenient later when we start calulating the weights of input values, as you will see.
  • Two triangles peak at the start and end of the interval. This is natural, since a newborn (0 years old) is considered to be the youngest. The age 0 is at the peak of the young triangle.
  • The triangles overlap each other. This overlap is important, since every age must belong to one or more age groups, or rules as I will call them from now on, to make it more general. A number of rules is called a ruleset.

Fuzzy computer AI

What use does this have in the game that you are making? Well, consider that you are programming the AI (Artificial Intelligence) for the monsters in your game. Things are happening to the monsters that they must react on. Take health for example. A monster may get damaged by a player, and it must decide what to do. Keep fighting or run away? Take a more defensive stance? By using only health to determine that, you may get away with some simple if-statements. But when there are many other variables, the if-statements can be overwhelming. Lets say that you use only two variables (also called inputs), health and ammo, and you want three states for every input. A code snippet for a monster AI could look like this then:

DetermineAction()
if(health < 10)
if(ammo < 5) return ESCAPE
if(ammo >= 5 && ammo < 20) return CAUTIOUS
else return NORMAL
else if(health >= 10 && health < 20)
if(ammo < 5) return CAUTIOUS
if(ammo >= 5 && ammo < 20) return NORMAL
else return ATTACK
else
if(ammo < 5) return NORMAL
if(ammo >= 5 && ammo < 20) return ATTACK
else return FULL_ATTACK

Do you see how much code it takes to determine the action of the monster? Even if you use switch statements you need to divide the code into hard-to-maintain blocks. And this is only for two variables. How about adding enemies in sight, friends in sight, experience and armor class? Now the situation is getting out of control for if- or switch-statements. We need a way to collect information from a number of inputs, put them together, and produce one output. The triangles gives us a way!

Making a fuzzy system

Lets make a fuzzy logic system for the behaviour of a monster. The first thing we need to do is to figure out what inputs we need, and what output we want. The output could be very simple: Three states called Escape, Defence and Attack. That is good enough in a simple example, so lets see what inputs we can use. I suggest the first input to be ammunition, which can have the states Low, Medium and High. The next step is to make a table with the behaviour we want for the monster. This is the point where AI programming can put most people down. The table can be extremely large when many inputs are needed, since it grows exponentially for every extra state added to it. Two inputs with 5 states each will have 5^2=25 states. That is no problem. So lets add a couple of inputs and make them 6, each containing 5 states. 5^6=15 625 states!! Totally out of scope!

Fortulately there is a way to reduce the behaviour table, using a method called Combs method [1]. Using his clever rewriting of logic statements, we can make a very simple table and still arrive at virtually the same result. Here is how you write a behaviour table for our input and output, using Combs method:

Ammo
Low
Then Escape
Medium
Then Defence
High
Then Attack

See how it is done? Your input variable to the left, and one input state, correlating to one output state, in each cell. But how much ammo is low, medium and high? This is where we start creating rulesets. The ammo can be expressed in percent (0-100) with the equation level = ammo / max_ammo * 100. In this example I determined that a level between 0 and 30% is low, between 20 and 80% is medium, and 70 to 100% is high. By following the points mentioned earlier in the article, this graph is the result:


Fig 4. Ammo level ruleset

Remember that peaking at the start and end of the range is very important. For some practice, you can sketch this graph on paper using the percentage ranges I mentioned, and you will see that it is quite easy. So now we have completed our first input system! Feel like testing it? Ok, to do that we need to send a value to it. The monster has used up quite a lot of ammo, and has now 40% left. Our input system should react on that value, and it will do that by weighing the rules.

Weighing rules

If we put a ruler vertically on value 40 in our graph, we will see that the ruler intersects the Medium triangle at some point. To get a weight of how important this rule is to us, we use this intersection to set the new height of the triangle. If it sounds confusing, look at this graph:


Fig 5. Weight of a rule depending on input value

See how the new triangle is a bit smaller? The peak is still at 50, but the area of the triangle is a bit smaller. The ammo level is quite medium, but not very medium! This type of reasoning can happen when you use fuzzy logic. If we calculate the area of this new triangle, we can use it as a weight for this rulesystem.

So what would happen if the line intersects where two rules overlap? Same thing, calculate the intersection point for both of them. It will look like this for input value 72:


Fig 6. Two overlapping weighted rules

The red triangle might be small, but it's still there! This value could be fuzzified to "not very medium and not high at all". So now we have a result from our input system: Triangles of a specific base and height. To simplify things now, since I suspect that you are getting the hang of this, lets make the second input based on health, with exactly the same properties. Then our behaviour table will look like this:

Ammo
Low
Then Escape
Medium
Then Defence
High
Then Attack
Health
Low
Then Escape
Medium
Then Defence
High
Then Attack

This list can keep going for as many variables and states as you would like. But the important thing to remember is that each column must have the same outcome in every cell. This can lead to inverting of some inputs. If you add another input, "enemies in sight" for example, it could look like this if you're not aware of this rule:

Ammo
Low
Then Escape
Medium
Then Defence
High
Then Attack
Health
Low
Then Escape
Medium
Then Defence
High
Then Attack
Enemies in sight
Few
Then Attack
Some
Then Defence
Many
Then Escape

See how the input values for the last row is going from low to high, but the outcome isn't the same in all columns anymore? This means that you must invert the input, so Escape and Attack will be placed in the columns where they should be. So we rewrite the last row to look like this:

Enemies in sight (I)
Many
Then Escape
Some
Then Defence
Few
Then Attack

Now the axis for the input will be going in the other direction. Programmatically, all you need to do is set a variable to do this, so it is nothing to worry about. I'm just mentioning it so you know when to invert your inputs.

Making the output

All input channels have created their triangles from different input values, and now it's time to put them together and produce the final output. There are many methods of doing this, and a nice and simple one is to take all the triangles from all inputs together, scale them so they match the output scale, and calculate the point of balance for the whole batch. The point of balance is the output from the system. The graph below should clarify things. Red is ammo, blue is health, and green is the enemies in sight-input, all gathered from their respective input value.


Fig 7. Final output of the system

Reaction

Now when the output value is ready, your monster is ready to react on it! Here we get some use for our behaviour table. As you know the output states goes from escape, to defence, to attack. The output we get from the system is a value from 0-100. So now you define the boundaries for the output states. A low output value should of course correlate to the "lowest", or leftmost output state in the table. One of the easiest ways to handle this is to create a simple switch statement for the output value, like a state machine. In pseudocode it can look like this:

DetermineAction()
var/output = fuzzy_system.FuzzyValue()


switch(round(output))
if(0 to 33) return ESCAPE
if(34 to 66) return DEFENCE
else return ATTACK

The nice thing about the output value being in an interval is that once you have specified the boundaries for certain behaviour (34 to 66 was chosen for defence in this case), you also know how much of this behaviour the AI should consider. Is the value close to 34? Then defend, but also prepare for escape or call for help. Is the value very close to 100? Then attack with all you got! This makes the AI much more realistic. And of course, the output value could be an input to another fuzzy system, which will create another output based on many other variables, and so on... To make the AI a bit more unpredictable as well, consider adding a random value to the output.

Extra weight

Some inputs might be more important than others. To handle this you can assign a coefficient for some inputs, so their weight will be more or less than the others. Each weight of the input is multiplied with this coefficient when producing the output. The behaviour table will get an extra column using this:

Ammo 1.0
Low
Then Escape
Medium
Then Defence
High
Then Attack
Health 1.2
Low
Then Escape
Medium
Then Defence
High
Then Attack
Enemies in sight (I) 1.0
Many
Then Escape
Some
Then Defence
Few
Then Attack

As you see here, health has been made slightly more important than the other two inputs. By careful tweaking of those values, you can get much more precise in the behaviour you want from your fuzzy system.

A fuzzy library

If you are a byondscape subscriber [Editor's note: BYOND Members should have access to this too], then you can download the library that is supplementing this article. It's called fuzzy_lib, and can be downloaded from the Byond hub here: http://developer.byond.com/hub/Gazoot/fuzzy_lib

You should have no problems following the documentation for the library after reading this article. Basically you create inputs, outputs and rulesets, then wrap them up in a fuzzy_system object, which is then used to retrieve the output value. I hope it will simpify things for you!

Ending and references

Fuzzy logic is a very interesting topic that can elevate your game AI to new levels. It is also an advanced topic. Many PhD's have been made on the subject, so it can be much (much!) more advanced than my introduction here. Finding additional information should be no problem, the links below should be a good start, and of course you have the Glorious Google. You are welcome to give me some feedback on the comments page, or look me up in the Byond community and send me a mail. Good luck with your fuzzy coding!

Gazoot

[1] William E. Combs, The Combs Method For Rapid Inference,
http://gaia.ecs.csus.edu/~hellerm/EEE222/Atricles/Combs_Fuzzy_Logic/Combs_Rapid_Inference.htm

Links

http://www.fuzzy-logic.com/ - Very nice introduction, giving hardware implementations as an example.

http://www.flll.uni-linz.ac.at/ - Another good introduction to the concept.

http://neuron.et.ntust.edu.tw/homework/91/Fuzzy/FzHomework2/M9107201/main.htm - Specializing on computer games!

http://www-ugrad.cs.colorado.edu/~cs3202/papers/Brigette_Krantz.html - Going a bit deeper on the terms used for fuzzy logic.

 

Copyright © 2004 Andreas "Gazoot" Söderlund.

 

Your &lt; is showing.
Aw, gee whiz. Those HTML entities are always tripping me up. Thanks for the heads-up.
I'm a BYOND Member, but I can't download the library. :(

-- Data
I don't believe the library works, anyways. I downloaded it before, and I got a ton of errors.
I personally prefer Fuzzy Logic, for the fact that Logic doesn't apply in a virtual world.
I could have sworn I'd downloaded and had a look at that library before.

Unless it's a different one.

Also, Mechana, what you just said made no sense
The library does have errors, but it's only related to BYOND 4.0's use of output() as an internal function; all of your occurrences of output need replaced with src.output, after which it should compile cleanly.