Transcript Data Structures in Games

Introduction
General Data Structures
- Arrays, Linked Lists
- Stacks & Queues
- Hash Tables & Binary Search Trees
- Graphs
Spatial Data Structures
-Why care?
- Binary Space Partitioning (BSP) trees
You tell me..
Which data structure is suitable?
• Tile maps & Terrain maps
• Inventory (Hint: Dynamic storage)
• Efficient searching
• Command queuing
• Menus
• Collision Detection
• Visibility
Arrays & Linked Lists
2D arrays and linked lists are used as:
- Single and multi- layered Tile maps in 2D scenes in
which each tile acts like a pixel.
- Terrain maps in 3D world where 2D array represents
the height of each tile in a level.
Utility:
- Abstracts the idea of pixels to a higher level
significantly simplifying a drawing engine:
Demo-1; Demo-2
- Linked Lists can be used for inventory: Demo-3
Stacks & Queues
Stacks:
used to construct Menu, Submenus: Demo-4
Queues:
used for command queuing e.g. Real Time Strategy
(RTS) games such as Command & Conquer, War
craft, Star craft: Demo-5
Trade Off:
When expandability is more important than speed,
use linked stacks and queues;
otherwise use arrayed stacks and queues.
Others..
Hash Tables & Binary Search Trees:
- searching; Demo-6
Trees:
- Map editor (hierarchy of maps);
- Skill system like RPGs such as Diablo 2 do.
option to choose the skills e.g. healing skills or
fighting skills.
Graphs:
- Portal Engine; games like Descent, Quake 2.
more efficient method for rendering things:Demo-7
Spatial Partitioning
• What do we mean by spatial partitioning?
Spatial partitioning mean dividing up the game world into
regions that can be used to find spatial relationships
between objects.
• Why do we need spatial partitioning?
Scenegraphs are great for recording the dynamic
relationships between dynamic objects, e.g. parts of a
body.
They are not so good for storing information about static
elements in a game world, e.g. walls in a building.
Using Spatial Partitioning
Spatial partitioning data structures are used to:
• Determine which parts of large static objects are visible,
e.g. buildings, terrains.
• Determine neighborhood relationships between dynamic
objects, e.g. for collision detection.
• Determine how much data needs to be sent across a
network, e.g. based on what is currently visible to the
client.
Spatial data Structures
Spatial data structures store data indexed in some
way by their spatial location
– For instance, store points according to their
location, or polygons, …
– Before graphics, used for queries like “Where is
the nearest hotel?” or “Which stars are strong
enough to influence the sun?”
Applications
• Multitude of uses in computer games
– Visibility - What can I see?
– Ray intersections - What did the player just
shoot?
– Collision detection - Did the player just hit a wall?
– Proximity queries - Where is the nearest powerup?
Spatial Partitioning Schemes
Two common spatial partitioning schemes are:
- Binary Space Partitioning (BSP)
- Quadtree/Octree Partitioning
The partitioning schemes are similar in some ways, both:
- Recursively subdivide a space into smaller spaces
- Construct tree data-structure that can be searched quickly
- Are expensive to modify, hence they are best used for static
features of a world when they can be pre-computed once
Binary Space Partitioning
• Binary space partitioning works by dividing a space into
two subspaces at each recursion with a plane
• Choosing the best plane to divide a given space into two
equally complex subspaces is the most difficult part.
• Most game engines analyze the geometry of a world
and choose an existing polygon to define a plane.
• The analysis should determine which polygon will result in
the most balanced tree.
Binary Space Partitioning Example
• Suppose that this figure - 1 represents the walls of a
building in a game
• We want to pre-process this complex shape into a
BSP tree consisting of simpler regions to assist
real-time rendering
Walls of a building as space
First subdivision: Split occurs at polygon 16
Second subdivision: Split at polygon 4, 21
Final BSP tree
BSP Tree Node Data Structure
• What needs to be stored in a node?
– Children pointers (always two)
– Parent pointer - useful for moving about the tree
– If a leaf node: Extents of cell
• How might we store it?
– If an internal node: The split plane
– List of pointers to the contents of the cell
– Neighbors are useful in many algorithms
• Typically only store neighbors at leaf nodes
• Cells can have many neighboring cells
– Portals are also useful - holes that see into neighbors
Building a BSP Tree
• Define a function, buildNode, that:
– Takes a node with its cell defined and a list of its contents
– Sets the splitting plane, creates the children nodes, divides the
objects among the children, and recurses on the children, or
– Sets the node to be a leaf node
• Create the root node and call buildNode with all the
objects
– Do we need the root node’s cell? What do we set it to?
• When do we choose to stop creating children?
• What is the hard part?
Choosing Splitting Planes
• Goals:
– Trees with few cells
– Planes that are mostly opaque (best for visibility calculations)
– Objects not split across cells
• Some heuristics:
–
–
–
–
–
–
Choose planes that are also polygon planes
Choose large polygons first
Choose planes that don’t split many polygons
Try to choose planes that evenly divide the data
Let the user select or otherwise guide the splitting process
Random choice of splitting planes doesn’t do too badly
Drawing Order from BSP Trees
• BSP tress can be used to order polygons from back to
front, or vice-versa
– Descend tree with viewpoint
– Things on the same side of a splitting plane as the viewpoint are
always in front of things on the far side
• Can draw from back to front
– Removes need for z-buffer, but few people care any more
– Gives the correct order for rendering transparent objects with a
z-buffer, and by far the best way to do it
• Can draw front to back
– Use info from front polygons to avoid drawing back ones
– Useful in software renderers (Doom?)
Dynamic Lights and BSPs
• Dynamic lights usually have a limited radius of influence
to reduce the number of objects they light
• The problem is to find, using the BSP tree, the set of
objects lit by the light (intersecting a sphere center (x,y,z)
radius r)
• Solution: Find the distance of the center of the sphere
from each split plane
– What do we do if it’s greater than r distance on the positive side
of the plane?
– What do we do if it’s greater than r distance on the negative side
of the plane?
– What do we do if it’s within distance r of the plane?
– Any leaf nodes reached contain objects that might be lit
BSP and Frustum Culling
• You have a BSP tree, and a view frustum
– With near and far clip planes
• At each splitting plane:
– Test the boundaries of the frustum against the split plane
– What if the entire frustum is on one side of the split plane?
– What if the frustum intersects the split plane?
• What do you test in situations with no far plane?
• What do you do when you get to a leaf?
References
• Data Structures for Game programmers by
Ron Penton
• http://www.cs.wisc.edu/~schenney/course
s/cs679-f2003/cs679.html
• http://www.soi.city.ac.uk/~rob/Lecture08.pd
f
• http://www.gamedev.net