book

Core Techniques and Algorithms in Game Programming

by Daniel SÃƒÆ’Ã‚Â¡nchez-Crespo Dalmau

September 2003

Intermediate to advanced

888 pages

19h 38m

English

New Riders

Read now

Unlock full access

Dedication
What You Will LearnWhat You Need to KnowHow This Book Is OrganizedPart I: Gameplay ProgrammingPart II: Engine ProgrammingPart III: AppendicesConventions
Phase I: Before SpacewarPhase II: Spacewar to AtariPhase III: Game Consoles and Personal ComputersGame Consoles and Game DevelopersPersonal ComputersPhase IV: Shakedown and ConsolidationPhase V: The Advent of the Game EnginePhase VI: The Handheld RevolutionPhase VII: The Cellular PhenomenonPhase VIII: Multiplayer GamesIn Closing
Real-Time SoftwareReal-Time LoopsThe Game Logic SectionPlayer UpdateWorld UpdateThe Presentation SectionWorld RenderingNPC RenderingThe PlayerCaveat: Networked GamesThe Programming ProcessStagesPreproduction: Where Do Ideas Come From?Discussing Feature SetsProduction: Milestones Are KingMaintenanceIn Closing
Types, Structures, and ClassesData StructuresStatic ArraysLinked ListsDoubly-Linked ListsQueuesStacksDequesTablesHash TablesMulti-Key TablesTreesTree Types and UsesBinary TreesN-ary TreesQuadtrees and OctreesTriesTree Traversal OperationsPriority QueuesGraphsThe Standard Template LibraryContainersVectorListDequeSets and MultisetsMap and MultimapHash_set, Hash_multiset, Hash_map, and Hash_multimapIteratorsIn Closing
Design Patterns DefinedSome Useful Programming PatternsSingletonStrategyFactorySpatial IndexSpatial Index as a ListSpatial Index as a Regular GridSpatial Index as a Quadtree/OctreeCompositeFlyweightUsability PatternsShieldStateAutomatic Mode CancellationMagnetismFocusProgressIn Closing

