AIGama

1. Preface
2. THE WANTED
3. Chasing and Evading
4. Pattern Movement
5. Flocking
6. Additional Resources

As AI is still a new field, there are many different approaches. Here we won't go deep into the theory behind AI. If you have no knowledge of AI you might want to research on your own. This wiki will contain my research and my small addition: AIGama. It tries to build up a framework that can be added to the jMonkey Engine for easily adding AI controllers. The content of this library is based on the O'Reilly's AI for Game Developers book in First Edition July 2004. The Wanted Section shows what we want to touch upon and implement in our AIGama framework.

This all only makes sense if there are affinities on AI in different types of Games. One Example:

• Landmark planning:

How to move an NPC(Non-Player-Character) over the map is a decision made by AI. So when do we have NPC acting like that?

Examples:

• Strategy Game where Units try to simulate a battle
• First Person Shooter where NPC has to navigate in realtime
• Simulations where population tries to look intelligent
• Racing Games where opponents try to reach the finish first
• several other approaches

Are you trying to tell me you can get that all under one crappy framework ?

No, I'm not!

This approach tries to realize the basics which are general. Some things use these approaches while others don't. The purpose is to build up some framework which can be easily extended without much knowledge of AI and be easy to use.

That brings up to the next chapter which defines The Wanted, what we want to accomplish in our approach:

• Chasing and Evading 80%
• Pattern Movement 65%
• Flocking
• Potential Function Based Movement
• Basic Pathfinding and Waypoints
• A* Pathfinding
• Finite State Machines
• Fuzzy Logic
• Rule-Based AI
• Basic Probability
• Decisions under Uncertainty - Bayesian Techniques
• Neural Networks
• Genetic Algorithms
• Vector Operations

Description:

Chasing and Evading:
We will cover basic techniques for chasing and evading as well as more advanced techniques for intercepting. We will also cover techniques applicable to both tile-based and continuous game environments.

Pattern Movement:
Pattern movement techniques are common to many video games and developers have been using them since the early days of gaming. You can use these techniques to preprogram certain behaviours such as the patrolling of a guard or the swooping in of a spacecraft.

Flocking:
The flocking method we examine in this chapter is an example of an A-life algorithm. In addition to creating cool-looking flocking behaviour, A-life algorithms form the bases of more advanced group movement.

Potentional Function Based Movement:
Potentional-based movement is relatively new in game AI applications. The cool thing about this method is that it can handle chasing, evading, swarming, and collision avoidance simultaneously.

Basic Pathfinding and Waypoints:
Game developers use many techniques to find paths in and around game environments. In this chapter, we cover several of these methods, including waypoints.

A* Pathfinding:
No treatment of pathfinding is complete without addressing the workhorse algorithm of pathfinding; therefore, we devote this whole chapter to the A* algorithm.

Finite State Machines:
Finite state machines are the nuts and bolts of game AI. This chapter introduces fundamentals of finite state machines and how to implement them.

Fuzzy Logic:
Developers use fuzzy logic in conjunction with or as a replacement for finite state machines. In this chapter, you'll learn the advantages fuzzy techniques offer over traditional logic techniques

Rule-Based AI:
Technically, fuzzy logic and finite state machines fall under the general heading of rule-based methods. In this chapter, we cover these methods as well as other vairants.

Basic Probability:
Game Developers commonly use basic probability to make their games less predictable. Such cheap unpredictability enables developers to maintain substantial control over their games. Here, we cover basic probability for this purpose as well as lay the groundwork for more advanced methods.

Decisions Under Uncertainty - Bayesian Techniques:
Bayesian techniques are probabilistic techniques, and in this chapter we show how you can use them for decision making and for adaptation in games.

Neural Networks:
Game developers use neural networks for learning and adaptation in games - in fact, for anything from making decisions to predicting the behaviour of players. We cover the most widely used neural network architecture, in detail.

Genetic Algorithms:
Genetic algorithm offer opportunities for evolving game AI. Although developers don't often use genetic algorithms in game, their potential for specific applications is promising, paricularly if they are combined with other methods.

Appendix: Vector Operations:
This Appendix shows you how tom implement a class that captures all of the vcector operations that you'll need when writing 2D or 3D simulations.

