Hello guys!

I have a task to make a fast paced ARPG work in cooperative mode, and with your help, it is working great, but I have another problem.

In every action rpg( like diablo, torchlight ) it is possible for the players to go on different maps.

#1 player( the server ) goes to the central HUB map, #2 player( client1 ) goes on map1, #3 player( client2 ) goes to map2 and #4 player( client3) goes to map1 with #2 player.

Since there are a lot of movement on one map( more than 100 entity can move simultaneously ), I think it's pretty impossible to make the server handle all the pathfinding, gamelogic, and AI on every map.

How would you solve this problem?

My solution was a secondary "server", every time someone is entering a map, the server sends info to the client if there is another player on that server already. If not, then the client creates a "server"( let's call it realm ), and registers it to the server that it's available. If there is another player on that map, this client connets to their realm. This realm is just a logic layer, it isn't necessary to connect directly to this player to be able to play on the same map, the realm will send the message to the server, and then it will relay it to the client. However, it burdens the server a lot, so it tries to open a direct communication channel between the realm owner and the clients.

This solution is actually working, however, there are problems like bandwidth( e.g. the client has less bandwidth available than the server, so if the client enters the map first, then the game can lag to even the server ), sometimes it cant even connect( due to router problems, NAT punchthrough not always working ).

Is there a better solution to this problem?

Thanks in advance, and sorry for the bad english

I think it's pretty impossible to make the server handle all the pathfinding, gamelogic, and AI on every map.

Honestly, doing 400 entities at 10 Hz across 10 maps is not a problem for a modern CPU.

However, in general, yes, MMO games will typically farm off simulation responsibility for different areas of the world to different physical servers, and then arrange for the client to talk to the right server depending on where it is. This arrangement is either using a "smart gateway" or just creating new connections as appropriate.

Maybe the fault is on our side, but when 400 unit simultaneously trying to find path on a relatively big map, then we often get low fps. On weaker pcs( or mac ) we often get 15-20 fps on one map, imagine that with 4 different maps.. Also, for that, you have to load all those maps in memory( at least the obstacle net ).

Also, this is not an MMO, it's just a coop game, where customers host their own server, simply by choosing "coop" in the menu. That's why there is a problem with the connectivity( shitty routers which are impossible to punch )

I would solve path finding on client. Client sends points to which he WANT to move, when server manages collision detection while moving player towards these points.

If you have master server NAT should not be a problem (I only read about it - try NAT introduction). Player connects to server, when he wants to join realm then your server can inform realm about new server and player about new (or existing) realm. This gives direct connection between players (and probably solves NAT).

For bandwidth I would send only informations which other player can see on screen. If you want to share everything then you can send rest in batches later.

Maybe the fault is on our side, but when 400 unit simultaneously trying to find path on a relatively big map, then we often get low fps.

Are you already caching the paths? You definitely don't want to recalculate each entity's path every frame. I'd only recalculate their paths once a second or so. And not every entity on the same second - spread out the entities over every frame so, for example, entities 1-20 re-calculate their paths on frame A, entities 21-40 calculate on frame B, and so on.

You still update their movement along the already-calculated path every update frame, but you only do the costly path calculations as infrequently as you can get away with.

Also, for that, you have to load all those maps in memory( at least the obstacle net ).

How large are your maps when loaded in memory? Don't forget the "host" doesn't need to load all the textures/models/music for the maps that the host-player isn't on. Honestly, I doubt your loaded in-memory maps are more than 100MB apiece (and I'd be surprised if they're even that large). Even cheap laptops nowadays have over 2GB of RAM.

I had formulated an answer in my head, but Servant already said pretty much the same thing :-)

Also, servers have cores. Many, many cores: http://ark.intel.com/products/75258/Intel-Xeon-Processor-E7-8890-v2-37_5M-Cache-2_80-GHz

Hello!

Thanks for the answers, it helps a lot :)

I would solve path finding on client. Client sends points to which he WANT to move, when server manages collision detection while moving player towards these points.

It was discussed in the topic I linked on the first post, that the client can't handle the pathfinding. Even the smallest difference( which will happen ) can lead to totally different paths, then pulling back to the correct place looks ugly, laggish, buggish.

