February 28, 2011

ISSUE 7: Do you read me, HAL?

We’ll be giving the bad guys pursue, attack, flyby and flee behaviours. How do we do this without all of the bad guys behaving identically? If we’re not careful they will flock together and fall into synchronized movements. Worse, they could be predictable (not much fun for a game!). Artificial intelligence (AI) is an interesting subject. Is the solution smoke and mirrors or do we need to program something “intelligent”?

When we’re done there we will add a new ‘picture in picture’ set of cameras and tackle different screen resolutions.

1. Artificial Intelligence

Artificial intelligence (AI) is a term used often yet strangely you’ll struggle to find a good short description. The key word is ‘intelligence’ while ‘artificial’ is a bit misleading. The intention, we assume, is to indicate ‘man made’ (the term does date back to 1956!). Arguably, if a computer program exhibits intelligence there’s nothing artificial about it.

AI, Computer Intelligence, Machine Intelligence, call it what you will. The subject area is basically concerned with the science of exhibiting ‘intelligent’ behaviour computationally.

So what is intelligent behaviour?

It’s a good question and again there’s no silver bullet answer. Terms such as reasoning, planning, learning, comprehension, problem solving, abstract thought and similar are banded about often. Yet the best descriptions are in simpler terms:

INTELLIGENCE:
making sense of our environment (inputs) and deciding what to do

We’ll take a look now at what challenges AI presents and what solutions are available. As we go through this keep the game in mind. What we are trying to achieve is effectively an autopilot for the bad guys. We want them to exhibit behaviours – pursue, attack, flyby and flee – as plausibly as possible. The first key when it comes to AI in games is simple: make it believable. Believable is a subjective term we should really suffix with “for an arcade shooter”. 🙂

The second key is knowing where to draw the line. There’s a trade off between believable (for an arcade shooter) and engineering a solution too complex. Historically, AI was generally last considered in game development. The reason? Processing power. By the time all the graphics, sound, user interactions and similar were dealt with there was little room in terms of “free CPU cycles” for AI. This has been alleviated somewhat in recent years due to the advent of the GPU and the rapid progression of processor technology (Moore’s law observes that the quantity of transistors that can be placed on a circuit has doubled approximately every two years).

Still, AI in gaming is often quite ‘crafty’. Processing power is still a concern as we continue to push the multimedia boundaries. If you’re looking for pure academic AI games are probably not for you! We will be using some very simple tricks to cause behaviours.

The field of AI is filled with problems:

  • Searching/Path Finding
  • Pattern Recognition
  • Planning
  • Learning
  • Creativity
  • Knowledge Representation
  • …and lots more!

The field of AI is equally filled with potential solutions:

  • State machines
  • Neural networks
  • Genetic algorithms/programs
  • Intelligent Agents
  • Semantic Networks
  • Expert Systems
  • Machine Learning
  • Fuzzy Logic
  • …again, lots more!

For our purposes we have opted for something called a “finite state machine” or “FSM”. We will design our FSM and then code it in Python.

2. The Finite State Machine (FSM)

Describes behaviour through a finite number of states. At any given moment the machine is in one state (it begins in the ‘start state’). The machine is fed input. The input is processed (differently depending on the state), actions performed and optionally output given.

When certain events (inputs) occur (‘transition conditions’) the machine moves from one state to another (a ‘transition’). The machine can only move to certain states depending on the state it is currently in. The states it could move to are called ‘accept states’.

To make things happen a FSM also specifies actions. Actions are specific to a particular state or transition. There are four types of action: entry (to a state), exit (of a state), input (machine stays in the same state but performs some action based on input) and transition.

Well, that’s the theory. It might not be clear at this stage. Thankfully, we can see what a FSM looks like if we represent it as a State Diagram. One is shown below (the one we will be using!) and hopefully clears up any confusion. 🙂

Finite State Machine

3. Making Behaviour Dynamic

