School of Engineering and Information Sciences

MIDDLESEX UNIVERSITY

EXAMINATION PAPER

2009/2010 Winter/Spring term

MODULE TITLE: Advanced Topics in Games Development

MODULE NUMBER: CMT 3325

MODULE LEADER’S NAME: Chris Huyck

___________________________________________________________________

Time allowed: 3 hours	 

Total number of questions:	 4					

Instructions to candidates:	Answer all questions.  Each question carries 25 marks.

Materials provided:								

Equipment permitted: The book Programming Game AI by Example (by Buckland) is allowed, along with one A4 page marked as notes on the top.  Please submit that page with the exam (it will not be marked).

Total number of pages:	

No books, papers or electronic devise are permitted to be brought into the examination room other than any specified above.

Candidates are warned that illegible scripts will not be marked	

1.  Automata and Semantic Nets  (25 marks)

A. 5 points
A Finite State Automata (FSA) is a graph.  What do the nodes mean, and what do the arcs mean?

The nodes are the states.  This automata is always in one state, at least in the deterministic case. The arcs are labelled with conditions for transition.  If it is reading input, depending on the current input, the automata transits from the current to the next state along the arc labelled by that input, depending on input.  The input is then consumed.

B.8 marks
  Here's a particular noughts and crosses game:
 XBB
 BOB
 BOX
 B means blank.  Write an FSA that plays O from this state.

S0 -1,3;2,1;2,3;3,1-> S1
|
1,2
|
V
S2 -2,3->S3
| \
| 2,1
3,1\
|     \
V     V
S4   S5
In S1 put an O in 1,2 and declare win
In S2 put an O in 1,3
In S3 declare a draw
In S4 put an O in 3,1 and declare a draw
In S5 put an O in 2,1 and declare a draw

C.5 marks
  A semantic net is also a graph.  What do the nodes and what do the arcs mean?

A node in a semantic refers to a concept.  An arc is directed and labelled, and refers to the relationship between the two nodes.  The inverse relationship is usually inferred.

D 7 marks
  Draw a semantic net for weapons in a modern first person shooter game.  Include ISA and instance arcs.

Question 2 Physics (25 marks)
A. 8 marks.
   The voyager space ship is currently beyond Pluto, 16.6 billion KM from the sun, and travelling at 60,000 km per hour.  It is almost entirely unaffected by the Sun's gravity or any other body’s.  How fast will it be going next year?  Paraphrase (or quote) Newton's principle that enables you to determine this speed.

It will be going at 60,000 km per hour.  The principle is that unless a body is effected by some force, it will continue to travel at the same rate in the same direction.

B. 9 marks. 
   The weight of Mars is roughly 6.4x1023 kg, and its radius is 3400 km.  How much force would it exert on someone standing on its surface?

F = G*m1/r2.  G is 6.656*10-11
So rounding, 6*10-11 * 6*1023/ (3.4*106*  3.4*106) = 36*1012/12*1012=3
(The answer from wikipedia is 3.67 m/s2, but this answer would get full credit)
C. 8 marks
Discuss the accuracy vs. calculation trade-off regarding physical motion in videogames.

Calculating the physical position of an object, or indeed making a wide range of decisions, can be done to a high degree of precision.  However, this precision often comes at the expense of complex calculations that can take an enormous amount of computational time.  In many circumstances, simpler calculations can lead to results that are nearly as good, but require much less time. At the other extreme, very simple calculations may be very quick but lead to very poor results.  The accuracy calculation trade-off involves finding the correct that intermediate position that is relatively simple to calculate, but yields relatively accurate results.

Question 3 Search and Search Spaces (25 marks)

Here is a maze we discussed in class.  Start at S and get to the goal G.
A. (5 marks)  
Describe the maze as a graph.

Label each junction in the maze as a node in the graph.  From top to bottom, left to right they are G, G0, F0, S0, S1, S, S2, S3, S4, T0, T1 and T2.  Mark the arcs between them, AG,G0,AG0,S2, AF0,S1, AS0,S1,AS1,S2, AS,S2, AS2,S3, AS3,S4, AS3,T1, AT0,T1,and AT1,T2.

