OO Analysis and Design Tips

  • General overview
  • Meaning of great software:
    • First, develop software that the customer needs and satisfy requirements
    • Second, apply basic OO principles to add flexibility (OOD)
      • Like duplicate code
      • Bad class design
    • Third, strive for maintainable, reusable design (DP)
  • Object Characteristics:
    • Objects should do what their names indicate: if I’m a plan I shouldn’t contain method GetTicket
    • Each object should represent a single concept: like ball! This could be basketball of football
    • Unused properties are dead giveaway:
      • If you have a field that is rarely has values. Why this property is a part from this object?
  • OOD:
    • Keep your objects well encapsulated
  • Design Pattern:
    • When try to edit your code you should modify the min number of classes
    • With min number of code lines!
    • Explain the principle Loosely Coupled Objects:
      • Separation of objects jobs so each one do its task separately and independently
  • Customers/Programmer Golden Rules:
    • Customers are satisfied when their apps work
    • Customers are satisfied when their apps keep working
    • Customers are satisfied when their apps upgraded
    • Programmers are satisfied when their apps reused
      • (Open-Closed-Principle (OCP) & Single-Responsibility-Principle (SRP))
    • Programmers are satisfied when their apps flexible -> Software Architects
  • Notes:
    • Encapsulation is breaking your application is logical parts
    • Find parts that could change and separate them from the stable parts
  • Gathering Requirements
  • What exactly is a requirement?
    • It’s a specific thing your system has to do to work correctly
  • When you are coming to requirements best thing to do is “let the customer talk”
    • Take care of what the system should do rather than how to do it
  • Make sure that the system could work although unexpected errors appear
  • After understanding the system and determine requirements, think under negative thinking
  • What is Main path and alternative path? What are the differences bettween them?
  • Requirements Should meet:
    • Ensure that the system works like customer expect
    • Covers all steps in the use cases
    • Use your use cases to recover point ur customers didn’t tell you
  • Characteristics of good use case:
    • Starting Condition
    • Stopping Condition
    • External Initiator
    • Clear Value
  • Chapter # 3:
    • Rules # 1: The customer is always right: D
    • Chapter keywords:
      • Scenario
  • Chapter # 4:
    • Your software should work in real world not perfect world
    • Analysis helps you ensure your system works in a real world context
    • Analysis Steps:
      • Identify the problem
      • Plan a solution
    • Delegation shields your objects from implementation changes to other objects in your software
    • Textual Analysis:
      • Looking at the nouns ( and verbs) in your use case to figure out classes and methods
    • Verbs in the use case are usually methods inside classes
    • Keywords:
      • Real-world context, peal-world context, Textual Analysis, Association
  • Chapter # 5:
    • Good design = flexible software
    • Keywords: Abstract Class, concrete, generalization, aggregation
    • Rule: Always favor coding to the interface not the implementation
    • Using a Map Data Structure to store variable properties
    • cohesive class: class that does one thing really well and doesn’t try to do or be something else
    • Keywords: cohesive class
  • Chapter # 7:
    • Commonality
    • Variability
  • OO Tips:
    • Avoid duplicate code
    • Objects should be loosely coupled:
      • objects are independent on each other
      • Change of an object doesn’t require bench of changes to other objects!
    • Classes shouldn’t store living things unless the system is going to store long-term information about them
    • Class Diagram Helps:
      • If there’s a mistake you can figure out it before writing actual code and fix it in the drawing
    • Using a Map Data Structure to store variable properties
    • Most good designs come from analysis of bad designs
    • It’s not recommended to add a new class with a constructor only!
    • To test your software flexibility:
      • How many classes did you have to add?
      • How many classes did you have to change?
  • OO Principles:
    • Encapsulate what varies
    • Always favor coding to the interface not the implementation
    • Each class has one responsibility

The more cohesive your software is, looser the coupling between classes

MACROS

What is a macro?

Let us start with a somewhat simple-minded example of a macro (not to be emulated in any real project):

