61 Cygni - Game prototype

I hope you will enjoy this new prototype.

Some screen captures:

I built it in 2 months. I used Box2D for physics. I used musics from Super Metroid and sounds from Doom PS1.

I used Daedalus Lib to triangulate automatically the entire level. It made things fast and easy for pathfinding, fast bullet collision detection and fog of war. A great save of time allowing me to focus deeply on gameplay.

I would love to continue the production of that game. If you are producer or publisher, feel free to contact me. We could target Steam as well as mobile platform.

Click below to play the game (fullscreen mode)

Triangulated circular maze generation

Always in the way to find new ways to proceduraly build dungeons and mazes, here the circular maze.

You can find many demos on internet showing circular maze generation, but my own is original and has many benefits:
- it is triangulated with Daedalus Lib, so pathfinding can be used directly
- it has several parameters

But more than words, there is a playable demo :



The build random button allows you to generate new mazes very easily.

So now, if you are interested by the method, just read the rest.

Step 1:
We start from a basic rectangular mesh with Daedalus Lib.

Step 2:
We add concentric circles as constrained edges in the mesh. We start with the smallest circle using min radius parameter. Then we continue with larger circles, increasing the radius with dist circles parameter each times. The circles has edge counts being the maximum possible, but keeping edges length larger than min len edge parameter.

Step 3:
We connect the circles with constrained edges from vertex to vertex.

Step 4:
We start from any point and we explore the set of constrained edges with a custom pseudo randomized depth-first-search algorithm (use the seed parameter). We keep only the traversed edges and build a new mesh from them.

At this step, the result show us the navigation path of our maze.

Step 5:
We add central edges in addition to our previously generated navigation path. It makes the center an important place in the maze.

Step 6:
Finally we apply a chamfer algorithm.

Here is the result with high values:

Introducing Daedalus Lib

Project on GitHub

Daedalus is a library I develop. It manages 2D environment modeling and pathfinding. I really hope this library will help designers and developers to invent new gameplays.

When I began to code Daedalus, I had many ideas in mind:

1- focus on 2D
2- fastness and accuracy
3- simplicity of use


1- Why focus only on 2D and not on 3D ? Because constraining to 2D allows to gain simplicity and efficiency. Many great games today are still based on 2D engines involving 2D mechanics, 2D physics and 2D display ; so I hope Daedalus will find his place as a new component for new 2D projects.


2- Fastness and accuracy are reached by using among the best techniques available in the fields of computational geometry : quad-edge structure and fully dynamic Delaunay triangulation. Daedalus algorithms are based on many research publications, among them:

Fully Dynamic Constrained Delaunay Triangulation by Kallmann, Bieri and Thalmann
An improved incremental algorithm for constructing... by Anglada
Efficient Triangulation-Based Pathfinding by Jon Demyen


3- For simplicity, I assumed that the library should work without any pre-generated data. Everything should work in real time : obstacles insertion/motion/deletion and path generation. Also I assumed that the library should be fault tolerant to designer/developer mistakes : obstacles can overlap and can be of any shape : open, convex, concave... At last, the path generation manages non-null size objects in order to avoid any obstacle collision.


Now the basics are exposed, I can show you some demos :

Today Daedalus is coded in Actionscript. But because the library has no dependancies from any other library (I wrote the whole mathematics), it can easily and quickly be translated in any other language. The project is not open-source at this moment, so not available for free download. I plan to use it in some new projects before release it in the open world.

So I am now looking for some collaboration. If you feel interested by Daedalus for your game engine, for a commercial game project or any other application, you can contact me directly at flash dot cedric at google mail service.

Box2D to Daedalus bridge

Things become interesting. Now Daedalus is equiped with 2 new components to cooperate closely with Box2D.

The first is a simple Box2D-body to Daedalus- object converter. It makes things very easy when you want to generate and update a constrained Delaunay triangulation as a mirror of a Box2D world.

The second is more complex. We can see it as a Box2D body object "drived" by the Daedalus pathfinder. It applies Box2D forces to the object to ensure it closely follows a path and reach a destination. This is the first attempt and many other "driver" must be created now according to the nature of the entities we want to simulate (a pedestrian, a car, a spaceship, a robot...).