If you look back at the state diagram you’ll notice it’s mostly static. In fact, the only ‘dynamic’ behaviour is the coin toss on the fly by (which, when we code it, means we will pick a random number and depending on the answer – fly by to the left or right of the player). Everything else is pretty rigid. So if we created an army of bad guys, they’d all do the same thing for the most part.

Queue the smoke and mirrors. It’s remarkable what a few random numbers can do. Before we go ahead and code our FSM consider the following. Whenever we create a bad guy, what if we jumble up the parameters? Easy to do and could mean:

  • Each bad guy would have a different ‘tolerance’ when height matching the player
  • Each bad guy would have a different maximum speed
  • Each bad guy attacks from a different range
  • Each bad guy flees at a different level of damage
  • Each bad guy begins to bank on a flyby at a different point
  • …etc…

😉

4. Coding It!

As you probably guessed, most of what we need to do is in volume1/enemies.py. Open up the file and edit it to look like this:

from player import AlliedFlanker
import random, math

# simple enumerated type
class States:
    pursue, attack, flyby, flee = range(4) 

class EnemyFlanker(AlliedFlanker):
    def __init__(self,loader,scenegraph,taskMgr,skillLevel):
        # take an ally and make it join the dark side...
        AlliedFlanker.__init__(self,loader,scenegraph,taskMgr)
        tex = loader.loadTexture('volume1/models/enemyflanker.jpg')
        self.player.setTexture(tex,1)
        self.player.setScale(0.5)
        self.skillLevel = skillLevel
        self.state = States.pursue
        self.engineSound.stop()

        self.speed = 0.0
        self.flybydistance = 0.0
        self.pursuedistance = 0.0
        self.attackdistance = 0.0
        origspeed = self.maxspeed

        # experiment with the random values to see different behaviour
        if self.skillLevel == 1:
            self.maxspeed = self.maxspeed * random.random()
            if self.maxspeed < ((1.0/5.0) * origspeed):
                self.maxspeed = self.maxspeed + ((1.0/5.0)*origspeed)
            self.flybydistance = 20.0 + (10.0 * random.random())
            self.attackdistance = self.flybydistance+100.0+(100.0*random.random())
            self.pursuedistance = self.attackdistance * 2.5

        # print "ENEMY: "+str(self.maxspeed)
        self.clockwise = True
        self.heightmatch = 10 + (90 * random.random())

    def teleport(self,boundingBox):
        # random X/Y within bounds
        self.player.setX(random.randint(0,boundingBox))
        self.player.setY(random.randint(0,boundingBox))
        self.player.setZ(100)

    def update(self,boundingBox,playerPos):
        validMove = True
        self.calculate()
        if self.exploding == False:
            self.ai(playerPos)
            validMove = self.move(boundingBox, False, False)
        return validMove

    def ai(self,playerPos):
        # Trig
        distance = math.sqrt (math.pow(self.player.getX()-playerPos[0],2)+ \
                   math.pow(self.player.getY()-playerPos[1],2)+ \
                   math.pow(self.player.getZ()-playerPos[2],2))

        if (self.state == States.pursue):
            self.heightMatch(playerPos)
            self.accelerate()
            self.player.lookAt(playerPos) # cheating badly!
            self.player.setH(self.player.getH()-90)

            if (distance < self.attackdistance):
                self.state = States.attack

        elif (self.state == States.attack):
            self.heightMatch(playerPos)
            self.player.lookAt(playerPos)
            self.player.setH(self.player.getH()-90)
            if (distance < self.flybydistance):
                if random.randint(0,1) == 0:
                    self.clockwise = False
                else:
                    self.clockwise = True
                self.state = States.flyby
            elif (distance > self.pursuedistance):
                self.state = States.pursue
            # Hook to FLEE will go here when we have player/enemy damage
            # will also add attacking at same time

        elif (self.state == States.flyby):
            self.heightMatch(playerPos)
            if (self.speed > (self.maxspeed/2)):
                    self.brake()
            if (self.clockwise != True):
                self.bankRight()
            elif (self.clockwise == True):# and self.player.getP() < 40.0):
                self.bankLeft()
            if (distance > self.pursuedistance):
                self.state = States.pursue
            # Hook to FLEE will go here when we have player/enemy damage

    def heightMatch(self,playerPos):
        diffZ = self.player.getZ() - playerPos[2]
        if (diffZ < -self.heightmatch):
           self.climb()
        elif (diffZ > self.heightmatch):
           self.dive()

