Implementing a Blackboard-like System for Squad-Level Combat AI
Artificial intelligence is fast becoming of primary importance for game developers as graphics hardware becomes faster and more commonplace and programmers begin to have more free processing power with which to make their games smarter and more believable. As a result, there are a large number of different types and styles of artificial intelligence that are being explored in game design terms which previously were thought to be primarily the realm of scientists working in laboratories on supercomputers.
One of these methods is the blackboard system. A blackboard system is one which takes inputs from a number of other artificial intelligence systems, processes those inputs, and then allows each of those systems to contribute their actions or inputs towards a common goal [McManus, 1992; GameAI]. This would be an almost perfect system to use for coordinating intelligent units in a combat situation.
Although this method has been used by major corporations and is currently being marketed as part of several business solutions, it is extremely complex and very difficult to implement from a design perspective; given the already extreme complexity of designing, creating, and managing (not to mention debugging) a game, it has so far been beyond the reach of game designers. AI programmers working on Close Combat [GameAI], for instance, initially intended to use such a system, but the complexity of it outstripped their time and resources. The system that eventually resulted from their labors was almost certainly the best artificial intelligence system to that point ever to grace a squad-level game, but the question of how much better it would have been had they been able to follow their vision is a tempting one. Certainly, the system might have benefited.
In this article, I will deal with the problem of implementing a simple blackboard system for use in a squad-level simulation taking place in real time. This technique is also applicable to the needs of turn-based games, but the designer then would have more freedom to expand the system; a real-time system forces us to constrain ourselves in our use of artificial intelligence, and to optimize as much as possible. Most importantly, however, a real-time system means that our decision-making processes, separate from the meat of the artificial intelligence, must be very fast to better mimic reality and enhance the suspension of disbelief.
The structure of our system is of paramount importance; it will determine whether we, down the road, will be able to extensively modify our system if necessary *without* recoding every part of the system. We can ensure this by introducing a great deal of modularity into the classes and structures that we create. This will also help with debugging and optimization.
The primary pieces of the structure in the implementation explained in this article are as follows: units, contributions, and circumstances. I have delineated the relationship between these different portions below and specified the names by which I will be calling these different components; I will explain them further in a moment.
In this case, Soldier refers to the individual men and women that are being simulated on the battlefield. Squad refers to any grouping of soldiers, large or small - a machine gun crew would be a squad, as well as a full-fledged rifle squad. Platoon refers to a grouping of squads under a central command, and the Commander is the overall decision-maker. Each of these units represents a different artificial intelligence system: Soldiers are finite-state machines (FSM), Squads operate on the principle of fuzzy logic, and Platoons use both fuzzy logic and a higher-order FSM. The Commander in this case is our blackboard system.
Contributions are those pieces of the situational puzzle that are supplied by a particular level of organization. Actions are the simplest. Firing a weapon, walking, and taking cover are all actions: they have a simple definition, they represent a single process of survival for the Soldier, and they are the building blocks for every larger scale maneuver in the game.
Thoughts are a different matter altogether. A thought can be more easily referred to as a strategy; in this case, however, the words "thought" and "strategy" represent different concepts, so keep that in mind. A thought represents something actually running through the mind of a soldier, most likely a squad or team leader. This leader needs to decide how best to react when something happens, like his team or squad being flanked by a large number of soldiers, or when a nearby team moves out to storm a farmhouse.
All of the things that happen during or immediately prior to this period of thought - a large force of enemy soldiers flanks the leader's team, a machine gun opens fire to their front, a friendly team arrives and suppresses the machine gun - all help the leader formulate his plan of action. If the things that happen match (or come close to) something that the leader already has an experience of, and the leader knows what actions will likely keep his team safe, he will attempt to carry out those actions. If this has never happened before, he will need to come up with a new way to react, based on his best guess of what will work. If the new way works, he will remember this experience the next time. If an old way works, he will be more confident in its usage. All of these things are represented in the fuzzy-logic-based squad AI model; read the implementation section for an explanation of how this works.
The combination of fuzzy logic and a high-order finite state machine at the platoon level come into play when the pre-defined actions and objectives available to a platoon leader (attack that hill, retreat, suppress, implement fire and maneuver) are combined with the leader's knowledge of previous situations and the weight he gives to his memory of things that have worked. Whereas a squad would simply process what was going on and make a decision based on what should work best and what orders they are currently under, a platoon leader has a much more vested interest in maintaining simplicity on the battlefield - formations are not just good ways to better engage the enemy, they are good ways to ensure that the platoon leader knows where everybody is. The platoon leader has to deal with a wider area of situational awareness. However, it also does him/her much good to remember past situations and apply them to the present, as real humans do. Therefore, the AI for the platoon leader represents not just a memory of things that worked and objectives, but a desire to maintain as much form and order as possible on the battlefield. A squad leader might not have time to worry about exactly where he is on the battlefield in relation to another platoon; that's not his job. It is, however, the platoon leader's.
The strategies of the Commander, on the other hand, involve not simply making a decision; just giving his troops an objective and then walking away wouldn't be a very effective or efficient way for a commander at the company/task force level to run a battle. Instead, the commander takes what all of his men are telling him (both with their reports (platoons) and with the actions that they take (squads)) and turns that into a successful battle. If, for instance, a platoon has attempted to assault a pair of buildings and the commander notes that two of the squads involved are currently spending their time finding cover rather than attacking, he most likely would decide to support the attacking units with more suppressive fire. If, at the same time an enemy force attacked another of his platoons, however, the commander would likely order the assaulting platoon to withdraw and commit his reserves against the attacking enemy force.
Now, what if the commander has an urgent objective? What if a bridge elsewhere needs to be taken immediately, regardless of loss? The commander, unlike the platoon or squad, has to deal with large numbers of what-ifs. Although certainly applicable, situations are unlikely to completely reproduce themselves for the commander. A squad might face the same type of situation repeatedly. In a fluid battle, this is unlikely to happen to the commander, and it might even be unprofitable for him to waste time thinking about whether or not anything he has done has fit the situation he is currently in.
In addition, more often than not, the people under the commander are not contributing to the overall solution unless the commander has resolved exactly what that solution is. The chances of a unit wasting their time are high; they do not know, nor are they required to know, what else is going on. It is the commander's job to make all of these units work together, and to ensure that a solution a) has been found and b) has a high likelihood of success.
It is in the commander's best interests not to micro-manage; his squad leaders know what they're doing when put in the proper place, and even the actions of his platoons are best controlled by his platoon leaders. However, by formulating and imposing his solution upon these units, rather than by controlling them or giving them direct orders, the units have a *much* higher likelihood of carrying out their duties in a useful manner, and the commander has a much better chance of winning the battle. He needs to tell his troops what to win, not how to win it.
This concept is perfectly represented by a blackboard system; the input from the units flows in, and ideally a solution is produced. This solution involves: a) a list of objectives, b) a list of threats, c) a list of units in trouble, and d) a list of units capable of providing support. How the units go about solving this problem is their own matter - a large number of sub-problems. What the commander does is make sure that they coordinate their actions according to the large problem or, if you will, the "big picture."
Circumstances are simultaneously the most and least important things on the battlefield. A circumstance is anything that is happening that can be defined as a concept - being flanked, being surrounded, having the advantage over visible enemies. These circumstances happen primarily to squads: a platoon may be flanked, but it is more likely that one or two of its squads have been flanked, while the other one or two might be able to maneuver, fire, or extract themselves. Further up in the level of organization, the Commander has little chance of being effected by circumstances. The Commander may not care whether a squad has been flanked. His solution may involve that squad holding its position at all costs. If his solution involves that squad both surviving and attacking a position, he might reformulate the solution to deal with the fact that that squad cannot move, or to deal with the flanking enemy directly. He might, for instance, move that unit up on the priority list of units in trouble, causing other units able to support to move to help. He might also increase the threat level registered for the flanking force. All of these things are not direct orders to his units -- they are changes to the current solution.
Meanwhile, squads and especially soldiers are profoundly affected by circumstances. To use a popular reference, even though the overall strategy of delaying the enemy was for the most part working, the fact that the sniper and his supporting machine gun could not easily displace in the movie Saving Private Ryan meant that they were quickly killed. The battle continued; the commander altered his solution and things worked again for a while. The circumstances that ended the lives of three men had little direct effect on the battle as a whole.
Eventually, of course, circumstances caught up with that commander, and the battle was lost (save for the miraculous arrival of attack planes and a large number of soldiers coming from who knows where). In the end, the commander himself was killed, but by that point, the battle had been lost for several minutes, due to poor circumstances affecting everyone in his command. In a sense the commander himself, when he stopped directing the battle (I would say around the part when he and Matt Damon started using mortar shells like hand grenades), became a soldier and allowed himself to be influenced by circumstance.
A rifleman has no idea what another platoon's machine gun is doing. He knows that there are enemy machine guns in front of him, and that he has little cover. He relies on the squad leader to find the best cover for him, or at best to get him out of the situation, but he also knows that if he lies down flat and tries to hide, he has a better chance of not being shot.
The squad leader, likewise, probably has little idea of the other happenings on the larger battlefield. He knows that he has a good chance of getting his squad to good cover if he moves to the left and into the trees. He relies on the platoon leader to communicate to him what objectives he should be taking. However, the squad leader is also aware that regardless of what needs to be done, his people need cover. (The squad leader's actions then communicate to the Commander that more support is needed in that sector, or that the objective needs to be changed.)
Lastly, the platoon leader is sometimes affected by circumstances - for instance, he himself may discover that he has been flanked. As he is less of an immediate threat than, say, a machine gun, however, it is likely that the enemy will attempt first to destroy his soldiers' ability to fight. The platoon leader relies on the commander to provide him with the information he needs from other units to influence the battle positively.
All of these elements of the AI structure have the ability to come together and form the basis for a very intelligent means of carrying out a battle. If properly implemented, they create a force that is capable of learning from its mistakes, remembering its successes, and acting based on a strategy that takes into account the situation of all forces involved. In the next section, I will explore the implementation of this system.