Anyway, after several tests I got a solution for pathfinding to find the correct path between different floors. I’ll post here the solution in steps, because some adjustments were needed to make it work well.
Stairs with different weights
The pathfinding is very smart! When a tile is near the origin, but on another floor, the pathfinding seek to the neighborhood to try to find the target, often moving away from the stairs. Sometimes the stairs go very bad directions (with major F) but which are necessary to reach the next floor.
Imagine, for example, the above map. Red tile is the origin and the blue tile is the destination. If the stairs had the same weight of ordinary tiles, pathfinding would take longer to find the path (in this case) and sometimes not come to find their way.
As you can see, this map have three tiles of stairs between floors. I applied different weights according to the search direction and height of degrais. For example, this quest (from red to blue), the first step will have G=3 ( (numberOfTilesBetweenFloors + 1) – heightTile) and H=0 (resulting in F=3). The second step will be G=2 and H=0 (F=2). The third, G=1 and H=0 (F=1). Finally, subsequent to the last stair tile (marked in green), G=0 and H=0 (F=0). By this seem strange, but this way the pathfinding will gradually adding the lowest stairs on the closed list and up to the next floor.
If the search is reversed (from blue to red) G value of the stairs will be exactly equal to the height of the stair tile. For example, the third stair (next green tile) will have a weight of 3 (G=3), the second a weight 2 (G=2), and so on.
Note: In fact, in my maps there are 4 tiles between floors. These pictures (which are not screenshots of the game) show only 3 tiles.
Middle Nodes
The different weights help to solve the problem, but in cases where the maps are very complex (a maze of walls blocking the passage to the stairs) pathfinding can not find the path. To resolve this I created a feature called the Middle Node (or intermediate nodes). The Middle Nodes are the tiles just before the start of the stairs. They serve as an intermediate destination for pathfinding when the tile floor of the destination is different from the tile floor of origin. In the picture below they are marked in green and yellow.
So a search from red to blue will have two yellow tiles as Middle Nodes. The first search will start in red until the first yellow tile (downstairs). Then a second search starts in green tile (first floor) and have as a target a second yellow tile (first floor). Finally, after climbing the stairs to the last floor, a little search will start in the green tile (second floor) and will finish in the blue tile.
But how do I find the Middle Nodes? When the game reads the map file containing the tiles, he makes this search. The previous tiles to the first stairs (in the picture, the yellows) are stored in a list called firstStairsGroup, corresponding to floor height. Confused? I have an array of lists where the array index is the height of the floor. The list, in fact, only stores the tiles. Thus, the first yellow tile (downstairs) would be added to list firstStairsGroup[0].add( yellowTile1 ), while the second yellow tile (first floor) would firstStairsGroup[1].add( yellowTile2 ). Now when the search occurs and the floor height of the target is greater than the height of the floor of origin, we calculate the value of H (with Isometric Manhattan) with the origin (red tile) and each element of the list (in this case, firstStairsGroup[0]). The lowest H indicates my first Middle Node. This same rule is used on the first floor.
However, when the destination is on the lower floors to the origin, the search is performed based on lastStairsGroup list. This list stores the tiles next to the last step of each stair (green tiles). Similarly, the Middle Nodes are obtained at the lowest H between the source (which may be blue tile or another Middle Node, for example, the yellow tile in the first floor) and the Middle Node of the floor (green tiles).
Note: in practice, in Java, I created the wrappers firstStairsGroup and lastStairsGroup containing the lists, and in the my object map I created a array (of 0-2 elements) for each. Java is bureaucratic to create arrays of list.
Warning: the Middle Nodes are not considered when the calculated node is a stair.
Blocking stairs
Another important rule is to block the stairs that should not be used. For example, assume that the source was the pink tile and the target was the orange tile. As the stairs have a value of G, H and F minor, pathfinding would down the stairs and uses search focusing on the downstairs.
To avoid this, whenever the source and destination are on the same floor, access to stairs is locked (is regarded with a blocked tile – not passable). This is a simple rule that aids in search and can be built into the core of pathfinding algorithm.
Larger G’s for different floors
This rule was implemented to prevent the sort of open-list (to find the node with the smallest F) end up finding a node of an unwanted floor. Remember that the ordering of the open list considers the value of F, regardless of the floor where the tiles are. If we impair the G values of the tiles located in the different floors of the destination floor, the ordination will automatically choose the most appropriate nodes.
In practice, we calculate the absolute value of the difference between the floor of the current tile (ie, the tile of the iteration in the pathfinding) and the floor of the destination tile. This calculation will bring me the values 0 (for tiles on the same floor), 1 or 2. Then we multiply this value by 0.5 (a value it deems as sufficient), add 1 (to avoid that the final result is zero) and multiply by the current value of G.
if ( node.floor() != destitation.floor() ) {
double additionalCostPerFloor = PropertiesUtil.INSTANCE.doubleBy("game.pathfinding.additional.cost.floor"); // 0.5d
int difference = Math.abs( node.floor() - destitation.floor() );
node.g( intValue( node.g() * ( 1 + ( additionalCostPerFloor * difference ) ) ) );
}
But be warned, I only realize this when the floors of origin and destination are different.
Another small adjustment that I applied, which is not directly related to the problem of stairs, but it helped pathfinding, is to consider the value of H as a second option in the ordering of the open list when the value of F is equivalent in nodes.
@Override
public int compareTo(Node o) {
if (this.f() < o.f()) {
return -1;
} else {
if (this.f() > o.f()) {
return 1;
} else {
if (this.h() < o.h()) {
return -1;
} else {
if (this.h() > o.h()) {
return 1;
} else {
return 0;
}
}
}
}
}This prevents the best way is lost when the map is a maze.
Final result
Let me illustrate a search starting at blue (top floor) to red (downstairs).
First, when the map is loaded, the Middle Nodes were already defined. From there, the pathfinding performs the following steps:
1 – As the floor of the destination tile is less than the floor of source tile, the Middle Nodes are obtained from lastStairsGroup. In this example, the map has only one entry stairs to each floor, but on larger maps, which are closer to the tile origin will be selected. In practice, this step gets the green tiles in the image.
2- The G costs of the first and second floor will be adjusted in 50% per level difference, ie, the G on the second floor will be increased by 100%, while the first floor will be increased by 50%. Thus, the ordering of the open list will prefer the downstairs nodes.
3- The G, H and F values of the stairs are adjusted depending on the height of the stair (as explained in the “Stairs with different weights” section).
4- Access to unwanted stairs will be blocked. Ie, if the pathfinding is performing the search on the first floor, access to the second floor by the yellow tile is defined not passable. This same rule is used in the search on the downstairs.
That’s it! With these rules, when the character is in blue tile and the player making a mouse click on the red tile, the pathfinding will estimate the best path. In this sample map it would be easy even without the adjustments, but in a maze map (with many walls and locked tiles), the adjustments are essential to the search.
Bye. Thanks for reading … 🙂
vectortowns.wordpress.com 