We will now go through this code. First, we create a new class called ‘States’. We then add four class variables representing our states (pursue, attack, flyby, flee) each set with a value returned via range(4) (we first covered Python ranges in Issue 4). This sets the variable values as follows:

  • pursue = 0
  • attack = 1
  • flyby = 2
  • flee = 3

What we are trying to do is create what is called an ‘enumerated type‘. Python does not directly support enumerated types hence the new class to achieve something ‘like’ an enumeration. An enumerated type is one that the programmer defines. For example, if we were programming traffic lights it might be nice to have a data/variable type that holds the value Red, Amber or Green.

The code might also look strange because we declare the variables outside of any method whereas in MGF to date we have only ever created member variables for a class inside its methods using the ‘self’ keyword. So what’s the difference?

Such variables are called class or static variables. They exist at the class level and can be accessed without creating an object. Look later in the code and note how we refer to ‘States.pursue’, ‘States.flee’ etc. without creating an object. You still can create an object if you like. It’s important to note that if you create an object it has its own separate copy/instance of each variable. This is unusual to those coming from a C++ or Java background where static variables are ‘shared’.

Next, our EnemyFlanker class. Based on how it was previously and what you have previously learnt about Python this should be pretty much self-explanatory. We would, however, point out the following:

  1. Engine sound. We turn it off. All it will achieve when playing is multiple aircraft engine sounds. We need to address enemy sounds differently – based on locality (distance) to the player.
  2. States. As discussed above, the use of a basic enumerated type.
  3. Random Variables. As discussed in the previous section, we will use some random variables to achieve dynamic behaviour.

Next, the teleport method which we introduced in the last issue. As its name suggests, it teleports the enemy to a random location on the map.

The ‘update’ method calls ‘calculate’ (the same as updateTask in game.py does for the main player) and then a new method ‘ai’. The AI method itself follows next in the code. Looking at it, you should see some resemblance in its logic to what we had in our FSM diagram previously.

Note we have not coded for ‘flee’ yet but have left comments where it will go. This is simply because we do not yet have any notion of player or enemy damage in our game! For the same reason, the ‘attack’ mode does not actually ‘fire weapons’ yet! Again, the code should make sense by itself at this stage with the interesting highlights as:

  • Note the comment ‘cheating badly!’. We admit it, we cheat! After a flyby/switch back to ‘pursue’ we rely on a call to ‘lookAt’. What this actually means, is that if the enemy is flying away from the player and then switched back to ‘pursue’ it will do a U-Turn (180 degrees) instantly without maneuvering! The good news is that this little trick works well because the enemy is far from view when it happens. Feel free to attempt something more elegant here!
  • It makes use of a ‘heightMatch’ method which is defined next in the code. It also makes use of a little bit of trigonometry to calculate the distance between the enemy and the player. You might recall the Pythagoras Theorem from School! If not, we suggest you head for Google. Very succinctly – the square of the hypotenuse is equal to the sum of the squares of the other sides on a right-handed triangle. The theorem can be used to calculate the distance between two points in 2D space. The same theorem also applies in 3D, we just have one further value to consider (Z).
     
    Wikipedia Entry on Pythagorean Theorem

To support the new enemy code we need a couple of minor tweaks in the base class. Open up volume1/player.pl and modify the ‘move’ method as follows:

    def move(self,boundingBox,gravity=True,checkBounds=True):
        # move forwards - our X/Y is inverted, see the issue
        valid = True
        if self.exploding == False:
            self.player.setFluidX(self.player,-self.speedfactor)
            if (checkBounds == True):
               valid = self.__inBounds(boundingBox)
            if (gravity == True):
               self.player.setFluidZ(self.player,-self.gravityfactor)
        return valid