All Chapters are fairly independent of each other. The goal is to create a framework that allows us to easily add different AI techinques as needed.

As we talk about Chase & Evade we will discuss two participates initially. One is the prey, the other is the predator chasing it. There are several approaches and we will try to implement a simple structure for each and explain its behaviour.

The simplest chase algorithm involves correcting the predator's coordinates based on the prey's coordinates so as to reduce the distance between their positions. This is a very common method for implementing basic chasing and evading. In this method, evading is virtually the opposite of chasing, whereby instead of trying to decrease the distance between the predator and prey coordinates you try to increase it. In code, the method looks something like that shown down here

      if(predatorX > preyX)
        predatorX--;
      else if(predatorX < preyX)
        predatorX++;
 
      if(predatorY > preyY)
        predatorY--;
      else if(predatorY < preyY)
        predatorY++;

In this algorithm, the prey is located at coordinates preyX and preyY, while the predator is located at coordinates predatorX and predatorY. During each cycle through the game loop the predator's coordinate are checked against the prey's.

Using the same methodology, we can implement evading by simply reversing the logic, as illustrated before:

      if(preyX> predatorX)
        preyX--;
      else if(preyX< predatorX)
        preyX++;
 
      if(preyY> predatorY )
        preyY--;
      else if(preyY< predatorY )
        preyY++;

For this I have implemented a new Class known for now as BCEController (Basic Chase and Evade Controller). It provides easy Chase and Evade Management for two Spatial Classes by using its constructor:

BCEController(Spatial predator, Spatial prey, byte algorithm)

The choice of the behaviour can be defined simply within the controller using:

static byte CHASE_MODE = 0x01
static byte EVADE_MODE = 0x02
static byte CHASE_AND_EVADE_MODE = 0x03;

The only method we will implement is updateCycle, this will update the positions every game loop.

A typical use would look something like this:

      try{
          ai.updateCycle();
      }catch(AlreadyGotcha ag){
          System.out.println(ag.getMessage());
      }

Notice that we created two new Exception classes, one the base class of our new Exceptions called AIGamaException, the next is a subclass called AlreadyGotcha. We use this because we want to know if the predator chased the prey for later cycles using this information. We could add a return type to updateCycle, but we want as few communications as needed. The exception will be the better approach.

The trouble with this basic method is that often the chasing or evading seems almsot too mechanical. Try out the BasicChasingAndEvadingTest Class to see how movement is going.

As you can see, the predator mfirst moves diagonally toward the prey until one of the coordinates, the x in this cas, equals that of the prey's. The the predator advances toward the predator straight along the other coordinate axis, the z in this case.

Clearly this does not look very natural. A better approach is to have the predator move directly toward the prey in a straight line. This algorithm can be implemented without too much difficulty, as we discuss the next section.

• AIGamaException
• AlreadyGotcha
• AIBasics
• BCEController
• BasicChasingAndEvadingTest

In this section i explain a few chasing and evading algorithms that use a line-of-sight approach. The gist of the line-of-sight approach is to have the predator take a straight-line path toward the prey; the predator always moves directly toward the prey's current position. If the prey is standing still, the predator will take a straight line path. However, if the prey is moving, path will not necessarly be a straight line. The predator still will attempt to move direvtly toward the current position of the prey, but by the time he catches up wich the movement of the prey, the path he would have taken might be curved.

In this figure, the circles represent the predator and the box represent the prey. The dashed lines and shapes indicate starting and intermediate positions. In the scenario on the left, the prey is sitting still; thus the predator makes a straight-line dash towards the prey. In the scenario on the right, the prey is moving along some arbitrary path over time. At each time step, or cycle through the game loop, the predator moves toward the current position of the prey. As the prey moves, the predator traces out a curved path from its starting point.

The results illusrated here look more natural than those resulting from the basic chase algorithm. Over the remainder of this section, i'll show you one algorithms that ímplements line-of-sight chasing. One algorithm is specifically for tiled environments, while the other applies to continuous environments. I will focus on continuous environments first but if there's some suggestion made in the forums i will think of providing the second too.

