N Puzzle

N Puzzle.

A classic problem in Computer Science.
The problem utilizes search techniques which are parts of Artificial Intelligence(AI) techniques to find the solution to the problem.
The solution of N Puzzle is how to move tiles in a series that leads from the starting state(scrambled ordered tiles) to the goal state(properly ordered tiles).

There are various search techniques that can be used to solve the N Puzzle problem.
The videos above show solving N Puzzle with heuristic search(informed search) techniques.
Algorithms utilized are Best First Search, A*, and IDA*.
Each algorithm has a different behavior in solving the problem. The amount of time required, CPU usage, and memory consumption are also different.

N Puzzle problem can be varied in complexity. For example, consider 8 Puzzle problem(8 tiles) with empty tile shown as x:
Goal state is
1   2   3
4  5   6
7   8   x
while starting state can be varied
1   2   3             6   7   2
4  5   6             8   x   4
x   7   8             5   3   1
Clearly, the state on the left is much easier to solve than the state on the right, thus the state on the right is more complex than the state on the left.

Another major factor of the N Puzzle problem is the number of the puzzle. 8 Puzzle has 8 tiles(excluding empty tile). 15 Puzzle has 15 tiles. 24 Puzzle has 24 tiles and so on.
The complexity of the puzzle grows with the number of the puzzle and how scrambled the order of tiles in the puzzle is.

The complexity of the puzzle, search algorithm utilized, and heuristic functions used are key factors that determine the amount of time needed, CPU usage, and memory consumption when solving the puzzle. Puzzles can take a very long time to solve due to the factors described. The numbers of possible states are 9! (factorial) for 8 puzzle, 16! for 15 puzzle, 25! for 24 puzzle, and so on. The size of the answer space is huge. N Puzzle problem is proved to be NP-hard problem.

Heuristic functions utilized for solving the N puzzle shown in the videos are Manhattan Distance combined with Linear Conflict.
In the videos, the app would calculate the solution to the puzzle when the user presses the Solve button. While calculating the solution, the Solve button would appear gray. After the solution is found, the Solve button would return to normal and the solution would be shown, animating the tiles for the user to see.
The amount of time used in solving the problem and the number of steps that leads from the starting state to the goal state along with the number of states generated while searching are shown in the table below. The same size of puzzle with different algorithms have the same starting state of the puzzle in order to compare the performance of the algorithms.

Number of puzzles - Search algorhthmTime consumption (milliseconds)Number of states generatedNumber of steps for solution
8 Puzzle - Best First Search1917637
15 Puzzle - Best First Search1593746239
24 Puzzle - Best First Search2184438317
8 Puzzle - A*223173627
15 Puzzle - A*XXX
8 Puzzle - IDA*1002363, 4 iterations27
15 Puzzle - IDA*20478682684, 10 iterations59

In the scope of N Puzzle, as shown from the results in the table.
Best First Search can find the solution to the problem quickly but does not guarantee the shortest path(the least number of steps that are needed to be taken) from the starting state to the goal state.

A* takes a longer time in searching for a solution. However, the A* algorithm guarantees to give the shortest path solution.
A* in 15 puzzle could not find a solution to the problem in practical time. This is due to the behavior of the A* algorithm. Since 15 puzzle can have 16! possible states(20,922,789,888,000 states), the A* algorithm would try to find the shortest path solution, having almost all states generated in the process due to the heuristic function utilized being consistent. The amount of time needed is enormous.

Improvement can be made on this issue by using IDA* algorithm instead. Like A*, the IDA* algorithm guarantees to give the solution that is the shortest path. Combining Depth First Search with Iterative Deepening Search, the amount of time needed to solve the N Puzzle is significantly reduced compared to the case of A* algorithm.

However, for 24 puzzle and above, to solve the puzzle with A* or IDA* algorithm in practical time will need a better heuristic function than Manhattan Distance. Disjoint Pattern Database can fill in for this role. Using Disjoint Pattern Database with IDA* algorithm, an arbitrary solvable 15 puzzle can be solved in just about 30 milliseconds on average.

