Table of contents for Algorithms and networking for computer games / Jouni Smed, Harri Hakonen.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
Jouni Smed and Harri Hakonen runall.tex V2 - 8th March 2006 7:50pm Page vii
Contents
List of Figures xi
List of Tables xv
List of Algorithms xvii
Preface xix
Acknowledgements xxi
1 Introduction 1
1.1 Anatomy of Computer Games . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Synthetic Players . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Humanness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Stance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Multi-playing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Games and Storytelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 Other Game Design Considerations . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Outline of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6.2 Networking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
I Algorithms 15
2 Random Numbers 17
2.1 Linear Congruential Method . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.1.1 Choice of parameters . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.2 Testing the randomness . . . . . . . . . . . . . . . . . . . . . . . . 22
2.1.3 Using the generators . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2 Discrete Finite Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Random Shuffling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.4 Creating GameWorlds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.1 Starmap generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.2 Terrain generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Tournaments 47
3.1 Rank Adjustment Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2 Elimination Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Scoring Tournaments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
4 Game Trees 73
4.1 Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
4.1.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1.2 Partial minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.2 Alpha-Beta Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.2.1 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.2.2 Principal variation search . . . . . . . . . . . . . . . . . . . . . . . 86
4.3 Games of Chance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5 Path Finding 97
5.1 Discretization of the GameWorld . . . . . . . . . . . . . . . . . . . . . . . 98
5.1.1 Grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.2 Navigation mesh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.2 Finding theMinimum Path . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
5.2.1 Evaluation function . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.2.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2.3 Algorithm A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.3 Realizing theMovement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
6 Decision-making 115
6.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.1.1 Levels of decision-making . . . . . . . . . . . . . . . . . . . . . . . 116
6.1.2 Modelled knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.1.3 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2 Finite StateMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.1 Computational FSM . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2.2 Mealy andMoore machines . . . . . . . . . . . . . . . . . . . . . . 129
6.2.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
6.2.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3 Flocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
6.4 InfluenceMaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
6.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7 Modelling Uncertainty 149
7.1 Statistical Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.1.1 Bayes? theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.1.2 Bayesian networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
7.1.3 Dempster?Shafer theory . . . . . . . . . . . . . . . . . . . . . . . . 152
7.2 Fuzzy Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
7.2.1 Membership function . . . . . . . . . . . . . . . . . . . . . . . . . . 156
7.2.2 Fuzzy operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
7.3 Fuzzy Constraint Satisfaction Problem . . . . . . . . . . . . . . . . . . . . 159
7.3.1 Modelling the criteria as fuzzy sets . . . . . . . . . . . . . . . . . . 161
7.3.2 Weighting the criteria importances . . . . . . . . . . . . . . . . . . 163
7.3.3 Aggregating the criteria . . . . . . . . . . . . . . . . . . . . . . . . 163
7.3.4 Making a decision . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
7.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
II Networking 169
8 Communication Layers 171
8.1 Physical Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.1.1 Resource limitations . . . . . . . . . . . . . . . . . . . . . . . . . . 173
8.1.2 Transmission techniques and protocols . . . . . . . . . . . . . . . . 174
8.2 Logical Platform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
8.2.1 Communication architecture . . . . . . . . . . . . . . . . . . . . . . 175
8.2.2 Data and control architecture . . . . . . . . . . . . . . . . . . . . . 176
8.3 Networked Application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
8.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
9 Compensating Resource Limitations 183
9.1 Aspects of Compensation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
9.1.1 Consistency and responsiveness . . . . . . . . . . . . . . . . . . . . 184
9.1.2 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
9.2 Protocol Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190
9.2.1 Message compression . . . . . . . . . . . . . . . . . . . . . . . . . 190
9.2.2 Message aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.3 Dead Reckoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.3.1 Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
9.3.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
9.4 Local Perception Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
9.4.1 Linear temporal contour . . . . . . . . . . . . . . . . . . . . . . . . 199
9.4.2 Adding bullet time to the delays . . . . . . . . . . . . . . . . . . . 202
9.5 Synchronized Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
9.6 Area-of-interest Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
9.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
10 Cheating Prevention 213
10.1 Technical Exploitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
10.1.1 Packet tampering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
10.1.2 Look-ahead cheating . . . . . . . . . . . . . . . . . . . . . . . . . . 215
10.1.3 Cracking and other attacks . . . . . . . . . . . . . . . . . . . . . . . 220
10.2 Rule Violations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.2.1 Collusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
10.2.2 Offending other players . . . . . . . . . . . . . . . . . . . . . . . . 223
10.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
A Pseudo-code Conventions 229
A.1 Changing the Flow of Control . . . . . . . . . . . . . . . . . . . . . . . . . 232
A.1.1 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
A.1.2 Control structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 234
A.2 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
A.2.1 Values and entities . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
A.2.2 Data collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
A.3 Format of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
A.4 Conversion to Existing Programming Languages . . . . . . . . . . . . . . . 244
Bibliography 247
Ludography 255
Index 257

Library of Congress Subject Headings for this publication:

Computer games -- Programming.
Computer algorithms.