The KeyboardKeyboard with DirectInputMouseMouselookJoysticksResponse CurvesHardware AbstractionForce FeedbackIn Closing
ContextStructure of an AI SystemSensing the WorldMemoryAnalysis/Reasoning CoreAction/Output SystemSpecific TechnologiesFinite State MachinesAn ExampleAI SpecificationGraphical LayoutLaying Down Some CodeParallel AutomataSynchronized FSMsNondeterministic AutomataRule SystemsImplementationDecision TreesSymbolic Rule SystemsUser-Defined FactsPlanning and Problem SolvingState-Space SearchBiology-Inspired AIGenetic ProgrammingGenerating PopulationsEvolutionary ComputationFitness TestingMating, Mutations, and PlateausIn Closing
On Action GamesChoreographed AIsImplementationObject TrackingEye Contact: 2D Hemiplane Test3D Version: SemispacesChasingChase 2D: Constant SpeedPredictive ChasingEvasionPatrollingHiding and Taking CoverShootingInfinite-Speed TargetingReal-World TargetingVersion A: The Still ShooterVersion B: The TrackerMachine GunsPutting It All TogetherParallel AutomataAI SynchronizationIn ClosingPlatform GamesShootersFighting GamesRacing Titles
Tactical Thinking ExplainedPath FindingCrash and TurnDijkstra's AlgorithmA*Region-Based A*Interactive-Deepening A*A Note on Human Path FindingGroup DynamicsBoidsFormation-Based MovementMilitary Analysis: Influence MapsData StructureSome Useful TestsRepresenting TacticsIn Closing
Building a Scripting LanguageParsing Simple LanguagesParsing Structured LanguagesEmbedded LanguagesLearning LuaProgrammingIntegrationUser-Defined FunctionsReal-World Lua CodingJava ScriptingJava Native InterfaceSocket-Based ScriptingIn Closing
How the Internet Really WorksThe Programmer's Perspective: SocketsClientsA Minimal TCP ClientConnectionData TransferClosing SocketsA Minimal UDP ClientA Simple TCP ServerMulticlient ServersConcurrent, Connection-Oriented ServersIterative, Connection-Oriented ServersUDP ServersPreventing Socket BlocksDesigning Client-Server GamesMassively Multiplayer GamesData ExtrapolationHierarchical MessagingSpatial SubdivisionSend State Changes OnlyWorking with Server ClustersDynamic Servers and the Braveheart SyndromeIn Closing
On Older HardwareData Structures for 2D GamesSprite-Based CharactersMapping MatricesTile TablesFormat of the TilesNumber of Tiles2D Game AlgorithmsScreen-Based GamesTwo- and Four-Way ScrollersMultilayered EnginesParallax ScrollersIsometric EnginesPage-Swap ScrollersSpecial EffectsPalette EffectsStippling EffectsGlenzingFireIn Closing
A First LookFundamental Data TypesVerticesIndexed PrimitivesQuantizationColorAlphaTexture MappingGeometry FormatsA Generic Graphics PipelineClippingTriangle ClippingObject ClippingBounding SpheresBounding BoxesCullingObject CullingOcclusion TestingResolution DeterminationDiscrete Level of Detail PoliciesContinuous Level of Detail PoliciesTransform and LightingRasterizationIn Closing
General AnalysisOccluder-Based AlgorithmsBinary Space Partition AlgorithmsConstructionView-Dependent SortingHierarchical ClippingOcclusion DetectionRenderingPortal RenderingOptical Effects Using PortalsHierarchical Occlusion MapsHybrid ApproachesPortal-Octree HybridQuadtree-BSP HybridHardware-Assisted Occlusion TestsIn Closing
OverviewData Structures for Outdoors RenderingHeightfieldsQuadtreesBinary Triangle TreesGeomipmappingROAMPass One: Construct the Variance TreePass Two: Mesh ReconstructionOptimizationsChunked LODsA GPU-Centric ApproachOutdoors Scene GraphsIn Closing
AnalysisExplicit Versus Implicit MethodsExplicit Animation TechniquesFrame AnimationKeyframe AnimationTagged InterpolationImplicit Animation OverviewForward KinematicsMath of Skeletal AnimationHardware-Assisted Skeletal AnimationProp HandlingA Note on VehiclesLimb SlicingFacial AnimationInverse KinematicsAnalytic IKCyclic Coordinate DescentBlending Forward and Inverse KinematicsIn Closing
First-Person ShootersHandling InertiaFlight Simulators and QuaternionsPopular OperationsThird-Person CamerasCinematic Cameras: Camera StylesCinematic Cameras: Placement AlgorithmsSelecting the Camera TargetSelecting the Relevant InformationSelecting View AnglesAgent-Based ApproachesIn Closing
Real-World IlluminationA Simple Rendering EquationPer-Vertex and Per-Pixel LightingLight MappingDiffuse Light MappingSpecular Light MappingGlobal Illumination Using Light MapsImplementing Light Mapping: OpenGLMultipass VersionImplementing Light Mapping: DirectXCreating Light MapsLight Map Computation: PhongLight Map Computation: Ray TracingAdvanced Light Maps Using Ray TracingLight Map Computation: RadiosityStoring Light MapsThe BRDFAverage VectorShadowsShadow MapsStencil ShadowsNonphotorealistic RenderingPencil RenderingOutlined DrawingStroked OutlinesCel ShadingPainterly RenderingIn Closing
Types of TexturesTexture MappingXYZ mappingCylindrical MappingSpherical MappingTexture Mapping a TriangleTiling and DecalsFilteringMipmappingTexture OptimizationTexture CompressionTexture Caching and PagingMultipass TechniquesMultitextureTexture Arithmetic and CombinationDetail TexturesEnvironment MappingBump MappingEmboss Bump MappingDot3 Bump MappingGloss MappingIn Closing
Anatomy of a Particle SystemLocal Versus Global Particle SystemsThe Particle Data StructureA Generic Particle SystemSpawning ParticlesParticle BehaviorParticle ExtinctionRendering ParticlesCompute Particles CheaplyUse Blending Modes AppropriatelyAnimated TexturesChained/Hierarchical SystemsVisual Parameters as Functions of TimeSome Notes on ArchitectureSpeed-Up TechniquesAvoid Malloc and FreeSpatial IndexingLOD Particle SystemsShader-Based Particle SystemsIn Closing
Nature and ComplexityTreesBillboardsImage-Based MethodsParallel IBR MethodOrthogonal IBR methodGrassLayered GrassStatistical Distribution AlgorithmsCloudsSkyboxes and DomesBillboarded CloudsVolumetric CloudsOceansRealistic Ocean GeometryOcean AppearanceCausticsIn Closing
Procedural ManifestoRendermanReal-Time Shading LanguagesCurrent LanguagesCgHLSLGL2 Shading LanguageTypes of ShadersA Collection of ShadersGeometry EffectsLightingTexture MappingParticle SystemsAnimationProcedural TexturingSpecial EffectsIn Closing
Point Inclusion TestsPoint-in-SpherePoint-in-AABBPoint-in-Convex PolygonPoint-in-Polygon (Convex and Concave): Jordan Curve TheoremPoint-in-Convex ObjectPoint-in-Object (Jordan Curve Theorem)Point-in-Object (3DDDA)Ray Intersection TestsRay-PlaneRay-TriangleRay-AABB TestRay-Sphere TestRay-Convex HullRay-General Object (3DDDA)Moving TestsSphere: SpherePoint Versus Triangle Set Collision (BSP-Based)Mesh Versus Mesh (Sweep and Prune Approach)Computing a Convex Hull2D Solution3D SolutionTriangle ReductionVertex CollapsingEdge CollapsingProgressive MeshesNonconservative Triangle ReductionIn Closing
Analysis TechniquesTimingMemory FootprintsAnalysis ToolsDetecting BottlenecksGeneral Optimization TechniquesChoose Your EnemyPrecompute EverythingSimplify Your MathStore Data EfficientlyForget Malloc() and Free()Be LinearWatch Out for PointersApplicationEfficient Data TransferTuning the Geometry PipelineTuning the Rasterizer StageOther Optimization ToolsIn Closing
PhilosophyBasic SyntaxImmediate Mode RenderingTransformationsConcatenation of TransformsHierarchical TransformsCamera ModelLightingTexturingWorking in RGBA ModeDisplay ListsVertex ArraysUsing Regular Vertex ArraysCompiled Vertex ArraysServer-Side Vertex ArraysVertex Array RangeVertex Array ObjectVertex Buffer ObjectOpenGL ExtensionsEfficiency ConsiderationsGeometric RepresentationGeometry RenderingAvoid Unneeded State ChangesDiscard EarlyIn Closing
HistoryBooting Direct3DHandling GeometryIndexed PrimitivesUser Pointer PrimitivesEfficient Geometry DeliveryFlexible Vertex FormatsMatrices, Cameras, and TransformsWorking with Texture MapsLightingRender StatesThe Extension LibraryID3DXMeshID3DXPMeshID3DXFontAnimation HelpersIn Closing
DistancesDistance Between Two PointsDistance Between Two LinesDistance from a Point to a LineDistance from a Point to a PlaneDistance Between Two PlanesTrigonometryVector MathModuloDot ProductCross ProductMatricesMatrix AdditionMatrix TranspositionMatrix-Matrix MultiplicationDeterminant of a MatrixInverse of a MatrixMatrices for GeometryTranslationScalingRotationBasis MatricesConcatenation of Transforms
Chapter 1: Chronology of Game ProgrammingChapter 2: Game ArchitectureChapter 3: Data Structures and AlgorithmsChapter 4: Design PatternsChapter 5: User InputChapters 6, 7, and 8: Fundamental AI Technologies, Action-Oriented AI, and Tactical AIChapter 9: ScriptingChapter 10: Network ProgrammingChapter 11: 2D ProgrammingChapter 12: 3D Pipeline OverviewChapter 13: Indoors RenderingChapter 14: Outdoors AlgorithmsChapter 15: Character AnimationChapter 16: CinematographyChapter 17: ShadingChapter 18: Texture MappingChapter 19: Particle SystemsChapter 20: Organic RenderingChapter 21: Procedural TechniquesChapter 22: Geometrical AlgorithmsAppendix A: Performance TuningAppendix B: OpenGLAppendix C: Direct3DAppendix D: Some Math Involved

Content preview from Core Techniques and Algorithms in Game Programming

Chapter 3. Data Structures and Algorithms

	“The loftier the building, the deeper must the foundation be laid.”
	--Thomas Kempis

KEY TOPICS

Types, Structures, and Classes
Data Structures
The Standard Template Library
In Closing

Our journey into game programming is going to be long and deep. Before we begin, we must make sure some key concepts are well laid out. We need to take a second to review the game programmer's basic tool set. This chapter is a survey of popular data structures and their access algorithms. We will be basing all our work on these cornerstones throughout the rest of the book. Therefore, it is essential that they be well understood, so we can move on to the game-specific content of the book.

So, consider this chapter a reminder. Read ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

Practical Algorithms for 3D Computer Graphics, 2nd Edition

R. Stuart Ferguson

Developing 2D Games with Unity: Independent Game Programming with C#

Jared Halpern

Procedural Content Generation for C++ Game Development

Dale Green

Human-Computer Interaction in Game Development with Python: Design and Develop a Game Interface Using HCI Technologies and Techniques

Joseph Thachil George, Meghna Joseph George

Publisher Resources

ISBN: 0131020099Purchase book