Spatial Indexing and Quadtrees

This post is going to be me breaking down and trying t understand this blog post (done by Nick) about Spatial indexing with Quadtrees and Hilbert Curves.  Hopefully I can learn how this algorithm would be useful for terrain and environment representation.  I have a few ideas currently, but I’d like to break down and understand the algorithm first.

Spatial Database’s and Spacial Indices

In order to understand what a spatial index is, we need to know what a spatial database (WIKI) is.  A spatial database is essentially a collection of data that stores points, lines and polygons and any other object data.  Simple terms: databases that store information related to objects in space.  Many databases feature the following functionality:

• Spatial Measurements: Distance between points
• Spatial Functionality: Modify existing features while creating new ones
• Spatial Predicates: Allows for binary/(true/false) queries like, “is there a boss located in that cave 1km from here?”
• Constructor Functions: Creates new features in the database with an SQL query specifying the vertices (node points) that create lines.  If the first and last vertex are connected (first and last vertex are identical) the feature will be a polygon
• Observer Functions: Queries that return specific information like the location of the center of a circle

[ASIDE] SQL – Structured Query Language that is designed for managing data in rational database management systems
[ASIDE] SQL Queries – Queries which retrieve data based on specific criteria.  Most important element in SQL

Spatial Queries

Spatial indices are used by the spatial database to make faster queries.
These queries are essentially functions with the following template: functionName (parameter(s)) : return type

Types of queries:

• Distance(geometry, geometry) : number
• Equals(geometry, geometry) : boolean
• Disjoint(geometry, geometry) : boolean
• Intersects(geometry, geometry) : boolean
• Touches(geometry, geometry) : boolean
• Crosses(geometry, geometry) : boolean
• Overlaps(geometry, geometry) : boolean
• Contains(geometry, geometry) : boolean
• Length(geometry) : number
• Area(geometry) : number

Quadtrees

Trees. OH NO! I personally hated my class on algorithms and data structure’s, except for the part on trees.  Trees were simple to understand and they were related to the more interesting computer animation algorithms (Skeletal Animation, global vs local transformations).  Trees are simply data structures of linked nodes.

So quadtrees are used as a form of spatial indexing.  They are a special type of tree where each internal node has exactly 4 children.  They are heavily used in partitioning 2D space by recursively subdividing it into four quadrants and regions.

This is an example of a 2D quadtree. Ignore the points for now if they confuse you. They are just point data.  This is to show how a quadtree divides an indexed area

Nick describes the quadtree very well on his blog.  Each node in the tree is represented by a bounding box covering a part of the space that in indexed, the root node would be covering the entire area.  Each node is either a leaf node with one or more indexed points, but with no children.  If it is an internal node then it has exactly 4 children, one for each quadrant obtained by diving the area covered in by half on each axes.  This next picture should make things a bit more clear:

Representation of how a quadtree is structured internally

To query a quadtree is very simple.  Since we have a good graphical representation of our quadtree we are essentially dealing with intersecting areas.  We know that the root encompasses the entire area of the quadtree, and each child is a subsection of that.  So to query, we need to examine each child node and see if the area inside that quadrant intersects with our current query.  Once we encounter a leaf node is when we have to search each entry within that area to see if it intersects with the query area.  Then you simply return it if it does.

Geohashing and Hilbert Curves

Both of these are ways of not using the quadtree to recursively look up through the tree, but rather use different methods of querying.

The order in which geohashing visits each quad

The order in which a hilbert curve visits each quad

Summary

Nick goes into a lot more detail in the geohashing and hilbert curve methods, if you are so inclined to learn more about them, click here.  However, as a game developer quadtrees and spatial databases make me think of maps in games.  Ways of representing them (mini-maps) or ways of maybe organizing our scene managers in ogre?  Who knows, but now that I am more familiar with the quadtree data structure I am sure my team an I can think of many ways to implement this useful data structure in our game.

A Theory of Fun or a Theory of …

I recently read a Theory of Fun at the recommendation of our professor.  Needless to say I enjoyed it, a bit.

I didn’t care for the beginning, the wacky art style and the handwritten note style of it was not something I am fond of.  It took a bit to get used to, that aesthetic.  My ADD distracted me from the content with the art style, it happens more than I’d like to admit.

Puzzles

I started to enjoy the book around the time he began to talk about how we grasp patterns and how we perceive them.  Once he began to get into how we get bored once we master a puzzle, I can relate to that fairly well.  Whenever I play a game that involves me to stop and think, or if that game involves redundant puzzles I immediately get bored.  If it’s a simple puzzle mechanic that is not rewarding enough to complete a second time, I normally stop playing the game and move onto something more interesting.

Lockpicking Skyrim

