One of the more welcome outcomes in computer AI is emergent behavior. It is very well suited to control simulated flocks of birds or crowds of people. For our purposes, we will bend the classical definition of emergence to mean behaviors that were not explicitly programmed into individual software agents but are exhibited by a group of interacting agents. Early examples are found in the video Eurythmy produced at the Ohio State University Computer Graphics Research Group [Girard85] and in Craig Reynolds “boids,” used to make Stanley and Stella in: Breaking the Ice [Reynolds87]. Since then, countless others have made use of this technology in movies and games.
The impact of the emergent behavior that arises from simple steering forces is best experienced with animated visual media. The Lord of the Rings movies are so engaging as films that it is difficult to study the computer-generated hordes in motion, but the boids demonstration on Craig Reynolds’ Web site [Reynolds01] is accessible to anyone with a Java-enabled browser. The paper airplane-shaped triangles are not particularly engaging, but the motion they exhibit certainly is. For anyone who has never seen the demonstration, a few minutes watching the motion and a glance at the explanation would be time well-spent.
Emergence is a welcome technology for two main reasons: It looks very realistic, and it can be computationally cheap. Reynolds programmed three simple behaviors into each boid. These behaviors told each boid to stay with its local group, to go where its local group is going, and to avoid getting too close to nearby neighbors. Not only are these behaviors simple, they do not involve the entire flock—just the local group. Because one of the behaviors avoids crowding, it provides a limit to the complexity of the computations required for a single boid, regardless of how high the total number of boids goes.
This computationally cheap algorithm produces lifelike results. The motion is often described as organic or realistic, even when simulated birds are drawn with simple triangles that look more like paper airplanes. Two similar but not identical flocks flying the same route will usually behave visibly—but not wildly—differently. It can be maddening to attempt this level of realism with other AI methods, particularly those with a centralized control mechanism.
While the life-like results are computationally cheap, so are any undesired behaviors. Emergent behavior can be hard to predict, difficult to tune, hard to control, and generally frustrating. The simplicity of the methods can be stymied by complex situations, something demonstrated to anyone who has seen a simple-minded bird trying to escape from the inside of a complex building.
This chapter is devoted to giving our software agents lifelike interactions. While the easiest way to do this is to copy the state of the art, we will examine what goes on under the hood in modest depth. We will use a freeway-simulation project, Cars and Trucks, as an example to illustrate some of the real-world issues that arise. Thankfully, this kind of AI is conceptually simple and rather robust. It even applies to behaviors outside of steering.
In various versions of the Frankenstein story, Dr. Frankenstein pounds his fist or exhorts to the thundering skies, “Give my creature life!” It does not turn out quite like he planned, however. Indeed, in some versions, it appears not to happen at all—at least not at first.
Anyone can make boids flock, but game developers are in the business of creating new and engaging interactions that no one has experienced before. Without a known-good cookbook recipe, a game AI programmer has to traverse uncharted territory in search of good, usable emergent behavior. And of course, completely new software agents do not come with guarantees as to what will emerge when they interact. (Recall that the results Dr. Frankenstein achieved did not meet his goals.)
This creates two critical concerns for AI programmers. The first concern is dealing with their game designer. Much like Dr. Frankenstein, a game designer who demands complete and total control over AI behavior will not gracefully deal with an AI gifted with all of the controllability of a herd of cats. If the designer’s task is to achieve a very specific entertainment experience, he or she may not be able to realize it with these methods. Designers with more leeway bring a more daunting challenge to the AI programmer—hence the AI programmer’s second concern. When this more flexible designer says, “That concept is too cool to leave out. Put it in and we’ll design around it if we have to,” the AI programmer is committed to making it happen. This second concern cannot be overemphasized. Any novel application seeking emergent behavior is a high-risk endeavor. Early prototyping and proof-of-concept work is mandatory. Early winemakers knew that grape juice usually turned itself into wine if they left it alone, but they also knew that sometimes it just went bad.
Fortunately, there are some guiding principles worth examining when there is no recipe. Start with the interactions of simple behaviors, searching for the potentially narrow zone between no results and an unstable system. As part of the search, you may need to carefully explore the interactions not only for balance but also for the right timing.
New systems that resemble existing systems are likely to show similar emergent behavior. Tanks and birds have substantial differences, but tank platoons and bird flocks can benefit from very similar code [VanVerth00]. Steering behaviors for groups of individuals are the poster child for emergent behavior. Besides keeping a group in formation, steering behaviors also excel at obstacle avoidance. Variations on this theme rarely destroy the desired emergent behavior. Failures in behavior are possible, but they tend to be moderately benign and reasonable. Car drivers caught in exit-only lanes are forced to leave the freeway when they do not want to. Game AI that makes mistakes that leave the player thinking, “That could have happened to me...” are more well regarded than AI that makes more unfathomable errors. Not all failures are benign; agents can get stuck, run in circles, or even into walls.
The problem of getting good emergent behavior is harder when the issue at hand does not relate to movement. In computer science, a classic method of attack is to transform a new problem into a better-known problem. If the two problems are truly isomorphic—that is to say, one can be transformed to another without loss of something important—then any reasoning that can be applied to the known problem also can be applied to the new problem.
Here’s an example: Although financial systems and flying birds hardly seem similar, the herd mentality of the stock market is a known phenomenon. Ponzi schemes might be modeled this way: “Some of the birds around me are flying this way. This way appears to be taking us closer to the goal.” As more “birds” (investors) “fly this way” (invest in the scheme), the purported value of their investments rises. The movement of some individuals in that direction attracts more “birds” and further reinforces the appearance of getting closer to the goal. As we have seen in prior chapters, the AI programmer has to be able to visualize the problem at hand in the terms of any particular proposed solution. We will cover these facets in detail.
Emergence comes from interaction of multiple influences. With multiple agents, the multiple influences felt by each agent are typically tied to the other agents. If the influences between agents are going to be meaningful, then clearly the agents need to be able to interact in meaningful ways. In the case of boids, the actions each boid takes change its direction of flight and thus position. All the surrounding boids are paying attention to both properties. The boids see the actions, they act on the actions, and their own reactions cause further actions. Another analogy is nuclear fission. One atom splits and ejects high-speed neutrons. Those neutrons might or might not hit other fissionable atoms. Those atoms might or might not split, yielding more high-speed neutrons. With too little interaction, the reactor is a very expensive warm pile. With the right amount of interaction, large but manageable quantities of usable heat are available to make power. If there is too much interaction, the expensive reactor melts down. So it goes with software agents and emergent behavior; too much or too little interaction will not give desirable results.
To a first-order approximation, a resting herd of buffalo on the prairie resembles scattered boulders in the high grass. Things change when one buffalo spots a hunting predator and gives the alarm. The herd self-organizes spatially, calves heading for larger members of the herd and males interposing between the herd and the threat. The individuals acting on their own interact, giving the herd coherence as a herd. Without interactions between individuals, there would be no herd behavior; as best we can tell, bison do not get instructions from any centralized sources.
Half of a randomly aligned buffalo herd will not see a hunting predator (buffalo ignore wolves that do not appear to be hunting) because they are pointed the wrong way. Their safety depends on actions taken by the rest of the herd. A deaf buffalo will not hear snorts and other signals; unless some action takes place where it is looking, it will not react with the herd. Its failure to react also means fewer cues for it neighbors. A deaf buffalo exhibits inferior individual actions, but it also weakens herd behavior due to its diminished interactions.
There is a chain in all of these examples. It goes like this: Agent A acts, Agent B notices the action, Agent B reacts, Agent A notices the reaction.... Unlike reactors, bison do not seem to have major problems if the chain of herd reactions result in a stampede.
In the Cars and Trucks freeway-simulation project for this chapter, each vehicle pays attention to the lane, speed, and position of the vehicles around it and reacts by changing its speed and/or its selected lane. The simulation moves the cars and trucks every animation frame, so differences in speed create changes in relative position. Thus, the actions taken by each vehicle cause interactions with the nearby vehicles. The agents could be programmed to do many other things, such as select a radio station, but the other agents would ignore these behaviors, and thus they would not cause any interactions.
The basic design for systems that create emergent behavior seems to be, “Toss in a few rules and turn them loose.” This exploits the simplicity of the system and keeps the programmer from investing in code that later proves superfluous. Boids only needed simple behaviors.
Simple behaviors do not always imply that they are simple to code. Simplicity was a design goal for the Cars and Trucks freeway simulator project for this chapter. It has three basic behaviors: The vehicles are not allowed to change lanes into another vehicle, the vehicles prefer the fastest lane possible, starting on the right, and the vehicles try to keep a safe following distance for their speed. Avoiding collisions when changing lanes proves to be relatively easy to implement. Determining the speeds available in nearby lanes is also quite simple.
Establishing a safe following distance is more involved and depends on many factors, however, as we will see in the code. The math for vehicles on a straight section of freeway is far simpler than the math for birds in flight.
When looking for new emergent behavior, start with the simplest interactions. The code should resemble general rules more than a book of moves. It is hard to force emergence, and it can be easy to over-think the problem; tightly scripted behaviors are too organized to allow new behavior to emerge.
Individual goal-directed boids do not compute the most direct path to their goal and take it. They are not striving for optimal behavior; they are settling for reasonable behavior. Optimization drives toward order, fewer choices, and predictability. There is little or no room for new behaviors to emerge when everything that is not mandatory is prohibited. This is fine if the AI is for battle droids marching in lockstep formation, deterred from conforming only by their own destruction. It certainly will not be lifelike. Optimal behavior can be hard or impossible to compute, turning this “close enough is good enough” approach into a virtue.
The flip side of too much order is none at all. If what emerges is to be termed behavior, it needs to have some minimal amount of coherence. Conflicting directives need a rational resolution. If the interaction inputs drown out the agent’s internal checks and balances, the system will probably not be stable. Ponzi schemes eventually collapse, stock-market bubbles burst, and bank runs are stopped by government authorities. If all agents disregard their internal checks and balances, the system crashes. In contrast, a system in which the agents disregard their internal checks and balances to varying degrees might exhibit large swings but on the whole remain stable. Getting the checks and balances right is one of the new challenges presented when dealing with emergent behavior.
The messy middle ground between order and chaos is a hallmark of living things. If we want our agents to have organic credibility, they must also appear to live in this messy middle ground. Programmers and designers who abandon the need for total control may find that emergent behavior gives them the lifelike appearance that they are after. Most people take steps to manage their time and their finances. While nearly everyone knows how they can further optimize their time and their finances, few find that they can comfortably live within the tighter constraints that additional optimization imposes.
The study of complex systems is beyond the scope of this book, but some of the basic ideas from feedback and control systems can be illuminating. Aside from the nuclear reactor example in which the atoms are destroyed, the actors in our examples can act upon the actions in others that were triggered by the original actor. “I do something, you react to it, and then I react to you.” This is known as feedback and is shown in Figure 8.1.
Figure 8.1 has been simplified to show only the feedback. Both agents could have other inputs. Both agents are free to decide what they do with any of the inputs, including ignoring some or all of them. We will ignore those complexities as much as we can. Timing and reinforcement are the key properties of feedback that we need to examine.
In Figure 8.1, if the reaction of Agent A to feedback is to do more of what it did in the first place, this is known as positive feedback. If left unchecked, positive feedback results in chaos or system failure. Reactors melt, bison stampede at full speed into places where going slow or perhaps turning might be prudent, and children act out in ever more outrageous ways. Of course, not all positive feedback is bad; in fact, positive feedback is one of the ways that good ideas get turned into innovation. “That’s a great idea! We should do that!” is positive feedback.
In Figure 8.1, if the reaction of Agent A to feedback is to do less of what it was doing, we call it negative feedback. Your intuitive ideas about positive and negative feedback are probably correct; feedback and control theory examine them in exacting detail. Negative feedback can also be good or bad. “I’d love to go boating, but there are small craft warnings out,” is probably wisdom. “Great idea, none of us has time for it,” has prevented countless innovations from becoming reality. Also called dampening, negative feedback is required to keep systems stable, but too much of it yields the ultimate in order in which nothing happens.
It should be obvious that stable systems need a balance between positive and negative feedback. Boids balance the need to stay with the flock against the need to avoid overcrowding. When designing a stable system with emergent behavior in mind, you should examine the interaction behaviors. Every positive-feedback input is a potential source of instability; it must be balanced in some manner. With a few simple behaviors, it should be easy to prove that the system will find a balance point. As the number of behaviors increases, proof becomes impossibly hard. The programmer is reduced to “flight testing” the system, looking for a stable regime and then programming in guards against excursions outside the stable envelope.
Both kinds of feedback are beneficial in emergent systems. Positive feedback drives emergence, and negative feedback keeps it from going out of control. Hidden in all of this is the effect of timing. How fast should the feedback loops operate? It should come as no surprise that the answer is neither too fast nor too slow, but just right. Our project simulation can provide some concrete insights into timing.
In the military, feedback is known as a decision loop, and the Holy Grail is to have a faster decision loop than the enemy. The idea is that the fast side acts, forcing the slow side to react. The fast side can then turn that reaction into a mistake before the slow side can adapt. If the advantage is extreme, the fast side can avoid destructive force-on-force styles of combat and still defeat the enemy. This works, however, only if the forces of the fast-thinking side are nimble enough to exploit the advantages of thinking faster. Many systems can think faster than they can act.
Faster feedback is not always better. Computer games need to stay at human-compatible speeds. In the case of boids, if the reaction times are too short, the flock will appear to vibrate instead of undulate. Short times imply higher frequencies, and at some point the frequency is too fast for human perception. Shorter feedback loops also carry an inherent disadvantage even if the system would benefit from them. Faster and faster feedback tends to result in decisions with less and less input data, because there is not enough time between decisions to gather enough data. You may need to analyze the data from several cycles of the decision loop to reliably discern any trends. In this case, you also need to determine the minimum number of data points required.
The stock market illustrates this dilemma quite well. Trades can be executed in about a minute. But how long does it take to reliably determine a trend? For a day-trader, five minutes may suffice. For a buy-and-hold, fee-averse investor, the answer may be one quarter or even one year. For the first investor, one hour is an eternity, and for the second investor, one hour is insignificant.
To be effective, feedback loops need to take long enough that real trends can be distinguished from noise. In the case of our software agents, our feedback loops need to take enough time that the agents can meaningfully act in ways that will cause interactions. Games do have an inherent upper limit on effective feedback speed, which we will see shortly when we look at feedback in Cars and Trucks.
Slow feedback loops give rise to plodding systems such as freight trains that often travel for miles before appreciably changing their speed. Technically, the feedback part is fast, but the control part is slow. The train engineer can hit the air brakes or the throttle very quickly, but the train needs time to change speed. For our purposes, we are combining feedback and control for simplicity and because software systems are far less constrained on the control side than physical systems are. If the feedback loop for a flock of boids takes too long, a boid that is too close to its flock mates will fly away from them long enough that it will no longer regard them as flock mates. A boid that is correcting for excess separation may collide with all the other flock mates that are making the same correction.
Slow feedback fights against the interaction needed for emergent behavior to appear. An e-mail exchange would be too slow for use in most games. Instant messaging provides far faster feedback and enables a sense of “being there” to emerge. Face-to-face conversation provides feedback at a rate that encourages a wide range of emergent behaviors.
Fast feedback loops give rise to frenetic systems such as mayflies, constantly darting here and there at the slightest input; slow feedback gives us freight trains. Neither would be satisfactory at controlling an automobile. The timing of the feedback has to be appropriate to the situation. Our project gives a good example to analyze. The physics implementation suggests a minimum think speed, as we shall see.
In the Cars and Trucks simulation, we will have independent control over the frame rate and the AI’s thinking rate. While many games have a single update loop for animation, AI, and game input, others split one or more of them out. We get reasonable animation as low as six frames per second. We get reasonable AI performance at two thoughts per second. The latter number was arrived at by tuning the system after examining the various options.
It makes no sense to have the think rate higher than the frame rate. The vehicles move forward only once per animation frame. The vehicles change lanes and speed every time they think, but they only move when the animation calls for them to move. Thinking faster than the system can react is pointless, as one would expect. In terms of the military decision loop, this is the equivalent of generals pounding their desks in frustration at their slow-reacting forces.
All games have this same upper limit. While you may or may not need to have the AI think at the frame rate, there is never any need to exceed the frame rate. To be more precise, the AI need not think faster than important things change. Most games have animation and physics running in lockstep, so the basic rate of change is the frame rate. Resource-limited mobile games that have small bits of rapid animation but slow overall movement can let the AI slow down to the movement rate. PCs and consoles left such limits behind years ago, making the frame rate the basic change rate.
In Cars and Trucks, thinking almost as fast as the system can react did not prove to be optimal, either. The cars changed lanes too often. We got the mayfly effect. Some dampening was added to the code to make staying in the current lane more acceptable if the car in front was too close but pulling away. In visual terms, all the drivers appear to drive like indecisive maniacs; this might be a reasonable model for some drivers but not for all drivers. Even after dampening the lane changes, fast AI updates made it hard for the user to see what the AI was thinking. The AI graphically shows what it is thinking, and the user can absorb that information only so fast. The simulation would get smoother if the AI ran more often, but the user would have a hard time keeping up with what the AI is doing to each car. Game design can place limits on how fast the AI should react.
A think rate of one thought per second proved slightly slow. The vehicles miss opportunities that go by them as they daydream. This rate was still fast enough to be safe, but the drivers sometimes appeared lethargic, letting openings go by that they could have safely taken. A think rate as slow as one thought every two seconds would have resulted in collisions or the possibility that some vehicles could drive right through other vehicles in their lane. You can replicate the effects of tuning the AI by completing the exercises at the end of the project.
The thinking speed not only has an impact on the AI, it has wider impacts that need to be examined. AI is one part of the game, and all parts must balance. There is give and take available among the major parts of the game; our simulation, as simple as it is, has enough of the right elements to illustrate this.
If the AI can make certain demands of the simulated physics, our simulation never has collisions. Once the code was debugged, collision detection was restricted to the think cycle, not the animation cycle. Given the right physics and a properly working AI, the collision detection can be skipped altogether. This is an engineering decision balancing fun, realism, and computational demand. It would clearly be unacceptable if there were humans driving any of the cars, for example.
Without certain guarantees, collisions could happen any time there is motion, which asks that collision detection be performed every frame. During debugging, collision detection was run every frame. Collision detection is physics, not AI, but in a virtual world everything is under software control. When working properly, our “physics” and AI provide certain guarantees that let us move collision detection out of the animation loop and then make it completely optional. There are three ways a vehicle can collide in our simulation: It can run into the back of a slower vehicle in its lane, it can change lanes directly into another vehicle, or it can change lanes into the path of an oncoming faster vehicle. We will look at the impact of each of these.
Our AI looks forward two seconds’ worth of travel distance at the vehicle’s current speed to see what it might hit in its lane. As long as what passes for physics in our simulation allows the AI to cut the vehicle speed in half before the next second of travel, a given vehicle will not collide when it comes up on a slower vehicle already in its lane, even if that vehicle is at a dead stop. We get a realistic-looking behavior with the fast drivers slowing down over many think cycles as they come up on slow traffic and match speeds while keeping a safe distance. The realism suffers when very high speed vehicles shed an unrealistic amount of speed in the initial braking. If the blocking vehicle is moving at a reasonable rate, this drawback is far less noticeable as the overtaking vehicle smoothly matches speeds. Note that cars can never travel backward in our simulation. They can stop if they have to, but on our freeway they never back up.
Physics can suggest a minimum feedback speed. In our case, a car that halves its speed every second needs one second of travel distance to stop. If you sum the sequence that begins one-half plus one-fourth plus one-eighth..., you get a number that is almost one. So our stopping distance is one second of travel distance, but we also have to factor in reaction time. The car needs to see the obstacle before it can get within one second of travel distance. So the AI must look ahead more than one second, with two seconds travel distance being the minimum. That minimum works only if the AI thinks at least once a second.
Our AI guarantees that it won’t change lanes into another vehicle, avoiding direct side-swipe collisions. In addition, it always makes sure that there is a safety margin of about half a car length of daylight in front and behind before it changes lanes right in front of or right behind another car. Since it only changes lanes to increase or maintain speed, it tends not to change lanes to get behind a slower car that it is now in danger of hitting. This is no help to overtaking drivers a little farther back in the new lane. Giving the overtaking car a full second of clearance would have been much more considerate.
The worst problem area for the simulation is when a slow vehicle changes into the lane of a very-high-speed vehicle. If it cannot change to a clear lane, our fast-vehicle AI needs to dump enough speed to keep it from slamming into the back of the slower vehicle that instantly appeared in front of it. When it happens, it appears unrealistic, even by the admittedly loose standards of our simulation. The slow-vehicle AI could check for more than half a car length of daylight behind it when it changes lanes and not change lanes into the clear zone in front of an overtaking faster car, but the simulation is slanted toward a more entertaining American “My taxes paid for that lane, I’m taking it” style of freeway driving than a German Autobahn style, where pulling into the path of an overtaking car moving at nearly twice your speed is clearly suicidal.
As you might expect, the problem shows up when there are large differentials in speed. Vehicles moving at speed of 50 to 85 pixels per second merely appear rude to each other, but when they interact with vehicles travelling at 120 or 180 pixels per second, it looks more like a death wish. If our rude vehicles were more considerate and gave the overtaking vehicle at least a one-second buffer, we could use the same realistic-appearing deceleration the normal overtake code uses and avoid having the high-speed vehicles conduct panic stops. Our simulation amusingly treads on the physics so that it avoids collisions altogether and so that the AI can think at a more leisurely pace.
To summarize, we actively balance realism, frame rate, fun, and AI think rate. We traded realism to protect frame rate. We could have made the AI more considerate, easing the unrealistic demands on physics, but it is more entertaining to watch the fast drivers stand on their brakes when they get into traffic. In many games, the limits on the amount of CPU available to the AI will place limits on how often it is allowed to think. This is always a potential issue, but with emergent behavior in the mix, it has a direct impact on the limit to feedback speed. Fortunately, as we have seen, slower feedback loops often work better. The point should be emphasized strongly that the real-time constraints the game places on the AI must be carefully considered when tuning the feedback loops that control emergent behavior.
So with the right feedback, we can get the interactions we want between our agents. The simple behaviors are sufficient, and they cause the group to exhibit a pleasing group behavior. All positive feedback is balanced by a negative feedback to keep the system in balance. While we were not striving for flocking behavior, by basing our simulation on similar behaviors, we started with good assurances that we would get a decent group behavior.
Steering behaviors are one very accessible way to exploit emergent behavior. Flocking just looks right. With the proper architecture, we can get emergent behavior in places other than motion control. Consider the Day in the Life project from Chapter 5, “Random and Probabilistic Systems.” Each actor is influenced by up to five inputs (cash on hand plus four pieces of data per job). In the original simulation, the inputs were fixed for every job. There were no pay raises, and the job descriptions never changed. What happens when the jobs begin changing? Will we get behaviors that we did not explicitly plan to get? If the chance of success for crime goes from 30 percent to 59 percent, Barry will give up the stunt show for a life of crime. Getting more criminals when crime is more enticing hardly seems unexpected. Similarly, the numbers for stunt show and day job are “close,” and minor changes will cause Eddy and Barry to change jobs in a predictable manner. How can we get something unexpected?
What happens when we add interactions and some feedback? We could run the simulation for all of our available actors simultaneously, and we could make the jobs and cash change according to what the actors were doing. As soon as the current actions of the actors change the data upon which the same actors base their future decisions, we have created feedback. When the current actions of the actors influence the future decisions of other actors, we have created interactions. What would that give us? Let us look at some examples.
The money that criminals steal ought to come from somewhere. If the money gained by each successful criminal action came from the cash on hand of others, it would slow down or even stop the steady Eddys of our world from ever making it to retirement as a financier. Successful rock stars, lotto winners, and criminals who have moved on to become financiers might have to leave their comfortable life of retirement if large amounts of their cash are stolen all at once. The richest financiers can tolerate a certain steady level of theft if the criminal Carls of the world have their successes spread out over time, but if some criminals got lucky at the same time, it would take the retirees below the minimum level needed to play the market. This still seems predictable.
If the job market itself was influenced by the actions of actors, we could expect waves and trends of activity that would be completely unpredictable. Using simple supply and demand, jobs where the supply of workers is less than the demand for work to be done will see rising wages as employers compete for workers. Jobs with an oversupply of workers will see wages drop. We already know from Chapter 5 that many of our workers are sensitive to the relative wages of the different jobs. The number of various jobs could shrink and grow, and the values used to define every job could change with every tick of the simulation. For example, entertainment jobs such as stunt show and rock star might be more sensitive to the average level of cash on hand in the population than day job or financier; a well-off population has discretionary money available for entertainment, and a struggling population does not. The simulation might get stuck if the interactions are heavily dampened, or it might become unstable if positive feedback loops are not balanced by negative influences. The basic architecture has each actor acting on four outside and one inside influences; with some feedback it is reasonable to predict that we could get emergent behavior from the system. We expect the job market part of the simulation to exhibit emergent behaviors driven by the actors. As written for Chapter 5, the actors are heavily optimized for specific behaviors. Some of the actors and some of the jobs are “close” in terms of how easy it is to get an actor to give up his or her expected job if another job changes slightly, but the bulk of the system is meant to be stable. Along with the feedback, a richer set of actors and a richer set of jobs may be required to get a critical mass of interactions. It certainly appears plausible that with a few changes, we could get the job market part of the simulation to give us emergent behavior.
This example illustrates the critical concerns with emergent behavior. Since we do not have running code, we do not know if we will get emergent behavior at all. We think that we can get it, but we cannot predict if we will like what emerges. Even if we like it, the architecture offers little guidance as to how we will control it or tune it. Experience from Chapter 5 suggests that some numbers and some equations will be more sensitive to change than others. That experience also suggests that we will see substantial run-to-run variations in the outcomes. That variation causes a particular fear for AI programmers; what if the players play the game differently from how it was tested, and a new and utterly inappropriate behavior emerges after the game ships? The fact that other AI techniques can exhibit a similar vulnerability is a small consolation.
Good emergent behavior gives the illusion of higher-order organization and coordination than are actually present. The method can be very cheap to program and is robust. The results typically have lifelike qualities that would be extremely difficult to achieve using other methods.
The drawbacks to emergent behavior tend to relate to the unknowns. Game designers and quality-assurance staff tend to place a very high value on control and predictability. Neither group will be pleased if the herd of water buffalo wanders out of the mouth of the ravine and makes itself unavailable for a stampede that would kill the evil tiger that the player has lured into place. The unknowns increase if the envisioned system is far from what others have done before; the AI programmer does not know if he or she will obtain good emergent behavior until after the system is programmed.
The Cars and Trucks project differs from a typical flocking implementation in that the vehicles are not expected to stay in a flock. The desired speeds of our vehicles cover a wide range—from 50-pixels-per-second trucks to 180-pixels-per-second exotic cars to the barely subsonic 600-pixels-per-second collision test vehicle. The player controls the number of available lanes as the simulation runs. Because the vehicles that have identical desired speeds are reasonably separated, as long as there are two or more lanes available, the vehicles eventually sort by speed as you would expect. Realistic group behavior results; the exotic car can get stuck in the slow lane when it attempts to pass on the right and fails to make it to a gap in time. When the 55-pixels-per-second truck passes the 50-pixels-per-second truck on a two-lane road, the rest of the convoy bunches up and jockeys for the best lane position. If the player adds three extra lanes, the really fast cars cannot clear off until the cluster of four bikes doing between 80 and 90 sort themselves out enough to clear an open lane. When the head of a line of cars gets an opening, the line behind accordions very realistically as the cars hold off on acceleration until the gap in front of them starts to open safely, as shown in Figure 8.2.
The simulation starts with the vehicles in a single lane. Those behind the truck start dangerously close together, forcing them to drop to a low speed. The upper lane was added a few frames before the screenshot was captured. The vehicles that change to the upper lane do so at a speed in the low 40s. In the upper lane, the Coupe leads, and with nothing ahead of it quickly makes it to its desired speed of 60. With a stable speed, it has a white background. Behind it is Bike C at a speed of 48 and climbing. The dark backgrounds of Bike C and Bike D are green when seen in color. Bike D can only accelerate when Bike C starts pulling away, so Bike D is at a speed of 44 and climbing. The 60-48-44 sequence of speeds shows the accordion effect as acceleration in vehicles ahead makes for increased clearance, calling for acceleration in the current vehicle.
As seen in Figure 8.2, our vehicles will be drawn as boxes using Label and TextBox controls. The position of a vehicle is the leading edge of the box. Inside each box is a number showing the current speed of the vehicle. The box will have a white background if the AI did not change speed the last time it thought. If the AI slowed down, the background will be reddish; if the AI accelerated, the background will be greenish. Projecting in front of each vehicle is a headlight—a narrow beam that projects forward two seconds’ worth of travel distance at the current speed. This is similar to the feelers or probes often seen in flocking demos. The vehicle ignores anything ahead of it beyond the reach of the headlight. Above each box is the vehicle’s name and its desired speed. All vehicles have a length, in pixels. (The bikes are too long, but a shorter bike body will not hold a two-digit number.) The sport and the exotic vehicles are the minimum size to hold a three-digit number.
Alongside the road is a “pixel marker,” equivalent to a mile-marker road sign. You can see it above the scrollbar and below and between Bike B and Truck in Figure 8.2. When the simulation is running, the display is centered on a reference vehicle, which is Bike B in Figure 8.2. The marker goes flying by at the equivalent of the road speed of the reference vehicle. When the marker falls off the left edge, it is redrawn at the right. The vehicles travel left to right; a wide-format monitor enables you to see more of them.
Position is stored in absolute pixels. This makes the motion and display math easy to understand. In each animation frame, the vehicles are moved and then drawn. For movement, the internal position of the vehicles is updated according to their speed in pixels per second, and the frame rate in frames per second. Lane changes take place on AI think time, not animation time. To draw, the three labels that make up a vehicle have their Top property set according to the selected lane and their Left property set to a value reflecting the vehicle’s relative position to the reference vehicle. Setting properties of labels and text boxes is rather rudimentary, but it is sufficient for our animation needs.
Two timers are used to control the AI and the animation. (Do not expect this method to be commonly used in commercial games.) The AI timer typically fires every half second to run the AI code. The animation timer typically fires 6 to 12 times a second, depending on the desired frame rate. This gives us the equivalent of complex, multi-threaded game code without the coding complexity. Performance will depend on the number of vehicles, but it will also depend greatly upon whether the code is run in the debugger or as an independent executable. In the code, comments identify the core five vehicles needed for initial testing. Using all 14 will have a speed impact on the simulation. Debugging statements, when turned on, will have a serious impact on speeds. A particularly fast computer is not required. (This book was written on an eight-year-old computer with dual 1.2GHz Athlon MP processors and 2GB of RAM running numerous background server processes at all times.)
The code has two parts: the road and the vehicles. We will develop both of them together. First we will put some cars on the road; then we will animate them. The last thing we will do will be to make them think.
The code uses LineShape controls to mark the edges of the pavement. These controls are part of the Visual Basic PowerPack, a free download from Microsoft. It is available at http://msdn.microsoft.com/en-us/vbasic/bb735936.aspx. Check the Toolbox window in Visual Basic to see if you already have the controls installed. If you do not have them and you do not want to download the PowerPack, the project will operate properly without the two lines. Simply do not add them when called for and do not add any code that manipulates them. The text will note these optional additions.
Launch Visual Basic and create a project called CarsAndTrucks. Then follow these steps:
Change the name of Form1.vb file to Road.vb. Set its Text property to Cars and Trucks.
Resize the form. 1,050 × 300 is a good size. Depending on your monitor width, you may want to unpin the Solution Explorer or the Toolbox to gain width. Wider is better.
Double-click My Project in Solution Explorer. Go to the Compile tab and set Option Strict to On. Option Strict turns off silent type conversions that could fail and forces us to make them explicit. Being mindful of type conversions as we write the code helps prevent bugs.
Save all. Do this on a regular basis as we go.
Add a class to the project and call it Vehicle.vb. Our vehicles will keep a modest amount of data, most of which will be private. To start with, we will want to be able to create a vehicle and draw it. We start with the data that each vehicle needs. Add the following code to the Vehicle class.
Public Const VehicleWidth As Integer = 20
'We keep most of the vehicle data private.
Private myName As String
'Speeds are in pixels per second.
Private myDesiredSpeed As Integer
'Length is in pixels.
Private myLength As Integer
'Use floating point so that we can accumulate fractions.
Private Xpos As Double = 0
Private myLane As Integer = 1
'Actual speed in pixels per second.
Private currentV As Integer
'Visually, a vehicle is two Label controls and a TextBox control.
'We want to react when the body is clicked, so it is WithEvents.
Dim WithEvents Body As TextBox
Dim HeadLights As Label
Dim NameTag As Label
Most of the data that a Vehicle class object stores will be known when the vehicle is created. The New() function will have many parameters, so we have a certain amount of work to do to create our vehicles. Add the following code to the class:
'Create a vehicle.
Public Sub New(ByVal length As Integer, ByVal desiredSpeed As Integer, _
ByVal parent As Road, ByVal X As Integer, ByVal V As Integer, _
ByVal callMe As String)
'Store the basic data.
myName = callMe
myDesiredSpeed = desiredSpeed
currentV = V
Xpos = X
myLength = length
'Create our three controls.
Body = New TextBox
HeadLights = New Label
NameTag = New Label
'Not moving? Side of the road please.
If desiredSpeed <= 0 Then
'Only signs have no speed.
NameTag.Visible = False
myLane = 0
End If
'Put the controls on the form.
Body.Parent = parent
HeadLights.Parent = parent
NameTag.Parent = parent
'Get their sizes right. (Note that the
'width of a vehicle is height on a control;
'our vehicles are sideways on the form.
Body.Height = VehicleWidth
HeadLights.Height = VehicleWidth 4
'The same way that vehicle length turns into
'control width.
Body.Width = length
HeadLights.Width = 2 * desiredSpeed
'Auto-size the name tag.
NameTag.Text = myName & ":" & desiredSpeed.ToString
NameTag.AutoSize = True
'Color them.
Body.BackColor = Color.White
HeadLights.BackColor = Color.Transparent
NameTag.BackColor = Color.Transparent
'Outline them or not.
Body.BorderStyle = BorderStyle.FixedSingle
HeadLights.BorderStyle = BorderStyle.FixedSingle
NameTag.BorderStyle = BorderStyle.None
'Tweaks for the body since it is a TextBox control.
Body.TextAlign = HorizontalAlignment.Center
Body.ReadOnly = True
'Put us on the map.
Me.Draw(-200)
End Sub
The careful eye will have noticed that the code for the width of a headlight uses a backslash () instead of a forward slash (/) when dividing by 4. The backslash is an integer divide with fractions truncated. The result does not need type conversion when assigned to an integer variable. We want narrow headlights, and we do not care if they are one pixel narrower than rounding would call for.
Also worth noting is that our road is sideways. That means we have to deal with the fact that height on the form turns into the width of our vehicles. The length of our vehicles is the width of the controls that draw them. The drawing code will also have to keep this transformation in mind. We will have our class speak in terms of X position and vehicle length to avoid confusion.
The development environment will complain about Me.Draw(-200) because we have not added that chunk of code. The —200 value will make more sense when we see the positions we use to place the initial vehicles on the road. Without the draw call, all the controls would wind up in the top-left corner of the form. This way, we can take a glance at our starting data before things move. Add the following code to the class.
Public Sub Draw(ByVal offset As Integer)
'Headlights go out twice our speed.
HeadLights.Width = 2 * currentV
'Position us in the proper lane.
Body.Top = VehicleWidth * (10 - 2 * myLane)
'Headlights same as the body.
HeadLights.Top = Body.Top
'Name tag above the body.
NameTag.Top = Body.Top - NameTag.Height
'And at the right spot along the way.
'Everything gets the offset.
'Body is a Label control. Its width is our
'vehicle's length. Our right edge is at X, so
'our left is our length further back.
Body.Left = Me.X - Body.Width - offset
'Headlights have their left edge at our position.
HeadLights.Left = Me.X - offset
'Center the name tag.
NameTag.Left = Body.Left + Body.Width 2 - NameTag.Width 2
'Show how fast we are going.
Body.Text = currentV.ToString
End Sub
This code deals with the sideways road, but it needs help from the class in terms of the X position. Our virtual world is one of integer values, usually in terms of pixels, made possible by our flat, 2D simulation. We use a floating point value to store position so that we can accumulate fractions of a pixel of motion because our frame rate and speeds do not always divide evenly. Aside from that, everything is integer pixels, so we will provide a function that converts our floatingpoint position to the closest integer. While we are doing that, we will provide the rest of the functions used to get read-only access to the internal data of the vehicle. Add the following code to the Vehicle class.
Public Function ID() As String
Return myName
End Function
'Where along the road is it?
Public Function X() As Integer
Return CInt(Xpos)
End Function
'How fast am I going?
Public Function Speed() As Integer
Return currentV
End Function
'How long is my car?
Public Function Length() As Integer
Return myLength
End Function
'What lane am I in?
Public Function Lane() As Integer
Return myLane
End Function
That gives us a good start on vehicles. We can test the code by adding some code to the Road form to create a few vehicles. We need to change our focus from the Vehicle class to the Road form. View the code of the Road.vb and add the following code:
#Region "Public Stuff"
'A place to keep our car collection.
Public ToyBox As New Collection
#End Region
Private Sub Road_Load(ByVal sender As System.Object,_
ByVal e As System.EventArgs) Handles MyBase.Load
'Keep this list in sorted X order, ascending.
'(length, desired speed, parent, X pos, initial speed, name)
'The barely subsonic vehicle for crash testing (250 is a
'more realistic top speed).
ToyBox.Add(New Vehicle(35, 600, Me, -3025, 50, "F1+"))
'To get serious speed differences.
ToyBox.Add(New Vehicle(35, 180, Me, -1025, 50, "Exotic"))
'Various fast bikes.
ToyBox.Add(New Vehicle(30, 95, Me, -605, 50, "Bike F"))
ToyBox.Add(New Vehicle(30, 90, Me, -545, 50, "Bike E"))
ToyBox.Add(New Vehicle(30, 85, Me, -485, 50, "Bike D"))
'Also shows good speed differences.
ToyBox.Add(New Vehicle(35, 120, Me, -425, 50, "Sport"))
ToyBox.Add(New Vehicle(30, 80, Me, -365, 50, "Bike C"))
'These five make good initial test vehicles.
ToyBox.Add(New Vehicle(30, 75, Me, -305, 50, "Bike B"))
ToyBox.Add(New Vehicle(45, 60, Me, -240, 50, "Coupe"))
ToyBox.Add(New Vehicle(200, 50, Me, 0, 50, "Truck"))
ToyBox.Add(New Vehicle(45, 60, Me, 70, 50, "Sedan"))
ToyBox.Add(New Vehicle(30, 80, Me, 120, 50, "Bike A"))
'A two-truck slow pass up ahead.
ToyBox.Add(New Vehicle(200, 55, Me, 1000, 50, "Truck"))
ToyBox.Add(New Vehicle(200, 50, Me, 1400, 50, "Truck"))
End Sub
Now we are ready to test. We have created numerous vehicles with widely varying capabilities. (Feel free to comment out vehicles to make things simpler as you debug your code.) We keep all of the vehicles in the toy box so that we have them in one convenient place. We keep the toy box sorted so that the AI and collision detection can run a great deal faster. If a given vehicle is not hitting the vehicle directly in front of it, it could hardly be hitting any vehicle in front of both of them. We will have to sort the toy box every time we want to go through it in order, but the sort should be quick because the list retains a great deal of order between sorts. Run the code in the debugger. You should see something resembling Figure 8.3.
If you look at the X positions we loaded and hunt for the —200 value in the list, you will see that there is a 200-pixel-long truck located at X=0. On the left side of the form, we see the tail end of that truck at —200. The —200 number we fed to the initial Draw() calls in New() was picked for this reason. We get a static view. If we extend the size of the form, we can see the two trucks up ahead, but there is no way to see the convoy of vehicles behind. They would be a lot easier to see if they were moving.
We loaded all the vehicles at a speed of 50 pixels per second. Without any AI, they cannot change speed. If we did not put any of them on top of another, we can defer collision detection until after we get them to move.
We will program in a variable frame rate. Each frame, every vehicle, starting from the front, is moved forward by its speed in pixels per second divided by the frame rate. Floating-point math keeps track of fractions for us, giving us some freedom in setting the frame rate. The upper limit to frame rate will depend on the particulars of your system. After moving everything, we draw it in its new place. Animation frames are initiated by a timer. We will start with the user-interface elements. Switch to the Design view of Road.vb; then follow these steps:
A glance at Figure 8.2 may be helpful as you place controls. Drag a Label control from the Toolbox to the upper-right corner of the form. Change its Name property to FpsLabel. Change the Text property to FPS. Change the Anchor property to Top, Right. This label will show how fast our animation actually runs.
Drag a Button control from the Toolbox to the lower-left corner of the form. Change its Name property to StartButton. Change its Text property to Start. Change its Anchor property to Bottom, Left. This button will start the simulation.
Drag another Button control from the Toolbox and place it next to the Start button. Change its Name property to StopButton. Change its Text property to Stop. Change its Anchor property to Bottom, Left. This button will stop the simulation.
Drag a Timer control from the Toolbox onto the form. When you let go, it will jump to the bottom of the editing pane. Timers have no visible user interface elements, so they are held at the bottom. Change the Name property of the timer to AnimationTimer.
Drag another Timer control to the form. Change its Name property to ThinkTimer. We do not need it to move the vehicles, but we want it on the form so that we do not have to revisit some of the code we are about to write.
Drag a HScrollBar control from the Toolbox to the bottom-right corner of the form. Change its Name property to PanScrollBar. Change the Small-Change property to 10. We will resize it later, after the rest of the controls are on the form.
Drag a Label control to the form and place it to the right of the Stop button. Change the Name property to RefLabel.
We need to track some data if we are going to compute the frame rate. We also need to set the frame rate. Once we do that we can turn on the Start and Stop buttons and ask our vehicles to move. Switch to the Code view of Road.vb and add the following code inside the class:
'Some constants we can tweak.
Dim FrameRate As Integer = 6
Dim ThinkRate As Integer = 2
'We need a start time to compute frame rate.
Dim startTime As Date
Dim framecount As Integer
Private Sub StartButton_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles StartButton.Click
'Store values for computing frames per second.
startTime = Now
framecount = 0
'Initialize and enable animation.
AnimationTimer.Interval = CInt(1000 / FrameRate)
AnimationTimer.Enabled = True
'Initialize and enable AI.
ThinkTimer.Interval = CInt(1000 / ThinkRate)
ThinkTimer.Enabled = True
'Don't show FPS when running.
FpsLabel.Visible = False
'Do not scroll when running.
PanScrollBar.Enabled = False
End Sub
Private Sub StopButton_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles StopButton.Click
'Stop animation and AI.
AnimationTimer.Enabled = False
ThinkTimer.Enabled = False
'Compute frames per second.
Dim stopTime As Date = Now
Dim min As Integer = stopTime.Subtract(startTime).Minutes
Dim secs As Integer = stopTime.Subtract(startTime).Seconds + 60 * min
'Avoid a divide by zero.
If secs < 1 Then secs = 1
'Compute the rate and show it.
FpsLabel.Text = Format((framecount / secs), "0.0") & " FPS "
FpsLabel.Visible = True
'Allow scrolling.
PanScrollBar.Enabled = True
End Sub
The buttons turn the timers on and off. They also disable and enable the scrollbar. Once we get the vehicles moving, we will switch from a static ground view of the vehicles going by to a vehicle-relative view so that we can stay with a particular vehicle. We need to ask the vehicles to move because they hold their position values internally. Switch to Vehicle.vb and add the following code:
Public Sub MoveForward(ByVal FrameRate As Integer)
Xpos += currentV / framerate
End Sub
What remains is to ask the vehicles to move when the animation timer fires. Switch back to the code for Road.vb and add the following code:
Private Sub AnimationTimer_Tick(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles AnimationTimer.Tick
Dim Toy As Vehicle
'Increment drawn frames.
framecount += 1
Dim offset As Integer = CInt(Me.Width / 2)
'Move them forward and draw
For Each Toy In ToyBox
Toy.MoveForward(FrameRate)
'Track the reference vehicle when we get it.
Toy.Draw(-offset)
Next
'Our floating marker will need to move when we put it in.
End Sub
Before we run the code, a word or two about timers, frame rate, and performance is in order. The timers we use have a maximum resolution of 55 milliseconds. This has an impact on how well the system can deliver the desired frame rate. Running the code in the debugger will not help matters. Our two timers will interact; the animation may lose smoothness when the AI runs. While the VB code itself is reasonably fast, changing the positions of controls using the native Windows desktop is a known choke point. The Microsoft DirectX technology exists for this very reason. These timers should give reasonable performance at our low frame rates. These timers do provide a number of concrete benefits to the beginning AI programmer. These are the simplest timers available. They let us control the think rate and the frame rate independently. We do not have to deal with threading issues or the need to write a time-locked core graphics loop.
We will add more to this code later as indicated by the comments. Run the code in the debugger. Start and stop the simulation and note the frame rate. Aside from rounding and the occasional glitch, it should stay near six frames per second. Change the frame rate to something very high, such as 60, and run again. The animation should be much smoother, but note that it does not run at 60 frames per second. If you run the executable outside of the debugger, the maximum frame rate will improve. Although the most demanding modern games strive for 60 frames per second, numbers in the 9 to 12 range are good enough for our purposes. The original Quake had a design goal of staying above 10 frames per second. When running the code in the debugger, six frames per second gives the system enough time to output any debugging data that you might need. If need be, reduce the number of vehicles to the five core vehicles mentioned in the code and retest. In any case, do not place extreme concern on the frame rate.
Let us switch from the ground view to a vehicle-relative view. When we do this, we will need a ground feature to indicate how fast we are going, so we will implement a sign at the edge of the road. Add the following code to the Road class.
'Who are we tracking?
Private refVehicle As Vehicle
'Let's have a mile marker go by.
Dim FloatingMarker As New Vehicle(2, 0, Me, 0, 0, "Floating Marker")
Now we can draw relative to the reference vehicle. We will set the reference vehicle later, but we can change the animation timer code to its final form now. Find the following line in the animation timer event handler:
Toy.Draw(-offset)
Change that line to read as follows:
Toy.Draw(refVehicle.X - offset)
Just below that code is a comment about the floating marker. Add the following code below the comment.
'Move the floating marker and draw.
FloatingMarker.MoveFloatingMarker(refVehicle, FrameRate, offset)
FloatingMarker.Draw(refVehicle.X - offset)
We will update the Vehicle class to implement the code needed to move the floating marker later. For now, we will stay with the Road.vb file.
Find the Public Stuff region and add the following code. We want to be able to click on a vehicle to make it the reference vehicle, so the Vehicle class will need a way to tell the form that a vehicle got clicked.
Public WriteOnly Property ReferenceVehicle() As Vehicle
Set(ByVal value As Vehicle)
refVehicle = value
RefLabel.Text = refVehicle.ID
End Set
End Property
Find Road_Load, the form’s Load event handler, and add the following code to it after the code that adds the last vehicle. At startup, the reference vehicle is the middle one.
'The middle vehicle is our starting reference vehicle.
Me.ReferenceVehicle = CType(ToyBox(1 + ToyBox.Count 2), Vehicle)
Switch to Vehicle.vb. We need to handle the floating marker, and we need to react if the user clicks a vehicle to make it the reference vehicle. Add the following code to the class:
Public Sub MoveFloatingMarker(ByVal refV As Vehicle, _
ByVal Framerate As Integer, ByVal halfSize As Integer)
If refV.Speed = 0 Then Return
'Markers appear to go backward.
Xpos -= refV.Speed / Framerate
'After it falls off the back end, put it back on the front.
While Xpos < refV.X - halfSize
Xpos += 2 * halfSize
End While
'If the user changed the refV, the marker may be too far ahead.
While Xpos > refV.X + halfSize + 1
Xpos -= 2 * halfSize
End While
End Sub
'Let the user tell us which car to follow.
Private Sub Body_Click(ByVal sender As Object, _
ByVal e As System.EventArgs) Handles Body.Click
Dim theRoad As Road = CType(Body.Parent, Road)
theRoad.ReferenceVehicle = Me
End Sub
Run this code in the debugger. Notice that on the first animation frame, the view jumps from —200 to center on the reference vehicle. Click a vehicle and watch the view center on that vehicle. You can walk up and down the chain this way. Below the vehicles, you can see the marker fly by at 50 pixels per second.
Now we will finish adding the final user-interface elements. While we have not yet added the AI, we can predict that the richness of the interactions will be greatly enhanced if we can have more than a single lane. Take a glance at Figure 8.2 and then switch to the Design view of Road.vb.
Drag a Label control to the form and place it to the right of the RefLabel. Change the Text property of the new label to Lanes.
Drag a NumericUpDown control next to the new label. Resize the control and make it smaller because it has to display only a single-digit number. Change the Name property to LanesUpDown. Change the Maximum property to 5 and the Minimum property to 1.
Enlarge the PanScrollBar control so that it takes up all of the rest of the available space.
If you have the PowerPack, drag a LineShape control to anywhere on the form. Change its Name property to FastLineShape. Drag another LineShape control to the form and change its Name property to SlowLineShape.
Switch to the Code view of Road.vb and locate the Public Stuff region. The AI will want to ask the form how many lanes there are. Add the following code to the region:
'Tell others how many lanes.
Public Function Lanes() As Integer
Return CInt(LanesUpDown.Value)
End Function
If you have the PowerPack and added the two LineShape controls to the form, add the following code to the form:
Private Sub Road_Resize(ByVal sender As Object, _
ByVal e As System.EventArgs) Handles Me.Resize
'Get the slow line into place.
SlowLineShape.X1 = 0
SlowLineShape.X2 = Me.Width
SlowLineShape.Y1 = Vehicle.VehicleWidth * 19 2
SlowLineShape.Y2 = SlowLineShape.Y1
'Get the fast line into place (it moves).
FastLineShape.X1 = 0
FastLineShape.X2 = Me.Width
FastLineShape.Y1 = Vehicle.VehicleWidth * 19 2 - _
2 * Vehicle.VehicleWidth * Lanes()
FastLineShape.Y2 = FastLineShape.Y1
End Sub
Private Sub LanesUpDown_ValueChanged(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles LanesUpDown.ValueChanged
'The AI can think for itself. The fast lane stripe needs our help.
Call Road_Resize(Nothing, Nothing)
End Sub
If you added the lines, run the code in the debugger and change the number of lanes. The fast line should respond correctly to the number of lanes specified by the control. The slow line should be in place half a car width below the line of cars. If you did not add the lines, there will not be any visible effect until we add the AI.
As a precursor to the AI, we need to add some helper code to the code in Road.vb. We will add two routines: one to sort the cars and another to check for collisions. A side effect of sorting the cars is that we can figure out how to set the scrollbar so that when the simulation is stopped, we can scroll around and see all the vehicles. Add the following code to Road.vb:
'The AI and the collision detection need a sorted list.
Private Sub SortToys()
Dim swapped As Boolean = True
Dim Behind As Vehicle
Dim Ahead As Vehicle
'This is the sorting loop.
While swapped
swapped = False
Dim i As Integer
For i = 1 To ToyBox.Count - 1
'The back has a lower subscript.
Behind = CType(ToyBox(i), Vehicle)
'The front has a higher subscript.
Ahead = CType(ToyBox(i + 1), Vehicle)
'Are they out of order?
If Ahead.X < Behind.X Then
'The one we thought should be ahead is not;
'we need to swap them.
swapped = True
'Debug.WriteLine("*** " & Behind.ID & _ " has passed " &
Ahead.ID)
ToyBox.Remove(i + 1)
ToyBox.Add(Ahead,, i)
End If
Next
End While
'Grab the leader and trailer to set the scrollbar.
Behind = CType(ToyBox(1), Vehicle)
Ahead = CType(ToyBox(ToyBox.Count), Vehicle)
'The world is half a form bigger on each side of the pack.
Dim offset As Integer = CInt(Me.Width / 2)
'The slow vehicle sets the minimum.
PanScrollBar.Minimum = Behind.X - offset
'The fast vehicle sets the maximum.
PanScrollBar.Maximum = Ahead.X - offset
If refVehicle IsNot Nothing Then
'Get the value right.
PanScrollBar.Value = refVehicle.X - offset
End If
'This more properly belongs on the resize event.
PanScrollBar.LargeChange = Me.Width 4
'Protective code to check that our code works OK.
Call CollisionDetect()
End Sub
'Run any time the list is sorted.
Private Sub CollisionDetect()
Dim Toy As Vehicle
'The bag holds groups of vehicles by lane.
Dim Bag As New Collection
'We use myBag to access one of those groups.
Dim myBag As Collection
Dim key As String
For Each Toy In ToyBox
'Convert the lane to a string so that we can
'use it as a key.
key = Toy.Lane.ToString
If Not Bag.Contains(key) Then
'This is the first one in that lane we've seen.
'Create the group.
Bag.Add(New Collection, key)
End If
'Get my group out of the bag...
myBag = CType(Bag(key), Collection)
'...and put me in it.
myBag.Add(Toy)
Next
'Since we started with a sorted ToyBox, all
'the groups have to be sorted.
Dim Behind As Vehicle
Dim Ahead As Vehicle
Dim i As Integer
For Each myBag In Bag
For i = 1 To myBag.Count - 1
'Grab two vehicles.
Behind = CType(myBag(i), Vehicle)
Ahead = CType(myBag(i + 1), Vehicle)
'My nose is ahead of your nose, so if my tail is
'behind your nose, we conflict.
If Ahead.X - Ahead.Length &= Behind.X Then
Debug.WriteLine("###### COLLISION: " & Behind.ID & _
" is hitting " & Ahead.ID)
End If
Next
Next
End Sub
The code needs to be called to be effective. We will call it when the ThinkTimer ticks. To see that it is working, we will turn on the scrollbar. Add the following code to Road.vb:
Private Sub ThinkTimer_Tick(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles ThinkTimer.Tick
'Passing happens; we need this to think, not to draw.
Call SortToys()
'Real AI code goes here.
End Sub
Private Sub PanScrollBar_Scroll(ByVal sender As System.Object, _
ByVal e As System.Windows.Forms.ScrollEventArgs) Handles _
PanScrollBar.Scroll
'Redraw at our new place.
Dim Toy As Vehicle
For Each Toy In ToyBox
Toy.Draw(PanScrollBar.Value)
Next Toy
End Sub
Run this code, making sure to start the simulation. Let it run a second or two and then stop the simulation. The scrollbar should allow you to scroll back to the F1 + vehicle way in the back. Going the other way should take you to the lead truck. The call to SortToys() also calls CollisionDetect(). The AI needs the sort, so we must sort before the AI runs because the animation moved the vehicles, and they could have been passing each other. However, when debugging, you can call the sort after every animation frame to make sure that everything works and no collisions have taken place. Be sure to watch the Immediate window for debugging output; the collision message will go there.
It is time to add that real AI code promised by the comment in the ThinkTimer Tick event handler. Replace that comment with the following code:
'Now do the AI.
Dim Toy As Vehicle
Dim i As Integer
'Debug.WriteLine("Thinking...")
'Run the AI, front to back.
For i = ToyBox.Count To 1 Step -1
Toy = CType(ToyBox(i), Vehicle)
Toy.Think(i, Me)
Next
We need to switch to the Vehicle.vb file to get the vehicles to think. The AI will need a variety of helper functions. The AI is interested in what vehicle is ahead of or behind it. The vehicles also have a limit to how hard they can accelerate. That limit allows high acceleration from low speed and lower acceleration when the vehicle is near its desired speed. The formula used is a simplification of actual acceleration curves. As you might expect, trucks have too much low-end pickup, and the exotic vehicles have too much high-speed charge. That said, even this token nod toward realism gives the right impression. Add the following code to the Vehicle class:
'Institute acceleration limits.
Public Function BestNextSpeed() As Integer
'Acceleration drops with speed.
Dim a As Integer = CInt(0.1 * (2 * myDesiredSpeed - currentV))
'But even the slowest truck can do 1.
If a < 1 Then a = 1
Dim newV As Integer = currentV + a
'Don't go faster than desired.
If newV > myDesiredSpeed Then newV = myDesiredSpeed
Return newV
End Function
'Who is ahead of me in a given lane?
Private Function CarAhead(ByVal desiredLane As Integer, _
ByVal myIndex As Integer, ByVal theRoad As Road) As Vehicle
Dim i As Integer
Dim OtherGuy As Vehicle
For i = myIndex + 1 To theRoad.ToyBox.Count
'Ahead of me in the lane we are checking.
OtherGuy = CType(theRoad.ToyBox(i), Vehicle)
If OtherGuy.Lane = desiredLane Then
Return OtherGuy
End If
Next
Return Nothing
End Function
'Who is behind me in a given lane?
Private Function CarBehind(ByVal desiredLane As Integer, _
ByVal myIndex As Integer, ByVal theRoad As Road) As Vehicle
Dim i As Integer
Dim OtherGuy As Vehicle
For i = myIndex - 1 To 1 Step -1
'Behind me in the lane we are checking.
OtherGuy = CType(theRoad.ToyBox(i), Vehicle)
If OtherGuy.Lane = desiredLane Then
Return OtherGuy
End If
Next
Return Nothing
End Function
Now that the AI can get answers about the cars around it and the capabilities of the vehicle itself, it is time for the AI to do some thinking. The AI has two parts. The first part picks the best speed from the available choices. It depends on the part that computes the best speed in a given lane.
'The next two are where the AI lives.
Public Sub Think(ByVal myIndex As Integer, ByVal theRoad As Road)
'Find the best lane:
'Which lane is fastest for me?
'Look from right to left.
Dim newlane As Integer = myLane - 1
'No lane is this bad:
Dim newspeed As Integer = -100
Dim i As Integer
'Go through up to three lanes.
For i = myLane - 1 To myLane + 1
'Don't let cars below lane 1.
If i > 0 Then
Dim otherspeed As Integer = SpeedInLane(i, myIndex, theRoad)
If otherspeed < newspeed Then
newspeed = otherspeed
newlane = i
End If
End If
Next
'Color based on speed changes.
If currentV = newspeed Then Me.Body.BackColor = Color.White
If newspeed > currentV Then Me.Body.BackColor = Color.LightGreen
If newspeed < currentV Then Me.Body.BackColor = Color.Pink
'Execute the decisions.
currentV = newspeed
myLane = newlane
End Sub
Private Function SpeedInLane(ByVal somelane As Integer, _
ByVal myIndex As Integer, ByVal theRoad As Road) As Integer
'Want some daylight between our bumper and bumpers in other lanes.
Dim CUTOFF_BUFFER As Integer = 21
'Does the lane exist?
If (somelane > theRoad.Lanes()) Or (somelane & 1) Then
'Debug.WriteLine(Me.ID & " checking lane " & somelane.ToString & _
' " which does not exist.")
Return 0
End If
'If it's not our current lane, we have to prevent side swiping
'a car in the other lane whose nose is behind our nose.
Dim BlindSpot As Vehicle = CarBehind(somelane, myIndex, theRoad)
If somelane & myLane Then
'Only if there is somebody in that lane behind me.
If BlindSpot IsNot Nothing Then
'Will I hit them? Add some padding to prevent
'cutting them off.
Dim tail As Integer = Me.X - Me.Length - CUTOFF_BUFFER
'If they are behind me and my tail is behind their nose,
'I'll hit them.
If tail & BlindSpot.X Then
'Debug.WriteLine(Me.ID & " sees that lane " & _
' somelane.ToString & " is blocked by " & BlindSpot.ID)
Return -1
End If
'Are we thinking about being rude?
'I could change this to 1x their speed and actually
'decline the lane, but we'll just cut them off instead.
tail += CUTOFF_BUFFER - BlindSpot.Speed * 2
If tail & BlindSpot.X Then
'Debug.WriteLine("++++" & Me.ID & " considers cutting off " & _
' & BlindSpot.ID & " in lane " & somelane.ToString & ".")
End If
End If
End If
'Is there anyone in front to worry about?
Dim OtherGuy As Vehicle = CarAhead(somelane, myIndex, theRoad)
If OtherGuy Is Nothing Then
'Debug.WriteLine(Me.ID & " finds lane " & somelane.ToString & _
'" is open for an available speed of " & BestNextSpeed().ToString)
Return BestNextSpeed()
Else
'Will we hit his tail end? (Should never happen in our own lane.)
If myLane <> OtherGuy.Lane Then
Dim tail As Integer = OtherGuy.X - OtherGuy.Length - _
CUTOFF_BUFFER
If tail < Me.X Then
'Debug.WriteLine(Me.ID & " sees that lane " & _
' somelane.ToString & " is blocked by " & OtherGuy.ID)
Return -1
End If
End If
End If
'The lane is usable. How fast is it?
'We like a distance that is numerically equal to twice our speed.
Dim deltaX As Integer = OtherGuy.X - Me.X - OtherGuy.Length
Dim matchSpeed As Integer = deltaX 2
'Is the other guy faster than we are?
'This is not worth changing lanes over - only applies in our
'lane. Not checking this in other lane dampens maniacal lane
'switching so we only switch into a lane with non-compromised
'clear distance ahead. In our lane, we'll take a compromise if
'it is safe.
If OtherGuy.Lane = Me.Lane Then
'If he's pulling away we don't slow down
If OtherGuy.Speed > Me.Speed Then
If Me.Speed > matchSpeed Then
matchSpeed = Me.Speed
End If
End If
'Is the other guy a nutcase?
If OtherGuy.Speed > myDesiredSpeed Then
'He's going faster now than we want to go, ignore him
'and floor it.
matchSpeed = myDesiredSpeed
End If
End If
'Go to match speed if we can and if we want that much.
If matchSpeed > BestNextSpeed() Then matchSpeed = BestNextSpeed()
'Debug.WriteLine(Me.ID & " can do " & matchSpeed.ToString & _
' " in lane " & somelane.ToString & " behind " & OtherGuy.ID)
Return matchSpeed
End Function
At this point, you should give the code a thorough thrashing. If your code misbehaves, there are numerous debug messages commented out that can be turned on. Some of them are split over multiple lines for readability, so you will need to uncomment all the lines involved. The easiest way is to select the lines using the mouse and then click the Uncomment button in the toolbar. Look at how the vehicles behave in tight groups and then open another lane and watch how they react. Watch an inbound, high-speed unit slow and match speed over many seconds. If you reduce the number of lanes, the cars in the closed lane come to a screeching halt and then dart into traffic as soon as they get an open window ahead of them, often cutting off oncoming cars. All sorts of accordion behaviors can be demonstrated. In a two-lane situation with the fast lane at 55 pixels per second and the slow lane at 50 pixels per second (easily arranged with the two leading trucks), you can watch the last car in the slow lane change lanes after the faster line gets past, which in turn keeps the slow line pinned to the slow lane until the new last car in the slow line can make the same maneuver.
Is any of this emergent behavior? Who really cares? Much of the behavior here can be deduced by studying the AI code of the individual agents. But some of the patterns, such as accordion speed changes and fighting for a newly opened fast lane, are not directly programmed in. In any case, the method gives realistic-looking (if somewhat rude) behaviors quite cheaply—the hallmarks of emergent behavior. Consider how hard it would be to orchestrate the same behaviors with a top-down, coordinated approach. As a thought problem, try to see if you can define these behaviors without resorting to using terms equivalent to the interactions of independent agents. Forcing these formations would be hard; letting them happen is simple.
Emergent behavior yields realism at a low run-time cost, especially when applied to group movement. More innovative uses will require exploration and tuning to achieve the maximum effectiveness of the method, but even these efforts are quite reasonable. AI built this way tends to degrade gracefully in the face of overly constraining circumstances, but it is not free of its own set of peculiarities. Every AI programmer considering these methods should keep in mind the unpleasant behaviors seen when a real bird gets trapped in an unfamiliar environment.
Answers are in the appendix.