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
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.
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.
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.
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.
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.
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.
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 … 🙂
Hi. I’m creating a 2d game in Java. I will post my progress here. In future I’ll create a oficial website. For now, I have an isometric map. I drew the tiles (floors, stairs and walls) and downloaded sprites of the Scias, a Breath of Fire IV (a ps1 game) character.
The project is organized into three sub projects: base, client and server. The dependence between them and the management of package dependencies being managed by Maven. The basic project contains database entities, rich model entities, utilities (eg, bundle resources, i18n, static classes), classes for artificial intelligence and classes for pathfinding. It is used as a library for the other two.
I’m currently still using the hibernate entities, but in the future I intend to replace the database access by simple jdbc (‘m still thinking about it later). Why? The client project do not access the database directly. Only the server project will have access to the database (directly) and perhaps better access via jdbc (because of performance).
The project client will access data from database through a statefull connection (and encrypted) with a script running on Node.js. These script (affectionately called SuperServer) will not have business rules and only provide a means for requests to the database.
What am I working on now? Like I already said, my map is isometric. Therefore pattern pathfinding algorithm can not be fully utilized. The first adaptation is to change the weights of the horizontal/vertical and diagonal movements. Usually a diagonal move has a higher cost compared to the horizontal/verticias, respectively have 14, and 10. In my case, the horizontal/vertical movement should have a higher cost. Why? See the representation of an isometric tile below:
See it to walk north from an isometric tile you need to hold a diagonal movement. Therefore, diagonal directions are more expensive than orthogonal directions.
Another adjustment was needed in Manhattan algorithm. In matrix map, Manhattan calculates exactly the orthogonal distance between the current node and the destination node. In an isometric map, this calculation is not always correct. Luckily, another game developer had already found a solution for this (http://www.quartertothree.com/game-talk/archive/index.php/t-69406.html).
package br.com.linu.vectortown.base.pathfinding;
import java.io.Serializable;
import br.com.linu.vectortown.base.modelo.auxiliar.Posicao;
public class ManhattanIsometrico implements Serializable {
private static final long serialVersionUID = -2242005057055685258L;
private static int intValue(Double d) { return d.intValue(); }
/* http://www.quartertothree.com/game-talk/archive/index.php/t-69406.html */
public static int calcular(No origem, No destino) {
int cx = origem.x() - intValue(origem.y() * 0.5);
int cy = origem.y() + cx;
int gx = destino.x() -intValue(destino.y() * 0.5);
int gy = destino.y() + gx;
int diagonal = Math.min( Math.abs(cx-gx) , Math.abs(cy-gy) );
int straight = (Math.abs(cx-gx) + Math.abs(cy-gy));
return 12 * diagonal + 10 * (straight - 2 * diagonal);
}
}
I copied your solution and it’s served me well 🙂
For now, however, I’m still having a few problems finding the best path when the source tile and destination tile are on different floors (the game will have at most three different floors per screen). Sometimes pathfinding goes to a far corner of the stairs that would take him to the different floors, and consequently for the destination tile. Soon I will post here the solution to this…
vectortowns.wordpress.com 