tiled environments are divided into discrete tiles - squares, hexagons, etc. - and the player's position is fixed to a discrete tile. Movement goes tile by tile, and the number of directions in which the player can make headway is limited.

In a continuous environment, position is represented by floating-point coordinates, which dan represent any location in the game domain. The player also is free to head in any direction.

Left out for now.

If you want me to put it in plz tell me.

In this section i discuss a line-of-sight chase algorithm in the context of continuous environments. Specifically, i will show you how to implement a simple chase algorithm that you can use for games that incorporate physics engines where the game entities - airplanes, spaceships, hovercraft, etx. - are driven by applied forces and torques.

The example we'll discuss in this section uses a simple two-fimensional, rigid-body physics engine to calculate the motion of the predator and prey vehicles. We'll cover as much rigid-body physics as necessary tp get through the example, but we won't go into great detail- For thorough coverage of this subject, refer to Physics for Game Developers (O'Reilly).

Here's the scenario. We want to extend our previously known algorithm to extend it to LOS Chasing.

Therefore we must make suggestions on direction vectors for not running into the same fault as it was before. If i say this, don't think it was useless, it was not as you see later.

    private void doLineOfSightChase() {
        Vector3f u = preypos.subtract(predpos).normalize();
        predator.setLocalTranslation(predpos.add(u.mult(0.005f)));
    }

As you can see algorithm is really easy. We get out the current vector laying between the predator and the prey and normalize it so it is some unified vector we can use to multiply to our speed, in here hardcoded 0.005f every cycle loop.

There is missing the rotation as i don't know yet how to use this correct, but our found vector u is also the direction we want to face, so the lines to add here should be few ones.

• LOSController
• LineOfSightChasingTest

The line-of-sight chase algorithm we discussed in the previous section in the context of continuous movement is effective in that the predator always will head directly toward the prey. The drawback to this algorithm is that heading directly toward the prey is not always the shortest path in terms of range to target or, perhaps, time to target.

Further, the line-of-sight algorithm usually ends up with the predator following directly behind the prey unless the predator is faster, in which case it will overshoot the prey. A more desirable solution in many cases - for example, a missile being shot at an aircraft - is to have the predator intercept the prey at some point along the prey's trajectory. This allows the predator to take a path that is potentially allow slower predators to intercept faster prey.

To explain how the intercept algorithm works, we'll use as a basis a physics-based game scenario. In fact, all that's required to transform the basic-chase algorithm into an intercepot algorithm is the addition of a few lines of code within the chase function. Before getting to the code, though,, we want to explain how the intercept algorithm works in principle. (You can apply the same algorithm, building on the line-of-sight example we discussed earlier.)

The basic idea of the intercept algorithm is to be able to predict some future position of the prey and to move toward that position so as to reach it at the same time as the prey.

At first glance it might appear that the predicted point is simply the point along the trajectory of the prey that is closest to the location or the predator. This is the shortest-distance-to-the-line probke, whereby the shortest distance form a point to the line is along a line segment that is perpendicular to the line. This is not necessarily the interception point because the shortest-distance problem does not consider the relative velocities between the predator and the prey. It might be that the predator will reach the shortest-distance point on the prey's trajectory before the prey arrives. In this case the predator will have to stop and wait for the prey to arrive if it is to be intercepted. This obviously won't work if the predator is a projectile being fired at a moving target such as an aircraft. If the scenario is a role-playing game, as soon as the player sees that the predator is in his path, he'll simply turn away.

To find the point where the predator and prey will meet at the same time, you must consider their relative velocities. So, instead of just knowing the prey's current position, the predator also must know the prey's current velocity - that is, its speed and heading. This information will be used to predict where the prey will be at some time in the future. Then, that predicted position will become the target toward which the predator will head to make the interception. The predator must then continuously monitor the prey's position and velocity, along with its own, and update the predicted interception point accordingly. This facilitates the predator changing course to adapt to any evasive maneuvers the prey might make. This, of course, assumes that the predator has some sort of steering capability.

At this point you should be asking how far ahead in time you should try to predict the prey's position. The answer is that it depends on the relative positions and velocities of both the predator and the prey. Let's consider the calculations involved step at a time.

