1 2 Previous Next 18 Replies Latest reply: Nov 17, 2009 1:01 AM by jwenting RSS

    Game server: Map managing questions

    843853
      Hello everyone,

      I'm trying to develop some kind of RPG. I have different issues, where I need advice:

      1) Map(2D) managment on game server
      The map I want to keep in memory on server will contain objects such as: Item, NPC, Character, etc.
      Item, NPC, Character and other objects going to extend MapObject class, because I want to keep all this data in same place.
      Let's suppose that the map will have 50x50 tiles..
      I want to use Hashtable array to store elements there... So I will have something like this:
      Hashtable <String, MapObject>[][] map = new Hashtable[50][50];
      String(aka key) is going to be object_name + "_" + object_id..
      The questions are:
      - What about performance in this situation?
      - Is there any other data structure which can suite better to this situation?

      2) The other question I have is about sending map object(once in fixed period of time) and updates(for example some character walked or picked an item).
      The architecture I thought for sending data to client is:

      TCP Connection for authentication anc chat
      MultiCast Socket for synchronizing map object and sending updates

      - Is this aceptable architecture for server?
      - Is MultiCast socket good for sending updates and map object?(because there will be significant gain in term of computation on server, comparing to TCP, but what about losses of packets? what about traffic? what kind of protections(excluding timeouts) should I implement on client-side? )

      Thank you in advance.
        • 1. Re: Game server: Map managing questions
          jwenting
          Don't use Hashtable unless there's no possible alternative. It's a legacy class and slow compared to e.g. HashMap (even its synchronized versions).

          50x50 is nothing, performance won't be an issue there at all.

          Avoid multicasting and especially broadcasting, most network routers will block it.
          • 2. Re: Game server: Map managing questions
            843853
            So instead of Hashtable, HashMap will be more suitable in terms of performance, I understood correctly?

            Is there any alternative to MultiCast, which I can implement to take off some computation from server?
            • 3. Re: Game server: Map managing questions
              843853
              I have made some performance tests, with following code:
              import java.util.Enumeration;
              import java.util.HashMap;
              import java.util.Hashtable;
              import java.util.Random;
              import java.util.Set;
              
              
              public class HashMapTest 
              {
                   public static void main(String [] agrs)
                   {
                        HashMap <String, MapObject> map = new HashMap<String, MapObject>();
                        
                        Long start_time = System.currentTimeMillis();
                        
                        for (int i = 0; i < 100000; i++)
                        {
                             MapObject ma = new MapObject("ID" + i,"NAME"+i);
                             map.put(ma.getId() , ma );
                        }
                        
                        for (int i = 0; i < 100000; i++)
                        {
                              Random randomGenerator = new Random();
                              int randomInt = randomGenerator.nextInt(99999);
                              map.get("ID" + randomInt);
                        }
              
                       System.out.println(System.currentTimeMillis() - start_time);
                       
                       Hashtable <String, MapObject> map_hash = new Hashtable<String, MapObject>();
                        
                       
                       start_time = System.currentTimeMillis();
                        
                        for (int i = 0; i < 100000; i++)
                        {
                             MapObject ma = new MapObject("ID" + i,"NAME"+i);
                             map_hash.put(ma.getId() , ma );
                        }
                        
                        for (int i = 0; i < 100000; i++)
                        {
                              Random randomGenerator = new Random();
                              int randomInt = randomGenerator.nextInt(99999);
                              map_hash.get("ID" + randomInt);
                        }
              
                       System.out.println(System.currentTimeMillis() - start_time);
              
                   }
              }
              
              class MapObject
              {
                   private String name;
                   private String id;
                   
                   public MapObject (String id, String name)
                   {
                        this.id = id;
                        this.name = name;
                   }
              
                   public void setName(String name) 
                   {
                        this.name = name;
                   }
              
                   public String getName()
                   {
                        return name;
                   }
              
                   public void setId(String id) {
                        this.id = id;
                   }
              
                   public String getId() {
                        return id;
                   }
              }
              And it's seems that Hashtable has better performance.. How comes?
              • 4. Re: Game server: Map managing questions
                gimbal2
                perhaps hashtable works faster in smaller datasets. If I change your values to 200000, the hashmap becomes a great deal faster.
                • 5. Re: Game server: Map managing questions
                  843853
                  Strange... I have also tried with 200k and same results... :D
                  How comes?
                  • 6. Re: Game server: Map managing questions
                    843853
                    patriot87 wrote:
                    Strange... I have also tried with 200k and same results... :D
                    How comes?
                    Well, one reason is that your test is broken. The first set of tests will always take longer, cause it's before hotspot has kicked in, etc. I moved the test to a method, precreated the objects (remember, if gc happens in one and not the other it's a huge difference), and called them repeatedly. Once I did that, there wasn't really a noticeable difference between them:
                    import java.util.HashMap;
                    import java.util.Hashtable;
                    import java.util.Map;
                    import java.util.Random;
                     
                     
                    public class HashMapTest 
                    {
                       private static MapObject[] objs = new MapObject[200000];
                       private static Random gen = new Random();
                       public static void main(String [] agrs)
                       {
                          
                          for ( int i = 0; i < objs.length; i++ ) {
                             objs[i] = new MapObject("ID" + i, "NAME"+i);
                          }
                          
                          hashMap();
                          hashTable();
                          hashMap();
                          hashTable();
                          hashMap();
                          hashTable();
                          hashMap();
                          hashTable();
                       }
                       
                       private static void hashMap() {
                          doTest(new HashMap<String, MapObject>());
                       }
                       
                       private static void hashTable() {
                          doTest(new Hashtable<String, MapObject>());
                       }
                       
                       private static void doTest(Map<String, MapObject> map) {
                          long start_time = System.currentTimeMillis();
                          
                          for (int i = 0; i < objs.length; i++)
                          {
                             map.put(objs.id , objs[i]);
                    }

                    for (int i = 0; i < objs.length; i++)
                    {
                    int randomInt = gen.nextInt(objs.length);
                    map.get("ID" + randomInt);
                    }

                    System.out.println(map.getClass() + ": " + (System.currentTimeMillis() - start_time));
                    }
                    }

                    class MapObject
                    {
                    String name;
                    String id;

                    public MapObject (String id, String name)
                    {
                    this.id = id;
                    this.name = name;
                    }
                    }
                    Results of one arbitrary test:
                    [pre]class java.util.HashMap: 343
                    class java.util.Hashtable: 500
                    class java.util.HashMap: 313
                    class java.util.Hashtable: 328
                    class java.util.HashMap: 453
                    class java.util.Hashtable: 313
                    class java.util.HashMap: 296
                    class java.util.Hashtable: 454[/pre]
                    
                    Edited by: endasil on 13-Nov-2009 10:34 AM                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
                    • 7. Re: Game server: Map managing questions
                      843853
                      patriot87 wrote:
                      So instead of Hashtable, HashMap will be more suitable in terms of performance, I understood correctly?
                      That's not the main reason. The main reason is because Hashtable is legacy. HashMap is more standard and therefore more widely used and understood by developers, and is more likely to be actively maintained.
                      • 8. Re: Game server: Map managing questions
                        843853
                        Ok, thanks a lot! It's a nice and valid argument. I think I'll proceed to programming with Hashmap, even through I have pervious implementations of "Online Users List" using hashtable(going to rewrite this part).
                        Thank you one more time!
                        • 9. Re: Game server: Map managing questions
                          843853
                          patriot87 wrote:
                          Ok, thanks a lot! It's a nice and valid argument. I think I'll proceed to programming with Hashmap, even through I have pervious implementations of "Online Users List" using hashtable(going to rewrite this part).
                          Note that if you have been programming to the Map interface, this is not a hard change to make:
                          Map<String, Clazz> map = new Hashtable<String, Clazz>();
                          map.put("hi", null);//etc
                          In this case, you literally only have to change "Hashtable" to "HashMap", since you're simply swapping implementations of the same interface.

                          If on the other hand you've been keeping references to a Hashtable instead of the more generic Map, you might have much more work to do. And you will have learned your lesson: in general, prefer coding to the interface, not the implementation.
                          Thank you one more time!
                          No problem.
                          • 10. Re: Game server: Map managing questions
                            843853
                            endasil wrote:
                            And you will have learned your lesson: in general, prefer coding to the interface, not the implementation.
                            Yes, it's very important lesson. Even if I pay maximum attention to what professor says, I won't be able to learn such lessons, just because professors don't say it..
                            • 11. Re: Game server: Map managing questions
                              843853
                              Hi. Can you explain to me why you are using a hashtable? (or hashmap if you have changed to that)
                              I see absolutely no benefit in this setup, and in fact using a 2D primitive array of MapObject will give you faster access.

                              The only use for a hashtable/map I can discern from your OP is that for each tile, you will have a number of MapObjects you want to access on that tile in O(1) which is all well and good, but unless you have a high number of objects per tile and you know the exact name of the object you are looking for, then hashtable/maps are useless in this situation, in my eyes.

                              Of course if you are using them for a different reason please tell me so I can understand.

                              Cheers, Sutasman

                              ps about the networking. It is a big coincidence that at this moment I myself am working on a medieval themed rpg with eventual online/lan capabilities (in fact is there anyone who isn't or hasn't worked on a medieval rpg?) As it stands I know that using TCP/IP is your best bet for sending all your data as it guarantees your data will get to the other side (and if it doesn't it gives an error, so just tell it to resend) and the order in which you send packets is kept, which is important for me. However if it isn't then you also might wanna look at UDP. However my knowledge of multicastsockets is thin so I can't claim anything there.
                              The way I thought of doing my game was just to send packets on events, eg you type, and pushing enter creates a custom event called sendMessage or something along those lines, and this just puts the message in a packet and tells the client to send a message to the server. Also I will probably use huffman encoding for messages/chat simply because I already have a working project of that, as well as it will reduce packet size substantially for messages.

                              Hope that helps
                              Cheers (again)
                              • 12. Re: Game server: Map managing questions
                                843853
                                Sutasman wrote:
                                Hi. Can you explain to me why you are using a hashtable? (or hashmap if you have changed to that)
                                I see absolutely no benefit in this setup, and in fact using a 2D primitive array of MapObject will give you faster access.
                                Hello,
                                I'm using HashMap because of fast access to elements. Imagine that I have several maps, I need to know in which of the maps is my character or another object, looping all arrays with for is not a good choice. So basicly I'm using it because of easy and faster access to the elements I need + it's always easier to see what you are pulling from HashMap(or Hashtable) rather then looking at the set of loops..

                                The way I thought of doing my game was just to send packets on events, eg you type, and pushing enter creates a custom event called sendMessage or something along those lines, and this just puts the message in a packet and tells the client to send a message to the server. Also I will probably use huffman encoding for messages/chat simply because I already have a working project of that, as well as it will reduce packet size substantially for messages.
                                I wouldn't use Huffman, it's not the question of sending 2-3MBytes of raw text... You will slowdown a lot your server and client... Imaging the you will also add encryption in some parts + compressing... This will hurt :P
                                • 13. Re: Game server: Map managing questions
                                  jwenting
                                  patriot87 wrote:
                                  Sutasman wrote:
                                  Hi. Can you explain to me why you are using a hashtable? (or hashmap if you have changed to that)
                                  I see absolutely no benefit in this setup, and in fact using a 2D primitive array of MapObject will give you faster access.
                                  Hello,
                                  I'm using HashMap because of fast access to elements. Imagine that I have several maps, I need to know in which of the maps is my character or another object, looping all arrays with for is not a good choice. So basicly I'm using it because of easy and faster access to the elements I need + it's always easier to see what you are pulling from HashMap(or Hashtable) rather then looking at the set of loops..
                                  Each item on a map should have a pointer/reference back to its location.
                                  Makes finding out where something is a lot faster if you already have the thing you want to know the location of.
                                  >
                                  The way I thought of doing my game was just to send packets on events, eg you type, and pushing enter creates a custom event called sendMessage or something along those lines, and this just puts the message in a packet and tells the client to send a message to the server. Also I will probably use huffman encoding for messages/chat simply because I already have a working project of that, as well as it will reduce packet size substantially for messages.
                                  I wouldn't use Huffman, it's not the question of sending 2-3MBytes of raw text... You will slowdown a lot your server and client... Imaging the you will also add encryption in some parts + compressing... This will hurt :P
                                  Some form of encryption of the data going over the line would be a good idea though. Any realistic mmo would do that to make attacks/exploits/cheats that much harder.
                                  Combine with doing all calculations serverside rather than clientside and you're well on your way to a secure system.
                                  • 14. Re: Game server: Map managing questions
                                    843853
                                    Combine with doing all calculations serverside rather than clientside and you're well on your way to a secure system.
                                    What you think about my idia...
                                    I have path calculation on client side, but I think to implement time to time validation of client position on server(cuz of speedhacks), so basicly what I'm goign to do is define max player steps in X time, and verify if player did more of that, then probably he is cheating. The reason why don't I want to work with distance, cuz cheater can walk in some small radius, so I won't detect if person is cheating or no... Drops, NPC spawn and some operations that can be done by simple packet sending and hard to detect if it's cheating or no, are going to be server sided..
                                    1 2 Previous Next