Quadtrees vs. Grid detection

Me and my groupmates are making a fighting game by the name of Shattered Tides, like any game we’re implementing collision detection code. There are many ways to implement it, however the real challenge is finding the most effect in the best possible time given our anemic time frame. After looking into it, it would seem that the quadtrees are the most common way to go but in some resources they mention the grid based solution.

So which is better and more effective? The right answer depends a little bit on the actual game you’re making, and choosing one over the other is needs implementing both and doing profiling to find out which one is more time or space efficient on your specific game.

Grid detection seems to solely apply to detecting collisions between moving objects and a static background. The greatest advantage is that the static background is represented as a contiguous memory array, and each collision lookup has the Big O of O(1) with good locality if you have to do multiple reads because entities need to be covered more than one cell in the grid. The disadvantage however is if the static background is large, is that the grid can be rather wasteful of space.

If instead you represent the static background as a quadtree, then the cost of individual lookups goes up, but because large blocks of the background take up small amounts of space, the memory requirements decrease, and so more of the background can sit in the cache. Even if it takes 10 times as many reads to do a lookup in such a structure, if it’s all in the cache, it’s still faster than a single lookup with a cache miss.

Personally I’d go with the grid implementation, because it’s easier to do and would be more productive for me to study. If I notice that our game is running slow, we’ll do some profiling and see what could use some help. If it looks like the game is spending a lot of time doing collision detection, we’d try quadtree and see if that’s any better.

Klonoa and its distinct 2.5D camera system

Image

Klonoa: Door to Phantomile (and its Wii remake) is a side-scrolling platform game viewed from a “2.5D” perspective. The player moves the protagonist, Klonoa, along a path in a two-dimensional fashion, but the game is rendered in three dimensions. This allows the path followed to curve and for the player to interact with objects outside of the path.

 Image

The term “2.5D” is also applied (though mathematically incorrect) to 3D games that use polygonal 3D graphics in order to render the world and characters, but the gameplay is still restricted to a 2D plane or gameplay system. The term is rather loose as term because it generally refers to any game with 3D graphics that feature any sort of 2D playing style.

For example, the Crash Bandicoot games of the Playstation 1 were considered 2.5D because despite the 3D graphics, most levels are not as free roaming as its competitor at the time Super Mario 64. There were even some levels where you can only traverse left and right (except maybe a part at the beginning and end where you move to and from your goal).

Image

The main problem is that the assumption of Crash Bandicoot being 2.5D is based on shallow aspects such as level layout and camera perspective of those levels, I’m not saying they’re not important, but in this case those aspects don’t make it a 2.5 game.

Image

The New Super Mario Bros. are also considered examples of the sub-genre as it uses 3D models and animations, but other than that it’s strictly 2D, the 3D parts of it are mere aesthetics. Layout, design, play style and controls, all of it is 2D. Street Fighter IV is another game considered 2.5D for similar reasons due to its 2D gameplay coupled with its 3D rendering.

I consider Klonoa to be the purest example of the subgenre because the combined design of the level layout, the gameplay and especially the camera angle are all 2D with 3D elements thrown in which is essentially the textbook definition of the term.

Image

Like many platformers you have a camera that interpolates accordingly along with the character’s ever changing position in a similar manner to other popular platformers like Mario. However there are points where you will end up turning as the level is not a straight line, when that happens the camera remains parallel to the character while maintaining a certain distance throughout, which includes moments when your character jumps towards the screen which is an example of a dynamic camera angle.

I chose this game in particular because it’s an example of how camera dynamics can ultimately create a new genre in a sense. Like in movies, camera works don’t just provide a visual of the audience but a whole new perspective.

Camera class system in game engines

The game’s camera system is nearly as vital as the player mechanics, it can make or break the entire experience, after all the most important aspect of a game is first and foremost being able to see what you’re doing.

Each game genre has its own camera control style according to how the gameplay will play out. There are several different types of cameras throughout games:

Image

You have Look-at cameras as seen above which rotates around your target point which is usually the playable character. Follow cameras that are usually in platformers and vehicle-based games. Unlike the Look-at camera that can be adjusted, this camera’s motion tends to lag around the playable character.

Image

The Follow camera is programmed with collision detection and avoidance logic in order to provide the player with some sort of control over the camera.

Image

First-person cameras are self-explanatory; its camera angle is at your character’s eye as you see the world from their perspective. The direction of sight translates directly into the aim direction of the player’s weapon. We move onto the RTS (Real-time strategy) cameras where the players’ points of view is from above the terrain looking down at an angle.

Image