The first thing the predator must do is to calculate the relative velocity between itself and the prey. This is called the closing velocity and is simply the vector difference between the prey's velocity and the predator's:

• Vr =Vprey - Vpredator

Here the relative, or closing, velocity vector is denoted Vr. The second steo involves calculating the range to close. That's the relative distance between the predator and the prey, which is equal to the vector difference between the prey's current position and the predator's current position:

• Sr=Sprey - Spredator

Here the relative distance, or range, between the predator and prey is denoted Sr. Now there's enough information to facilitate calculating the time to close.

The time to close is the average time it will take to travel a distance equal to the range to close while traveling at a speed equal to the closing speed, which is the magnitude of the closing velocity, or the relative velocity between the predator and prey. The time to close is calculated as follos:

• Tc = |Sr|/|Vr|

The time to close, Tc, is equal ro the magnitude of the range vector Sr, divided by the magnitude of the closing velocity vector Vr.

Now, knowing the time to close, you can predict where the prey will be Tc in the future. The current position of the prey is Sprey and it is traveling at Vprey. Because speed multiploed by time yields average distance traveled, you can calculate how far the prey will travel over a time interval Tc traveling at Vprey and add it to the current position to yield the predicted position, as follows;

• St = Sprey + (Vprey)(Tc)

Here St is the redicted position of the prey Tc in the future. It's this predicted position St, that now becomes the target, or aim, point for the predator. To make the interception, the predator should head toward this point in much the same way as it headed toward the prey using the line-of-sight chase algorithm. In fact, all you need to do is to add a few lines of code to the last Example, the line-of-sight chase function, t convert it to an interceoting function.

        Vector3f u = preypos.subtract(predpos).normalize();
        Vector3f vr = preymove.mult(preyvel).subtract(u.mult(predvel));
        Vector3f sr = preypos.subtract(predpos);
        float tc = sr.length() / vr.length();
        Vector3f st = preypos.add(preymove.mult(preyvel).mult(tc));
 
        u = st.subtract(predpos).normalize();
 
        predator.setLocalTranslation(predpos.add(u.mult(predvel)));

The changes are really easy and only do what's written up there. As you can see, wee added a few lines of code to calculate the closing velocity, range, time to clos that calculates the target point in the predator's local coordinates to use the predicted position of the prey rather than its current position.

That's all there is to it. This function should be called every time through the game loop or physics engine loop so that the predator constantly updates the predicted interception point and its own trajectory.

Notice the difference between the path taken by the predator using the intercept algorithm versus the line-of-dight algorithm. Clearly this approach yields a shorter path and actually allows the predator an d prey to cross the same point in space at the same time. In the line-of-sight algorithm, the predator chases the prey in a roundabout manner, ending up behind it. If the predator was not fast enough to keep up, it would never hit the prey and might get left behind.

In here, after the prey makes an evasive move to the right, the predicted intercept point is immediately updated and the predator takes corrective action so as to head toward the new intercept point.

The interception algorithm we discussed here is quite robust in that it allows the predator to continuously update its trajectory to effect an interception. After experienting with this demo, you'll see that an interception is made almost all the time.

Sometime interceptions are not possible, however, and you should modify the algorithm we discussed here to deal with these cases. For example, if the predator is slower than the prey and if the predator somehow ends up behind the prey, it will be impossible for the predator to make an interception. It will never be able to catch up to the prey or get ahead of it to intercept it, unless the prey makes a maneuver so that the predator is no longer behind it. Even then, depending on the proximity, the predator still might not have enough speed to effect an interception.

In another example, if the predator somehow tets ahead of the prey and is moving at the same speed or faster than the prey, it will predict an interception point ahead of both the prey and the predator such that neither will reach the interception point - the interception point will constantly move away from both of them. In this cast, the best thing to do is to detect when the predator is ahead of the prey and have the predator loop around or take some other action so as to get a better angle on the prey. You can detect whether the prey is behind the predator by checking the position of the prey relative to the predator in the predator's local coordinate system.

If the predator is in front of the prey he must turn around. An easy way to make the predator turn aroud is to have it go back to the line-of-sight algorithm insted of the intercept algorithm. This will make the predator turn right around and head back directly toward the prey, at which point the intercept algorithm can kick back in to effect an interception.