Like the Fallout/Oblivion/Skyrim lock picking.  If you could call that a puzzle, it simple involves you rotating the lock while listening for audible cues when to put pressure.  To much pressure and the stupid lock pick breaks in the most frustrating sound ever, then you are back to square one and start from the beginning.

Dragon Claw with Puzzle Markings

A better example would be the dragon claw puzzles.  You simply find these dragon claws, and open the item in your inventory to see simple glyph’s on the front of it.  Needless to say, this glyph pattern ‘puzzle’ is used to open several doors in dungeons.

Seeing past Fiction

I found this line to be especially meaningful, ” We’re very good at seeing past fiction. This is why gamers are dismissive of the ethical implications of games – They don’t see ‘get a blowjob from a hooker, then run her over.'”  He placed a picture of Grand Theft Auto III as a bit of icing on that cake of a line.  I am pretty sure Koster means that gamers are more susceptible to immersion which allows us to be dismissive of otherwise unethical decisions in games.  This is interesting because of all the mass murder and otherwise “unethical” behavior gamers have been known to show (teabagging) while playing games.  Rather than surprising most people, we just start hysterically laughing like a bunch of serial killers.

It’s good that we don’t take games to be super serious and we take them for what they are; simply games.

Survival

Koster also mentions that players will always try to optimize what they are doing.  This kind of goes back to how important survival skills are learned by animals in a playful way (games).  Players optimizing goes to show how goal oriented we are to reach that next level, or beat that boss through hacking, grinding, exploiting etc.

Self Refreshing and Interpreting Puzzles

The ending of the book really brought forth this idea of mature games and games as a form of art.  What I understood of it was that, games can never be seen as a form of art until they are left to be open for interpretation.  The idea of puzzles not having a distinct answer really confused me.  I feel that Koster means that games need to create puzzles that pose tough questions that can’t be solved easily.  I think he meant that the puzzles we have now are fairly simple like a tic-tac-toe game, they are too easily perceived.  Does that mean that he wants choices in games to become puzzles? Or puzzle-like?

I can see how that can make player decisions more meaningful, however if every single decision in the game involved deep thought, it would ruin the flow of the game.  I like my games to require some form of muscle memory and quick reflex that would help me immerse myself into the game.

I think Raph Koster’s idea (theory of fun) of a fun game is one that really poses deep controversial puzzles without definite answers that engage the player in more thought provoking ways instead of getting them pumped on action, adventure and shooters.

Summary

What does this mean to us as upcoming game designers?  Something to take away from this would be the idea of thought-provoking puzzles.  While they don’t need to be so deep that we have to put down the controller and wiki the effects of virtual genocide, they can’t be so simple that we solve them at a glance.

This also applies to level design.  Good levels should have a puzzle element ingrained in their development.  Especially for any adventure game.

Time to go see if I can make my Portal Level better!

Recap of Summer and Third Year

Hello!

My penultimate year of my undergrad has now officially begun.  I had big plans for the summer and it didn’t really go exactly as planned.  I ended up shooting out a whole bunch of goals I wanted to reach for the longest time and didn’t exactly create a way to reach many of them.  I guess my main goal was to actually write them all down so I could see what I wanted to accomplish.

I ended up doing a lot more reading and game design work since it was a lot more interesting at that time.   Programming wasn’t really one of my main goals, I would much rather script in Unity.  Its so much easier.  Also I am super lazy and Unity was the faster and more immediately rewarding choice for me at that time.

Summer 2012 – Recap

The biggest accomplishment that I can show on this post of my summer is a design blog post (Long one) about my experience of the Mass Effect  trilogy.  The post is broken down into 3 main parts: Story, Gameplay and Review.  I don’t go into detail about the gameplay, because I felt that there was not much to say about it that has not already been said.  The gameplay is without a doubt very fun throughout the franchise and only gets better through each game.

The story however is deep and engaging.  It is also a clear controversy with the obvious fan backlash and media attention that caused.  I find that as a good thing in many ways, games are slowly evolving as a art medium that is not only appreciated and analysed by a small population anymore.  The backlash shows that people are expecting developers to create true forms of art instead of slapping something on last minute to appease the publisher.

Third Year

Finally our group situation has been sorted out and I am very happy to say that I was able to be placed in the group that I desired.  Kevin, the always productive member of our team.  Branden, the lazy but great programmer.  Now I have the privilege to work with Branan and David.  Branan is a very hardworking and experienced 3D modeler (something our team really needed) and David is another Jack of all trades like myself and Kevin.

We already have a game that all of us seem ready to start making.  We have decided on a pirate themed RPG.  With ship combat, devil may cry style action combat and a lush and interesting world filled with characters.  Also polish, lots of polish.  We are not going to have another blocky game with bad collision and trees that can be walked through.

Overall I am super excited for this year and I can’t wait to stop writing this and finish my character design!