Terrain

from sIArena.terrain.Terrain import Terrain

The main element is the Terrain. This element represent a map or grid where the search algorithm will be performed.

It is a matrix of size NxM where each cell or tile contains an integer value. Each value represents the height of the terrain at that point. The difference of value between adjacent cells is used to determine the cost of moving from one cell to another.

The terrain has within it cells 2 special cells: the origin and the destination. These cells are used to determine the start and end of the path to be found. It also counts with a cost_function that is used to determine the cost of moving from one cell to another depending on their values.

Attributes

n: number of rows
m: number of columns
matrix: numpy matrix of size NxM
origin: tuple(int,int) with the coordinates of the origin cell
destination: tuple(int,int) with the coordinates of the destination cell
cost_function: function that receives 2 integers x,y and returns the cost of moving from one cell with value x to another with value y

Built-in Methods

str: returns a string representation of the matrix of the terrain. The origin and destination cells are marked with the characters + and x respectively.
getitem [Coordinate]: returns the value of the cell at the given coordinates. i.e. terrain[(0,0)].
ctor: constructor that receives a matrix.
- matrix: numpy matrix of size NxM
- origin: Coordinate with the coordinates of the origin cell. If None is provided, the origin will be set to (0,0)
- destination: Coordinate with the coordinates of the destination cell. If None is provided, the destination will be set to (n-1,m-1)
- cost_function: function that receives 2 integers x,y and returns the cost of moving from one cell with value x to another with value y. In case is not provided, the Default cost function will be used.

Methods

size: returns a tuple with (n,m).
get_neighbors: returns a list of the coordinates of the cells that are adjacent to the given cell. - pos: Coordinate
get_cost: returns the cost of moving from one cell to another. - pos1: Coordinate - pos2: Coordinate
get_path_cost: returns the cost of a whole Path. - path: Path
is_complete_path: returns True if the given Path is valid and complete. - path: Path
why_complete_path: returns the same value as is_complete_path and also retrieves a string with information why the path is not complete (if this is the case). - path: Path

Some of this methods use the element Path that is seeing afterwards.

Cost Function

The cost function is a function that receives 2 integers x,y referring to the height of 2 adjacent cells, and returns the cost of moving from one cell with value x to another with value y.

Default cost function

The default cost function is as follows:

If the origin cell and the target cell are at same height (x==y), the cost is 1.
If the origin cell is higher than the target cell (x>y), it means it moves down, and the cost is their difference: x-y.
If the origin cell is lower than the target cell (x<y), it means it moves up, and the cost is double their difference: 2*(y-x).

The following snippet shows the implementation of the default cost function:

def default_cost_function(x,y):
    if x == y: return 1
    elif x > y: return x-y
    else: return 2*(y-x)

Visualization

There are several ways to easily visualize the terrain:

String

Function str returns a string representation of the matrix of the terrain: The origin and destination cells are marked with the characters + and x respectively.

print(terrain)

+---+---+---+---+---+
|+3 | 9 | 3 | 9 | 3 |
+---+---+---+---+---+
| 9 | 2 | 0 | 3 | 0 |
+---+---+---+---+---+
| 3 | 9 | 3 | 3 | 3 |
+---+---+---+---+---+
| 0 | 6 | 3 | 0 | 6 |
+---+---+---+---+---+
| 3 | 9 | 3 | 3 |x3 |
+---+---+---+---+---+

2D plot

In order to learn how to visualize a 2D plot of the terrain, please refer to the 2D Plot section.

3D plot

In order to learn how to visualize a 3D plot of the terrain, please refer to the 3D Plot section.

Multiple Destinations Terrain

There is other class for Terrain that is called MultipleDestinationTerrain. This class allows to have multiple destinations in the terrain. This means that the path must pass through all of them in order to be considered complete. The destinations are not sorted, so they can be visited in any order.

from sIArena.terrain.Terrain import MultipleDestinationTerrain

The use and methods of this class are similar to Terrain ones. It changes:

The argument destination in the constructor is now a set of Coordinate.
The method is_complete_path now checks if the path passes through all the destinations.
To get the destinations, use the attribute destinations, that is a set of Coordinate.

Example on how to create a MultipleDestinationTerrain:

from sIArena.terrain.Terrain import MultipleDestinationTerrain
from sIArena.terrain.Coordinate import Coordinate

matrix = np.array(...)
destinations = {Coordinate(4,4), Coordinate(0,4)}
# It uses the top-left cell as origin by default
terrain = MultipleDestinationTerrain(matrix, destination=destinations)

# To get the destinations of the terrain
destinations = terrain.destinations

Multi Endpoint Terrain

There is another Terrain class called MultiEndpointTerrain. This class is used when the problem has several possible starting points and several possible ending points. Paths valid are those that start in any of the allowed origins and end in any of the allowed destinations, as long as they are valid paths in the terrain.

from sIArena.terrain.Terrain import MultiEndpointTerrain

Difference with Terrain

The complete-path rule for MultiEndpointTerrain is:

The path must be valid: every consecutive pair of coordinates must be neighbors in the terrain.
The first coordinate of the path must belong to the set of allowed origins.
The last coordinate of the path must belong to the set of allowed destinations.
The path may pass through other origins or destinations in the middle, but this is not required.
The path does not need to visit all destinations.

This MultiEndpointTerrain class is similar to Terrain with some minor differences:

Method get_origins() returns the set of allowed origins, instead of a single origin.
Method get_destinations() returns the set of allowed destinations, instead of a single destination.
There is no attribute origin or destination.

The constructor keeps the same parameter names as the standard Terrain constructor:

origin: a single Coordinate or a collection of Coordinate values.
destination: a single Coordinate or a collection of Coordinate values.

Examples

Example with several origins and several destinations:

from sIArena.terrain.Terrain import MultiEndpointTerrain

matrix = [
    [0, 0, 0, 0],
    [0, 5, 5, 0],
    [0, 0, 0, 0],
]

terrain = MultiEndpointTerrain(
    matrix,
    origin={(0, 0), (2, 0)},
    destination={(0, 3), (2, 3)},
)

path = [(2, 0), (2, 1), (2, 2), (2, 3)]

terrain.is_complete_path(path)      # True
terrain.get_origins()               # {(0, 0), (2, 0)}
terrain.get_destinations()          # {(0, 3), (2, 3)}

The following path is also complete in the same terrain, because it starts in another valid origin and ends in another valid destination:

other_path = [(0, 0), (0, 1), (0, 2), (0, 3)]

terrain.is_complete_path(other_path)  # True

However, this path is not complete, even if it is a valid sequence of neighboring cells, because it does not start in one of the allowed origins:

wrong_start = [(1, 0), (2, 0), (2, 1), (2, 2), (2, 3)]

terrain.is_valid_path(wrong_start)     # True
terrain.is_complete_path(wrong_start)  # False

And this path is not complete because it does not end in one of the allowed destinations:

wrong_end = [(2, 0), (2, 1), (2, 2)]

terrain.is_valid_path(wrong_end)       # True
terrain.is_complete_path(wrong_end)    # False

Sequential Destinations Terrain

There is other class for Terrain that is called SequentialDestinationTerrain. This class have multiple destinations, but in this case the path must pass through them in the same order as they are provided.

from sIArena.terrain.Terrain import SequentialDestinationTerrain

The use and methods of this class are similar to Terrain ones. It changes:

The argument destination in the constructor is now a list of Coordinate.
The method is_complete_path now checks if the path passes through all the destinations in the same order as they are provided.
To get the destinations, use the attribute destinations, that is a list of Coordinate.

Example on how to create a SequentialDestinationTerrain:

from sIArena.terrain.Terrain import SequentialDestinationTerrain
from sIArena.terrain.Coordinate import Coordinate

matrix = np.array(...)
destinations = [Coordinate(4,4), Coordinate(0,4)]
# It uses the top-left cell as origin by default
terrain = SequentialDestinationTerrain(matrix, destination=destinations)

# To get the destinations of the terrain
destinations = terrain.destinations