I hope you will enjoy the demo:

Pathfinding on bitmap triangulation

Because large triangulated maps can be a pain to design by hand, I implemented into Daedalus an algorithm generating optimized triangulations from bitmap images. It is directly inspired by the bitmap segmentation in the Potrace algorithm.

How does-it work ?

Just give a picture made from black and white pixels to the algorithm. For example:

Then the algorithm returns to you a clean and beautiful triangulation:

Neither parameter nor configuration filling are required. Just give the bitmap and get the mesh.

However, black and white pictures are required. But we can consider the use of a threshold to easily convert gray scale and color images.

From that, I experimented with success the use of pathfinding on several triangulations generated from:

- a SNES Mario Kart circuit map

- a Doom map

- a picture of the labyrinth at Grace Cathedral

- a map of Paris created by artist Jazzberry Blue

I used Photoshop to extract properly black and white pictures from the previous maps. Then I just played with the algorithm and enjoyed the fast and accurate pathfinding implemented in Daedalus Lib.

As you can see by yourself:

Daedalus : group pathfinding and FOV

Today 2 new demos made with Daedalus, showing in action 2 new components: group pathfinding and field of view.

The group pathfinding has many interesting features:
- it can manage any number of entities
- it can manage any size of entities
- generated paths are automatically sampled in order to synchronise the entities and avoid collision between them

We could just reproach the single common path the entities use. Indeed, if the entities have different sizes, it could be legitimate to expect them to reach the goals by different optimized paths and keep synchronisation to avoid collision. But in fact, this behavior is the subject of a new component coming soon, more focused on synchronisation for entities having completely different start and goal positions.


Then the field of view, while looking not so impressive, is a very important component to give awareness to AI entities, allowing them to detect cleverly the other entities. The features are:
- radius, opening angle, position and direction as dynamic properties
- the FOV is broken by constrained edges (other entities can hide behind walls)
- it manages non-null size entites

In the details, the FOV implementation is simply an accurate clipping system. So it can really manages the visibility of an entity through very complex situation with partially overlapping walls.

Demo : fully dynamic Delaunay triangulation

Demo : pathfinding on Delaunay constrained triangulation

A simple planar mesh primitive with half-edge

In a previous article, I explained why and how to implement the half-edge data structure. This article will focus on the implemention of a simple primitive: a 2 polygons rectangular planar mesh. Later we will see how to add some useful tools allowing us to expand the primitive by adding/removing vertices and flipping edges,

The implementation of a simple 2 polygons rectangle primitive could look easy at first glimpse. In reality, with half-edge, it is not so obvious. We need to be very careful and set all the relevant adjacency relations between the 4 vertices, the 10 oriented edges and the 2 faces:

Remember that each edge must references 4 datas: the origin vertex, the opposite edge, the next left edge and the left face:

We immediatly face an annoying problem : the 4 border edges e01, e12, e23 and e30 have neither left face nor next left edge. We could think that leaving null references as datas for these edges is safe, but in fact it would lead to several problems because the missing core datas would break the way we hope to iterate through the mesh. That's why I suggest rather to extend the rectangle in order to obtain a complete closed and consistent mesh:

We just added 2 new edges e13, e31 and 2 new faces f2 (bounded by e12, e23, e31) and f3 (bounded by e30, e01, e13)  This figure could look strange at first glimpse, but in fact it is really intuitive if you imagine our planar mesh lying on a sphere:

Finally, if these 4 new elements are convenient to get a mesh with a complete adjacency structure, they can be cumbersome when you display your mesh on screen or when you iterate in order to navigate from element to element. So feel free to add a new visible property to your classes and set it to false for any object lying outside the rectangle v0, v1, v2, v3. In this way you will be able to simply skip them.

As a conclusion, we will simply give now the complete declarations necessary to implement this simple rectangular primitive:

// (x, y) is any 2d coordinates system
// w is the rectangle width
// h is the rectangle heighy

v0.position = (0, 0)
v0.edge = e01 // or e02 or e03

v0.visible = true

v1.position = (w, 0)
v1.edge = e12 // or e10 or e13

v1.visible = true

