* Preface ** Educating the Nintendo generation ** Mining the past for the future * [no game] Getting Started ACM CC2007: History, ethical and social context of computing (1/5 hours) How programs execute (0.75/1 hour) Basic von Neumann architecture Instructions Fetch-decode-execute cycle ** TODO Remake drawings - using black and nicered ** Definition of games *** A game is a set of components interacting according to a set of rules ** Two classes of components *** Passive *** Active **** Rules followers are active components ** Definition of strategy *** A set of rules for interacting with a game ** Definition of a computer program *** [sidebar] von Neumann *** Defnition of a computer **** Memory - stores components and rules ***** von Neumann's genius: both rules and components are in memory ***** Some rules are components for other, higher-level rules ***** What something means depends on what _type_ it has **** CPU(s) - follows rules, updates state in components **** I/O devices - permits user interaction with the program *** A program is a set of components (some defined by the language, some defined by the programmer) interacting according to a set of rules - Note: Can you distill the gamemaster example down to a three-part loop? (I am sure you can) Displays abstraction (the removing of details, creation of general solutions); also introduces the three part loop (which we'll see again in the next chapter). * [PlayingCard] Your First Program ACM CC2007: History, ethical and social context of computing (0.5/5 hours) How programs execute (0.25/1 hour) Basics of compiling, loading, and running programs ClownFace ** ClownFace *** No such thing as a game without selection. *** Constructing components. *** Designing a program ** Java (Using the command-line; this avoids using a given IDE) *** Definition of syntax **** Java class template *** Compiling *** Running *** Virtual Machine and History of Java ** Why use a framework *** Java = large + flexible *** large + flexible = complex *** Video games and tutorial levels *** Video game editing websites *** Framework mediates complexity **** Uses abstraction **** Much modern software development uses library (framework) code **** Student focuses on one thing at a time ** Introduction to FANG *** Freely-available **** Open source **** Free (Beer) **** Free (Speech) *** [sidebar] Open Source Software *** Networked **** Networked games *** Game Engine **** What is a game engine *** Structure of a FANG program **** public void setup() ** Screen coordinates *** RectangleSprite **** Constructing a new object *** Layers and adding sprites to a scene ** Introduction to Sprites *** OvalSprite *** StringSprite *** ImageSprite *** PolygonSprite ** Transformation ** Get the Picture ** TODO Summary ** TODO Templates *** class *** comments **** single-line **** multi-line **** JavaDoc *** setup method **** @Override annotation *** local variable declaration *** new ** TODO Review Exercises ** TODO Problems *** Fish *** Movie Camera *** Bull *** Cat * [NewtonsApple] Deciding What Happened: Making Choices NewtonsApple ACM CC2007: History, ethical and social context of computing (1/5 hours) How programs execute (0.25/1 hour) Basics of compiling, loading, and running programs Basic programming constructs (1/8 hours) Variables Types and classes Conditionals ** Introduction to NewtonsApple *** Fetch-decode-execute *** Video game loop **** Display **** Get input **** Update state ** Game design *** Design is problem solving *** Techniques in rules **** Sequence **** Selection **** Iteration **** Delegation **** Abstraction ** TODO Summary ** TODO Template *** class *** declaration *** method *** comment ** TODO Review Exercises ** TODO Problems *** Hockey variant *** Computer player variant *** Billiards? * [EasyDice] Components: Names, Types, Expressions EasyDice Rework example to simplify naming of classes and to move the actual "rolling" action down into the die class. Make a simple game which just rolls dice when button is pressed. A little design, a lot of syntax ACM CC2007: Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Sequential control flow Conditionals Iteration Anatomy of a class (1/6 hours) Data available to a method Design and implementation of simple classes Software development (0.5/5 hours) Analyzing problem statements, designing for users, software design, testing Concepts of procedural abstraction ** EasyDice *** Address gambling sensibilities *** Explain rules *** Explain what dice do: **** What is a public interface **** Constructor **** set/get value **** roll **** isRolling **** advance *** Dice roller "game" **** Use the die public interface to just roll when button pressed **** Challenge: Make it roll twice per button push and display results in StringSprite ** Components *** All Java components have _types_ **** A type determines the public interface of the component: what it provides **** A component can have a name to make it easier to ask for services **** A type is a blueprint, an instance is a house ***** All pawns follow the same rules ***** The white pawn at A3 is NOT the rules for all pawns ***** Blueprint/house *** Java has two types of types: objects and POD **** Objects, types named with initial capital letters, require construction **** POD, types named with initial lowercase letters, don't *** Java expressions evaluate to components **** Simple arithmetic expressions **** Simple boolean expressions ** Variable declaration *** Lifetime/scope *** Declaring a name **** Names have types **** type name; - standard form ***** type of thing ***** name of thing ***** this is used in almost every declaration in Java *** Assigning to a name **** Names have values *** Names for Java components are labels **** Object names are references ** Objects *** Construction **** new places an order **** parameters determine customization **** constructor uses blueprint (class definition) to create component **** Java doesn't care if you keep track of object or not **** Garbage collection *** Invoking methods on an object **** Need a reference to the object **** Available methods are determined by the type of the object *** null ** Primitive types *** No constructors *** No "null" value *** Literals *** int (there are others) *** double (there are others) *** char *** boolean *** WHY? **** Efficiency *** String **** Literals ** Using Java Documentation *** Finding types and interfaces ** Naming Conventions *** Names for things (variables) are nouns *** names for methods (the things we ask objects to do) are verbs *** names for interfaces (next chapter) are descriptions or adjectives *** names for classes are more general nouns or adjective-noun phrases ** Finishing EasyDice ** TODO Summary *** Simple top-down design of methods *** Types **** POD **** Objects *** Variable declaration **** Scope **** Parameters ** TODO Templates *** Field declaration *** Local variable declaration *** Method with parameters ** TODO Review Exercises ** TODO Problems *** Modify die rolling example **** 100 rolls and make a table of data **** 100 rolls and make a histogram of data * [SoloPong] Rules: Methods, Parameters, and Design SoloPong A little syntax, a lot of design ACM CC2007: Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Software development (1/5 hours) Expressions vs. statements Scope ** SoloPong ** Top-down design *** Top-down design names services or new rules for components *** Rules for components become methods **** Determining what methods are necessary **** Determining the signatures ** Methods *** Declaring methods *** Using parameters to customize operation **** All passed by value **** Means changes are local **** But references are shared ***** TODO Picture *** Returning values from methods ** Expressions (compress from current coverage; this is summary) *** POD expressions **** Arithmetic expressions *** Object expressions **** Creating a new object **** Using object methods **** Chaining method calls **** String Expressions ** TODO Summary *** Methods *** Expressions *** Top-down design principles ** TODO Templates *** Field/variable declaration (w/final) *** Method declaration(?) is it new ** TODO Review Exercises *** Define top-down design terms ** TODO Problems *** TODO final Keyword * [<<>>Networked] Components meet Rules: Classes ACM CC2007: Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Sequential control flow Conditionals Iteration Anatomy of a class (1/6 hours) Formal and actual parameters Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Design and implementation of simple classes Inheritance: extending classes to provide additional or modified behavior (1/3 hours) Software development (1/5 hours) Analyzing problem statements, designing for users, software design, testing Basic constructs revisited: a more detailed look at control structures, ex- ceptions, and other constructs Expressions vs. statements; functions vs. procedures (or accessors vs. modifiers) Scope Concepts of procedural abstraction ** Introduce the Game [sidebar] History of multi-player games ** Network programming with FANG *** Sharing: Where is the game? **** Client/server computing ***** TODO Useful picture *** The distributed game loop **** Display **** Get input ***** Locally and across the network **** Calculate new state **** What if something bad happens? ***** Loss of connectivity ***** Cheating client [sidebar] Bots, cheating in multi-player games ** Review: Components have types; what's a type? Abstract Data Type *** An interface (a set of behaviors) *** An implementation *** Limited interaction *** Example: Chess pieces **** Material the chess set is made of makes no difference in what the peices are permitted to do **** The rules of chess do not permit smashing with a hammer (though that might be possible with some materials); interaction is limited to the defined behaviors, regardless of what we know about the implementation. **** Rules of game define interface; manufacturer of our instance determines implementation ** A screen within a screen: CompositeSprite ** Defining our own types *** Structure of a class file **** Interface ***** public method declaration **** Implementation ***** private instance variables ***** static variables *** Instance of our class **** Constructors ** Using our own types *** Construction *** Delegation **** Method invocation **** Computation model of a method call Evaluate parameters Suspend (but don't end) processing where you are When other thing is done, return here ** Documenting our own types *** Document your _intent_ [McC04] *** Assume someone reading your Java code can understand Java ** Finishing the game ** TODO Summary ** TODO Templates *** class (if just to reiterate) ** TODO Review Exercises ** TODO Problems *** Multi-player version of Pong * [<<>>]Making Games: Simple Arcade Game : Cooperating classes; advance methods in class objects ACM CC2007: Basic programming constructs (1//8 hours) Variables Sequential control flow Conditionals Iteration Anatomy of a class (1/6 hours) Return values; embedded method calls in complex expressions Inheritance: extending classes to provide additional or modified behavior (0.5/3 hours) ** Statements *** Definitions (Part 2) *** Expressions as Statements ** Sequence ** Selection *** The if statement **** Multi-way selection ** Iteration *** Automatically through FANG's game loop. ** Where are delegation and abstraction? ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * [Infection] Collections: Arrays [Simple: Epidemic Simulation]: Disease interface Person interface: healthy(), sick(), contagious(), expose(Disease), giveMedicine(Medicine) Medicine interface ACM CC2007: History, ethical and social context of computing (1/5 hours) Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Sequential control flow Conditionals Iteration Interfaces as type abstractions (1/2 hours) Using interfaces as types Dynamic binding of messages to methods (i.e., of method calls to method implementations) Creating interfaces and implementing classes Inheritance: extending classes to provide additional or modified behavior (3 hours) Linear and multi-dimensional indexed data structures (2/6 hours) Constructing arrays, accessing elements Variations on linear traversals (basic traversal, accumulating results, find- ing min/max values, linear search) Alternatively, could focus on collections and iterators, or on recursive data structures such as linked lists as the first linear data structure. ** Introduction to Simple Epidemic Simulator ** One and many *** Declaring an array *** Filling an arrray *** POD/Object arrays *** Traversing an array **** Iterators **** Printing each element out (a console application?) **** Find an element **** Check for some() (does some element in the array have a given quality) **** Updating elements ** Arrays are objects *** Array interface ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * [Hangman]Making Games: Hangman [Hangman]: Need to be able to get a word from the user (1 or 2 player) ACM CC2007: Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Conditionals Anatomy of a class (1/6 hours) Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Software development (1/5 hours) Analyzing problem statements, designing for users, software design, testing Complex Boolean expressions and propositional logic Strings Linear and multi-dimensional indexed data structures (1/6 hours) Constructing arrays, accessing elements Variations on linear traversals (basic traversal, accumulating results, find- ing min/max values, linear search) ** Introduction to Hangman ** Reading user input ** Computers and strings *** Strings are arbitrary sequences of arbitrary values *** Computers do not have an inherent understanding of anything ** Strings *** Characters *** Words *** Numbers *** Iterators ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems *** Caesar Cipher (or rather solver) **** Scrabble score (relates to a game) * [<<>>] Abstraction: Interface ACM CC2007: Anatomy of a class (1/6 hours) Formal and actual parameters Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Design and implementation of simple classes Interfaces as type abstractions (1/2 hours) Using interfaces as types Dynamic binding of messages to methods (i.e., of method calls to method implementations) Creating interfaces and implementing classes Inheritance: extending classes to provide additional or modified behavior (1/3 hours) Software development (1/5 hours) Analyzing problem statements, designing for users, software design, testing Expressions vs. statements; functions vs. procedures (or accessors vs. modifiers) ** Abstraction *** Dynamic dispatch ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * [TwentyQuestions] Separating Program from Data [20 Questions] ACM CC2007: Basic programming constructs (1/8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Iteration Anatomy of a class (6 hours) Formal and actual parameters Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Design and implementation of simple classes Interfaces as type abstractions (1/2 hours) Using interfaces as types Dynamic binding of messages to methods (i.e., of method calls to method implementations) Creating interfaces and implementing classes Software development (1/5 hours) Analyzing problem statements, designing for users, software design, testing Basic constructs revisited: a more detailed look at control structures, ex- ceptions, and other constructs Variations on conditional and iterative constructs Strings Recursion (1/2 hours) (alternatively, may be introduced with recursive data structures, either early in CS1 or in CS2) ** Introduction to 20 Questions *** Architecture *** Interfaces *** Classes *** Inter-object references [sidebar] Artificial Intelligence Consider: In an array, references by "name"; could read sequentially and reconstruct tree if written in pre-order (no parents means no parents). Need recursion for writing if we do it by tree order. If, instead, we just load the array in order and write the array in order (requires swapping when adding a new question; not that bad) Otherwise we need a recursive read and a recursive write. ** Introduction to Java I/O streams *** Memory hieararch revisited *** Self-documenting data *** Input and output files ** while loop *** Syntax and semantics ** Reading data: input streams and scanners *** Opening text files **** Exceptions **** Attaching a Scanner *** Reading an entire file while loop redux **** By line **** By word **** By character *** Closing text files *** Simplified serialization **** Multiple lines per object **** Making an object factory *** Java serialization ** Writing data: output streams *** Opening text file for output *** Iterate over all the data, writing it *** toString method *** Simplified serialization **** Writing what the reader expects to see **** Self-documenting data ** Data-driven programs *** Separating code from data **** Modify code without recompiling **** Use the same code to do differnt things ***** Multiple DIFFERENT 20 questions games ** TODO Summary ** TODO Templates while loop ** TODO Review Exercises ** TODO Problems * [RescueMission] Making Games: Arcade Games Swimmers in river, rushing toward waterfall. Must rescue them (Space invaders with a non-violent theme) ACM CC2007: Basic programming constructs (1/8 hours) Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Conditionals Iteration Software development 1/(5 hours) Analyzing problem statements, designing for users, software design, testing Basic constructs revisited: a more detailed look at control structures, ex- ceptions, and other constructs Complex Boolean expressions and propositional logic Variations on conditional and iterative constructs ** Game introduction ** A brief history of arcade and console games [sidebar] Space Invaders ** The Game Loop Redux *** Games use the same model as interactive programs! *** Need to get input without waiting for input [sidebar] Roberta Williams and Atari/Activision ** Array lists of array lists *** Multiple dimensions *** Nested loops **** Nested enhanced for loops ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * [Euchre] Making Games: Card Games Euchre/Hearts ACM CC2007: ** Designing a Card Class *** Design of the card data **** Handling trump *** Design of the appearance *** How is a collection of cards represented? *** How is a collection of cards put in order **** What if trump suit (and opposite suit) use a different ordering? Euchre/pinochle use the bowers (jack in suit, opposite jack above ace) ** Sorting ** Circular Definitions: Recursive methods *** What is a palindrome? **** Writing a palindrome checker *** Finding an element in a hand of cards **** Linear search **** Binary search: recursive ** General Recursion *** Base case *** Recursive case ** Tree traversal *** Recursive 20 Questions load/save ** Finish Hearts ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * [ProgrmmingAdventure] Making Games: Text Adventure Games [TAG] ACM CC2007: History, ethical and social context of computing (1/5 hours) Basic programming constructs (1/8 hours) Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Anatomy of a class (1/6 hours) Formal and actual parameters Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Design and implementation of simple classes Inheritance: extending classes to provide additional or modified behavior (3 hours) Software development (1/5 hours) Analyzing problem statements, designing for users, software design, testing Basic constructs revisited: a more detailed look at control structures, ex- ceptions, and other constructs Complex Boolean expressions and propositional logic Expressions vs. statements; functions vs. procedures (or accessors vs. modifiers) Variations on conditional and iterative constructs Shared data: class variables Scope Strings Linear and multi-dimensional indexed data structures (1/6 hours) Constructing arrays, accessing elements Variations on linear traversals (basic traversal, accumulating results, find- ing min/max values, linear search) Alternatively, could focus on collections and iterators, or on recursive data structures such as linked lists as the first linear data structure. ** A game from scratch: No FANG here. ** Back to the future *** A brief history of interactive fiction *** Pointers to shining examples **** Adventure **** Trinity ** The Game Loop *** Show state *** Get user input *** Use input (if any) to modify state and do it again ** Building a system: software architecture *** Requirements *** Design **** GameObject **** Location **** Critter **** Item ** Path finding (building a computer opponent) ** Incremental (agile) implementation *** Separating code and data **** Constructing locations **** Linking locations This should be modeled on the connections made in the 20 Questions chapter *** Making it a real game **** Conversation **** Combat **** Keys ** TODO Summary ** TODO Templates ** TODO Review Exercises ** TODO Problems * ----- Appendices ----- * Java Keywords * Java Templates Collect final, most complete, Java templates in one place at the end of the book * Index ---------------------------------------------------------------------------------- Object-oriented CS1 ACM Computing Curriculum 2007 Suggested Schedule (ACM CC2007) History, ethical and social context of computing (5 hours) How programs execute (1 hour) Basic von Neumann architecture Instructions Fetch-decode-execute cycle Basics of compiling, loading, and running programs Basic programming constructs (8 hours) Variables Types and classes as sets of operations: basic operations on primitives, reading class documentation to discover the operations on classes, using classes from a library Objects: constructing objects, methods as definitions of objects & behaviors, invoking methods, capturing return values in variables Sequential control flow Conditionals Iteration Anatomy of a class (6 hours) Formal and actual parameters Data available to a method Local variables, parameters, and instance variables Return values; embedded method calls in complex expressions Design and implementation of simple classes Interfaces as type abstractions (2 hours) Using interfaces as types Dynamic binding of messages to methods (i.e., of method calls to method implementations) Creating interfaces and implementing classes Inheritance: extending classes to provide additional or modified behavior (3 hours) Software development (5 hours) Analyzing problem statements, designing for users, software design, testing Basic constructs revisited: a more detailed look at control structures, ex- ceptions, and other constructs Complex Boolean expressions and propositional logic Expressions vs. statements; functions vs. procedures (or accessors vs. modifiers) Variations on conditional and iterative constructs Shared data: class variables Scope Concepts of procedural abstraction Strings Recursion (2 hours) (alternatively, may be introduced with recursive data structures, either early in CS1 or in CS2) Linear and multi-dimensional indexed data structures (6 hours) Constructing arrays, accessing elements Variations on linear traversals (basic traversal, accumulating results, find- ing min/max values, linear search) Alternatively, could focus on collections and iterators, or on recursive data structures such as linked lists as the first linear data structure. Informal Algorithm Analysis (1 hour) Multiple algorithms to solve a problem (e.g., linear and binary search, sorting algorithms) Comparison of appropriateness of algorithms based on Performance Constraints (e.g., binary search requires sorted data in a random-access data structure) Readability and maintainability