Hakonen Harri - Algorithms and Networking for Computer Games

This edition first published 2017
2017 John Wiley & Sons, Ltd

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by law. Advice on how to obtain permission to reuse material from this title is available at http://www.wiley.com/go/permissions.

The right of Jouni Smed and Harri Hakonen to be identified as the authors of this work has been asserted in accordance with law.

Registered Offices
John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, USA
John Wiley & Sons, Ltd. The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

Editorial Office
The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, UK

For details of our global editorial offices, customer services, and more information about Wiley products visit us at www.wiley.com.

Wiley also publishes its books in a variety of electronic formats and by print-on-demand. Some content that appears in standard print versions of this book may not be available in other formats.

Limit of Liability/Disclaimer of Warranty
While the publisher and authors have used their best efforts in preparing this work, they make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives, written sales materials or promotional statements for this work. The fact that an organization, website, or product is referred to in this work as a citation and/or potential source of further information does not mean that the publisher and authors endorse the information or services the organization, website, or product may provide or recommendations it may make. This work is sold with the understanding that the publisher is not engaged in rendering professional services. The advice and strategies contained herein may not be suitable for your situation. You should consult with a specialist where appropriate. Further, readers should be aware that websites listed in this work may have changed or disappeared between when this work was written and when it is read. Neither the publisher nor authors shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

Library of Congress Cataloging-in-Publication Data

Names: Smed, Jouni, author. | Hakonen, Harri, author.
Title: Algorithms and networking for computer games / Jouni Smed, Harri Hakonen.
Description: Second edition. | Hoboken, NJ, USA : John Wiley & Sons Inc., 2017. |
Includes bibliographical references and index.
Identifiers: LCCN 2017005948 (print) | LCCN 2017006972 (ebook) | ISBN 9781119259763 (cloth) |
ISBN 9781119259824 (Adobe PDF) | ISBN 9781119259831 (ePub)
Subjects: LCSH: Computer games--Programming. | Computer algorithms.
Classification: LCC QA76.76.C672 S62 2017 (print) | LCC QA76.76.C672 (ebook) |
DDC 794.8/1526--dc23
LC record available at https://lccn.loc.gov/2017005948

Cover Design: Wiley
Cover Image: Pobytov / Getty Images

When students at MIT competed against each other in the first real-time graphical computer game Spacewar in 1962 (Graetz 1981), probably none of them could have dreamt how realistic and complex computer games would develop in five decades and how large a business would grow around them. Commercial arcade games such as Pong and Space Invaders arrived in the 1970s, and home computers brought computer games within the reach of all enthusiasts in the 1980s. Since then game development has grown from small amateur enterprises into an industry, which is now in spite of popular claims the second largest branch of the entertainment industry, steadily narrowing the lead of the film industry (Newzoo 2014; Statista 2016).

Games are also becoming ever more pervasive in our lives. Smartphones and mobile gaming are a handy pastime in almost any situation, and technological advances in augmented and virtual reality along with internet of things are pushing forward the frontiers of gaming. This has coincided with a change in the ecosystem for game distribution from bricks-and-mortar stores into digital online stores and new monetization methods. Single-player mode which is an anomaly in the known 5000-year history of games starting from the Egyptian Senet and the Sumerian Royal Game of Ur is no longer the standard playmode, and networking can now bring massive numbers of players together to participate in the same game. We have witnessed the rise of gamification and application areas outside of pure entertainment to assist, guide, rehabilitate and teach children, youngsters, adults and elders alike. Game development has also become more democratized, because the development platforms make it easy and quick for everyone to create digital games. Finally, there is more knowledge and research on various aspects of games from design to productization, and modern game developers are more educated and aware of the possibilities of their medium. Behind the seven established forms of art (Canudo, 1988,b; Hegel 1975), games are truly emerging as the eighth art form.

The first edition of this book was published ten years ago in 2006. It was a time before smartphones, tablets, digital distribution and social networks. Massive multiplayer games such as World of Warcraft and Eve Online had just been released and were gathering momentum, the social media of today were still in their infancy, and the verb to google had just been added to the Oxford English Dictionary. The single-player PC games delivered in DVDs were the top of the line, and mobile games resembled simple games from the early 1980s. If we were back then careful in asserting that computer games are a valid topic for academic research, there is today no argument as to their importance.

Despite the changes, something still remains the same: the algorithms and networking making it all possible. Game programming is not an isolated field of study but intersects many essential research areas of traditional computer science. Solving an algorithmic or networking problem is always more than just getting it done as quickly as possible; it is about analysing what is behind the problem and what possibilities there are to solve it. This is the the motivation for this book, and our intention right from the beginning has been to provide the reader with a glance into the world of computer games as seen from the perspective of a computer scientist.

We assume that the reader is familiar with the fundamentals of algorithms and data structures (e.g. complexity analysis and graph theory). In a case of uncertainty, the reader can consult basic textbooks such as Introduction to Algorithms (Cormen et al. 2001) and, of course, the ever inspirational The Art of Computer Programming (Knuth 1998a,b,c, 2011). We describe classical game algorithms and review problems encountered in commercial computer games. Thus, in selecting material for this book we have walked a tight-rope between these two worlds. The current selection may seem a bit of a ragbag, but the common factor in the choice of the topics has been a combination of algorithmic and practical interest.

Going through the original files of the first edition, we were pleasantly surprised how fresh many of the ideas have remained. Hardly anything was outdated; rather the problems the developers are facing today are still the same. It also inspired us to continue and expand the work with a similar mindset. We have tried again to pick relevant topics from both academic literature and trade journals, forum posts and blogs to squeeze out their essence. We have still refrained from tying our hands with a particular platform (of which there have been many throughout the past decade) and programming language (of which there have been equally many). We are aware that that has been a common critique over the years, but we have strived to unlock the timeless beauty that many of the ideas conceal. Granted, there are many things that escape our grasp or which we could only briefly introduce, which is why we provide references to the works of the wiser and better informed. Also, the exercises at the end of each chapter hide many gold nuggets and possibilities for expanding ones thoughts and even venturing into uncharted waters.