v2.position = (w, h)
v2.edge = e23 // or e21 or e20

v2.visible = true

v3.position = (0, h)

v3.edge = e30 // or e32 or e31

v3.visible = true

e01.originVertex = v0
e01.oppositeEdge = e10
e01.nextLeftEdge = e13
e01.leftFace = f3
e01.visible = true

e10.originVertex = v1
e10.oppositeEdge = e01
e10.nextLeftEdge = e02
e10.leftFace = f0
e10.visible = true

e12.originVertex = v1
e12.oppositeEdge = e21
e12.nextLeftEdge = e23
e12.leftFace = f2
e12.visible = true

e21.originVertex = v2
e21.oppositeEdge = e12
e21.nextLeftEdge = e10
e21.leftFace = f0
e21.visible = true

e23.originVertex = v2
e23.oppositeEdge = e32
e23.nextLeftEdge = e31
e23.leftFace = f2
e23.visible = true

e32.originVertex = v3
e32.oppositeEdge = e23
e32.nextLeftEdge = e20
e32.leftFace = f1
e32.visible = true

e30.originVertex = v3
e30.oppositeEdge = e03
e30.nextLeftEdge = e01
e30.leftFace = f3
e30.visible = true

e03.originVertex = v0
e03.oppositeEdge = e30
e03.nextLeftEdge = e32
e03.leftFace = f1
e03.visible = true

e02.originVertex = v0
e02.oppositeEdge = e20
e02.nextLeftEdge = e21
e02.leftFace = f0
e02.visible = true

e20.originVertex = v2
e20.oppositeEdge = e02
e20.nextLeftEdge = e03
e20.leftFace = f1
e20.visible = true

e13.originVertex = v1
e13.oppositeEdge = e31
e13.nextLeftEdge = e30
e13.leftFace = f3
e13.visible = false

e31.originVertex = v3
e31.oppositeEdge = e13
e31.nextLeftEdge = e12
e31.leftFace = f2
e31.visible = false

f0.edge = e10 // or e02 or e21
f0.visible = true

f1.edge = e32 // or e20 or e03
f1.visible = true

f2.edge = e31 // or e12 or e23
f2.visible = false

f3.edge = e13 // or e01 or e30
f3.visible = false

Doubly connected edge list implementation

If you are interested by the half-edge or curious about sophisticated data structures, this post is for you. I know it is very difficult for people new in the field of computational geometry to find relevant informations about implementation of half-edge structure, so I will try to explain the concepts very carefully.

First, what is the motivation behind the use of half-edge ? Maybe you already know data structures like linked-list, tree, or graph, but what is half-edge and why you would need to implement it ?

One answer I would give is the following: you need a half-edge structure when you need to navigate very quickly and easily inside a polygon mesh. Remember that you need polygon mesh not only for 3D, but also for some 2D complex datas representation like Delaunay triangulation (note that in this article we will deal only with 3 sides polygon mesh).

Now the problem is that in many libraries or softwares, the polygon mesh datas are stored inside 2 arrays: one that explicitly stores the vertices positions and one that stores vertices indexes for each triangle. For example, it is the case in Unity3D Mesh class. We can illustrate this by the following diagram:

This data structure is quite simple to understand and to implement, but it is a performance disaster when you need to write an algorithm that needs to navigate and search efficiently inside the mesh. One obvious example of navigation is pathfinding. But why is it not efficient ? Because the adjacency access is not. For example, if you want to find all the vertices connected by an edge to a given vertex, you need to scan the entire triangle array to find the relevant indexes ; so the time you spend to do it increases by the size of your mesh.

But with half-edge you can access adjacency in constant time, because in this structure it becomes the explicit way to keep the datas. For this purpose, the main object you will implement will be not a vertex or a face, but an oriented edge. Think oriented edge as the core node of your data, as we can see in this illustration:

Given an Edge object current edge, a descent half-edge API should give you access to the complete adjacency: Vertex, Edge and Face objects adjacent to current edge. For example, my own interface for half-edge structure as a library contains 4 core classes: Vertex, Edge, Face and Mesh with the following public methods :

public class Vertex

