Page 5
© 2002 by Premier Press, a division of Course Technology. All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system without written permis- sion from Premier Press, except for the inclusion of brief quotations in a review. The Premier Press logo and related trade dress are trademarks of Premier Press, Inc. and may not be used without written permission. Publisher: Stacy L. Hiquet Technical Reviewer: André LaMothe Marketing Manager: Heather Hurley Interior Layout: Danielle Foster Managing Editor: Heather Talbot Cover Designer: Mike Tanamachi Series Editor: André LaMothe CD-ROM Producer: Jenny Davidson Acquisitions Editor: Mitzi Foster Koontz Indexer: Sharon Shock Project Editor/Copy Editor: Jenny Davidson Proofreader: Marge Bauer Colin McRae Rally 2 is a registered trademark of Codemasters. Codemasters is a registered trademark owned by Codemasters. Space Invaders is a registered trademark of Taito Corporation. Pac-Man is a registered trademark of Namco, Ltd. All other trademarks are the property of their respective owners. Important: Premier Press cannot provide software support. Please contact the appropriate software manufacturer’s technical support line or Web site for assistance. Premier Press and the author have attempted throughout this book to distinguish proprietary trademarks from descriptive terms by following the capitalization style used by the manufacturer. Information contained in this book has been obtained by Premier Press from sources believed to be reliable. However, because of the possibility of human or mechanical error by our sources, Premier Press, or others, the Publisher does not guarantee the accuracy, adequacy, or completeness of any information and is not responsible for any errors or omissions or the results obtained from use of such information. Readers should be particularly aware of the fact that the Internet is an ever- changing entity. Some facts may have changed since this book went to press. ISBN: 1-931841-08-X Library of Congress Catalog Card Number: 2002108325 Printed in the United States of America 02 03 04 05 BH 10 9 8 7 6 5 4 3 2 1 Premier Press, a division of Course Technology 2645 Erie Avenue, Suite 41 Cincinnati, Ohio 45208
Page 8
Foreword Welcome to AI Techniques for Game Programming. I think you’re going to find that it just might be one of the most useful books on game programming that you’ve ever picked up. Mat first came to my attention back in 2000 or so when he began posting in the GameDev (www.gamedev.net) forums on various aspects of game AI, answering questions of all kinds. He quickly garnered attention and praise from his fellow posters, particularly when he posted two tutorials he’d done on neural networks and genetic algorithms for public consumption. Mat saw a need for AI technologies such as these to be more accessible to game developers in hopes that they might incorporate them into their games, and his tutorials and patient answering of questions in the GameDev forums were obviously a way to try to make that happen. It is with some pride that I find myself now writing a foreword for a book on the subject; may it be the first of many. Content of This Book This book is fundamentally about making better games. It focuses on doing this by making the computer opponents smarter, more capable, and more human. This is an area of knowledge that has only been getting attention in any meaningful sense for the past decade or so. As this book goes to press, developers can look around and find the game indus- try exploding with activity, reaching out to new audiences, and evolving like never before. As new consoles and PC platforms flood the market, developers find themselves faced with an abundance of riches in terms of memory, CPU speeds, connectivity options, and video resolutions. These new capabilities provide the game developer with endless possibilities—and endless decisions for trade-offs and focus. Should the new game step up video resolution another notch, or should we focus on making the collisions more realistic? What about speed—can we do what we want to do with the standard machines in a year and a half when we’re ready to hit the market? How can we make our product different from our competitor’s down the street?
Page 9
viii Foreword Great game AI is one obvious way to make your game stand out from the crowd, and the flood of books and articles on the subject bears this out. Good quality game AI is no longer something to be done as long as it doesn’t hurt the framerate—it’s now a vital part of the design process and one which can make or break sales, just like graphics or sound. Developers are doing everything they can to investigate new AI technologies that they can assimilate to help build better, smarter game AIs. They want to explore new ideas that might take AIs to the next generation, an era in which games don’t just provide an interesting opponent but one in which they can talk to the player, interact with legions of online adventurers, and learn from game to game to be a more cunning and twisted opponent the next time around. Of course, these new AIs have to help make the game sell better, too. That’s always the bottom line—if a game doesn’t sell, it doesn’t really matter how good its AI is. Making Smarter Games This book focuses on exploring the relatively (to the game industry, anyway) “ex- otic” technologies of genetic algorithms and neural networks and how the developer might use them in his games. This has been a notoriously tough area to get develop- ers interested in for a number of reasons. Most developers feel that their current techniques are just fine and are easy to debug. The standard finite state machine (FSM) and fuzzy state machine (FuSM) have done a great job of providing robust, easy-to-debug AIs that have led to hit games from Age of Empires to Quake. They work, and with enough code time, they can be built to cover almost any situation. They’re also sadly predictable in so many ways, and that’s where developers are beginning to run into the Law of Diminishing Returns. Building an FSM to handle the innumerable possibilities inherent in some of the new games can be mind-boggling, the number of choices an AI must evaluate is overwhelming. To the human player, there might be two or three potential decisions which are “obviously” better—but what if the guy who coded the AI the Saturday night before the game’s final version was sent to the publisher didn’t think about those? The player sees the AI faced with a terrific decision upon which the entire fate of the game hangs—and it chooses incorrectly. Or worse than that, it chooses stu- pidly. A few instances of that and it’s pop! The CD is out of the drive and the player has moved on to something else. Suppose instead that the player faced a computer opponent that didn’t have a blind spot, that a game didn’t have a special combination of features that would render
Page 10
Foreword ix the AI brain-dead once the player discovered it. Suppose instead that the player faced an AI that might actually adapt to the player’s style over time, one that played better and smarter as the player learned more about the game. This kind of adaptation, or learning, is something of a Holy Grail for developers and players alike, and players clamber for it whenever they’re asked what they’d most like to see next. Gamers want to be challenged by an AI that actually adapts to their style of play, AIs that might anticipate what the player is most likely to do and then do something about it. In other words, an AI that plays more like another human. To the Future That’s where some of the more interesting AI technologies, such as the ones cov- ered in this book, come in. These technologies bring a more biological focus to the normally dry, logic-like realm of AI, giving the developer tools through which she might construct computer opponents that think like the players do. Using these techniques, a developer might build an AI that is smart enough to try a few differ- ent things to see what works best rather than simply selecting options from a menu of whatever the programmer thought to include. It might analyze the relative strengths and positions of its opponent’s forces, figure out that an invasion is near, and reposition forces to intercept it. The benefits that are possible don’t just affect the player’s ability to have a good time. Properly built, an AI that learns can have real impacts on development and test time on the part of the programmer, because he no longer has to build and test dozens or hundreds of fragile, special-case AI logic. If the AI can instead be given a few basic guidelines and then learn how to play the game by watching expert hu- man players, it will not only be more robust, it will simply play a better game. It’s like the difference between reading about basketball and actually playing it. Does that mean that Mat has done all the hard work here, and all you have to do is copy and paste his code into your latest project to build an AI that plays just like any human player? No, of course not. What is presented here is a guide, a framework, a baseline for those of you who don’t know anything about these more exotic AI technologies and are looking for a new angle for your next project. Maybe you haven’t had the time to research these possibilities on your own or perhaps you were just turned off by the more “academic” explanations found in other texts or around the Web.
Page 11
x Foreword The chapters that follow explore these technologies in an easy-going, friendly way. The approach is by a game developer for a game developer, and Mat maintains that focus throughout. AIs that can learn and adapt are an emerging technology that clearly point the way to better games, more satisfied gamers, and, most importantly, more sales. Steven Woodcock ferretman@gameai.com
Page 12
Acknowledgments First and foremost, I’d like to thank the love of my life, Sharon, for her patience, understanding, and encouragement while I was writing this book. Not even after the umpteenth time I turned away from my keyboard, blank-eyed, muttering “sorry, what was that you just said?” did she once throw a plate at me. Thanks to Mitzi at Premier for babysitting me through the whole process and for all her help with my often ridiculous queries (even if she does think Yorkshire-men sound like Jamie Oliver!). A big thanks also to Jenny, my editor, who has been awesome, to André who has combed my work for bugs, and to Heather for correct- ing all my mistakes and for suitably “Americanizing” my text. Many thanks to Gary “Stayin’ Alive” Simmons who suggested I write a book in the first place, to all the fans of my Internet tutorials whose e-mails provided daily encouragement, to Steve “Ferretman” Woodcock for taking the time to write the foreword, and to Ken for answering my many queries regarding NEAT. And of course, I shouldn’t forget Mr. Fish and Scooter, who always made sure I had a warm lap and a runny nose whenever I sat down to write.
Page 14
About the Author After studying Computer Science at London University, Mat Buckland spent many years as a Risk Management Consultant. He finally grew bored with all the money and corporate politics, made a bonfire of his designer suits, and went to work for a developer producing games for Gremlin Software. This paid a lot less but was a whole lot of fun—besides he got to wear jeans on weekdays! He now works as a freelance programmer and AI consultant. Mat has been interested in evolutionary computing and AI in general since he first read about these techniques back in the early ’80s. He is the author of the ai-junkie.com Web site (www.ai-junkie.com), which provides tutorials and advice on evolutionary algorithms.
Page 16
Contents at a Glance Letter from the Series Editor ....................................... xxvi Introduction ............................................................... xxix Part One Windows Programming ........................................................................... 1 Chapter 1 In the Beginning, There Was a Word, and the Word Was Windows ............................................... 3 Chapter 2 Further Adventures with Windows Programming .................. 35 Part Two Genetic Algorithms ...............................................................................87 Chapter 3 An Introduction to Genetic Algorithms ..............................89 Chapter 4 Permutation Encoding and the Traveling Salesman Problem ... 117 Chapter 5 Building a Better Genetic Algorithm ............................... 143 Chapter 6 Moon Landings Made Easy ............................................. 177 Part Three Neural Networks .................................................................................. 231 Chapter 7 Neural Networks in Plain English .................................. 233 Chapter 8 Giving Your Bot Senses ............................................... 275 Chapter 9 A Supervised Training Approach .................................... 293
Page 17
xvi Contents at a Glance Chapter 10 Real-Time Evolution .................................................... 327 Chapter 11 Evolving Neural Network Topology ................................. 345 Part Four Appendixes ........................................................................................... 413 Appendix A Web Resources ........................................................... 415 Appendix B Bibliography and Recommended Reading ........................... 419 Appendix C What’s on the CD ........................................................ 425 Epilogue ................................................................... 429 Index ......................................................................... 431
Page 18
Contents Letter from the Series Editor ...... xxvi Introduction ..............................xxix Part One Windows Programming ................................... 1 Chapter 1 In the Beginning, There Was a Word, and the Word Was Windows ..............3 And Then Came Word, and Excel, and… ..................................................... 4 A Little Bit of History.................................................................................... 4 Windows 1.0....................................................................................................................... 4 Windows 2.0....................................................................................................................... 5 Windows 3.0/3.1 ................................................................................................................ 5 Windows 95........................................................................................................................ 6 Windows 98 Onward ....................................................................................................... 7 Hello World! ................................................................................................... 7 Your First Windows Program ....................................................................... 8 Hungarian Notation:What’s That About? ................................................................... 12 Your First Window .......................................................................................................... 14 The Windows Message Pump ....................................................................................... 22 The Windows Procedure ............................................................................................... 25
Page 19
xviii Contents Keyboard Input ................................................................................................................. 32 Tah Dah! ............................................................................................................................. 34 Chapter 2 Further Adventures with Windows Programming ................... 35 The Windows GDI ....................................................................................... 36 Device Contexts .............................................................................................................. 37 Tools of the Trade: Pens, Brushes, Colors, Lines, and Shapes ................................. 39 Text ................................................................................................................ 55 TextOut .............................................................................................................................. 55 DrawText ........................................................................................................................... 55 Adding Color and Transparency ................................................................................... 56 A Real-Time Message Pump .......................................................................................... 58 How to Create a Back Buffer ..................................................................... 60 That Sounds Great, but How Do You Do It?............................................................. 62 Okay, I Have My Back Buffer, Now How Do I Use It? ............................................. 64 Keeping It Tidy .................................................................................................................. 67 Using Resources ........................................................................................... 68 Icons.................................................................................................................................... 70 Cursors .............................................................................................................................. 71 Menus ................................................................................................................................. 72 Adding Functionality to Your Menu ............................................................................. 73 Dialog Boxes ................................................................................................. 75 A Simple Dialog Box ....................................................................................................... 75 Getting the Timing Right ............................................................................ 83 At Last! ......................................................................................................... 85
Page 20
Contents xix Part Two Genetic Algorithms ...................................... 87 Chapter 3 An Introduction to Genetic Algorithms .................................89 The Birds and the Bees ............................................................................... 90 A Quick Lesson in Binary Numbers .......................................................... 96 Evolution InsideYour Computer ................................................................ 98 What’s Roulette Wheel Selection? .............................................................................. 99 What’s the Crossover Rate? ...................................................................................... 100 What’s the Mutation Rate? ......................................................................................... 101 Phew! ............................................................................................................................... 101 Helping Bob Home .................................................................................... 101 Encoding the Chromosome ....................................................................................... 104 Epoch ............................................................................................................................... 109 Choosing the Parameter Values ................................................................................. 112 The Operator Functions ............................................................................................. 113 Running the Pathfinder Program ............................................................................... 115 Stuff to Try .................................................................................................. 116 Chapter 4 Permutation Encoding and the Traveling Salesman Problem ..... 117 The Traveling Salesman Problem ............................................................. 118 Traps to Avoid................................................................................................................ 119 The CmapTSP, SGenome, and CgaTSP Declarations ............................................ 122
Showing the first 20 pages. Download the document to see it all.
Comments (0)
No comments yet. Be the first!