Earlier we told you that chasing and evading involves two, potentially three, distinct problems: deciding to chase or evade, actually effecting the chase or evasion, and obstacle avoidance. In this chapter we discussed the second problem of effecting the chase or evasion from a few different perspecives. These included basic chasind, line-of-sight chasing and intercepting in continuous environments. Tile-based will be explained if wanted so! The methods we examined here are effective and give an illusion of intelligence. However, you can greatly enhance the illusions by combining these methods with other algorithms that can deal with the other parts of the problem - namely, deciding when and if to chase or evade, and avoiding obstacles while in pursuit or on the run. We'll explire several such algorithm in upcoming chapters.

Also, note that other algorithms are availabe for you to use to effect chasing or evading. One such method is based on the use of potentional functions, which we discuss in Chapter 5.

• InterceptController
• InterceptTest

This chapter covers the subject of pattern movement. Pattern movement is a simple way to give the illusion of intelligent behaviour. Basically, the computer-controlled characters move according to some predefined pattern that makes it appear as though they are performing complex, thought-out maneuvers. If you're old enough to remember the classic arcade game Galaga, you'll immediately know what pattern movement is all about. Recall the alien ships swooping down from the top and in from the sides of the screen, performing loops and turns, all the while shooting at your ship. The aliens, depending on their type and the leve you were on, were capable of different maneuvers. The maneuvers were achieved using pattern movement algorithms.

Although Galaga is a classic example of using pattern movement, even modern video games use some form of pattern movement. For example, in a role-playing game or first-person shooter game, enemy monsters might patrol areas within the game world according to some predefined pattern. In a flight combat simulation, the enemy aircraft might perform evasive maneuvers according to some predefined patterns. Secondary creatures and nonplayer characters in different genres can be programmed to move in some predefined pattern to give the impression that they are wandering, feeding, or performing some task.

The standard method for implementing pattern movement takes the desired pattern and encodes the conrol data into an array or set of arrays. The control Data consist of specific movement instructions, such as move forward and turn, that force the computer-controlled object or character to move according to the desired pattern. Using these algorithms, you can create a circle, square, zigzag, curve - any type of pattern that you can encode into a concide set of movement instructions.

In this chapter, i'll go over the standard pattern movement algorithm in generic terms before moving on to the implement variations of the standard algorithm. The example shows how to implement pattern movement in physically simulated environments in which you must consider certain caveats to such einvironments. In here too, if u want tile-based explanatory tell me !

The standard pattern movement algorithm uses lists or arrays of encoded instructions, or control instructions, that tell the computer-controlled character how to move each step through the game loop. The array is indexed each time through the loop so that a new set of movement instructions gets processed each time through.

The next class shos a typical set of control instructions:

package com.aigama.basics;
 
public class ControlData {
 
    float turnLeft;
    float turnRight;
    float stepForward;
    float stepBackward;
}

In this example turnLeft and turnRight would contain the number of degrees by which to tzrn right or left. If this were a tile-based game in which the number of directions in which a character could head is limited, turnRight and turnLeft could mean turn right or left by one increment. stepForward and stepBackward would contain the number of distance units, or tiles, by whicht to step forward or backward.

This control structure also could include other instructions, such as fire weapon, drop bomb, release chaff, do nothing, speed up, and slow down, among many other actions appropriate to your game.

Typically you set up a global array or set of arrays of the control structure type to store the pattern data. The data used to initialize these pattern arrays can be loaded in from a data file or can be hardcoded within the game; it really depends on your coding style and on your game's requirements.

Initialization of a pattern array one that was hardcoded, might look something such as shown down here

Pattern[0].turnRight = 0;
Pattern[0].turnLeft = 0;
Pattern[0].stepForward = 0;
Pattern[0].stepBackward = 0;
 
Pattern[1].turnRight = 0;
Pattern[1].turnLeft = 0;
Pattern[1].stepForward = 2;
Pattern[1].stepBackward = 0;
 
Pattern[2].turnRight = 10;
Pattern[2].turnLeft = 0;
Pattern[2].stepForward = 0;
Pattern[2].stepBackward = 0;
 
