The title of this project is Block Link 3D
Block Link is a kind of picture matching game and the traditional Block Link Game is implemented in 2D.
Figure 1: Traditional Block Link Game
The mechanics of this game:
Step 1: Find out the same pictures in the game board.
Step 2: Check the path: if the path contains no more than 2 corners, this path is considered as valid and the matching picture can be deleted. Otherwise the path is invalid and a simple notice will be displayed in the game world.
Step 3: If there’s no valid path in the game board, the blocks will be replaced. The goal of this game is to clear all the blocks on the game board.
The relevant algorithms in this game are path finding, items matching and map creation. In this project, a 3D version of Block Link game is developed and all those algorithms are implemented in 3D world.
3D Path finding: 3D path finding is a little different with 2D path finding and in this project, there are two solutions.
Solution 1: Use the existing 2D path finding algorithm like A Star and Depth first. It can get many paths by using this solution, and from those paths one valid path can then be chosen. However this is not the best solution. According to the solution the steps we need to do is
Step 1: Finding a path.
Step 2: check whether the path is valid
Step 3: if the path is valid, go to Step 4, otherwise go to Step 1.
Step 4: path finding complete
Step 1 waste a lot of time. In order to improve the performance of the path finding, the executed steps should be as less as possible. In this solution, the step 1 will be executed many times if the application can’t find a valid path. In figure 2, there are at least 6 paths with the same distance, we assume that the path with 2 corners is invalid, that means there is no valid path from A to B. The application needs to execute 6 times of step 1 to get this result. If there are more nodes between A and B, the execution time will be an amazing number.
FIGURE 2: USE THE EXISTING 2D PATH FINDING ALGORITHMS
Solution 2: In this solution we will try to find a path by using the existing limiting condition and geometry algorithm.
Limiting condition: path with no more than 2 corners is valid.
That means if the application finds a path with more than 2 corners, it should stop this thread and start another one.
According to the limiting condition and geometry algorithm we can define 3 conditions.
Condition 1:
A and B have same X and Z values, so that the coordinate for node A is (x, y1, z) and node B is (x, y2, z). There are four options under this condition.
| X | Y1 | Z | X | Y2 | Z | ||
| A’ | X+N | Y1 | Z | B’ | X+ N | Y2 | Z |
| A’ | X- N | Y1 | Z | B’ | X- N | Y2 | Z |
| A’ | X | Y1 | Z+ N | B’ | X | Y2 | Z+ N |
| A’ | X | Y1 | Z- N | B’ | X | Y2 | Z- N |
| N is 1, 2, 3, 4….Until the max length of the lines. | |||||||
The application needs to check whether there is a block between A’ and B’. If there’s no blocks between A’ and B’, it means A’B’ is a valid path (no corner) and a valid path between A and B has been found: A->A’->B’->B. If there is a block between A’B’, then the application need to check other nodes.
This condition 1 also can be applies when node A and B have the same X and Y coordinates when the coordinate of node A is (x, y, z1) and node B is (x, y, z2). Or when node A and node B have same Y and Z coordinates when the coordinate of node A is (x1, y, z) and node B is (x2, y, z).
FIGURE 3: CONDITION 1
Condition 2:
A(x1, y, z2) and B(x2, y, z2) have the same Y value, it means they are on the same plane. In this condition, the application needs to check whether there’s a path between A and B with no blocks. And the path also needs to meet the following conditions:
Every node in the path has a same Y coordinate. First define node C(x2, y, z1), this node share the same X coordinate with node A and same Z coordinate with node B.
If there are two corners existing in the path: A’(x1’, y, z1’), B’(x2’, y, z2’) which meet the following condition
|BB’ – AA’| = |AC| or |BB’-AA’| = |BC|
That means this is a valid path.
The path meets this conditions are illustrated in the Figure 4.
FIGURE 4: CONDITION 2
This condition 2 can also be applied when node A (x, y1, z1) and node B (x, y2, z2) have the same X value or when node A (x1, y1, z) and node B (x2, y2, z) have the same Z value.
Condition 3:
Node A (x1, y1, z1) and node B (x2, y2, z2) has different X, Y, Z coordinates. A cube with A and B as two nodes can be created. There are 6 different paths need to be checked. If none of those 6 paths is valid. There’s no valid path between A and B.
FIGURE 5: CONDITION 3
Six different paths:
A->D’->F->B
A->D’->E’->B
A->C->E->B
A->X->E’->B
A->D->F->B
A->D->E->B
2.21 Blocks Array
There are two solutions for storing the block data: Array and Matrix. Matrix has a lot of advantages however it’s not easy for finding the positions of a block. In this project, an array is used to store the data of the block data.
public int ThreeDToOneD(int x, int y, int z)
{
return MatrixLength * MatrixLength * z + MatrixLength * y + x;
}
public void OneDToThreeD(int w, out int x, out int y, out int z)
{
z = w / (MatrixLength * MatrixLength);
y = (w / MatrixLength) % MatrixLength;
x = w % MatrixLength;
}
Matrix to Array
2.23 Block Information
A Struct has been used in this project to store the block information.
public struct BL_3D_Block
{
public bool IsSelected { get; set; }
public int Index { get; set; }
public Matrix ModelWorldTransform { get; set; }
public bool IsDeleted { get; set; }
}
3.1 GAME PROCESS
The game contains 4 different statuses: Game_Welcome, Game_Start, Game_Success and Game_End.
Game_Welcome: The welcome screen of the game, it contains game menu, game information and some animations.
Game_Start: Start a new level of the game
Game_Success: Successful complete one level
Game_End: Game Over
FIGURE 6: GAME PROCESS
There are four levels in this game. The level design depends on the following properties of the game.
The blocks number, Auto-Rotation, Add new blocks when the player find invalid path and enable the keyboard rotation. The level settings can be pre-defined in the app.config file.
<?xml version=”1.0″?>
<configuration>
<appSettings>
<add key=”level1″ value=”4|7|0|0|Y|Y|0|4″/>
<add key=”level2″ value=”4|8|1|1|Y|Y|0|4″/>
<add key=”level3″ value=”5|12|0|0|Y|Y|1|2″/>
<add key=”level4″ value=”5|12|1|1|Y|N|1|2″/>
</appSettings>
</configuration>
FIGURE 7: FILE STRUCTURE
BL_3D_Background.cs
The code in this file implements the background animation of the game. There are two objects in the background which do the rotation transform. It also plays the background music by using the Microsoft.Xna.Framework.Media.song.
BL_3D_Mouse.cs
The code in this file contains all the mouse events that occur in this project, besides it also implements the Ray test in the game. It enables the mouse to choose blocks.
BL_3D_Game.cs
The code in this file implement the map creation, map resetting and it also init the block world transform.
BL_3D_Levels.cs
The code in this file implemented the following functions:
BL_3D_Path_Finding.cs
Implement the 3d path finding.
BL_3D_GameEnd.cs/ BL_3D_GameStart.cs/ BL_3D_Success.cs/ BL_3D_Welcome.cs
Implement the interface of different game status: Game menu, Game music and Game information
BL_3D_GameRelatedValue.cs/ BL_3D_InformationBarAndTimer.cs
Provide game information to the players.
BL_3D_GameStatus.cs/ BL_3D_GameRelatedValue.cs
The definition of the game related struct and enum
BlockLink3D.cs
The code in this file controls the processes of the game.
Program.cs
This is the entry point of the application. It also loads the basic setting of the game.
Welcome:
Figure 8: Welcome
Level 1:
Figure 9: Level 1
Level 3:
Figure 10: Level 3
Level 1 Finishes:
Figure 11: Level 1 Finishes
Game Over:
Figure 11: Game Over
