1
\$\begingroup\$

I want to make 2D MMORPG in a post-apocalyptic world.

I would like to make the game world seamless and big, with big battles for the players. Something similar is in Eve Online (in 3D), but I do not like the fact that during major battles time in EVE slows down. All this due to the limitations of the game. I thought, what if we come up with a new architecture to handle large player numbers in one region without slowing down? I had the following idea:

Server cluster Quadtree

The whole world is one big quadtree. And each quadrant of the tree is processed by a separate server.

Diagram of quadtree divisions and hierarchy

If a big battle is coming, the quadtree subdivides, and the number of servers in the battle region increases automatically.

Can this strategy work at all?

How do you handle conflicts in this world?

I think that everything will be built using ECS (EnTT). Each server should have a connection to the servers nearby tell them information if, for example, I shoot a player while I am in server 1 and they are in server 2.

Perhaps you see some other problems with the implementation of such an architecture?

\$\endgroup\$
2
  • \$\begingroup\$ "Do you think it can work at all?" is a question I generally find StackExchange does not answer well. Any idea that makes enough sense to you to describe at a high level probably could work. The devil is in the details we can't see in your question. So any answer we give you could be completely wrong, since we're assuming different implementation and runtime condition details than what your project will ultimately entail. A better strategy is to start building small tests to prove your idea, and asking for help if a specific test fails. \$\endgroup\$ – DMGregory Nov 4 '20 at 22:09
  • \$\begingroup\$ How much do players on one side of the battlefield need to know about what happens on the other side of the battlefield (which is run by a different server)? \$\endgroup\$ – Philipp Nov 5 '20 at 9:37
3
\$\begingroup\$

Can this strategy work at all?

Yes.


Thus, I will answer a different but related question: How can we build up to that strategy?

I will cover most of what you ask. Except one detail: ECS. Why? it is a detail.


Base architecture

Go back to the original conception of object oriented programming. The way Alan Key expressed about it. Objects are like little computers, with memory, processing, input and output. These objects exchange messages. Alan Kay was thinking of cells, due to his background in biology.

Let us start there. Make every node in your quad tree an object. An object that would make Alan Kay proud. So no getters and setters, and no query methods. Tell, don't ask.

We will later make this into a networked solution. To make that transition easier, make the communication between these objects async.

For async the following is the easy route: forbid returning anything from methods. That way, there is no waiting for anything (no need for promise objects or similar). If an object needs to tell another something it will call a method on it send a message. And if there were something to return we use the same mechanism.

Of course, to send a message you need the objects to be aware of each other. You cannot have pointers/references because that does not work across the network. Instead, have a service object that will allow communication.

The communication service object will have methods to send messages between objects. Also methods to callbacks. The communication service object will execute the callbacks when it receives a message. Inject the communication service object on construction. You will also need a way to address objects, so they can say to which other object to send the message.

Each server will run ticks, at some predetermined frequency. That gives the server a time budget. It has to deal with all the messages before the next tick comes. The messages can arrive at any moment, so buffer them. Each tick, the server swaps the buffer and deals with the messages.


The division problem

Each object will decide when to divide. To divide, the object has to:

  • Create the new objects
  • Send messages to the new objects to set them to the same state
  • Sends messages to the neighbors to notify them about the change
  • Die

To create the new objects, the object will need a factory. Which, again, you can inject on construction. No, don't call new. Using a factory will make it easy to replace this later.

Sending messages takes time from the time budget. Thus, this time budget is a good measure to know when to divide. Let us say that when the time used to process the messages reaches 50% the time budget, you divide. You will later test it in practice if that good, tweak the percentage as needed. Or even change the metric. For example, if you know how much time it takes to deal with each entity, you can compute how many entities are too much.

There might be messages that arrived while the object was sending messages. Deal with any messages left on the buffer by relaying them to the new object. Then the object can die.


The joining problem

Joining has a different challenge: objects need to agree to join.

I believe it is necessary for nodes to know who are their siblings. So they can notify them when they want to join, and when they no longer want to join. Each object would keep track of whether or not its siblings want to join, and if they all agree they can migrate to a single object that remplaces them.

This adds to the factory the constrain that they must all get the same object, so they actually join, instead of creating four versions of the parent. Given that we will later distribute them over the network, you would want to put that coordination on a central server. Which would the same that does load balance.

You may find the situation where one object believe all the siblings agree… Then it goes on to request the parent object… Meanwhile, one of the siblings decides it no longer wants to join.

To avoid that, each of the objects will request the new parent, then notify to the siblings that they requested it. If an object gets notified that the parent was requested, it will migrate to it.


Milestones

First milestone: the architecture described above, single process, single thread. Make sure it works OK, fix any problems. If the system does not work under this conditions, it will not work later.

Second milestone: single process, each object runs on a thread. See that threading does not introduce bugs, fix any.

Third milestone: single process, each object on a thread, use sockets for communication. Each thread listens to a different port. Make sure that those messages are sending get serialized and deserialized. Also, you need to solve how you are going to address/identify the objects.

Fourth milestone: add a facade process. It serves as a layer between the client and the servers, over the network. It relays input from the client to the corresponding server. Also it queries the server to tell the client what to show. The servers will have to notify the facade when they divide.

Fifth milestone: multi process. Each process runs a single object, they all talk over the network. Do you remember that factory to create objects? It has to spawn processes now. You need to update the facade.

You might also want to synchronize ticks. NTP comes to mind.

Sixth milestone: works across many machines. Thus, if you had "localhost" hard-coded, fix that. You got to solve how to start a server process on another machine.

Have a instance manager service running on each machine, listening to a fixed port. The instance manager service returns how many server processes it is running. It is able to spawn new processes on that machine. You could discover these services on the local network with a broadcast. You could do simple load balance by spawning in the machine with less process servers. It also makes it easy to add machines. I guess the idea of having servers sleep when they have no activity is also useful.

You will still have the challenge of removing machines. Start with a solution to migrate a server. It works like division, except it only creates one the new object, on a different machine. Migrate all servers on a machine, and then you can shutdown the machine.


As you are aware, it takes less to come up with this plan than to actually try it. I don't know what I don't know. We don't expect the unexpected, but unexpected things happens. Thus, I guess you will run into some problems along the way. Make those their own questions when you get there. If you find a better way, consider sharing what you learned so it can help others.

\$\endgroup\$
1
  • \$\begingroup\$ It's kind of funny how I realized who wrote the answer by amount of scrolling it took to get to the end \$\endgroup\$ – Ocelot Nov 5 '20 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.