#define SquareOf(x) x*x

It defines a kind of function which, used in an actual piece of code, looks exactly like any other function call:

double yout,xin=3;
yout = SquareOf(xin);

As we shall see in a moment, the problem is that SquareOf only pretends to be a function call, while it is really something completely different.

The formal syntax of a macro is:

#define name(dummy1[,dummy2][,…]) tokenstring

The symbols dummy1, dummy2, … are called dummy arguments (as usual, square brackets indicate optional items). There are a few additional rules such as that the macro can extend over several lines, provided one uses a backslash to indicate line continuation:

#define ThirdPowerOf(dummy_argument) \
dummy_argument \
*dummy_argument \
*dummy_argument

How does a compiler handle a macro?

What makes a macro different from a standard function is primarily the fact that a macro is a scripted directive for the compiler (rather than a scripted piece of run-time code) and therefore it gets handled and done with at compilation time rather than at run time.

When the compiler encounters a previously defined macro, it first isolates its actual arguments, handling them as plain text strings separated by commas. It then parses the tokenstring, isolates all occurrences of each dummy-argument symbol and replaces it by the actual argument string. The whole process consists entirely of mechanical string substitutions with almost no semantic testing!

The compiler then substitutes the modified tokenstring for the original macro call and compiles the resulting code script. It is only in that phase that compilation errors can occur. When they do, the result is often either amusing or frustrating, depending upon how you feel at the moment. You are getting mysteriously looking error messages resulting from the modified text and thus referring to something you have never written!

Example 1:

#define SquareOf(x) x*x

void main() {


int Test = 3;

cout << Test << endl;

cout << SquareOf(Test) << endl;

cout << SquareOf(Test + 4) << endl;

cout << SquareOf(Test + Test) << endl;

}

Intuitively, you probably expect the output of this program to be:

3

9

49

36

What you actually get, however, is this:

3

9

19

15

Before you conclude that computers are stupid and become a farmer, consider what has happened. When the compiler met the string “SquareOf(x+4)”, it replaced it with the string “x*x” and then replaced each of the dummy-argument-strings “x” by the actual-argument-string “x+4”, obtaining the final string “x + 4*x + 4” which, in fact, evaluates to 18 and not to the expected 49. Likewise, it is now easy to work out the case of SquareOf(x + x) and understand why and how the result differs from the expected one.

The problem would have never happened if SquareOf(x) were a normal function. In that case, in fact, the argument xin+4 would be first evaluated as a self-standing expression and only then would the result be passed to the function SquareOf for the evaluation of the square.

Actually, none of the two ways is wrong. They are just two different recipes on how to handle the respective scripts. Given the formal similarity between the macro function call to a standard function call, however, the discrepancy is dangerous and should be removed. Fortunately, there is a simple way to do so. Replacing the original definition of the SquareOf macro by

#define SquareOf(x) (x)*(x)

the problem vanishes because, for example, the macro-call string “SquareOf(x+4)” is transformed into “(x)*(x)” and then into “(x+4)*(x+4)” which evaluates exactly as intended.

Example 2:

#define Sum(x, y) (x) + (y);

void main() {

int x = 20;

int y = 15;

int sum = Sum(x, y);

cout << sum << endl;

}

Output:

35

Example 3:

Macro can be expression

#define IsXGreaterThanY(x, y) {if ((x) > (y)) (x) = (y);}

void main() {

int x = 20;

int y = 15;

IsXGreaterThanY(x, y);

cout << x << endl;

cout << y << endl;

}

Output:

15

15

References:

http://www.ebyte.it/library/codesnippets/WritingCppMacros.html#2

http://en.wikipedia.org/wiki/C_preprocessor

