Accessible cells

Accessible cells

> Programming

This algorithm purpose is to find the cells that can be reached by a leek starting from a given cell and number of Movement Points.

This results in a function taking a cell and a number as a parameter, and which will return an array of cells.

If you are told about the "getAccessibleCells" or "getReachableCells" functions, or any other similar name, you will now know what it is.

Usage

From the moment you want to plan your moves, this function will be essential.

Knowing the cells where you can go allows you, for example, to choose the cell where you will suffer the least potential damage, or to see where you could move to inflict damage on your opponent.

This algorithm is notably used in the Hide-and-seek algorithm (Hide-and-seek).

First approaches

Principle

By itself, it's quite simple to implement a way to get the accessible cells. The simplest way is to test the distance to each cell on the map using getPathLength.

But this function has a high operational cost. So use it on every cell of the map... Your operation consumption would skyrocket.

A slightly smarter solution would be to first find the cells within range of Movement Points, then check that they are reachable via getPathLength.

If these two solutions are feasible, they have an operating cost that quickly becomes high.

If you are a beginner and the solution we are going to discuss in the following still seems a bit complicated, feel free to settle for these solutions at first. At the beginning of the game, you will not necessarily have a lot of calculations to do, and at low level, you will not have a large amount of Movement Points. So, you can afford to use these solutions.

The issue

Getting your cells accessible through these methods will be hassle-free.

But a first problem arises when your number of Movement Points increases. The higher it climbs, the more cells there will be to test. In the worst case, if you run through the entire map with getPathLength, you would end up with a bill of about 4 million operations, "only".

Suffice to say that this greatly reduces the operations available for other algorithms such as Combos, or the Damage Map.

And that's not all! There is another problem: You are not alone in a fight. You will most definitely need to get your opponents' accessible cells to be able to protect yourself from their attacks. And if the various leeks start summoning bulbs, that's even more cells to calculate.

In short, if you start wanting to calculate the accessible cells of all this little world with these methods, it will cost you much more than an arm.

Thus, we use another method, much more effective: Go from neighbor to neighbor!

Neighbor propagation

Prerequisites

First, what is a "neighbor"? The neighbors of a cell are simply the cells adjacent to it. And we are obviously talking about the cells that have a common side, the cells that are directly next to them, and not those diagonally.

Thus, the cells that are in the corners of the map have a single neighbor. Cells on the edges have two. And all the others have four.

The first thing you will need to know how to do is to retrieve the neighbors of a cell. By using the functions getCellX, getCellY and getCellFromXY, you can easily determine these famous neighbors.

Once you can retrieve a cell's neighbors, you need to determine if that cell is "walkable". Clearly, if the cell is an obstacle or a leek is already on it, your leek will not be able to move through it.

To know this, you will need the functions isObstacle, isEmptyCell, isLeek or getCellContent.

Principle

The principle is actually quite simple. Even if it is not necessarily easy to set up for a beginner at programming.

Your leek is on a cell, and has a certain number of Movement Points to move. The cell it is currently on is at a distance of 0 Movement Points; So far so good...

If your leek has 1 Movement Points, where can it move? Well, on the free neighbors of his starting cell.

What if he has 2 Movement Points? It can therefore move for 1 Movement Points on the free neighbors of its starting cell. But also, for 2 Movement Points, on the free neighbors of the free neighbors of the starting cell.

And so on...

Fichier:TutoCellAccessibleIteration.gif

In green, the starting cell. In red, the cells that are explored.

By going like this, from neighbor to neighbor, we get all the cells where we can move, and as a bonus, we also have the number of Movement Points needed for each.

But when should you stop? When we have no more Movement Points, of course. And to know that, just count backwards.

If, for example, a leek has 3 Movement Points, then by staying in place, it will have 3 Movement Points left. By moving one cell, it will have 2 Movement Points left, etc...

Fichier:TutoCellAccessibleIterationInverse.gif

In green, the starting cell. In red, the cells that are explored.

And hop! By stopping at zero, we only obtain the cells accessible with our Movement Points.

Finally, to manage the obstacles, there is only one thing to do, if it hasn't already been done. To manage obstacles, simply ignore cells that are obstacles, or that are occupied by a leek. And of course, the edges of the map.

