Sign in to follow this  
yapposai

parallel algorithms/techniques in a MMORPG

Recommended Posts

yapposai    410
Greetings! It is feasible to use parallel algorithms/distributed computing techniques in a MMORPG setting? This is purely for discussion since I do not have the resources/skill needed to make a MMORPG. I imagine using the players processors to simulate weather, NPC automation, AI, Economy of the virtual world. Spawn points of monsters move from place to place. Even monster migration/evolution might be simulated. Wars between NPC factions could play out, you would see one faction gradually losing/winning, prices could become higher in war torn states. The users only recieve instructions like "here are a few arrays of floats, add this col to this col and give me the result array" or some simple commands that the user has no context of. The user might be computing the state machine of a village of NPCs far away or just the global weather. The server then gets the results and compares each with other results from redundant clients for consistency. majority vote wins. I imagine some calculations must be sorted spatially. Only low priority data (such as states of NPCs/Towns where no players are near) must be sent to be processed by the clients. weather and economy can be done by external pcs most of the time while combat and enemy AI should be always server side. The worst case is there is very few clients or the clients reply are very slow so the server has to do all the calculations itself and discard a lot of outdated information. Will the added tasks of organizing, processing the parallel algorithms be too complicated to add on top of the other things the server has to do such as calculate damage, collisions, items, etc? Is using another server/thread for these low level processing preferrable than sending redundant data and checking the results from untrusted clients? On a side note, will the all clients regardless of the machine output the same random sequence given identical seeds? I am pretty sure rand() is constant for each seed but I do not know if it still holds given different machines. I would think that some calculatations involving random numbers could be distributed but I do not think sending a random number stream is a good way. Any comments, ideas are welcomed.

Share this post


Link to post
Share on other sites
Dave Weinstein    1313
Is it feasible?

Yes.

Is it wise?

Probably not.

You are increasing network traffic and code complexity for no real win. You could get a cheaper benefit by shifting older development machines to doing it full time, and producing the data you described.

--Dave

Share this post


Link to post
Share on other sites
hplus0603    11356
Sending data to users to have them run "math" at the low level probably won't ever be a win. You have to touch all the data in four stages (server send, client receive, client process/send, server receive/dispatch), and there's dozens of milliseconds of transmission latency to contend with.

Meanwhile, doing the math on the server just needs to touch the data twice (compute, and send results), which means that unless the math is horribly complex and runs in cache (i e, a fractal generator, or ray tracer), it's probably more efficient to just run it on the server in the first place.

Share this post


Link to post
Share on other sites
yapposai    410

I also realized that having too low level chunks will result in too much data being passed around while not really making up for the speed.

Thank you for your replies and your time.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
If u build something specificly to work within such a distributed platform, it might work. Impl a scripting lanuage which can encapsualte your logic as a blobs of data/code/history with built in persistancy. Take care to make them completely determinsitic in terms of execution. Put them in a network which can guarentee dilvery of messages and u might get away with it. Just using simple lock step schemes u can syncrhonize something as complex as a RTS. Making it interactive is another problem ;), however weather is not interactive so u would get a win there. Perodically dump the state of the blob to other machines for redundancy.

As long as there isn't unmeidated interaction between these blobs, they should stay synced.

So u have the cost of downloading the blob, running it in step with the controlling authorithy, and seralizing it once in awhile. These blobs migrate through the network, and seed peers which use/need them. Authoritve servers store history for the blobs so anyone wanting too can catchup to the latest state. Remeber they have to be completely determinstic. So from stored event data + snapshot any peer can reocover the current state. This makes the blobs completely transparent network wise.

If events are lost or blobs becomes desynched u can download a snapshot and retrive the latest events to catch up. Though this might take a long time, but with good delta compress u can getaway with only download the diff between ur version and servers.

Good Luck!

-ddn


Share this post


Link to post
Share on other sites
_winterdyne_    530
The use of parallel computing algorithms depends very strongly on where you decide the concept of parallel computing is applied. Distributed computing (in terms of load balancing and task allocation) is essential as a technique for large player loads. Simply managing the simulation of a large scale gameworld (as in MMOs) where more than can be handled by one machine may be required is an exercise in distributed computing.

For example, I operate a tiered simulation, with fine-detail simulations being performed on the machine responsible for updating a zone, and course simulation being a more distributed beast - with spatial nodes exchanging simulation events amoungst themselves. Each spatial node is also directly responsible for communicating with its own local set of clients. These nodes are free-roaming objects in a distributed environment - they are semi-independent regulated sub-processes (more technically threads) that can be transferred from one physical machine (server process) to another in order to balance load or maintain an effecient hierarchical division of labour across the cluster. The spatial nodes can also be reconfigured to allow exchange of responsibility for portions of the true spatial hierarchy of the world. Typically however the domain of a spatial node is going to be a contiguous chunk of the hierarchy.

The use of parallel computing (on a single problem) is not so often used - there are not really that many algorithms where this is a useful technique (in an MMO environment), or efficient in business terms (financial cost over development/maintenance cost), compared to introducing a dedicated node in the cluster for that task (e.g. A* /AI server, database server).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this