Introduction to Game AI

  • It is a common mistake to think that the more complex the AI in a game, the better the characters will look to the player. Creating good AI is all about matching the right behaviors to the right algorithms
  • Knowing when to be complex and when to stay simple is the most difficult element of the game AI programmer’s art. The best AI programmers are those who can use a very simple technique to give the illusion of complexity
  • You need to make sure that a characters’ AI matches their purpose in the game and the attention they’ll get from the player
  • Perceptions should only be what exactly AI character need not more
  • Take care of changing behaviors (2 solders conversion example – 63)
  • For in-game AI, behaviorism is the way to go. We are not interested in the nature of reality or mind; we want characters that look right. In most cases, this means starting from human behaviors and trying to work out the easiest way to implement them in software
  • Developing Game AI Could Use:

    • Hacks: ad-hoc solutions and neat effects
    • Heuristics: rules of thumb that only work in most, but not all, case
    • Algorithms (the "proper" stuff)
  • Developers rarely build a great new algorithm and then ask themselves, "So what can I do with this?" Instead, you start with a design for a character and apply the most relevant tool to get the result
  • Some if the AI doesn’t require an algorithm or a technique it only requires a simple bit of code that performs an animation at the right point
  • Human beings use heuristics all the time. We don’t try to work out all the consequences of our actions. Instead, we rely on general principles that we’ve found to work in the past (or that we have been brainwashed with, equally)
  • Problems with heuristics all the time: range units when shooting peons (65)
  • Common Heuristics:

    • Most constrained

      • For example, a group of characters come across an ambush. One of the ambushers is wearing phased force-field armor. Only the new, and rare, laser rifle can penetrate it. One character has this rifle. When they select who to attack, the most constrained heuristic comes into play: it is rare to be able to attack this enemy, so that is the action that should be taken
    • Do the most difficult first

      • For example, an army has two squads with empty slots. The computer schedules the creation of five Orc warriors and a huge Stone Troll. It wants to end up with balanced squads. How should it assign the units to squads? The Stone Troll is the hardest to assign, so it should be done first. If the Orcs were assigned first, they would be balanced between the two squads, leaving room for half a Troll in each squad, but nowhere for the Troll to go
    • Try the most promising first:
  • Hacks and heuristics will get you a long way, but relying on them solely means you’ll have to constantly reinvent the wheel. General bits of AI, such as movement, decision making, and tactical thinking, all benefit from tried and tested methods that can be endlessly reused (use algorithms here)
  • Just remember that for every situation where a complex algorithm is the best way to go, there are likely to be at least five where a simpler hack or heuristic will get the job done
  • One of the major reasons that new AI techniques don’t achieve widespread use is their processing time or memory requirements
  • Processor Issues in Game AI:

    • Complex AI that does work in games needs to be split into bite-size components that can be distributed over multiple frames. The chapter on resource management shows how to accomplish this. Applying these techniques to any AI algorithm can bring it into the realm of usability
    • SIMD:

      • Most modern CPUs have dedicated SIMD processing. SIMD (single instruction multiple data) is a parallel programming technique where a single program is applied to several items of data at the same time
      • Steering algorithms benefit from this feature
    • Multi-Core Processing and Hyper-Threading:

      • Modern processors have several execution paths active at the same time. Code is passed into the processor, dividing into several pipelines which execute in parallel. The results from each pipeline are then recombined into the final result of the original code. When the result of one pipeline depends on the result of another, this can involve backtracking and repeating a set of instructions. There is a set of algorithms on the processor that works out how and where to split the code and predicts the likely outcome of certain dependent operations; this is called branch prediction. This design of processor is called super-scalar
      • Normal threading is the process of allowing different bits of code to process at the same time. Since in a serial computer this is not possible, it is simulated by rapidly switching backward and forward between different parts of the code.
      • A multi-core processor effectively has multiple separate processing systems (each may be super-scalar in addition). Different threads can be assigned to different processor cores
    • Virtual Functions/ Indirection

      • Virtual functions add flexibility to the code but it’s very costly
  • Memory Concerns:

    • Cache:

      • If processors had to rely on the main RAM, they’d be constantly stalled waiting for data
      • All modern processors use at least one level of cache: a copy of the RAM held in the processor that can be very quickly manipulated. Cache is typically fetched in pages; a whole section of main memory is streamed to the processor. It can then be manipulated at will. When the processor has done its work, the cached memory is sent back to the main memory.
      • In my experience (author), dramatic speed ups can be achieved by making sure that all the data needed for one algorithm is kept in the same place
  • PC Constraints:

    • If the AI gets less time to work, how should it respond? It can try to perform less work. This is effectively the same as having more stupid AI and can affect the difficulty level of the game. It is probably not acceptable to your quality assurance (QA) team or publisher to have your game be dramatically easier on lower specification machines
  • Develop your AI code to be an AI Engine that could be reused
  • Try to develop tools that can generate you AI Code ( as in steering behaviors)
  • AI-Implant’s Maya module, for example, exposes complex Boolean conditions, and state machines, through graphical controls