You’ll note it takes and uses two new parameters – ‘gravity’ and ‘checkBounds’. What is interesting is that on the method declaration we write ‘=True’. This is called a default parameter value. It means the method can be called without providing a value – in this case, if no value is given, it defaults to True. This is useful in this instance because we know there are already calls to the move method elsewhere in our code (to move the main player!). We’re making sure we do not break existing code by the addition of our new value. Of course, if we feel strongly about a new parameter (e.g., the programmer really ought to think about it in every call to the method anywhere in the code), we could leave out the default value and thus force code updates (existing code will fail with an error). If you’re wondering why we’re not boundary checking for the enemy – it is simply because (a) they will never get too far out of bounds if pursuing the player and (b) the AI will still impose the same decision regardless of boundaries and this would cause the enemy to appear ‘stuck’. We’re not applying gravity either because gravity is just an effect we use to make the player concentrate on their height in-game.

Next add a new method to the code:

    def getPos(self):
        return self.player.getPos()

Lastly, we made one further tweak. We observed that both player and enemy were climbing too fast so we updated the calculate method declaration of climb factor to:

        self.climbfactor = self.scalefactor * 0.2

By changing it in the base class both player and enemy respect the change. You may disagree with our change and are actively encouraged to experiment with different values!

Some might also argue that we should have a base ‘character’ class and then derive ‘player’ and ‘enemy’ separately because presently changes to the player class effect the enemy and this might not always be wanted. This again comes down to the ethos of our approach… my game FAST! If we reach a stage where our design is causing us a problem it will not be too much effort to re-factor the player/enemy into a different/more suitable class hierarchy.

All we need to do now is hook all of this into our game. Open up volume1/game.py and first modify startLevel to:

    def startLevel(self):
        if (self.level == 1):
           self.spawnBadGuys(5,1)

All we have done here is increase the number of bad guys – it’s far more fun with 5 as opposed to 2 as it was before. Update spawnBadGuys to:

    def spawnBadGuys(self,howMany,skillLevel):
        for i in range(0,howMany):
            self.baddies.append(EnemyFlanker(self.loader,self.render, \
                                        self.taskMgr,skillLevel))
        # jump start em
        for baddy in self.baddies:
           baddy.teleport(self.world.getSize())

Basically as it was before though we now pass the skill level value (look back above to enemies.py and note we added the value in the constructor too). Finally, in the updateTask method, after the line:

        validMove = self.player.move(self.world.getSize(), True)

…add the following:

        for baddy in self.baddies:
           retval = baddy.update(self.world.getSize(),self.player.getPos())

That’s it! Run the game and you should now find you have some bad guys flying around. You can see exactly what they’re doing if you look at the RADAR. Remember you also have an Enemy Cam accessible via the TAB key.

You’ll note we have not done anything about enemy collisions. Yet. Right now they can fly through the terrain, each other and the player. We will address this in a future issue. Having said that, you probably won’t even notice as things in the game are happening so fast (and the enemies are height matching the player).

5. More elaborate State Machines

Panda3D does actually include classes specifically for FSMs. We have opted not to use them at this stage (our machine and logic is really quite simple, implemented with an ‘if’ statement!) but may revert to them in the future if needed. If you are interested we recommend viewing the Panda3D Manual Page for FSMs. If you’re feeling adventurous, try and adapt the code we have provided to use the FSM classes from the Panda3D library. A short example is shown below:

from direct.fsm.FSM import FSM
 
class EnemyFSM(FSM):
    def __init__(self):
        FSM.__init__(self, 'EnemyFSM')
 
    def enterPursue(self):
        # accelerate etc.
 
    def exitPursue(self):
        # exit actions

    def enterAttack(self):
        # attack
 
    def exitAttack(self):
        # exit actions
 