Finally we have cinematic cameras; lots of games nowadays, particularly the big budget titles like God of War have cinematic moments where the camera moves in a filming manner which contrasts with the straightforward camera works of gameplay sections.

Image

Of course you can easily switch between both of these camera systems with the usage of camera states and a trigger system to switch between them.

A camera object in 3D gaming akin to a camera in a movie studio; you’re always switching from camera to camera, angle to angle by design of trigger systems and basic movement physics. It represents the window that players can look into and observe the objects, events and actions in the game.

Image

The OGRE viewport corresponds to a clipping region where the contents within view of the camera will be rendered in the window for each frame. Once a scene manager has been created using createSceneManager, the WinMain method is continued by creating a camera object along with a viewport object.

The camera object is created using the createCamera on the SceneManager, and developers must then create a viewport based on the same camera. The camera is a view into a scene and therefore depends on a scene manager for its existence. As a result, SceneManager objects are to be rendered before the cameras. In OGRE, camera are encapsulated in the Camera class using the createCamera method in the SceneManager class.

A look at abstract interface

Abstraction is about producing generalizations from certain instances. A complete abstraction can be identified by the general nature entirely, because it makes no reference to particular cases. The principle of abstraction is useful for engine developers because by designing the components of the engine to be abstract as opposed to particular so that developers increase their versatility which is proportional to their degree of abstraction.

An example of this is a render manager that may be used for all games as rendering is a vital process for every games. A text renderer manager on the other hand is less abstract and more limited in scope as it’s meant to render only text.

The main principle of abstraction encourages the engine developer to think in the abstract. To encourage them to identify many particular needs of a certain case and then proceed to expand upon it. Thus the purpose of abstraction is to increase versatility of engines.

An interface is not a class. It is an entity that is defined by the word Interface. An interface doesn’t have implementation; it only has the definition of the methods without the body. Similar to the abstract class, it is a contract that is used to define hierarchies for all subclasses or it defines specific set of methods and their arguments. The main difference between them is that a class can implement more than one interface but can only inherit from one abstract class. Since C# doesn’t support multiple inheritance, interfaces are utilized to implement multiple inheritance.

When we create an interface, we are basically creating a set of methods without any implementation that must be overridden by the implemented classes. They are used to define the peripheral abilities of a class. When it comes to features like multiple inheritance, a class may inherit several interfaces. Default implementation dictates that an interface cannot provide code, only signatures. Similarly they can access modifiers for the functions and properties with access modifiers, as everything is assumed as public.

If various implementations only share method signatures, it is recommended to use Interfaces as they are more efficient in this regard. If a new method is added to an Interface then we have to track down all the implementations of the interface and define implementation for the new method. A drawback is that they require more time to find the actual method and no field can be defined in interfaces.

More on Havok, physics and collision

What is the most important aspect of a video game? That’s something that has been debated since the inception of video games, and said question could be applied to its technological, spiritual predecessor which are sports, board games and other sorts of games. Every individual has their own opinion on the matter, and my personal opinion is that the most vital fundamental aspect of any game is interactivity; the point where the player’s choices and the game’s mechanics meet on mutual ground and develop an agreement. All games have rules that allow players certain freedoms and limitations, the player’s enjoyment essentially comes down to what state of mind these boundaries put them in.

Last week we made a very general observation of the Havok physics engine. This relates to my thesis statement as physics are an integral part of a games internal logic; the ability to move your character and do any other action is part of your freedoms, whilst falling in chasms and not penetrating walls makes up your limitations.

Collision detection is important for every game in that regard. Take away any form of collision and every object would fall through the ground with the ground itself, making any form of interaction impossible, unless you’re making a kill screen, this is not a reasonable programming design.

Collision and physics are more often than not a tightly knit pair. This is because at the moment collisions are detected, they are always resolved as part of the engine’s logic in physics and constraint integration.

The purpose of collision in a game engine is to determine whether any of the objects in the game’s world are in contact. In order to properly address this, each logical object is represented by geometric shapes. The collision system of the engine determines whether or not these specific shapes are intersection, which means that the collision detection is system is nothing more than a geometric intersection tester.

Collision systems are more than a true or false question regarding shape intersection. Its purpose is to provide relevant information about each contact. That information can be used to prevent unrealistic visual anomalies on screen. For example, last weekend at game jam, I coded an invisible border at the end of the level to go to the game over screen, an example of collision utilized to convey certain information on screen through the programming interface.

This information is used to prevent on-screen anomalies by moving the interpenetrating objects apart prior to rendering the next frame. They can also provide support for an object, such as an object at rest on the ground thanks to the force of gravity on the geometric shape of the ground acting upon it.