Introduction to AI

  • What is AI?
  • Many of trivial problems ( playing Connect 4) were solved by computers but there are many things that computers aren’t good at which we find trivial: recognizing familiar faces, speaking our own language, deciding what to do next, and being creative. These are the domain of AI: trying to work out what kinds of algorithms are needed to display these properties
  • In academia, some AI researchers are motivated by philosophy: understanding the nature of thought and the nature of intelligence and building software to model how thinking might work. Some are motivated by psychology: understanding the mechanics of the human brain and mental processes. Others are motivated by engineering: building algorithms to perform human-like task. Where game developers concerns with the last motivation
  • History of Academic AI:

    • The Early Days:

      • In the early days (before computers) some questions appeared (in philosophy of mind) as:

        • What produces thought?
        • Could you give life to an inanimate object?
        • What’s the difference between cadavers (جثة) and human it previously was?
      • Pioneers of the field these days were: Alan Turing (father of AI), von-Neumann, Shannon
    • The Symbolic Era:

      • From 1950s till 1980s main thrust in AI research was in "symbolic" systems
      • A symbolic system: is one in which the algorithm is divided into two components (as Expert Systems):

        • Set of knowledge: represented as symbols such as words, numbers, sentences, or pictures
        • Reasoning algorithm: that manipulates those symbols to create new combinations of symbols that hopefully represent problem solutions or new knowledge
      • Other symbolic approaches in games: blackboard architecture, pathfinding, decision trees, state machines, steering algorithms
      • Common disadvantage of symbolic systems: when solving a problem the more knowledge you have, the less work you need to do in reasoning
      • The more knowledge you have, the less searching for an answer you need; the more search you can do (i.e., the faster you can search), the less knowledge you need
    • The Natural Era:

      • From 1980s to 1990s frustration symbolic approaches come into two categories:

        • From engineering point:

          • early success on simple problems didn’t seem to scale to more difficult problems
        • From philosophical point:

          • Symbolic approaches are not biologically plausible (i.e. You can’t understand how a human being plans a route by using a symbolic route planning algorithm)
          • The effect was a move toward natural computing: techniques inspired by biology or other natural systems (like ANN, GA and simulated annealing)
  • The no-free-lunch theorem and subsequent work has shown that, over all problems, no single approach is better than any other
  • The narrower the problem domain you focus on, the easier it will be for the algorithm to shine. Which, in a roundabout way, brings us back to the golden rule of AI: search (trying possible solutions) is the other side of the coin to knowledge (knowledge about the problem is equivalent to narrowing the number of problems your approach is applicable to)
  • Game AI:
  • Till 1990 all computer-controlled characters used FSM
  • In 1997 the new technique included was ability to see colleagues and notify them when killed
  • In mid-1990s RTS games (Warcraft II) was the first time popular game having robust pathfinding implementation
  • The AI in most modern games addresses three basic needs:

    • The ability to move characters,
    • The ability to make decisions about where to move
    • The ability to think tactically or strategically
  • Model of Game AI:

  • Movement:

    • Movement refers to algorithms that turn decisions into some kind of motion
    • Examples (49):

      • Super Mario example when attacking enemies with bullets
      • Guard that want to reach alarm example
  • Decision Making:

    • Involves character working out what to do next
    • Examples: take the decision to attack, defend, patrol…
  • Strategy:

    • To coordinate whole team you need a strategic AI
    • In the context of this book, strategy refers to an overall approach used by a group of characters
    • In this category are AI algorithms that don’t control just one character, but influence the behavior of a whole set of characters
    • Example: surrounding a player in FPS Game
  • Infrastructure:

    • These are Information Gatherer (perception) and execution management issues
  • Agent-Based-AI:

    • agent-based AI is about producing autonomous characters that take in information from the game data, determine what actions to take based on the information, and carry out those actions
  • Techniques in this book are implemented into 3 categories: Algorithms, Data Structures, Game Infrastructure
  • Key elements to know when implementing algorithms:

  • Know the problem the algorithm want to solve
  • A general description of the working mechanism of the algorithm including diagrams
  • A pseudo-code presentation of the algorithm
  • Indication to the data structure used in the algorithm
  • Particular implementation node
  • Analysis of the algorithm performance: execution speed, memory footprint and scalability
  • Weaknesses in the approach