myfsm = EnemyFSM()
myfsm.request('Pursue')

6. Screen resolutions

Does your game support multiple screen resolutions? Yes, it does! Changing screen resolution can be done quite easily in code. There is also a global configuration file for Panda3D called config.prc that sets the defaults (a future topic) and you can also have a separate .prc file per project/game (again, a future topic). In code, you can simply open up volume1/game.py and add, after your import statements, the lines:

from panda3d.core import loadPrcFileData
loadPrcFileData('','win-size 1024 768')

In the example given, the screen is set to a width of 1024 and a height of 768. We suggest keeping with standard screen resolutions and suggest keeping the resolution relatively low: 640×480 (VGA), 800×600 (SVGA), 1024×768 (XGA), 1280×768 (WXGA) or 1280×960 (SXGA-).

We tested in a number of other resolutions too and the game worked perfectly. The only instances of any problems we could find pertained to the on screen text messages. We fixed this via modifying the makeStatusLabel method in game.py to read as follows:


    def makeStatusLabel(self, i):
        """ Create a status label at the top-left of the screen,
        Parameter 'i' is the row number """
        return OnscreenText(style=2, fg=(.5,1,.5,1), pos=(-1.75,0.92-(.08 * i)), \
                               align=TextNode.ALeft, scale = .08, mayChange = 1)

While we are here, this method really belongs in our Game GUI and not the main logic. Open up gui.py and move the makeStatusLabel method from game.py (ArcadeFlightGame) into gui.py (GameGUI). Then, in the ArcadeFlightGame constructor, move the lines:

        self.statusLabel = self.makeStatusLabel(0)
        self.collisionLabel = self.makeStatusLabel(1)

…to after the declaration of self.gui and change them to read:

        self.statusLabel = self.gui.makeStatusLabel(0)
        self.collisionLabel = self.gui.makeStatusLabel(1)

You will also need to add imports to gui.py:

from direct.gui.OnscreenText import OnscreenText
from panda3d.core import TextNode

…the same imports can be removed now from game.py.

Since we have covered default parameters in this Issue we may as well quickly cover named parameters! Look at the call to OnscreenText in makeStatusLabel. The parameters are named. This helps code readability but also means parameters can be in a different order. This approach is used quite often when there are many parameters and many have default values (i.e., you only want to pass a few values in, not all, so we make it clear what we are passing).

Would you like to try the game running in full screen? You can do it via adding the line:

loadPrcFileData('', 'fullscreen t') 

…after the import. 🙂 You can also change the title bar for when in Windowed mode (it currently reads ‘Panda’ as we’re sure you noticed):

loadPrcFileData("", "window-title All Known Threats - MGF Volume 1") 

7. Picture in Picture (PIP) and taking Screenshots

Picture in Picture

We thought it might be nice to have a ‘picture in picture’ feature to the game. Let the player see the game as normal but, at the same time, some ‘mini screens’ showing a left, right and backward looking viewpoint of the action. It’s actually quite easy to do!

