Ian Millington - AI for Games, Third Edition

AI for Games

THIRD EDITION

AI for Games

THIRD EDITION

Ian Millington

CRC Press

Taylor & Francis Group

6000 Broken Sound Parkway NW, Suite 300

Boca Raton, FL 33487-2742

2019 by Taylor & Francis Group, LLC

CRC Press is an imprint of Taylor & Francis Group, an Informa business

No claim to original U.S. Government works

Printed on acid-free paper

Version Date: 20190221

International Standard Book Number-13: 978-1-138-48397-2 (Hardback)

This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged.

Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe.

Library of Congress Cataloging-in-Publication Data

Names: Millington, Ian, author.

Title: AI for games / Ian Millington.

Other titles: AI for games

Description: Third edition. | Boca Raton : Taylor & Francis, a CRC title, part of the Taylor & Francis imprint, a member of the Taylor & Francis Group, the academic division of T&F Informa, plc, [2019] | Includes bibliographical references.

Identifiers: LCCN 2018041305 | ISBN 9781138483972 (hardback : acid-free paper)

Subjects: LCSH: Computer games--Programming. | Computer animation. | Artificial intelligence.

Classification: LCC QA76.76.C672 M549 2019 | DDC 794.8/1525--dc23

LC record available at https://lccn.loc.gov/2018041305

Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com

and the CRC Press Web site at
http://www.crcpress.com

for Daniel

my favorite game designer

CONTENTS

PART I
AI and Games

PART II
Techniques

PART III
Supporting Technologies

PART IV
Designing Game AI

G AME DEVELOPMENT lives in its own technical world. It has its own idioms, skills, and challenges. Thats one of the reasons games are so much fun to work on. Each game has its own rules, its own aesthetic, its own trade-offs, and the hardware it will run on keeps changing. Theres a reasonably good chance you will be the first person to meet and beat a new programming challenge.

Despite numerous efforts to standardize game development, in line with the rest of the software industry (efforts that go back at least 25 years), the style of programming in a game is still rather unique. There is a focus on speed, but it differs from real-time programming for embedded or control applications. There is a focus on clever algorithms, but it doesnt share the same rigor as database server engineering. It draws techniques from a huge range of different sources, but almost without exception modifies them beyond resemblance. And, to add an extra layer of intrigue, developers make their modifications in different ways, often under extreme time pressure, and tailored entirely to the game at hand, leaving algorithms unrecognizable from studio to studio or project to project.

As exciting and challenging as this may be, it makes it difficult for new developers to get the information they need. Twenty years ago, it was almost impossible to get hold of information about techniques and algorithms that real developers used in their games. There was an atmosphere of secrecy, even alchemy, about the coding techniques in top studios. Then came the Internet and an ever-growing range of websites, along with books, conferences, and periodicals. It is now easier than ever to teach yourself new techniques in game development.

This book is designed to help you master one element of game development: artificial intelligence (AI). There have been many articles published about different aspects of game AI: websites on particular techniques, compilations in book form, some introductory texts, and plenty of lectures at development conferences. But this book was designed to cover it all, as a coherent whole.

In my career I have developed many AI modules for lots of different genres of games. I developed AI middleware tools that have a lot of new research and clever content. I have worked on research and development for next-generation AI, and I get to do a lot with some very clever technologies. However, throughout this book I tried to resist the temptation to pass off how I think it should be done as how it is done. My aim has been to tell it like it is (or for those technologies I mention that are still emerging, to tell you how most people agree it will be).

The meat of this book covers a wide range of techniques for game AI. Some of them are barely techniques, more like a general approach or development style. Some are full-blown algorithms, ready to implement in a reusable way. And others are shallow introductions to huge fields that would fill multiple books on their own. In these cases, Ive tried to give enough of an overview for you to understand how and why an approach may be useful (or not).

This book is intended for a wide range of readers: from hobbyists or students looking to get a solid understanding of game AI through to professionals who need a comprehensive reference to techniques they may not have used before. I will assume you can program (though I will not assume any particular languagesee for a discussion of implementation languages), and I will assume you have high-school level mathematical knowledge.

Before we get into the techniques themselves, this chapter introduces AI, its history, and the way it is used. Well look at a model of AI to help fit the techniques together, and Ill give some background on how the rest of the book is structured.

Artificial intelligence is about making computers able to perform the thinking tasks that humans and animals are capable of.

We can program computers to have superhuman abilities in solving many problems: arithmetic, sorting, searching, and so on. Some of these problems were originally considered AI problems, but as they have been solved in more and more comprehensive ways, they have slipped out of the domain of AI developers.