Hello all,
Now, I was thinking, if every time an entity moved (player or NPC) all players were notified, the bandwidth would quickly add up, so I came up with the following idea:
This is a big problem that is the subject of a lot of active research. Like most of MMOG development, it's always a case of tradeoffs - PC's these days are still far too puny to handle MMOG's without a lot of compromises.
A data structure will be maintained for each zone that stores the position of each active entity (player and NPC). Each active will have a list of other actives within its "square of influence" (a few grid squares past the edge of the screen). Whenever an active moves, it will first drop any references that have left the square of influence, then acquire any new references that have entered the square on influence, and finally notify all references within the square that the move has been made so they can update their respective client displays.
This will certainly work. However, 99% of the approaches to MMOG development "work"; it's just they break whenever e.g. "more than X players in the game", either because the algorithm uses too much memory or too much CPU.
If you want advice on what algo to use for this task, you need to sit down and very carefully think about your requirements first. You haven't, for instance, told us the most important thing of all - which is the max number of players that any given player will ever be able to "see". Equally, we'd need to know what limit you're going to place on the number of players in your game.
The algo itself is perfectly good...indeed it sounds just like one that I think Ensemble Studios (Age of Empires people) proposed - although they suggested a more generic system that enabled an RTS to constantly update info in multiple different dimensions (e.g. "Line of Sight + FoW", "Pathfinding", "desirable locations", etc). The aim was to provide a system that had a high cost per unit-movement, but a very very low cost per query - so that units could calculate e.g. whether they could see another unit almost instantly. Works particularly well when you have many more units "looking" at the map/data than are moving.
This system works based on the assumption that active A can "see" active B if and only if B can "see" A. This data structure could also be extended to allow the passing of communication messages to everyone on the screen.
Actually, it makes a lot more assumptions than that, mainly to do with performance, relative numbers of moving objects, etc etc. Hopefully what I've mentioned above gives you a small taste of this?
To be honest, I hope you aren't really attempting an MMOG unless you've got a large team or financial backing or something
. You'd be much better off doing a 16-player or 64-player or etc game. MMOG development is really really really hard, and although it's certainly within the reach of anyone, there's a lot of specialist stuff you have to learn in order to make your game work OK (in addition to getting all the standard things from game development right - graphics, sound, networking, collision detection, AI).
If you (or anyone else) really want to work on an MMOG, I'd suggest getting involved with WorldForge.org (Open Source MMOG development). They've been going for about 6-7 years, and have developed lots of technology for MMOG game development. The main benefit of getting involved is learning all about MMOG development from people who have been working through the issues for years. The main problem is that it's OpenSource, so people come and go, and there's a very large number of people with little or real understanding of MMOG technical problems at any one time. On the plus side, they have something like 50+ talented artists constantly churning out graphics for use in any WorldForge-based game (and it's OS, so you can go ahead and start a new game based on their tech).