Pattern[3].turnRight = 10;
Pattern[3].turnLeft = 0;
Pattern[3].stepForward = 0;
Pattern[3].stepBackward = 0;
 
Pattern[4].turnRight = 0;
Pattern[4].turnLeft = 0;
Pattern[4].stepForward = 2;
Pattern[4].stepBackward = 0;
 
Pattern[5].turnRight = 0;
Pattern[5].turnLeft = 0;
Pattern[5].stepForward = 2;
Pattern[5].stepBackward = 0;
 
Pattern[6].turnRight = 0;
Pattern[6].turnLeft = 10;
Pattern[6].stepForward = 0;
Pattern[6].stepBackward = 0;
 
.
.
.

In this example, the pattern instructs the computer-controlled character to move forwared 2 distance units, move forward again 2 distance units, turn tight 10 degrees, turn right again 10 degrees, move forward 2 distance units, muve forward again 2 distance units, and turn left 10 deggrees. This specific pattern causes the computer-controlled character to move in a zigzag pattern.

To process this pattern, you need to maintain and increment an index to the pattern array each time through the game loop. Further, each time through the loop, the control instructions corresponding to the current index in the pattern array must be read and executed. Next Example shows how such steps might look in code:

Object.orientation += Pattern[CurrentIndex].turnRight;
Object.orientation -= Pattern[CurrentIndex].turnLeft;
Object.x += Pattern[CurrentIndex].stepForward;
Object.x -= Pattern[CurrentIndex].stepBackward;

As you can see, the basic algorithm is fairly simple. Of course, implementations details will vary depending on the structure of your game.

It's also common practice to encode several different patterns in different arrays and have the computer select a pattern to execute at random or via some other dexision logic within the game. Such techniques enhance the illusion of intelligence and lend more variety to the computer-controlled character's behaviour.

Left out for now.

If you want me to put it in plz tell me.

The trouble using Pattern Movement in physically simulated environmentsis(PSE) that the benefit of PSEs - namely, letting the hysics take control of movement - isn't conducive to forcing a physically simulated object to follow a specific pattern of movement. Forcing a physically simulated aircraft, for example, to a specific position or orientation each time through the game loop defeats the purpos of the underlying physical simulation. In physically simulated environments, you don't specify an object's position explicitly during the simulation. So, to implement pattern movement in this case, you need to revise algorthms we discussed earlier. Specifically, rather than use patterns that set an object's position and orientation each time through the game loop, you need to apply appropriate control forces to the object to coax it, or essentially drive it, to where you want it to go.

You saw in the second example in Chapter 2 how we used steering forces to make the predator chase his prey. You can use thses same steering forces to drive physically simulated objects so that tey follow some pattern. This is, in fact, an approcimation to simulating an inteligent creature at the helm of such a physically simulated vehicle. By applying control forces you essentially are mimicking the behavior of the driver piloting his vehicle in some pattern. The pattern can be anything - evasive maneuvers, patrol paths, stunts - so long as you can apply the appropriate control forces, such as thrust and steering forces.

Keep in mind, however that you don't have absolute control in this case. Hte physics engine and the model that governs the capabilities - such as speed and turning radius among others - of the object being simulated still control the object's overall behavior. Your input in the form of steering forces and thrust modulation, for example, is processed by the physics engine, and the resulting behavior is a function of all inputs to the physics engine, not just yours. By letting the physics engine maintain control, we can give the computer-controlled object some sense of intelligence without forcing the object to do something the physics model does not allow. If you vialoate the physics model, you run the risk of ruining the immersive experience realistic physics create. Remember, our goal is to enhance that immersiveness with the addition of intelligence.

To demonstrate how to implement path movement in the context of physically simulated environments, we're going to use as a basis the scenario we describes in Chapter 2 for chasing and intercepting in continuous environments. Recall that this scenario included two vehicles that we simulated using a simple Box Simulation. The computer-controlled one vehicle, while the player controlled the other. In this chapter, we're going to modify that example.