B. (5 marks)
How big is the search space?  There are 12 states.

C. (7 marks)
Write an algorithm that will find a path from the start to the goal state in any such non-cyclic maze.

Breadth First Search.  Start at S and put it into a queue (a list where you add to the end and remove from the front).  
Repeat until the goal is found:
    Remove the first item and mark as current
    Expand all searches from the start of the queue.  If they aren’t already visited, add those to the end of the queue.  (For example, add S-S1 and S-S2.
    Put current into the visited list.

D. (8 marks)
Describe simulated annealing and the characteristics of the search spaces that it is good for.

Simulated annealing is a search method done by finding a place in the space, then hill climbing, then jumping.  Each time you jump, you reduce the distance jumped.  In the correct type of search space, that finds a good solution and avoids particularly bad local minima.  The correct type of space needs to have a reasonable degree of regularity with adjacent states having similar values.  However, it need not be entirely regular.  A good example is finding a high spot in a mountain range.  If the space is entirely regular, simple hill climbing works.

Question 4 Components and OO techniques (25 marks)
A.  (5 marks)
In the Spacewars game we did in the early labs and for the first course work, we created a specialized agent subclass.  This did not fit in particularly well with the class structure of the game.  What were the problems?  

The problem was that the there was not a single class associated with an agent.  The ship was a reasonable class, but did not provide easy access to the data needed by an agent.  For example, a user playing a ship saw the screen and could see the opponent.  An agent doing the same thing did not have access to the same data either via the picture (which would have been difficult to interpret) or the underlying data.  
Another problem was that the ship did not have access to the movements.  That is, it did not explicitly move forward, left or any other direction.  (It did fire and go into hyperspace, though that was embedded in the update function.)  

B.  (5 marks)
What would have been a better class structure to resolve these problems? 

A better structure would have enabled an agent to look at the data it needed, and to make the movements it needed without making key strokes or guessing parameters.  For example, the ship class could have moveLeft, moveRight, fire, and other action functions.  The class that contained the ship (say screen) would allow access to particular data to any of the agents.  For example, getPosition(opponent) would enable an agent to see where another agent was.  It’s reasonable that spacewars was written this way because it was not written with the idea of AI agents in mind.

C. (7 marks)
Scripting is frequently used in games to create content.  What are the advantages and disadvantages of scripting?

The advantages of scripting include:
  Avoiding recompilation:  scripts are usually interpretive.  When the program starts up, it reads the script and uses that data.  It can then be rerun with a different script.  This is why spacewars provides an xml file.  The underlying program need not be recompiled.
  Simpler language: it is often said that a scripting language is easier for novices to use.  This may be the case with domain specific languages.  This allows the user of the game to modify the code and specialise it.
  This may also enable creation of agent in the game.
Disadvantages include:
  Support of optionality: the flexibility inherent in scripts requires support.  In the case of xml files setting global variables, this is relatively minor.  However, the more complex the scripting language, the more options that the underlying code must support.
    A related problem is bugs: the complexity of the script may allow a really vast number of options, and it may be difficult to test these options.  That is, the system may have a lot of bugs. 
  Slow run time is another problem.  Interpreted script usually runs slower than compiled code.  Moreover, even compiled script is often slower than code that is written to be compiled.  However, faster processing speeds makes this less important.
  Finally, the developers need to develop in multiple languages.  This can lead to complexities.

D. (8 marks)
The crystal space games engine that we encountered in the labs uses smart pointers.  What are some advantages and disadvantages of smart pointers?
  Advantages include:
     	The system is it is more efficient.  As memory is explicitly managed, the system does not need to have different memory support systems.  
     	The system is consistent.  Memory management for each type is the same.  
  Disadvantages include:
  	Readability and writability:  One of the problems is that smart pointers make the code difficult to understand because it adds a layer of indirection.  
	Inability to specialise:  it becomes difficult to handle memory differently for different items.  This may lead to inefficiencies.