N Puzzle Solver part of the app is written in C/C++(Modern C++) and can run on any platform that supports C/C++. Testing for the solvable property of the puzzle presented is also implemented.

Platform: iOS
Programming Language: Objective-C, C/C++
Device: iPhone 5S

DirectX 11 – Game Scene with C++11/14

Game Scene post updated with C++11/14.

In order to compare with the previous version of the program, the update is done in a manner that preserves the original algorithm and data structure. Updates that result in major changes in algorithm or data structure are not performed.
Since the Game Scene is not designed with C++11/14 features in the first place, after the scene is updated, performance only improves slightly.
However, the scene and program’s code still benefit from the new C++ features.
For example, the code structures in various parts of the project are cleaner.
Load time is reduced and data are handled in more efficient ways with the use of move and rvalue reference.
Function overhead is also reduced due to the use of lambda.
This experiment shows that the C++11/14 standard offers useful and powerful features for Game development and programming in general.

Features utilized: auto, decltype, uniform initialization and initializer list, new style function declaration, delete keyword, override identifier, nullptr, range-based for loop, right angle bracelet, strong typed enum, smart pointer, move and rvalue reference, lambda, and digit separator.

DirectX 11 – Game Scene

A Game scene implemented in DirectX 11.

Floor utilizes normal mapping to make it appear to have more details.
Sky is implemented using a sky-dome primitive and a cube map texture.
Tower objects are rendered using instancing method. Each tower has its own transformation(rotation and translation) but all towers have the same scaling. Since the tower model has transparency parts on it, alpha clipping is utilized.
Bat object has skeletal animations implemented as a combined animation. Skeletal animation system is manually implemented and utilizes vertex blending and quaternion interpolation.
Tower and bat objects have back-face culling disabled when drawn since they have some parts that have to be visible even though they are back-facing.
Lighting is also implemented in this scene.

All the objects in the scene are shaded in a way like there are in sunlight.
Tower and bat objects are just normal models with only model textures, no normal map textures are provided. In this scene, the bat object appears to have specular highlights. This is because the bat model does not have normal map texture provided, as a result, averaged normal vectors from the model’s vertices are used instead.
Light source utilizes in the scene is a point light to demonstrate shadow. The light source can be moved around in the scene which will make shadows of the objects in the scene change position.

Shadows of the objects in the scene are implemented using dynamic shadow mapping which renders the scene from the perspective of the light source into shadow map(depth map) texture every frame. Any change of objects in the scene(like the bat’s animation) will result in its shadow being changed in real time. The intensity of shadows can also be changed, however, the shadow’s intensity is fixed in this program.
(Rendering and litting the scene from the perspective of light sources are part of volumetric lighting technique. Projective light maps can be utilized for this technique.)

Shadow map texture generated is used to render shadows of objects in the scene via projective texturing. PCF filtering is implemented for smoothing the edge of shadows rendered. Depth bias is also utilized when rendering the shadow map(depth map) to help fix shadow acne problem. (Shadow mapping in this scene can still be improved and shadow acne can still appear on some surfaces in the scene which becomes noticeable when zooming in).

Shadow map(depth map) texture generated can be viewed. Any change of objects in the scene will be reflected in the shadow map in real time. For showing shadow map texture as a greyscale image, re-linearization is needed for depth values in the shadow map texture since the original depth values from shadow map texture are non-linear values.

Camera systems are manually designed and implemented from scratch and can be switched between 3 modes.

First person shooter(FPS) mode. Camera mode like in FPS games. The bat character can be controlled in the same manner as in FPS games.

Third person shooter(TPS) mode. Camera mode like in TPS games. The character can be controlled in the same manner as in TPS games.