If you have master server NAT should not be a problem (I only read about it - try NAT introduction). Player connects to server, when he wants to join realm then your server can inform realm about new server and player about new (or existing) realm. This gives direct connection between players (and probably solves NAT).

NAT is a pain in the ass. some of the routers support it, some aren't. Sometimes it works, sometimes it doesn't. At least that's what Raknet offers. And I can't get much out of raknet support( all they did was asking for logs, then no more replies )

Servant:

About the pathfinding, and collision detecting: I don't really know much about this thing, it wasn't me who wrote it, nor did I work with it. The only thing I know, when 100+ entities moving, colliding with each other, the FPS drops. Even with one map, shit computers, like mac gets really low fps. And since we support mac, we have to work with it.

How large are your maps when loaded in memory? Don't forget the "host" doesn't need to load all the textures/models/music for the maps that the host-player isn't on. Honestly, I doubt your loaded in-memory maps are more than 100MB apiece (and I'd be surprised if they're even that large). Even cheap laptops nowadays have over 2GB of RAM.

32 bit executables can only handle 2GB ram, and we are using like 1.7 or more for the graphical content and others. If we only supported 64 bit executables, it would be fine, but that's not the case.

Also, servers have cores. Many, many cores

Sorry, maybe I was not clear, but the players host servers. There aren't dedicated servers, you can only join to another player. And the game is already using 3 cores.

The only thing I know, when 100+ entities moving, colliding with each other, the FPS drops.

You need to break out the profiler, then!

32 bit executables can only handle 2GB ram, and we are using like 1.7 or more for the graphical content

You may need to reduce the size of your graphical content for lower-end machines, then. Also, on Windows, /LARGEADDRESSAWARE will give you 3 GB, not 2.

players host servers

That makes it impossible to guarantee good performance in general.

About the pathfinding, and collision detecting: I don't really know much about this thing, it wasn't me who wrote it, nor did I work with it. The only thing I know, when 100+ entities moving, colliding with each other, the FPS drops.

Well, if you want to meet your hardware requirements, either you need to cripple your design (i.e. have less entities), or learn the code and fix the problem. Lucky for you, in this case, it's actually likely an easy fix: Just don't call the pathfinding for every entity every frame.

32 bit executables can only handle 2GB ram, and we are using like 1.7 or more for the graphical content and others.

1.7GB all loaded at once, or unloaded sitting on the harddrive? You only need to load the resources you are currently using, and then unload them when they are no longer needed.

And besides, I'd rather have a better game with slightly poorer graphics, then a beautiful game with slightly lower gameplay. If the graphics are standing in the way of you implementing this important feature, then you need to make a decision concerning the graphics. Either keep less in memory at one time, or reduce the cost of them when they are in memory. Don't forget that some or all of the textures are likely stored in the videocard's RAM, not the CPU's RAM.

You also still haven't mentioned what size your maps actually are when loaded in memory (without loading all the sounds, textures, and so on). They could be as little as 10MB, for all we know.

32 bit executables can only handle 2GB ram, and we are using like 1.7 or more for the graphical content and others. If we only supported 64 bit executables, it would be fine, but that's not the case.

As hplus0603 mentioned, it's 3GB, not 2GB. I don't know the details you need to do on the programming side to be able to access ~3GB, but I do know that until a few months ago, I was stuck on 32bit machine, and I definitely had 3GB RAM that functioned properly.

A 32 bit pointer can actually address up to 4GB (2^32 = 4 * 1024 * 1024 * 1024), but, due to the videocard RAM, CD drives, and other pieces of hardware that take some of the addressable space, it actually becomes about ~3.5GB or less. (see wikipedia for more details)

Ofcourse, this doesn't help you if your target devices don't have a third stick of RAM installed, and you have to take into account that the OS itself uses some RAM.

However, if >65% of your potential players have 3GB or more of RAM (Jan 2015 Steam hardware measurements of PC and Mac gamers), maybe you ought to limit your host players to those 65%, so everyone, including the not-65%, can have a better experience. Besides, how much longer is your development going to go on for? 1 year? 2 years? That '65%' number is going to continue to increase in your favor, by the time you are ready to release your game.