Indeed collisions essentially make up most of the gameplay. Think about it; coming into contact with a health power up, shooting at an object to destroy it, even being on the ground is a form of collision. Collision is the main fundamental aspect of interactivity in games, it supports nearly all of the player functions while fulfilling the main objective of the game, to enforce an experience on players.

A brief overview of the Havok Physics Engine

At 2K Czech, games demanded a physics solution that can scale efficiently and handle highly detailed interactive environments. Having recently moved to the next generation of Havok Physics, Havok’s new physics technology is able to make highly efficient utilization of all available hardware cores with a very lean runtime memory footprint. This combination allows us to deliver the high quality simulation at the scale we need and we are really looking forward to making some incredible games with the new technology.” -Laurent Gorga, Technical Director at 2K Czech.

Laurent Gorga, 2K Czech’s Technical Director, further added that “At 2K Czech, our games demand a physics solution that can scale efficiently and handle highly detailed interactive environments. Having recently moved to the next generation of Havok Physics, we’ve been blown away by how Havok’s new physics technology is able to make highly efficient utilization of all available hardware cores with a very lean runtime memory footprint.”

Developed by the Irish company Havok, the eponymous Havok Physics is a physics engine designed for video games to allow for real-time interaction between objects in 3D. The engine uses dynamic simulation to allow for ragdoll physics. The company was founded by Hugh Reynolds and Dr. Steven Collins in 1998 in Trinity College Dublin where much of its development is still carried out. Dr. Steven Collins currently acts as course director to Interactive Entertainment Technology in Trinity College Dublin, as well as lecturing in real-time rendering. Havok can also be found in Autodesk 3ds Max as a bundled plug-in called Reactor. A plugin for Autodesk Maya animation software and an extra for Adobe Director’s Shockwave are also available.

As a result Havok offers the fastest and most robust collision detection and physical simulation technology available, which is why it has become the ideal physics engine to go to within the games industry and has been used by leading game developers in over 400 launched titles and many more in development.

Havok Physics is fully multi-threaded and cross-platform optimized for leading game platforms including, Xbox 360™, Playstation® 4, PlayStation®3 computer entertainment system, PC Games for Windows, PlayStation Vita®, Wii™, Wii U™, Android™, iOS, Apple Mac OS and Linux.

In 2008 Havok released details of its new Cloth and Destruction middleware. Cloth deals with simulation of character garments and soft bodies while Destruction provides tools for creation of destructible and deformable environments. Havok Cloth was the company’s most widely adopted and bestselling piece of software to date.

At GDC 2009 Havok showcased the first details of its forth coming artificial intelligence tools which will allow for better performing AI in games without the need for the developers to create their own AI models.

Whenever people say “Havok Physics”, all I can think of is The Elder Scrolls: Oblivion.  One of its major selling points was Havok Physics.  Anyone who has played that game knows how messed up Havok Physics can get, and how silly of situations you can create with it. Grand Theft Auto 4 also uses Havok Physics.

It was also used throughout the Halo games from Halo 2 onwards. In the Halo 3 engine The Halo 3 physics engine runs calculations on every single frame of animation, similarly to the collision detection engine. The engine is capable of calculating, among other things, elasticity on portions of character models; and bullet ricochet.

Character models are quite elastic at points, a characteristic that is clearly demonstrated by the Character Stretch Glitch’s presence in the game. The elasticity helps to improve realism at slower speeds. Only some parts of a character’s model are elastic; if you look closely at screenshots of the aforementioned glitch, you will find that the rigid parts of Spartans’ and Marines’ armor don’t stretch.

The physics engine utilizes an optimization found in many video game physics engines: objects that remain at rest for several seconds are temporarily exempted from physics calculations (but not collision detection) until they are disturbed again; this is why floating Crates and Fusion coils can remain floating in the air until the round is restarted or the items are disturbed. An object is considered “disturbed” if it is moved, picked up (in Forge), or if something collides with it.[5] The optimization is likely based on the premise that an object that isn’t moving now isn’t likely to move in the near future unless something moves it or it moves on its own.

Havok has announced the launch of the third major iteration to its Havok Physics technology that features “significant technical innovations” in performance, memory utilization, usability, and is a “major leap forward” for in-game physics simulation. The release is specifically targeted towards next-generation consoles, mobile devices, and PCs with full compatibility and support for current devices.

