第1页 / 共521页
第2页 / 共521页
第3页 / 共521页
第4页 / 共521页
第5页 / 共521页
第6页 / 共521页
第7页 / 共521页
第8页 / 共521页
Programming Game AI by Example.pdf
Programming Game AI by Example
Dedication
Contents
Foreword
Acknowledgments
Introduction
Chapter 1 A Math and Physics Primer
Chapter 2 State-Driven Agent Design
Chapter 3 How to Create Autonomously Moving Game Agents
Chapter 4 Sports Simulation—Simple Soccer
Chapter 5 The Secret Life of Graphs
Chapter 6 To Script, or Not to Script, That Is the Question
Chapter 7 Raven: An Overview
Chapter 8 Practical Path Planning
Chapter 9 Goal-Driven Agent Behavior
Chapter 10 Fuzzy Logic
Appendix A C++ Templates
Appendix B UML Class Diagrams
Appendix C Setting Up Your Development Environment
References
Bugs and Errata
Index
TLFeBOOK
Programming Game
AI by Example
Mat Buckland
Wordware Publishing, Inc.
Library of Congress Cataloging-in-Publication Data
Buckland, Mat.
Programming game AI by example / by Mat Buckland.
p. cm.
Includes index.
ISBN 1-55622-078-2 (pbk.)
1. Computer games—Design. 2. Computer games—Programming. 3. Computer
graphics.
QA76.76.C672B85 2004
794.8'1526—dc22
2004015103
I. Title.
© 2005, Wordware Publishing, Inc.
All Rights Reserved
2320 Los Rios Boulevard
Plano, Texas 75074
No part of this book may be reproduced in any form or by any means
without permission in writing from Wordware Publishing, Inc.
Printed in the United States of America
ISBN 1-55622-078-2
10 9 8 7 6 5 4 3 2 1
0409
Black & White, the Black & White logo, Lionhead, and the Lionhead logo are registered trademarks of Lionhead Studios
Limited. Screenshots used with the permission of Lionhead Studios Limited. All rights reserved.
Impossible Creatures and Relic are trademarks and/or registered trademarks of Relic Entertainment, Inc.
NEVERWINTER NIGHTS © 2002 Infogrames Entertainment, S.A. All Rights Reserved. Manufactured and marketed by
Infogrames, Inc., New York, NY. Portions © 2002 BioWare Corp. BioWare and the BioWare Logo are trademarks of BioWare
Corp. All Rights Reserved. Neverwinter Nights is a trademark owned by Wizards of the Coast, Inc., a subsidiary of Hasbro, Inc.
and is used by Infogrames Entertainment, S.A. under license. All Rights Reserved.
Unreal® Tournament 2003 ©2003 Epic Games, Inc. Unreal is a registered trademark of Epic Games, Inc. All rights reserved.
Other brand names and product names mentioned in this book are trademarks or service marks of their respective companies.
Any omission or misuse (of any kind) of service marks or trademarks should not be regarded as intent to infringe on the property
of others. The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to
distinguish their products.
This book is sold as is, without warranty of any kind, either express or implied, respecting the contents of this book and any disks
or programs that may accompany it, including but not limited to implied warranties for the book’s quality, performance,
merchantability, or fitness for any particular purpose. Neither Wordware Publishing, Inc. nor its dealers or distributors shall be
liable to the purchaser or any other person or entity with respect to any liability, loss, or damage caused or alleged to have been
caused directly or indirectly by this book.
All inquiries for volume purchases of this book should be addressed to Wordware Publishing, Inc.,
at the above address. Telephone inquiries may be made by calling:
(972) 423-0090
TLFeBOOK
Dedication
For Mum and Dad, who bought me my first computer, and therefore must
share some responsibility for turning me into the geek that I am. J
iii
TLFeBOOK
“Programming Game AI by Example stands out from the pack by providing indus-
trial-strength solutions to difficult problems, like steering and goal-oriented
behavior. Mat guides the reader toward building a foundation robust enough for
real games. This book is a must-have for anyone new to the field, and has tips for
the seasoned professional as well. I wish I [had] read it eight years ago!”
Jeff Orkin
AI architect, Monolith Productions, No One Lives Forever 2 and F.E.A.R.
“…a nice combination of a lot of really useful information, put together in a way
that doesn’t make my brain leak.”
Gareth Lewis
Project leader, Lionhead Studios, Black & White 2
“Each chapter of Mat’s book gently introduces the reader to a fundamental game
AI technology before expanding the new idea into a fully formed solution replete
with extensive code and clearly worded examples. The tone of the book is uncom-
plicated and accessible to the reader, allowing a novice programmer the
opportunity to get to grips with the basics of game AI programming by implement-
ing their own systems direct from theory or expanding upon code examples offered
to gain understanding in a sandbox environment. Once individual technologies are
fully understood, the book goes on to combine these ideas into several complete
game environments allowing the reader to understand the relationships between the
interacting systems of an overarching game architecture.”
Mike Ducker
AI programmer, Lionhead Studios, Fable
“Using easy-to-follow and well-described examples, this book shows you how to
use most of the techniques professional AI programmers use. A great introduction
for the beginner and an excellent reference for the more experienced!”
Eric Martel
AI programmer, Ubisoft, Far Cry (XBox)
“Programming Game AI by Example is an excellent book for the game program-
ming neophyte, the intermediate programmer, and even the expert — it doesn’t
hurt to go over familiar ground, does it? The book concisely covers all of the
important areas, including basic maths and physics through to graph theory and
scripting with Lua, to arm any programmer with the tools needed to create some
very sophisticated agent behaviours. Unusually for books of the type, Pro-
gramming Game AI by Example is solid in its software engineering too, with the
example code demonstrating game uses of familiar design patterns. I’d have no
qualms about recommending Programming Game AI by Example to any program-
mer. It’s an excellent read and an excellent springboard for ideas.”
Chris Keegan
Technical director, Climax Studios (Solent)
TLFeBOOK
Contents
Foreword . . . . . . . .
Acknowledgments . . . . .
Introduction.
.
.
.
.
.
.
.
. . .
. . .
. . .
. . .
.
.
.
. . .
.
.
.
.
. .
. . .
.
.
.
. . .
. . .
.
.
.
.
. . .
. .
.
.
. . .
.
.
.
.
. .
.
. . .
.
.
.
. .
.
. . .
.
.
.
. .
.
. . .
.
.
.
. .
. . .
.
.
. . .
. . .
.
.
.
.
. . .
. xiii
. . . xvii
.
. xix
.
.
.
.
.
.
.
.
.
Mathematics .
.
.
.
Cartesian Coordinates .
Functions and Equations .
Chapter 1 A Math and Physics Primer .
.
.
.
.
.
.
Exponents and Powers .
.
Roots of Numbers (Radicals) .
Simplifying Equations.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Vectors .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Trigonometry .
.
Rays and Line Segments .
.
Angles .
.
.
Triangles .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Adding and Subtracting Vectors .
.
Multiplying Vectors .
.
.
.
Calculating the Magnitude of a Vector .
.
.
Normalizing Vectors .
.
Resolving Vectors .
.
.
The Dot Product .
.
.
.
.
A Practical Example of Vector Mathematics.
.
The Vector2D Struct .
.
.
.
.
.
.
.
.
.
.
.
Local Space and World Space.
.
.
.
.
.
.
.
.
.
.
.
.
.
Time.
.
.
Distance .
.
Mass.
.
.
Position .
Velocity .
.
Acceleration .
.
Force .
Summing Up .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Physics .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Chapter 2
State-Driven Agent Design .
.
.
What Exactly Is a Finite State Machine?.
.
Implementing a Finite State Machine .
.
.
.
.
.
.
State Transition Tables .
.
Embedded Rules .
.
.
The West World Project
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 1
. 1
. 1
. 3
. 5
. 6
. 7
. 10
. 10
. 11
. 12
. 18
. 19
. 20
. 20
. 21
. 22
. 23
. 24
. 25
. 26
. 28
. 28
. 29
. 29
. 30
. 30
. 32
. 38
. 40
. 43
. 44
. 45
. 47
. 48
. 50
v
TLFeBOOK
vi | Contents
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The BaseGameEntity Class .
.
.
The Miner Class.
.
The Miner States .
.
.
The State Design Pattern Revisited .
.
.
.
.
The EnterMineAndDigForNugget State .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Making the State Base Class Reusable .
.
Global States and State Blips.
.
.
.
.
Creating a State Machine Class .
Introducing Elsa .
.
.
.
Adding Messaging Capabilities to Your FSM .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The MessageDispatcher Class .
.
.
.
.
.
.
.
.
Message Handling.
Elsa Cooks Dinner
.
Step One .
Step Two .
.
Step Three .
Step Four .
.
.
Step Five .
.
.
.
The Telegram Structure .
Miner Bob and Elsa Communicate .
Message Dispatch and Management
Summing Up .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 52
. 53
. 54
. 55
. 60
. 62
. 63
. 64
. 67
. 69
. 70
. 71
. 71
. 73
. 75
. 78
. 78
. 79
. 80
. 80
. 81
. 82
. 85
. 85
. 87
. 89
. 91
. 91
. 92
. 93
. 94
. 96
. 96
. 99
. 100
. 103
. 104
. 106
. 107
. 110
. 111
. 113
. 115
. 116
. 117
. 118
. 119
. 120
. 121
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
What Is an Autonomous Agent? .
.
The Vehicle Model .
.
.
.
.
Seek .
.
.
Flee .
.
.
.
Arrive .
.
.
Pursuit .
.
Evade .
.
.
Wander .
Obstacle Avoidance .
The Steering Behaviors .
.
.
.
.
.
.
Chapter 3 How to Create Autonomously Moving Game Agents .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Updating the Vehicle Physics .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Finding the Closest Intersection Point
.
Calculating the Steering Force .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Weighted Truncated Sum .
.
Weighted Truncated Running Sum with Prioritization .
Wall Avoidance .
.
.
Interpose .
.
Hide .
.
.
.
Path Following .
.
.
Offset Pursuit
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Combining Steering Behaviors .
Group Behaviors .
Separation .
Alignment .
.
Cohesion .
Flocking .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
TLFeBOOK
Chapter 4
Prioritized Dithering .
.
.
.
Ensuring Zero Overlap .
Coping with Lots of Vehicles: Spatial Partitioning .
Smoothing .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Designing the AI .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
The SoccerTeam Class .
The Soccer Pitch .
The Goals .
.
The Soccer Ball .
Sports Simulation — Simple Soccer.
.
.
.
.
.
The Simple Soccer Environment and Rules .
.
.
.
.
.
.
.
.
.
.
.
.
.
SoccerBall::FuturePosition .
SoccerBall::TimeToCoverDistance .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
SoccerTeam::isPassSafeFromAllOpponents .
.
.
SoccerTeam::CanShoot .
.
SoccerTeam::FindPass .
.
.
SoccerTeam::GetBestPassToReceiver .
.
.
.
.
.
.
.
.
The Receiving Player .
.
The Closest Player to the Ball
.
The Controlling Player .
.
The Supporting Player .
.
.
SoccerTeam States .
.
.
.
.
.
Field Player Motion.
.
.
Field Player States .
.
.
.
.
.
Goalkeeper Motion .
Goalkeeper States.
.
.
.
.
Key Methods Used by the AI .
Making Estimates and Assumptions Work for You .
Summing Up .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Field Players .
Goalkeepers .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Chapter 5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Graphs .
The Secret Life of Graphs .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A More Formal Description .
.
.
Trees .
.
.
.
Graph Density .
.
.
.
Digraphs .
.
.
.
.
Graphs in Game AI .
.
Navigation Graphs .
.
Dependency Graphs .
State Graphs .
.
.
.
.
.
.
Uninformed Graph Searches.
.
.
.
.
Implementing a Graph Class .
.
The GraphNode Class .
The GraphEdge Class .
.
The SparseGraph Class .
.
Graph Search Algorithms .
Depth First Search .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Contents | vii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. 123
. 124
. 126
. 130
. 133
. 134
. 135
. 138
. 138
. 141
. 142
. 144
. 145
. 146
. 146
. 146
. 146
. 152
. 155
. 155
. 156
. 170
. 170
. 171
. 176
. 177
. 182
. 184
. 185
. 189
. 189
. 193
. 193
. 195
. 196
. 196
. 196
. 197
. 198
. 199
. 201
. 203
. 204
. 205
. 207
. 209
. 210
. 210
TLFeBOOK
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