The approach we'll take in this example is very similar to the algorithms we discussed earlier. We'll use an array to store the pattern information and then step through this array, giving the appropriate pattern instructions to the computer-controlled vehicle. There are some key differences between the algorithms we discussed earlier and the one required for physics-based simulations. In the earlier algorithms, the pattern arrays stored discerte movement information - take a step left, move a step forwars, turn right, turn left and so on. Further, each time through the game loop pattern array index as advanced so that the next move's instructions could be fetched. In physics-based simulations, you must take a different approach, which we discuss in detail in the next section.

As we mentioned earlier, in physics-based simulations you can't force the computer-controlled vehicle to make a discrete step forward or backward. Nor can you tell it explicitly to turn left or right.Instead, you have to feed the physics engine control force information that, in effect, pilots the computer-controlled vehicle in the pattern you desire. Further, when a control force - say, a steering force - is applied in physics-based simulations, it does not instantaneously change the motion of the object being simulated. These control forces have to act over time to effect the desired motion. This means you don't have a direct correspondence between the pattern array indices and game loop cycles; you wouldn't want that anyway.If you have a pattern array that contains a specific set of instructions to be executed each time you step through the simulation, the pattern arrays would be huge because the time steps typically taken in a physics-based simulation are very small.

To get around this, the control information contained in the pattern arrays we use here also contains information so that the computer knows how long, so to speak each set of instructions should be applied. The algorithm works like this: the computer selects the first set of instructions from the pattern array and applies them to the vehicle being controlled. The physics engine processes those instructions each time step through the simulation until the conditions specified in the given set of instructions are met. At that point the next set of instructions from the pattern array are selected and applied. This process repeats all the way through the pattern array, or until the pattern is aborted for some other reason.

The down code shows the pattern control data structure we set up for this example:

    public boolean steer;
    public boolean thrust;
    public float degrees;
    public float unitlength;

Be aware that this control data will vary depending on what you are simulatin in your game and how its underlying physics model works. In this case, the vehicle we're controlling is steered only by bow thruster forces. Thus, these are the only two control forces at our disposal with which we can implement some sort of pattern movement.

Therefore, the data structure contains two boolean members, pThrusterActive and SThrusterActive, which indicate whether each truster should be activated. The next two members, dHeadingLimit and sPositionLimit, are used to determine how long each set of controls should be applied. For example, dHeadingLimit specifies a desired change in the vehicle's heading. If you want a particular instruction to turn the vehicle 45 degrees, you set this dHeadingLimit to 45. Note that this is arelative change in heading and not an absolute orientation. If the flag limitHeadingChange is set to true, dHeadingLimit is checked each time through the simulation loow while the given pattern instruction is being applied. If the vehicle's heading has changed suffiviently relative to its last heading before this instruction was applied, the next instruction should be fetched.

Similar logic applies to dPositionLimit. This member stores the desired change in position - that is, distance traveled relative to the position of the vehicle before the given set of instructions was applied. If limitPositionChange is set to true, each time through the simulation loop the relative position change of the vehicle is checked against dPositionChange to determine if the next set of instructions should be fetched from the pattern array.

Before proceeding further, let us stree that the pattern movement algorithm i am showing you here works with relative changes in heading and position. The pattern instructions will be something such as move forward 100ft, then turn 45 degrees to the left, then move forward anoother 100ft, then turn 45 degrees to the right, and so on. The instructions will be absolute: move forward until you reach position(x,y)0, then turn until you are facing southeast, then move until you reach position(x,y)1, then turn until you are facing southwest, and so on.

Using relative changes in position and heading enables you to execute the stored pattern regardless of the location or initial orientation of the object being controlled. If you were to use absolute coordinates and compass directions, the patterns you use would be restricted near those coordinates. For example, you could patrol specific area on a map using some form of pattern, but you would not be able to patrol any area on a map with the specific pattern. The latter approach, using absolute coordinates, is consistent with the algorithm for tile-based examples. Further, such an approach is in line with waypoint navigation, which has its own merits, as we discuss in later chapters.

Because we're using relative changes in position and heading here, you also need some means of tracking these changes from one set of pattern instructions to the next. To this end, i defined another structure that stores the changes in state of the vehicle from one set of pattern instructions to the next.