Common AI Development Concerns

  • Designing Issues:
  • Data-Driven AI System:

    • Data-Driven primitive Levels: animations, behaviors and strategies
    • Designers could build animations themselves
    • Data-Driven system doesn’t improve AI engine but supplies its degree of organization
    • Be sure that you are not driving data for areas that are better with code solutions
    • Rule of Thumb Here:

      • Create reusable, simple primitives that allow users to build more complex objects
  • The One-Track-Mind Syndrome:

    • The problem is that AI programmer apply one AI technique on all AI problems in the game
    • Most error here: "State Machines are all you need!"
    • Every AI technique is suitable for particular input and under particular game conditions
    • You can use FSM for basic layout of the game, FuSM for main short decision layer, a simpler planner to run your pathfinding and long term decision making layer , and a scripting system to drive your animations
  • Load of Details (LOD):

    • LOD might entail (handle AI details between various levels):

      • Off-screen and faraway: characters are completely non-exist for human player
      • Off-screen and close: characters can’t be seen but the human player might still hear them
      • Very far-off: character is visible a pixel or two
      • Far-off: characters are visible as solid colors but no real details yet (you can differentiate between truck and car)
      • Medium: this distance would be your true area of sight
      • Close: anything closer than medium
      • Interaction: the character is interacting directly with the player someway
    • If characters are in off-screen faraway then we can forgot about real obstacle avoidance
    • There could be LOD systems for your engine that determines the current level of detail
    • Areas under human sight could be updated thirsty times per second and far-away area could be 3/2 times
    • Scientist example (page 647)
    • LOD in RTS Game (page 648)

      • Buildings and mining will be statistically determined (without moving peons)
  • Helper AI:

    • Some areas still benefit from AI techniques as:

      • User Interface
      • AI Advisors
      • Automated Testing Systems

        • Testing Areas:

          • Limits Testing: testing values around of system’s capabilities
          • Random Testing: uses completely random input to the system
          • Smart Testing: real-game play techniques are applied
  • General AI Thinking:

    • Determine the goals of your AI controller
    • Brainstorm about how to solve these problems
    • Talk with AI staff about each proposed solution you have got
    • Coining the solutions in a small prototype (like AIsteroids)

      • Here you have 80% of the solution the rest 20% will be discovered in the code
    • Think in fuzzy with your colleagues
  • Always differentiate between good programming and programming for sake of goodness
  • Consider novelty in your AI Engines (like MOHAA when you throw grenade on them they pick up it and throw it back)

Stupid AI could do: Rules Enemy, Bad Pathfinding, Non-Contextual Enemy, Oblivious Enemy