• public get position : Vector // (can be any 2D or 3D coordinates data)
• public get edge : Edge // (any Edge with this Vertex as origin)

public class Edge

• public get originVertex : Vertex
• public get destinationVertex : Vertex
• public get oppositeEdge : Edge
• public get nextLeftEdge : Edge
• public get prevLeftEdge : Edge
• public get nextRightEdge : Edge
• public get prevRightEdge : Edge
• public get rotLeftEdge : Edge
• public get rotRightEdge : Edge
• public get leftFace : Face
• public get rightFace : Face

public class Face

• public get edge : Edge // (any Edge with this face adjacent at left)

public class Mesh

• public get vertices : Vertex []
• public get edges : Edge []
• public get faces : Face []

Equiped with that, you must be able to iterate efficiently in order to navigate through the whole mesh. For example, from any Vertex v, you can iterate to any direct adjacent Vertex by calling a sequence like:

v.edge.destinationVertex // 1st adjacent vertex
v.edge.rotLeftEdge.destinationVertex // 2nd adjacent vertex at left
v.edge.rotLeftEdge.rotLeftEdge.destinationVertex // 3rd adjacent vertex at left

v.edge.rotLeftEdge. ... .rotLeftEdge.destinationVertex // n-th adjacent vertex at left


The same idea works for faces. From any Face f, you can reach the 3 direct adjacent Face just by:

f.edge.rightFace // 1st adjacent face at left
f.edge.nextLeftEdge.rightFace // 2nd adjacent face at left
f.edge.nextLeftEdge.nextLeftEdge.rightFace // 3rd adjacent face at left

When you understand the basic principles of navigation, then maybe you want to expose a compliant API in order to iterate more easily through your mesh. So it can be done very easily by implementing a collection of iterators on top of the half-edge structure. For example, some ideas of iterators you can add to your library:

public class IteratorFromVertexToNeighbourVertices

• public function set fromVertex(value:Vertex)
• public function get next : Vertex

public class IteratorFromFaceToNeighbourFaces

• public function set fromFace(value:Face)
• public function get next : Face

public class IteratorFromEdgeToRotatedEdges

• public function set fromEdge(value:Edge)
• public function get next : Edge

public class IteratorFromVertexToHoldingFaces

• public function set fromVertex(value:Vertex)
• public function get next : Face

Now come back to low level half-edge implementation. We saw that the list of 11 getter methods exposed by the Edge class is quite useful to use. But at first look, it will imply a lot of datas to maintain and in consequence a nightmare to implement. But don't worry, because in reality almost of the adjacency relations between the objects can be deduced from the very small core of datas showed in this illustration:

You can see here that given an Edge object current edge, only 4 datas are required: origin vertex opposite edge, next left edge and left face. As a justification, I will simply give you a possible implementation of the Edge class with the complete deduced adjacency relations:

public class Edge
// core datas:

• private var _originVertex : Vertex
• private var _oppositeEdge : Edge
• private var _nextLeftEdge : Edge
• private var _leftFace : Face

// public interface:

• public get originVertex : Vertex { return _originVertex }
• public get destinationVertex : Vertex { return _oppositeEdge.originVertex }
• public get oppositeEdge : Edge { return _oppositeEdge }
• public get nextLeftEdge : Edge { return _nextLeftEdge }
• public get prevLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge }
• public get nextRightEdge : Edge { return _oppositeEdge.nextLeftEdge.nextLeftEdge.oppositeEdge }
• public get prevRightEdge : Edge { return _oppositeEdge.nextLeftEdge.oppositeEdge }
• public get rotLeftEdge : Edge { return _nextLeftEdge.nextLeftEdge.oppositeEdge }
• public get rotRightEdge : Edge { return _oppositeEdge.nextLeftEdge }
• public get leftFace : Face { return _leftFace  }
• public get rightFace : Face { return _oppositeEdge.leftFace }

This proves that only 4 datas need to be maintained in order to implement a complete half-edge structure.

So now that we have a descent core API, we need some additionnal tools to comfortably build concrete structures. For example, we could code a parser that generates a complete half-edge structured Mesh from a .3ds file (3D Studio Max native export format). An other possibility is to code some simple primitives and tools allowing us to expand them. We choose this second approach and it is the subject of the next articles:

A simple planar mesh primitive with half-edge

Chinese checkers on a spherical board

Do you like board games ? Do you like to experiment new game concepts ?

If you answered yes to one of these questions, I think you will appreciate this article. Indeed, here I offer you a variation of the chinese checkers game... on a spherical board ! This was already done for chess, but I think it is the first time for chinese checkers. So, just stop to speak now and have a game.

Choose to play against a friend on the same computer (Human VS Human), against the machine (Human VS AI), or just see the machine against herself. Then, drag the screen to navigate around the sphere and just follow instructions :

Content displayed within Unity Web Player

This project was a good opportunity for me to learn more about Unity 3D, C#, data structures and IA.

First I built the board in 3D Studio Max (from the geosphere primitive) and then I imported it into Unity. The most boring part in my C# code was to write a parser able to analyze the mesh board structure and generate automatically the core graph data structure. Indeed, it was out of question to generate the graph structure "by hand" ; I wanted a flexible solution, able to work quickly with new board designs without any long and boring new configurations. So maybe the next version of the game will offer you a large set of original boards, with some strange topologies...

Then I built my game code following a very simple MVC pattern. If you are curious about how we can apply MVC to board games, I think it will be interesting for you to look into my package structure. Maybe you could think that this is a very large package for such a simple game, but I always work in a way that allow me to extend my projects. Here my package structure is suitable to add new boards, new AI, new game modes...

• [_] chineseCheckers
• [_] controlers
• [_] ai
• AIControler
• DistanceTable
• [_] human
• HumanControler
• AbstractControler
• MoveData
• [_] data
• CellData
• DataManager
• [_] games
• AbstractGame
• AIVsAIGame
• HumanVsAIGame
• HumanVsHumanGame
• [_] gui
• [_] elements
• InGameHud
• Menu
• GameGui
• [_] navigator
• DragNavigator
• [_] parser
• BoardParser
• [_] view
• Cell3D
• CellColors
• Pawn
• View

[_] FOLDER

CLASS

Finally, I coded an AI, trying to keep it very simple and CPU-light. I will explain the algorithm in a future article, but you can see now that it is very fast (so fast that I must slow-down the run in order to keep the "AI vs AI" game comprehensible).

I hope you enjoyed the game !

Chinese checkers best opening moves

If you are a chinese checkers player, I am sure you already ask yourself what is the best opening moves you can do.

Trying to answer this question, I wrote an algorithm that found what we could call the best 5 starting moves !

Here are the moves:

To better understand why these moves are interesting, let's see how my algorithm work.

The algorithm just focus on the first player moves and his basis is a depth first search with maximum depth 5. It means that from the starting board configuration, the algorithm tries all sequences of 5 moves for the first player (green), then keeps the best among all. I used the depth first search and not a breadth first search because it allows to manage more easily the memory by cuting the uninteresting branchs all along the computation.

So, why a depth search of 5 ? The number is obviously arbitrary, but it leads to a decent computing time (1 hour on my machine) and it allows a pawn to reach the center of the board. It means that with depths higher than 5, our pawns will certainly meet an opponent's pawn. So in this case we just can't ignore what the opponent moves and we are out of what we consider as "opening moves".

Then, why can I consider these 5 moves as the best ? In fact it depends on what we consider as "best". So it depends on what method we use to compare the configurations in order to keep what we consider as the "best". In my algorithm, I focus only on the distances from our pawns to the goal. More precisely, I consider the sum of the cartesian distances from our pawns to the average of the target positions. Less this sum is, more I consider the configuration is good.

An illustration will help to understand :

The algorithm keeps the configuration that minimize the sum of the purple lines lengths after 5 moves

The question now I ask myself is the following : is there any strategical considerations we could add to have a better result ?

If you want to experiment by yourself, you can find the complete Actionscript 3 source of the project on GitHub:

Chinese Checkers lib on GitHub

It contains everything you need to build games (logic and display), including AI.

Chinese checkers artificial intelligence

I am currently experimenting artificial intelligence for chinese checkers. This game is very interesting, because despite very simple rules, it is not obvious to obtain a challenging AI.