Third person(TP) mode. Camera mode like in third-person games. The camera can be moved around in the scene in this mode and has been designed in a way that prevents Gimbal lock. Camera focuses on the character. Moving the character forward will make the character move in the direction the camera is facing. Moving the character backward will make the character move toward the camera. In both cases, the camera will adjust itself according to the character’s position. Moving in the left or right direction will cause the character to move left or right in a circle, the camera will also adjust itself according to the character’s position. Moving the character diagonally forward or backward will cause the camera to adjust itself to the character’s position too. Notice that when the character turns around in this mode when moving around in the scene. It will always turn around from one orientation to another orientation using the shortest arc.

Collision detection is also implemented. Collision detection implemented is just a simple collision detection using AABB(Axis-Aligned Bounding Box). Collision detection in this program is meant to be a test feature and is not optimized in any way. Unintentional behavior can occur sometimes. Collision detection feature can be turned on and off to help ease unintentional behavior if it occurs. Camera collision is not implemented.

Gamepad is also supported. Gamepad’s type supported is X-Input gamepad type. The program will recognize the gamepad automatically when plugged in.

Uses fixed-axis rotation.

Program file can be downloaded here.

Requirements: DirectX 11 supported graphics card, Windows 7/8/8.1/10/11, Visual C++ Redistributable Packages for Visual Studio 2013(x86).

Control:
Press “p” on the keyboard to make the bat character perform animations.
Press “l” on the keyboard to toggle light source re-positioning mode on and off. In this mode, the light source can be moved around in the scene via holding left-click and drag the mouse.
Press “m” on the keyboard to toggle the rendering of shadow map on the screen. If turned on, the dynamic shadow map that is rendered every frame can be viewed as a minimap at the corner of the program’s screen.
Press “u” on the keyboard to toggle collision detection on and off.

The default camera mode is Third person mode.
The character’s orientation and position are consistent across all of the camera modes.

Press “1” on the keyboard to change the camera into First person shooter mode.
FPS camera mode:
Moving the mouse will change the direction the character is facing.
Press “w” on the keyboard to move the character forward.
Press “a” on the keyboard to move the character to the left.
Press “s” on the keyboard to move the character backward.
Press “d” on the keyboard to move the character to the right.
Moving character diagonally is also possible by pressing w and a/d or s and a/d at the same time.

Press “2” on the keyboard to change the camera into Third person shooter mode.
TPS camera mode:
Moving the mouse will change the direction the character is facing.
Press “w” on the keyboard to move the character forward.
Press “a” on the keyboard to move the character to the left.
Press “s” on the keyboard to move the character backward.
Press “d” on the keyboard to move the character to the right.
Moving character diagonally is also possible by pressing w and a/d or s and a/d at the same time.

Press “3” on the keyboard to change the camera into Third person mode.
TP camera mode:
Left-click anywhere in the scene then hold left-click and drag the mouse to move the camera around in the scene.
Press “w” on the keyboard to move the character in the direction the camera is facing.
Press “a” on the keyboard to move the character to the left of the direction the camera is facing.
Press “s” on the keyboard to move the character in the opposite direction of the direction the camera is facing.
Press “d” on the keyboard to move the character to the right of the direction the camera is facing.
Moving character diagonally is also possible by pressing w and a/d or s and a/d at the same time.

Using Gamepad:
Gamepad control is referenced based on the layout of the buttons of Xbox360 game controller and Xbox One game controller.

Moving the left analog stick up will give the same result as pressing “w” on the keyboard in any camera mode.
Moving the left analog stick left will give the same result as pressing “a” on the keyboard in any camera mode.
Moving the left analog stick down will give the same result as pressing “s” on the keyboard in any camera mode.
Moving the left analog stick right will give the same result as pressing “d” on the keyboard in any camera mode.
Moving the character diagonally is possible by moving the left analog stick diagonally.
Moving the right analog stick will give the same result as moving the mouse in First person shooter and Third person shooter camera mode and “hold left-click and drag the mouse” in Third person mode.