First, our updated constructor in game.py declares the new cameras:

    def __init__(self):
        ShowBase.__init__(self)
        self.debug = False
        self.maxdistance = 400
        self.player = AlliedFlanker(self.loader,self.render,self.taskMgr)
        self.world = GameWorld(1024,self.loader,self.render,self.camera)
        self.gui = GameGUI(self.render2d)
        self.statusLabel = self.gui.makeStatusLabel(0)
        self.collisionLabel = self.gui.makeStatusLabel(1)
        self.taskMgr.add(self.updateTask, "update")
        self.keyboardSetup()

        # performance and map to player so can't fly beyond visible terrain
        self.player.setMaxHeight(self.maxdistance)

        self.leftCam = base.makeCamera(base.win, \ 
                            displayRegion = (0.79, 0.99, 0.01, 0.21)) 
        self.rightCam = base.makeCamera(base.win, \ 
                              displayRegion = (0.79, 0.99, 0.23, 0.43)) 
        self.backCam = base.makeCamera(base.win, \ 
                              displayRegion = (0.79, 0.99, 0.45, 0.65)) 
        if self.debug == False:
            self.camLens.setFar(self.maxdistance)
            self.leftCam.node().getLens().setFar(self.maxdistance*2.0)
            self.rightCam.node().getLens().setFar(self.maxdistance*2.0)
            self.backCam.node().getLens().setFar(self.maxdistance*2.0)
        else:
            base.oobe()

        self.camLens.setFov(60)
        self.leftCam.node().getLens().setFov(60)
        self.leftCam.node().setActive(False)
        self.rightCam.node().getLens().setFov(60)
        self.rightCam.node().setActive(False)
        self.backCam.node().getLens().setFov(60)
        self.backCam.node().setActive(False)

        self.setupCollisions()
        self.textCounter = 0

        newGameSound = base.loader.loadSfx("volume1/sounds/gamestart.wav")
        newGameSound.play()

        self.level = 1; self.score = 0; self.baddies = list()
        self.startLevel()
        self.enemyCam = False; self.currentEnemy = 0;

Next, we update our keyboardSetup method. We will use the ‘p’ key for PIP and will only show PIP while the key is held down. Once released, we will again hide the PIP cameras. The code below also adds support for the ‘s’ key which we will use for taking screen shots in a moment:

        self.keyMap = {"left":0, "right":0, "climb":0, "fall":0, \
                        "accelerate":0, "decelerate":0, "fire":0, \ 
                        "cam":0, "pip":0, "shot":0}
        self.accept("p", self.setKey, ["pip",1])
        self.accept("p-up", self.setKey, ["pip",0])
        self.accept("s", self.setKey, ["shot",1])
        self.accept("s-up", self.setKey, ["shot",0])

In your actionInput method, activate/deactivate the cameras:

        if (self.keyMap["pip"]!=0 and self.enemyCam == False):
            self.leftCam.node().setActive(True)
            self.rightCam.node().setActive(True)
            self.backCam.node().setActive(True)
        else:
            self.leftCam.node().setActive(False)
            self.rightCam.node().setActive(False)
            self.backCam.node().setActive(False)

All we need to do now is control what these cameras are looking at. Modify the updateCamera method as follows:

    def updateCamera(self):
        if self.enemyCam == True:
           if len(self.baddies) &amp;amp;gt; self.currentEnemy:
               self.baddies[self.currentEnemy].lookAtMe(self.camera)
           else:
               self.enemyCam = False
        else:
            self.player.lookAtMe(self.camera)
            self.player.lookAtMeLeft(self.leftCam)
            self.player.lookAtMeRight(self.rightCam)
            self.player.lookAtMeBack(self.backCam)

The supporting methods need to be added to AlliedFlanker in player.py as shown below:

    def lookAtMeLeft(self,camera):
        camera.setPos(self.player,0,16,3)
        camera.setHpr(self.player,-180,-20,0)

    def lookAtMeRight(self,camera):
        camera.setPos(self.player,0,-16,3)
        camera.setHpr(self.player,0,-20,0)

    def lookAtMeBack(self,camera):
        camera.setPos(self.player,-9,1.5,3)
        camera.setHpr(self.player,-90,-30,0)

That’s it for PIP! Give it a try by launching the game then holding down the ‘P’ key. Finally, to add in screen shot support, add the following to actionInput in game.py:

        if (self.keyMap["shot"]!=0):
            base.screenshot()
            self.keyMap["shot"] = 0

Run the game, press the ‘S’ key. Now quit the game. You should find a new image file in the main game directory! A screen shot of the game as it was when you pressed the ‘S’ key! Simples. 🙂

8. Wrap up and Summary

A lot of ground covered! We introduced AI and implemented a simple state machine for our enemy. We need to add enemy collisions (and sounds, and damage, and firing!). We have also added a nice PIP feature along with the ability to take screen shots. Quite a productive Issue!

Goto Issue 8 >>>