By the way, 80% of your target audience today uses a 64bit OS (same Jan 2015 survey). Two years later, it'll be higher.

Sorry, maybe I was not clear, but the players host servers. There aren't dedicated servers, you can only join to another player. And the game is already using 3 cores.

Three threads or three cores? Because 50% of your target audience still only has two cores... But each core can run more than one thread.

It sounds like you have two issues:

Issue A: Pathfinding is too slow for all the entities you are wanting to deal with at once.

Recommended fix:

• Learn how your pathfinding code works, at least at a high level.
• Don't call pathfinding so frequently. Cache the results. Spread the calls out over a larger area of time (i.e. many frames).

Alternative fix 1: Learn how your pathfinding works at a low level, optimize your pathfinding, and optimize the data it is operating on.

Alternative fix 2: Require your users to have better CPUS. (Bad idea, because CPU speed increases have been very slow).

The reason why I suggest spreading the work out instead of immediately jumping in and trying to optimize the algorithms, is because you can get much larger results, faster, and easier. The joking truth among programmers is, "doing nothing is always faster than doing something".

If you're calling your pathfinding every frame, for every entity, then by simply doing half the entities on one frame, and half on the next frame, you instantly save 50% of the work - by not doing the work you don't need to be doing. And even updating the pathfinding every other frame is still a huge waste of work doing things you don't actually need to do. Update it once a second, or once every two or three seconds (but spread the entities out over those two or three seconds). That'll instantly save you 98% (!!!) of your pathfinding workload, very easily, without having to understand the algorithms at a low level (you will need to understand how to use them at a high level though). That 98% is a real number, not an exaggeration.

Issue B: Not enough RAM for all the maps you want to load at once.

Recommended fix:

• Know your actual numbers. Find out how much it actually takes to keep one map, without graphics, loaded.
• Figure out how many maps you want loaded, without graphics, at one time (the same as your player-count).
• Knowing you need (PlayerCount * MinimumCostOfMapInRAM), make sure you reserve that amount of memory for your maps.
• If you need to, optimize the amount of space each map requires.
• Only load the graphics the player actually needs.
• If you need to, optimize the size of the graphics.
• If you absolutely positively need to, reduce the quality of the graphics.

Alternative fix: Require your users to have 64 bit machines and 3GB or more of RAM. (Not a bad idea, because RAM has been increasingly fairly rapidly)

Programming often requires making choices and tradeoffs. To make informed choices, you need hard data.

You say your pathfinding is slow. How much time does one pathfinding call actually take (best time, worst time, average time)? How frequently is it called? Does it need to be called that frequently?

After being loaded in RAM, without assets, what size are your maps actually? This is information you need to measure to make your decisions.

(Note: I keep on saying "after being loaded", because the size of your files in your computer folders is definitely not the same as the size of your files in your RAM. The same thing with your textures. The files merely describe what data to create. You need to measure how much the created (i.e. in RAM) structures actually cost)

About the graphical content and design, that's not my job to decide what to put in, what to cut. My job is only to get it work with network, can't change the whole concept, has to get the best out of the content I have.

All I know about pathfinding that is has been optimalized like hell. Every entities has own timer to find path, there also a "smart pathfinding" and a "dumb" one. Only some of the entities can use smart( slow ) pathfinding for a time, others use a dumber, but faster, and when they found theirs, it gives the privilige to others. But really, I'm not the one who wrote the pathfinding, and I don't really have time to understand it fully, but I'm sure it's pretty much optimalized, just the obstacle net is really detailed, because there are small passages, and so ( I don't really know the reason, but I know that we were using a lot smaller obstacle net before, and it had problems ).

About the RAM usage, things are more complicated.. There was some problem with the largeaddress before with another game( don't know what was it, I just heard ), so we stopped using that, also steam has problems with 64 bit executables( it makes loading files a LOT slower, even contacted steam about it, and they couldn't figure out, but it works fine in 32bit.. ). Ofc 64 is better, but we can't simply drop the 32bit support( also, there isn't 64bit steamlib for mac ), so it has to work.

How does other games do it? How did diablo 2 did it for example? Is this the only way what you described?