You should get an algorithm acting like this:

Fichier:TutoCellAccessibleIterationObstacle.gif

In green, the starting cell. In red, the cells that are explored.

If you get this kind of result, then congratulations, you have successfully implemented a superb accessible cells algorithm!

Explosion of operations

Be careful, this method is not necessarily less expensive than the one using getPathLength. If you manage it badly, it could cost you much more.

Indeed, when you explore the map by going from neighbor to neighbor, you must be careful not to go back. You need to expand the area of your accessible cells without traversing them again in reverse.

If you didn't plan for it and you go through cells again like in the picture, the cost in operations may explode when your Movement Points increases.

Fichier:TutoCellAccessibleIterationArriere.gif

In red, the cells scanned. In orange, the cells that are analyzed at each iteration.

On the left, what should happen. On the right, what can happen if you "roll back".

Various improvements

Here are some improvements, allowing either to reduce the number of operations of the algorithm, or to obtain more practical results to use.

Using an associative array

Prerequisites

To be able to use this trick, it is necessary to know how associative arrays work and how to use them.

Principle

Rather than conventionally storing the accessible cells, or those being tested, in an array, it is possible to use them as keys in an associative array: thus, checking whether a cell is accessible , or has already been tested is done without using the inArray function, but simply by doing:

Particularity

Since the cells are the keys of the table, it is possible to store information for each cell, such as the number of Movement Points needed to go to this cell.

Using a cache

Prerequisites

Know the existence of global variables, know how to put arrays in arrays, and possibly know the function getTurn.

Principle

For a given cell, the neighboring cells that are not obstacles (if we except the leeks) generally vary little in combat. Thus, it is not necessary to recalculate them each time the function is called, it suffices to store them at turn 1 in a global variable, in the form of a gigantic array storing, for each cell, a small array containing all non-wall neighbors. Thus, it suffices, for a given cell, to traverse this small table, and to check that each of these boxes is not occupied by a leek. It is also possible, at the start of each round, to modify the global variable, to remove the neighbors occupied by leeks (and put back those who were occupied by a leek in the previous round).

Storing the existence of neighbors

This method is a slight improvement on the previous method.

Prerequisites

In addition to what is required to be able to apply the previous method, it is also necessary to know what binary is, and to know the bitwise operators.

Principle

Rather than storing the neighbors directly in an array, it suffices to store their existence: a cell can have a maximum of four empty neighbors, which therefore requires the use of four bits. Thus, a number is associated with each cell, and from this number, four bits are chosen which will indicate the existence of neighbors in each of the four given directions (positive x, negative x, positive y, negative y).

The existence of a neighbor is done very simply by doing:

Then, to get the corresponding neighbor, if it exists, just take the id of the base cell, and add 18, 17, -18 or -17 depending on the direction.

Using binary

Prerequisites

This method is based on a representation of the map using the properties of the binary, and bitwise operators: an integer is made up of 32 bits, and some of these bits make it possible to store information concerning a given cell.

Principle

The map is broken down into 35 lines, and each line is associated with an integer. the bit of rank i of this integer then makes it possible to store information on the i-th cell of this line.

!Access binaires

the cells colored in dark blue are those of the first line, the one in bright yellow belong to the 8th line, and the red box is the 3rd box of the 19th line

You must then create two tables respecting this principle:

It is then necessary to initialize the algorithm by setting to 1 the bit corresponding to the starting cell, in the second table.

Then, it suffices to use a few bitwise operators in order to be able to know all the cells adjacent to those which are already accessible:

the 4 "|" allow everyone to know the neighbors of the accessible cells located in a given direction, and the "&obs[N]" makes it possible to ensure that these neighbors are indeed empty cells, located on the map.

After repeating these calculations the right number of times, just look at the second table to know all the cells that are accessible starting from the initial cell and with the right number of Movement Points.

Particularities

This method uses bitwise operators, which have the particularity of costing only one operation each. Thus, this method is much less expensive in operation than the others. Nevertheless, it is not perfect: it is difficult to know how many mp are required to move on a given cell, it only allows to know if this cell is accessible or not.

Benchmark

Feel free to visit this Leek Wars forum topic

You can compare the results of your algorithm with other players.

You will also find many ways to optimize the cost in operations of your code.