Press “B” button on the gamepad to make the bat character perform animations.
Press “A” button on the gamepad to toggle light source re-positioning mode on and off. In this mode, the light source can be moved around in the scene by moving the right analog stick.
Press “X” on the gamepad to toggle the rendering of shadow map on the screen.
Press “Y” on the gamepad to toggle collision detection on and off.
Press “RB” on the gamepad to change the camera into First person shooter mode.
Press “RT” on the gamepad to change the camera into Third person shooter mode.
Press “LT” on the gamepad to change the camera into Third person mode.

Platform: Windows
Programming Language: C/C++, HLSL

Resources: Sky cube map texture is from companion DVD of the book 3D Game Programming with DirectX 11 by Frank D. Luna, Mercury Learning.

Texture loading is implemented using DirectX TK library.
3D model loading is implemented using ASSIMP. ASSIMP loads 3D models and provides data loaded in its own format.
In order to make 3D model data loaded by ASSIMP easier to use, a wrapper for ASSIMP that parses data from ASSIMP’s format into a format that is easier to work with, handles model loading and animation processing has been manually created.
Gamepad’s input handling is implemented using DirectX TK library.

DirectX 11 – Skeletal Animaiton and Mirror effect

A Game scene with 3D models, skeletal animation, and mirror effect.

The bat model has skeletal animations that are created and embedded in the model as a combined animation.
Skeletal animation system is manually implemented and utilizes vertex blending and quaternion interpolation.
Tower model has alpha clipping implemented since it has transparent parts.
Mirror effect is implemented using stenciling.
The mirror in the scene has been designed as an ideal mirror, with no surface effects or distortion of the picture in the mirror.
Mirror’s surface can be modified by modulated with colors from textures to create surface effects.

Back-face culling is disabled for the bat model, tower model, and floor while enabled for the mirror and wall the mirror was on.
Uses fixed-axis rotation.

Program file can be downloaded here.

Requirements: DirectX 11 supported graphics card, Windows 7/8/8.1/10/11, Visual C++ Redistributable Packages for Visual Studio 2013(x86).

Control:
Left-click anywhere in the scene then hold left-click and drag the mouse to move the camera around in the scene.
Scroll up and down to zoom in and zoom out.
Press “p” on the keyboard to make the bat character perform animations.

Platform: Windows
Programming Language: C/C++, HLSL

Texture loading is implemented using DirectX TK library.
3D model loading is implemented using ASSIMP. ASSIMP loads 3D models and provides data loaded in its own format.
In order to make 3D models’ data loaded by ASSIMP easier to use, a wrapper for ASSIMP that parses data from ASSIMP’s format into a format that is easier to work with, handles model loading and animation processing has been manually created.

DirectX 11 – Waves with Tessellation, Displacement mapping, Normal mapping, and Transparency blending

Another improvement can be added to Waves posts(here and here).

With lighting and normal mapping already implemented. The color of the waves can also be modified to make them look more like real water. The waves’ surface transparency property is then taken into account.
By having another surface beneath the waves and making the surface of the waves semi-transparent using transparency blending, a more realistic wave surface can be achieved.

Backface culling is disabled.
Uses fixed-axis rotation.

Program file can be downloaded here.

Requirements: DirectX 11 supported graphics card, Windows 7/8/8.1/10/11, Visual C++ Redistributable Packages for Visual Studio 2013(x86).

Control:
Left-click anywhere in the scene then hold left-click and drag the mouse to move the camera around in the scene.
Double-click to toggle between solid and wireframe mode.
Scroll up and down to zoom in and zoom out.

Platform: Windows
Programming Language: C/C++, HLSL

Resources: Normal map and height map textures(Normal vector values and height values are combined into the same texture) are from companion DVD of the book 3D Game Programming with DirectX 11 by Frank D. Luna, Mercury Learning.

Texture loading is implemented using DirectX TK library.