So, at first I give you my list of constraints :

About the game :

• versus game : one player against one player
• the board can have any arbitrary shape (not only the classic star shape)
• any total number of pawns (but the 2 players have the same number)
• the goals positions of a player are the starting positions of the opponent
• we suppose that the pawns of a player start as a group (not disseminated)

About the AI :

• the AI must play in real time
• the AI must play in resonable time
• the AI algorithms must be not blocking (don't freeze the application because overloading the processor)

The game contraints are "weak". I chose them because I think it can be interesting to experiment some variations of the chinese checkers while keeping the rules of movement.  On the other side, the AI constraints just ensure that it is comfortably playable.

So, after some experimentations (depth search, alpha-beta, some heuristics...) I have a first interesting result. I mean that I have an AI that is playable and challenging.

If you like chinese checkers, I invite you to play a game ! Just choose your board, and start by moving a red spawn. You will notice an assistant helping you by showing the reachable positions.

The classic star board :

Small board version :

More experimental weird board :

So as previously said, the AI is interesting. But I feel not satisfied because better can be done.

I  currently use the following heuristics, inspired by my own way to play the game:

1. We only analyses our own moves. The moves of the opponent are not anticipated. It means that the algorithm don't use any form of minimax method. I tried it at first, but the time consumed was very high. And finally I really think that a good chinese checkers player don't try to anticipate the opponent's moves. So my algorithm is based on a breadth first search. Actually the tree generated has depth 3.
2. A board configuration is scored using only the sum of the distances from our pawns to the goal. It brings a really simple and fast way to compare many board configurations. That is exactly what we need when we have to choose a good move among many thousands.
3. We never play a pawn in backward direction, except near the end of the game. It is a simple way to limit the moves in consideration when building the tree. It can divide the time consumed by a factor 2.
4. If a good move is possible, we do it immediatly ; we don't wait. It is a natural balance for the 1. Because we don't anticipate the opponent's moves, we need to avoid too complex strategies, because too fragile.  It better to play a good move immediatly instead of try a better move but in 2 or 3 turns.

I think a good way to improve the AI would be to divide the game in 3 phases:

1. the beginning (the first 5 turns), when the pawns ot each players are not in interactions. This phase only needs a breadth first search, but with high depth.
2. the main, when the pawns are meeting in the center of the board. It could be interesting to switch to a minimax of low depth.
3. the end, when we need to carefully put the pawns in goal. Switch again to a breadth first search would be a good choice.

More experimentations soon !

Tetris AI explained

If you want to experiment your own Tetris AI, or just understand how it works, this post is for you.

At first I want to precise that I thought my AI as universal as possible:

• it works for all playfield dimensions
• any type of pieces could be added or removed (not only tetrominos)

For example, here you have the AI playing on a 16x16 playfield with some unusual pieces :

So how does it work ? The main structure of the algorithm acts as a BFS. The idea is the following: given the current playfield state and the tetrominos to come, we have to explore the tree of possible moves, evaluate their relevancy and keep the best to play.

But what is a move in Tetris ? Is a tetromino rotation or shifting considered as a move ? The answer is no. A move in Tetris is the action to lock a tetromino in a stable position on the playfield. It is relevant to think a move in this way, because it is only when a tetromino is locked that important events occur (lines collapse, game over) and as a result we can evaluate if the situation is good or not for us.

Then, we need to fix a limit to the depth of search. As a Tetris game can simply be infinite, and also because we want to limit the time the machine spend in this task. For pratical considerations, we will assume here the depth of search being at maximum the number of tetrominos that are previewed. Sometimes, the depth can simply be 1 (we consider only the current tetromino).

An exemple of partial game tree of depth 2, starting with the empty playfield

Last clarification: there is no perfect situation evaluation, simply because our information of the future is limited (by the arbitrary depth of search). That's why we will talk about heuristics for situation evaluation.

Now that we have some relevant concepts, we can look at the process more precisely. Given a playfield state (empty at start), the current tetromino to play and the next tetrominos in preview, the algorithm does the following:

1 : construction of the game tree of the chosen depth:

Depth 0: the current playfield state.

Depth 1: the generation of all the playfield states given by all possible locked positions of the current tetromino from the current playfield.

Depth 2: the generation of all the playfield states given by all possible locked positions of the next tetromino from all the payfields built at depth 1.

...

Consider here that for a playfield of width 10, your tree has an average total of 30^n nodes, where n is your chosen depth of search.

2 : utilization of an appropriate heuristic to score all the terminal nodes of the game tree previously generated.

3 : selection of the node with the better score, then going up through the branch of the game tree until the node of depth 1 is reached. It gives the move for the current tetromino that could potentialy leads to the best playfield state.

4 : generation of the relevant inputs (rotation, shifting...) in order to play correctly the current tetromino regarding the move previously found.

Some relevant remarks at this point. At first, this process is very time consuming, so if the AI has to played in real time, it is reasonable to keep your depth of search at maximum 2. Then, the inputs generation is an interesting part of the algorithm ; by tweaking it you can add some personnality to your virtual player in versus games. For example by allowing or not the quick fall and the hard drop, you can give the illusion of playing against a beginner or an expert.

Now let's talk about the more interesting part: the heuristic. It is where every developer can lead to different results. As previously said, there exists no perfect heuristic. What you need is to translate your own experience in playing the game into an algorithm. Here is the list of components I used to build mine:

• h0 = the number of holes in the playfield
• h1 = the altitude of the higher full cell in the playfield
• h2 = the number of full cells in the playfield
• h3 = the value of the higher slope in the playfield
• h4 = the roughness
• h5 = the number of full cells in the playfield weighted by their altitude

Notice that for each component, higher the value is, worse is the playfield state. Then we just need to combine them in order to finely express the balancing between them. The simplest way to do it is by using a linear form :

score = c0*h0 + c1*h1 + c2*h2 + c3*h3 + c4*h4 + c5*h5

with c0, c1, c2, c3, c4, c5 fixed numeric values

Of course it is possible to use more generic polynomial formulas, regarding the strategy you want to express. Actually I use a very simple version, where I set that holes in the playfield is the worse thing, by applying a coefficient of value 20 :

score = 20*h0 + h1 + h2 + h3 + h4 + h5

And surprisely, it works very well even with value 1 as depth of search.

Hoping it can inspire you.

Artificial intelligence for Tetris

Let's look on artificial intelligence applied to Tetris game. First, we need a base code to run the game. Here is a minimalistic version you can test, it can be controled by keyboard:

Basic indeed, but some clarification could be useful. Tetris has a lot a different implementations, but by his evolution, some relevant rules of gameplay are now well settled. These rules are listed as a Tetris Guideline. The main rules I implemented are the following:

• official rotations are respected
• infinite rotation (tetrominos are not falling while rotating)
• wall kick (automatic left/right shifting allowing rotation of a tetromino against a wall)
• 7 system random generator (fill a bag with the 7 tetrominos ; then draw each by random, and fill it again when empty)
• ghost piece is visible
• 3 next tetrominos are in preview
• quick fall (you can accelerate the falling speed of your current tetromino)
• hard drop (you can throw your current tetromino directly at the bottom of playfield)
• you have a delay to shift your tetromino between the last fall movement and the lock
• the game speed can be modified
• you loose when a tetromino lock while overlaping one the 2 top lines

I think I forgot some little rules, but here is the essential. On the artificial intelligence side, I early took some crucial decisions:

• "fair-play". It means that everything the AI can do, the player can do. No cheat, no special moves for the AI. Briefly, the AI acts on the game with exactly the same controls as a human player and has no more informations that what can be seen on the screen

• on the other side, the AI has a direct access to the game datas during the game. The AI doesn't "see" the game states by analyse of the pixels on the screen, but by introspection of the datas building the game model (but always in a fair-play manner, no more datas that can be seen on screen)

• the AI has to run in real time, in such way a human can play against

Here is my first working version:

It is very efficient, even if not tweaked very precisely. But it can be much more impressive. For example if I put the game speed at maximum and allow the AI to proceed the hard drop movement:

If you are very patient, you could see the AI failing and triggering the game over. But it is actually a very good basis to build some interesting AI behaviors to challenge a human player in Versus game.