hi! Finally.
This video was ready eight months. sorry I just publish it now …
lol
Client-server communication: solved!
August 20, 2014 – 1:20 pm
After some searching (http://www.gamedev.net/topic/659071-sending-and-receiving-udp-packets-to-character-status-need-be-encrypted/, and other) testing I got a good architecture for client-server communication. It’s something very close to the exposed solution in post Adversities in client-server communication (https://vectortowns.wordpress.com/2014/07/31/adversities-in-client-server-communication/). I will comment on the details here.
First I should clarify that this communication will only work if met with premises security and login (ie, a handshake). See the following:
1- At first, the player will send a TCP packet over SSL with your username and password. In the authentication process, a certification authority (CA) will be consulted to ensure the authenticity of the game server;
2- After confirmed the authenticity of the server, the client obtains a public key server;
3- The client generates a secret key (AES 128) and a sessionId and sends to the server by encrypting the packet with the server’s public key;
4- Thereafter all packets exchanged between them (either TCP or UDP) will be encrypted and decrypted with the secret key (AES 128).
After this handshake, the communication will be as shown in the following image:
Below are the details of communication:
– The client application is built in Java; the recipient of requests (which I call SuperServer) is built on NodeJS; the application of business rules (manage an NPC, for example) will be built (not yet exist) in Lua (http://www.lua.org/about.html) and is called ManagerServer; only SuperServer and ManagerServer applications communicate with the MySQL database;
– Every event (WALKING, CASTING, TALKING …) sent by a player occurs by a UDP datagram encrypted with AES 128 and 32 CRC checksum;
– For events that require confirmation, the response will occur via a UDP datagram checked with CRC 32 unencrypted. Note: An event like WALKING, for example, needs a server validation; one as LOGOFF, is sent only and has no return;
– All events logged by other players are obtained for the TCP socket without encryption;
– Sending events from Java client to NodeJS SuperServer occur by 9731 port; Java client application get events from other players by SuperServer 9732 port; Communication between the SuperServer NodeJS and ManagerServer Lua will occur by 9730 port.
With this architecture I’m getting a good performance. Sending events from Java application client to NodeJS server and your confirmation is performed in the range of 130-155ms. Obtaining the events of the other players is occurring in the range 180-200 ms. As there is an intentional delay of 200 ms for the game to run the events controlled by the player (same happens in the game Age of Empires 2) the sending and receiving of data occur at the expected time – without causing lag in game.
In the near future I will post here a video of the game with some online testers!
lol
bye
Domain registration
August 4, 2014 – 4:48 pm
I hired a designer to do the game symbol. The work is going great. When trying to register the domain, I noticed that there is a site vectortown.com. I thought about registering as .net or gamevectortown.com, but the designer has convinced me that if we changed the name to Vector Towns would be even better.
In hindsight, the point of view of the game history (which I have not mentioned to you), Vector Towns would be even better than the singular name. So now the game will be called Vector Towns. The domain has been registered and the future points to a website. For now he just point to this blog (which also had its name changed).
Thanks for reading.
Adversities in client-server communication
July 31, 2014 – 4:44 pm
Hi ..
I’m already a while without posting, but keep developing the game with great intensity. During that time, I did several things but the most important one was the server configuration. In my first version, all event processing player … oops, before explaining the server, I will talk a little about the ‘events’.
Events
Everything that occurs in the game will be considered an event. If the player clicks a position to move around the map, pathfinding calculates the route to your destination and pass this list to an executor of events (I’m calling AsyncConsumerEvents). The origin-destination path is composte various events WALKING, where each is responsible for moving a tile to another. Other examples of events would be: ATTACK, JUMP, DIE … 🙂
First version
Returning to the main issue: on my first experience, the events were fully processed at the client and the outcome of these events (repositioning and select the appropriate image of the player) were passed to the server. The update of the sprites on the map was made by consulting all the sprites in each iteration to draw the screen.
I was naive … of course this would not work. One iteration of the drawing screen lasts 16 ms. This means that 16 in 16 ms I searched all changes of sprites on the server. In my home network, sending and searching this information occurred 12-13 ms, but when I put on the internet, the cost came to 190 ms. That is, each iteration of drawing the screen suffered a delay of 174 ms, causing a lot of lag in the game.
In this version I used TCP packets without encryption.
Second, third, fourth… version
After that I have read many, many papers in an attempt to capture best practices for game MMOG client-server communication. All pointed to hybrid solutions with TCP and UDP. I found very interesting cases: the game Outgun and the peer-to-peer of the game Age of Empires 2. Outgun used an adapted version of the UDP protocol called RUDP that was all the game logic on the server. Age of Empires 2 had the complete state of the players on each client and always applied a delay of 200 ms to move players to avoid any lag in communication.
From these studies I made several experiments, all frustrated. I tried to use: UDP with the same port; UDP with different ports; UDP with different processes for sending and receiving; UDP recording state database and returning by another UDP; UDP to send the player status and TCP to other information… well, all these tests gave me something between 150 to 200 ms of delay between sending and receiving.
The problem was that in all cases I kept the rule in which the client processes the information, sends the result of processing and search all the updates from the server. This logic could not be maintained.
My current experience
AsyncConsumerEvents: Now, I mofifiquei all the logic of communication. First, even for security, event processing can not be performed by the client prior to authorization by the server. Why? If a client is malicious he may cheat. Before executing an event, I just send a request to the server. This request is being sent over UDP (encrypted) and does not expect any confirmation. If the server does not authorize another client process (AsyncReceiverEvents) that receives events simply will not receive this event. Just for clarification, I called him AsyncConsumerEvents why he consumes the events performed by the player and then send them to the server.
AsyncReceiverEvents: this process is continuously sending TCP requests (no encryption – in this case need not) asking the server if there is any event of the players (including this player). If there is any event, the client runs.
This logic only works well because I am also applying a maximum delay of 200 ms (as in Age of Empires 2) for the execution of the events after the command of the players. As the transmission (over UDP) and receiving (for TCP) is being conducted around 180 ms, we have a few instances of lag in the game when the network is slow.
Details
Why sending the event (UDP) is encrypted and the return (for TCP) does not? As the UDP packet is encrypted will be very difficult (unless a malicious user has the private key player) else pretend to be the player or modify events this player. Send to a fake server event would be a problem. So is encrypted. You no longer receive events such concern. If by chance the customer get a false event, its next iteration seek a true event. The client application knows how to treat it without problems. The most that can happen is a lag in the progress of the affected client.
Talking about encryption
I used AES 128 to encrypt the data and the CRC 32 to checksum the payload of the UDP datagram. The secret key of AES will be exchanged at an early stage to login with public key cryptography and authentication server in a certificate authority (as in https). This initial part is not yet implemented.
Server details
Once I started testing the client-server communication, I created a home server. It was an old machine running Ubuntu (too old). I installed MySQL 5.6.15 (64 bits) and the latest version of NodeJS via apt. I did several tests on the local network and got to publish it on the internet with no-ip.com. Suddenly the server stopped! Some hardware bug occurred. I abandoned that server and decided to create it in the cloud. I created an Ubuntu instance on EC2 amazon AWS. In it are configured MySQL 6.5.19 and NodeJS. I’m still using an old version of MySQL because of the large amount of stored procedures already created that need to be tested. In the future I will update.
Well, it is. I’m still programming this last alternative and while tests are good. After I comment with you the performance of the final result.
First communication between Java and node.js
April 19, 2014 – 2:00 am
My first feature communication between the Java client and node.js server project focused on bringing data of CHARACTER_SPRITE table. Until then, attributes such as “number of steps”, “current step”, “speed” were obtained from properties files. Now they are coming directly from the database through a socket. I’ll explain here how it is built.
Plan to maintain only two node.js scripts: server.js and controller.js. The first will receive the socket connections, open communication with MySQL and encapsulate all in a domain (or try/catch) to handle errors. In future it will also have a TLS (SSL) layer on the socket to encrypt the data, but so far not implemented this. See below server.js code.
var net = require('net');
var mysql = require('mysql');
var d = require('domain').create();
var controller = require('./controller');
var HOST = '127.0.0.1';
var PORT = 8000;
var TERMINAL_CHAR = '\n';
var SEPARATOR_CHAR = '#';
var pool = mysql.createPool({
host : '127.0.0.1',
user : 'myadmin',
password: 'mypass',
database: 'vectortown'
});
process.on('uncaughtException', function(err) {
// handle the error safely
console.log(err);
console.log('Server listening on ' + HOST +':'+ PORT);
});
d.on('error', function(err){
console.log(err);
console.log('Server listening on ' + HOST +':'+ PORT);
});
// catch the uncaught errors in this asynchronous or synchronous code block
d.run(function(){
// Create a server instance
net.createServer(function(sock) {
// We have a connection - a socket object is assigned to the connection automatically
console.log('CONNECTED: ' + sock.remoteAddress +':'+ sock.remotePort);
// Add a 'data' event handler to this instance of socket
sock.on('data', function(data) {
console.log('Data received by ' + sock.remoteAddress );
var full_msg = data.toString();
var array_msg = full_msg.split( SEPARATOR_CHAR );
var command = array_msg[0];
var msg = array_msg[1];
// Run controller
controller[ command ]( pool , msg , function( result ) {
sock.write( result + TERMINAL_CHAR );
});
});
// Add a 'close' event handler to this instance of socket
sock.on('close', function(data) {
console.log('CLOSED');
});
}).listen(PORT, HOST);
console.log('Server listening on ' + HOST +':'+ PORT);
});
Note that I do not write here (hard coded) the name of the controller methods. They will be referenced by a string that comes from the Java application. The command will be divided into two elements separated by a #: the code to indicate the command and any parameters. Like this:
C0001#5
In this example, I separate them by # and call the C0001 method with the parameter 5. The code controller.js keep the declaration of all methods of communication with MySQL. See the code below:
module.exports =
{
C0001: function ( pool , msg , callback ) {
var query = 'SELECT FLOOR.HEIGHT as \'height\', SPRITE.CODE as \'code\', ' +
'CHARACTER_SPRITE.DIRECTION as \'direction\', CHARACTER_SPRITE.STEP as \'step\', ' +
'CHARACTER_SPRITE.NUMBER_STEPS as \'numberSteps\', CHARACTER_SPRITE.SPEED as \'speed\', ' +
'SPRITE.FLOOR_CODE as \'floorCode\', SPRITE.TILE_CODE as \'tileCode\', SPRITE.X as \'x\', ' +
'SPRITE.Y as \'y\', SPRITE.IMAGE_CODE as \'imageCode\', SPRITE.BLOCKED as \'blocked\' ' +
'FROM CHARACTER_SPRITE INNER JOIN SPRITE ' +
'ON CHARACTER_SPRITE.SPRITE_CODE = SPRITE.CODE ' +
'INNER JOIN POSITION_TILE ' +
'ON SPRITE.FLOOR_CODE = POSITION_TILE.FLOOR_CODE AND ' +
'SPRITE.TILE_CODE = POSITION_TILE.TILE_CODE AND ' +
'SPRITE.X = POSITION_TILE.X AND SPRITE.Y = POSITION_TILE.Y ' +
'INNER JOIN FLOOR ' +
'ON POSITION_TILE.FLOOR_CODE = FLOOR.CODE ' +
'WHERE SPRITE.CODE = ' + msg;
pool.getConnection(function(err, connection){
connection.query( query , function( err , rows , fields ){
if(err) {
throw err;
} else {
if ( rows.length == 1 ) {
callback( JSON.stringify( rows[0] ) );
} else {
callback( null );
}
}
});
connection.release();
});
}
}
Ok, the query is big. Do not worry, it simply loads the data needed for the Java model.
The application models are on the base project (there are three Java projects: base, client and server) and will be consumed by other projects. Meanwhile I kept hibernate layer for communication with MySQL. This layer is formed only by anemic classes annotated with @Entity. As this layer will only be used in server project, the performance requirement is not as essential as the client project.
There is also a model that will make communication with the Super-Server node.js. As the node.js returns a JSON, I preferred to create model classes (like DTOs) who will receive the JSON data through a conversion by the framework Jackson JSON Processor. Below is the class that receives the JSON implemented in C0001 method described above.
package br.com.linu.vectortown.base.model.json;
import java.io.Serializable;
import org.codehaus.jackson.annotate.JsonIgnore;
import br.com.linu.vectortown.base.model.enumeration.DirectionEnum;
public class SpriteJson implements Serializable {
@JsonIgnore
private static final long serialVersionUID = -1421845826361208213L;
private int height;
private Long code;
private DirectionEnum direction;
private int step;
private int numberSteps;
private int speed;
private Long floorCode;
private Long tileCode;
private int x;
private int y;
private Long imageCode;
private int blocked;
public SpriteJson() {}
public int getHeight() { return height; }
public void setHeight(int height) { this.height = height; }
public Long getCode() { return code; }
public void setCode(Long code) { this.code = code; }
public DirectionEnum getDirection() { return direction; }
public void setDirection(DirectionEnum direction) { this.direction = direction; }
public int getStep() { return step; }
public void setStep(int step) { this.step = step; }
public int getNumberSteps() { return numberSteps; }
public void setNumberSteps(int numberSteps) { this.numberSteps = numberSteps; }
public int getSpeed() { return speed; }
public void setSpeed(int speed) { this.speed = speed; }
public Long getFloorCode() { return floorCode; }
public void setFloorCode(Long floorCode) { this.floorCode = floorCode; }
public Long getTileCode() { return tileCode; }
public void setTileCode(Long tileCode) { this.tileCode = tileCode; }
public int getX() { return x; }
public void setX(int x) { this.x = x; }
public int getY() { return y; }
public void setY(int y) { this.y = y; }
public Long getImageCode() { return imageCode; }
public void setImageCode(Long imageCode) { this.imageCode = imageCode; }
public int getBlocked() { return blocked; }
public void setBlocked(int blocked) { this.blocked = blocked; }
}
The JSON returned from node.js will be transformed into SpriteJson class with a command like this:
SpriteJson spriteJson = (SpriteJson) ConverterJson.INSTANCE.from(json).to( SpriteJson.class );
I encapsulated the logic conversion org.codehaus.jackson in a class with “fluent interface”, but we will not discuss the features of the Jackson JSON Processor here. Now I will show the class that create and maintain the socket with node.js.
package br.com.linu.vectortown.client.infrastructure;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.Serializable;
import java.net.Socket;
import org.apache.log4j.Logger;
import br.com.linu.vectortown.base.model.json.FloorAndTileJson;
import br.com.linu.vectortown.base.util.ConverterJson;
import br.com.linu.vectortown.base.util.PropertiesUtil;
import br.com.linu.vectortown.client.infrastructure.enumeration.TransCodeEnum;
import br.com.linu.vectortown.client.infrastructure.exception.CommunicationServerException;
public class SuperClient implements Serializable {
private static final long serialVersionUID = -6376764477013637988L;
private static final Logger LOGGER = Logger.getLogger(SuperClient.class);
public static final SuperClient INSTANCE = new SuperClient();
private int port;
private String host;
private Socket socket;
private BufferedWriter writer;
private BufferedReader reader;
private SuperClient() {
port = PropertiesUtil.INSTANCE.inteiroPor("game.server.port");
host = PropertiesUtil.INSTANCE.valorPor("game.server.host");
}
public void open() {
try {
socket = new Socket( this.host , this.port );
writer = new BufferedWriter( new OutputStreamWriter( socket.getOutputStream() ) );
reader = new BufferedReader( new InputStreamReader( socket.getInputStream() ) );
LOGGER.info( "Open server connection." );
} catch (Exception e) {
LOGGER.error( e.getMessage() , e );
throw new CommunicationServerException( e );
}
}
public void close() {
try {
socket.close();
LOGGER.info( "Close server connection." );
} catch (Exception e) {
LOGGER.error( e.getMessage() , e );
throw new CommunicationServerException( e );
}
}
private void send(String message) {
try {
writer.write(message);
writer.flush();
} catch (Exception e) {
LOGGER.error( e.getMessage() , e );
throw new CommunicationServerException( e );
}
}
private String recieve() {
try {
return reader.readLine();
} catch (IOException e) {
LOGGER.error( e.getMessage() , e );
throw new CommunicationServerException( e );
}
}
public String recieve(String command) {
this.send( command );
return recieve();
}
}
To receive data from node.js server, we can run something like:
SuperClient.INSTANCE.open(); // Get sprite with code 5 String json = SuperClient.INSTANCE.recieve( TransCodeEnum.C0001 + TransCodeEnum.getSeparatorChar() + 5 ); System.out.println( json ); SpriteJson spriteJson = (SpriteJson) ConverterJson.INSTANCE.from(json).to( SpriteJson.class ); System.out.println( spriteJson.getCode() ); SuperClient.INSTANCE.close();
This code will generate the following text at the prompt:
{"height":1,"code":5,"direction":"SOUTH_EAST","step":0,"numberSteps":7,"speed":100,"floorCode":1200000001000000000,"tileCode":504,"x":1,"y":9,"imageCode":500000000,"blocked":1}
5
The node.js server will log:
C:\java\workspace\vectortown\super-server>node server.js Server listening on 127.0.0.1:8000 CONNECTED: 127.0.0.1:51541 Data received by 127.0.0.1 CLOSED
Besides the anemic domain JSON and Hibernate, I have a rich model with well-defined attributes and behaviors. In the server project, the data will be read by the MySQL layer and Hibernate entities to be loaded later in the rich model. In the client project data will be read from node.js converting JSON in anemic model and then be loaded in the rich model. You may be finding it a bit complex, but actually I prefer to keep my rich model exclusively to treat the rules of the game without spoiling them with annotations or getters and setters required for a reading from the database.
Good staff, that is. While I am writing this post my SuperServer node.js has other implemented methods, but these are basically similar to what I showed you. In the future there will be a more interesting method in which the node.js script will execute a stored procedure MySQL with various actions directly in the database. This will help me to reduce the access time between the node.js server and the database server, but I’ll leave those details for another conversation.
Thanks for reading. Bye!
Database tables
April 8, 2014 – 11:10 am
Recently I’ve been modifying the domain model layer. As I said, the system is divided into different projects by Maven. The domain objects are the basic project. To date, there are database entities and rich entities. The rich model has objects organized with rules and methods for operating the game, considering non-functional requirements such as performance, coupling, heritage and composition, and the communication between objects.
Today, the entities of communication with the database are built with Hibernate. I have not decided if I will keep the Hibernate. Why? I’m thinking about the performance of communication between the client application and the server. I want to keep this link with a Java Socket (client side) with stateful communication with a Socket in Node.js (server side), but I would in a single request to perform many transactions in the database with store procedures. This in practice means that queries and changes to the database will be through stored procedures. Hibernate will only serve to facilitate the communication between Server Project (Maven) and the database when upgrading the game objects without stored procedures. I’m still thinking about it … later post here my decision 🙂
Now I am creating database tables of the game, like this…
Of course that the model is not complete. This is only the first version, where I intend to allow players to walk for a map online, as with the rules of collision between them. Hope it works.
The basic idea is that each player (client project) open a stateful socket with the server (Node.js), changing its position (x and y axis) in the database during the walk. Each transition between tiles need a query to the server (Node.js) to see if another sprite (player) is blocking the way. Node.js scripts will communicate directly with MySQL through the Store Procedures. Note that at this time the Project Server does nothing. It is only necessary when other sprites (enemies or NPCs, for example) walk along with the other players.
Well, it is. After I tell if it worked…
Pathfinding with many floors: solved!
March 17, 2014 – 2:27 am
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 … 🙂
Nothing important
March 16, 2014 – 11:24 am
Now my code is written in Portuguese. I’ve been thinking of translating it to English … why? So it will be easier if one day I have a team 🙂
vectortowns.wordpress.com 