Now, to define some patterns, you have to fill in an array of ControlData structures with appropriate steering control instructions corresponding to the desired movement pattern. For this example, we set up three patterns. The first is a square pattern, while the second is a zigzag pattern. In actual game, you could use the square pattern to have the vehicle patrol an area bounded by the square. You could use the zugzag pattern to have the vehicle make evasive maneuvers, such as when Navy ships zugzag through the ocean to make ti more difficult for enemy submarines to attack them with torpedoes. You can define control inputs for virtually any pattern you want to simulate; you can define circles, triangles, or any arbitrary path using this method. In fact, the third pattern we included in this example is an arbitrarily shaped pattern.

For the square and zigzag patterns, i set up two global arrays called patrolPattern and zigZagPattern, as shown next:

ControlData patrolPattern[] = new ControlData[8];
ControlData zigZagPattern[] = new ControlData[4];
 
StateChangeData patternTracking;

As you can see, i also defined a global variable called patternTracking that tracks and changes in position and heading as these patterns get executed.

The next examples show how each of these two patterns is initialized with the appropriate control data. I hardcoded the pattern initialization in this demo; however, in an actual game you might prefer to load in the pattern data from a data file. Further, you can optimize the data structure using a more concise encoding, as opposed to the structure i used here for the sake of clarity.

    /**
     * Initializes our Patterns
     */
    private void initializePatterns(){
        // Patrol Pattern for Square Movement
        // Patrol Pattern for Square Movement
        patrolPattern[0] = new ControlData(false, true, 0, 20);
        patrolPattern[1] = new ControlData(true, false, 90, 0);
        patrolPattern[2] = new ControlData(false, true, 0, 20);
        patrolPattern[3] = new ControlData(true, false, 90, 0);
        patrolPattern[4] = new ControlData(false, true, 0, 20);
        patrolPattern[5] = new ControlData(true, false, 90, 0);
        patrolPattern[6] = new ControlData(false, true, 0, 20);
        patrolPattern[7] = new ControlData(true, false, 90, 0);
 
        // ZigZagPattern for ZigZag Movement
        zigZagPattern[0] = new ControlData(false, true, 0, 10);
        zigZagPattern[1] = new ControlData(true, false, 60, 0);
        zigZagPattern[2] = new ControlData(false, true, 0, 10);
        zigZagPattern[3] = new ControlData(true, false, -60, 0);
    }

As you can see i also invented a new Constructor which is really very easy!

    public ControlData(boolean steer,
                       boolean thrust,
                       float degrees,
                       float unitlength){
        this.steer = steer;
        this.thrust = thrust;
        this.degrees = degrees;
        this.unitlength = unitlength;      
    }

The square pattern control inputs are fairly simple. The first set of instructions corresponding to array element[0] tells the vehicle to move forward by 200 distance units. In this case no steering forces are applied. Note here that the forward thrust acting on the vehicle already is activated and held constant. You could include thrust in the control structure for more complex patterns that include steering and speed changes.

The next set of pattern instructions, array element[1], tells the vehicle to turn right by activating the port bow thruster until the vehicle's heading has changed 90 degrees. The instruction in emelent[2] are identical to those in element[0] and they tell the vehicle to continue straight for 200 distance units. The remaining elements are simply a repetition of the first three. The end result is eight sets of instructions in the array that pilot the vehicle in a square pattern.

Know that i know i only needed 2 of them, but this square is for clarity! The only difference is that you'd have to repeat those two sets of instructions four times to form a square.

The zigzag controls are similar to the square controls in that the vehicle first moves forward a bit, then turns, then moves forward some more, and then turns again.

However this time the turns alternate from right to left, and the angle through which the vehicle turns is limited to 60 degrees rather than 90. The end result is that the vehicle moves in a zigzag fashion.

Now there comes the implementation stuff.

• PatternMovementTest
• PatternController

• The Game AI Page at http://www.gameai.com
• AI Guru at http://www.aiguru.com
• Gamasutra at http://www.gamasutra.com
• GameDev.net at http://www.gamedev.net
• AI-Depot at http://ai-depot.com
• Generation5 at http://www.generation5.org
• The American Association for Artificial Intelligence at http://www.aaai.org