According to Andew Bond, Vice President of Technology for Havok, this version has resulted in a “new engine core built around fully continuous simulation that enables maximum physical fidelity with unprecedented performance speeds. Beta versions of the technology have been in the hands of a number of leading developers for some time and we have seen dramatic performance gains with simulations running twice as fast or more, and using up to 10 times less memory. Additionally the new core’s performance is extremely predictable, eliminating performance spikes.”

The game engine I am destined to create

Every aspiring game developer has hopes of making the next great game, or for those who are more realistic, make a game that can be enjoyed by people while paying your light bill. Strangely enough, it’s usually those starting out in their game development school who think the former while people with more education in the field along with more experience tend to sway towards the latter.

Does it necessarily have to do with the fact that our youthful energy is being syphoned out of us as we progress?

Image

Considering it is university yes, however the main reason is as we mature we develop a more realistic outlook on things which makes us set realistic goals. How you set the scope for your projects may make or break it with carefully consideration of your resources, talents and limitations.

Hence why we’re studying Game Engine Design and Implementation, to culminate all our coding knowledge so far to be able to put together a workable engine that can support graphics, animation, gaming mechanics and all our gaming knowledge. So for this blog, I will talk about how I would design the engine of a standard platform game.

The term game engine was coined in the nineties in which it was referring to first-person shooters such as Id’s prolific title Doom due to how intricately its architecture was defined. With separation between core software components, art assets and gameplay mechanics, this is when developers started licencing games and re-tooling them into newer games which opened a whole new world for independent studios and other small organizations.

Image

The game in question will be based on Uncharted’s engine along with the player mechanics of the Spiderman games and the recent Ninja Gaiden games. Given that the engine in question contains many of the ideal mechanics required to put out a solid platformer on the level of Crash Bandicoot which was also created and published by Naughty Dog.

I intend to use this engine as a template for other types of games such as adventure and fighting games since those are the types of games I intend to make and both games require the following:

–       A third-person view camera that follows your characters and stays focused on the players general area in order to focus on its location and the surrounding radius to alert the player of incoming hazards.

–       A camera collision system to ensure that view points never go into places it’s not supposed such as into the background or into a mountain.

–       A rich set of animations rendered for all sorts of commands from climbing to fighting.

–       User inputs that allow players to execute all sorts of tasks.

I mentioned earlier that I aim to include the player mechanics of Spiderman from the Spiderman games and Ryu Hayabusa from the Ninja Gaiden games. Why you ask? Because both characters both characters can do virtually anything; from jumping to climbing to fighting. More than most characters, they do the best job of making the player feel like their capabilities are limitless.

Image

Spiderman for the Playstation, the game the developers of Superman 64 wish they’d made.

There has never been a concrete measurement or assessment of how a game can be good as games can be good for several different reasons, in my opinion, I think the ultimate way to determine a game’s quality is to identity how deeply you can immerse players into the experience and what better way to do so that with a character who can do just about everything.

This is why user inputs is very important, the possibilities of the game’s world is placed in their hand and the transition from one action to the next should be seamless and effortless on the part of the player.

In order to ensure an acceptable framerate it’s important to design the engine so that it can manage all the objects on screen without slowing down the action. In this regard we can take a page out of Insomniac’s hit title Spyro which managed to create massive worlds with distances that expanded to the horizon without relying on fog effects, this was done writing code that would decrease and increase the polygon count of far away objects relative to your character’s distance. This way objects can be slowly loaded over time so as not to overload the console.

Image

Platformers tended to be drawn and designed in cartoon like manners with little emphasis on realism. I grew up with cartoons and platformers such as Mario, Crash Bandicoot and Sonic, so I intend to use such a style. Many of these games relied on principles of animation such as anticipation, squash and stretch, pose to pose, timing and exaggeration in order to achieve the cartoon-like style they were aiming for.

Most of these games were made before Smilebit’s Jet Set Radio spearheaded the use of toon shading in games. I like the toon shading effect because it gives games the comic book feel that I like, however since most of these games were animated and rendered the way they were prior to cel-shading, it’s important to realize that just combing them would be overkill, so it’s important not to just throw them together but to create a balance.

Motion capture generally results in the smoothest and most realistic movement animations so I appoint to utilize it with motion capture artists who can capture the exaggerated movements of cartoon characters in conjunction with the model rendering to capture the less feasible principles such as exaggeration when it comes to characters changing size for the sake of humor.

That’s all for now, it’s still pretty early in the course with much to learn on game engines hence my immature knowledge of the subject, so I just gave you may basic understanding based on previous education and a lifetime passion for gaming. Stay tuned to my blog and see how far I come with my understanding of the topic.