Peer-to-peer first person shooter

Question

I've been developing a first person shooter/massive multiplayer online roleplaying game for my small business, and was wondering if it would be feasible to use peer-to-peer technology to communicate between players, without the use of an intermediary server (as our company does not have enough funds for a high-speed connection to run a game server on). How would such Peer-to-peer technology be best implemented in such a game? Here's a few of the options I've been considering:
a) Divide the game into segments, and have each segment be played on a separate P2P "mesh" (currently named XRevolution)
b) Have one mesh for all portions of the game, and place all of the players on a single grid
c) Some other P2P solution
I've already used option A (considering only one area of the game is done) on a small scale (4 computers), but am wondering how well that would scale when thousands of computers would potentially be bound to the same mesh.
Here's a list of possible concerns with P2P technology

During penetration testing, it was identified that a client could spoof packets to lie about the state of the game to other peers, allowing people to cheat. This is identified as "medium" risk, as it could be prevented to a certain extent through various security routines that would be integrated within the game (such as encryption, movement prediction, double-checking state with other peers, AI, etc.)

Lag was originally a problem on slower networks, but now movement prediction and other techniques are used to reduce the effect of lag, and disconnect peers whose lag is too high. However, a problem which remains is the amount of time it would take on a larger-scale network to find peers (other players), and establish connections. Due to the amount of time it would take to connect to so many peers, solution A would seem optimal to solve this particular problem

A problem with solution A, would be in-game chat between meshes (as no two peers in different meshes can communicate with each other, except for the purpose of relaying), however, this problem could be potentially solved by using something in-between solutions A and B (such as creating a separate mesh for inter-mesh communication, which would be specific to each player or something)

What's the best way to do something like this? Solution A, or B, something in-between the two, or an entirely different solution altogether. Due to our budget, using a server to facilitate communication between players is completely out of the question, so it would be nice to use a P2P solution, otherwise the project would have to be abandoned.

Answer 1

One idea, borrowed from distributed communication models, is to use a gossip-like approach. Gossip protocols are mostly concerned with scalability and reliability. The nice thing, however, is that they all use a very low bandwidth, which is crucial for P2P systems. The cost is latency, but read on, it might be solvable.

The main idea of gossip protocols is that each client sends a message to a small number of peers - let's say log(n) - and whenever a client receives a message it sends it against to log(n) peers. This creates redundancy (a client can receive a message more than once) which is good for reliability but bad for you - but on the other hand, this can lead to very fast broadcasts.

The question is, how to choose those log(n) clients in a way that will

1. Guarantee all clients will eventually get the message in X time.
2. Minimize the travel time of messages between two clients that are close to each other in the game world.

Point (2) above is - in my opinion - the key here. As long as not all peers can affect each other immediately in the game world, having high latency between them is less of an issue. A FPS in a small arena is a poor candidate here, but a massively-multiplayer online game is a great candidate.

So, how do you choose which peers will be connected to which? What you want is to build a small world network (also called small world graph). You can find some algorithms used to create it (see Harari Graph), as well as algorithms that will allow you to change it on-the-fly according to user data (I recall something involving darknet which can change links according to location). I wouldn't just use a plain Harari Graph - instead, you're probably better off with a variation that takes super nodes into consideration, I'm just not familiar with any.

I think using these kinds of protocols is a better approach than the less-scalable (and more discrete - what happens in edge boundaries?) local mesh concept.

Answer 2

One of the major problems about peer-to-peer is connectivity. I mean, really- a lot of customers just won't be able to connect to each other. Symmetric NAT, firewalls, and all this kind of thing is something that your customer will not want to deal with, the average customer just can't. Lag is also going to be an incredible problem as the number of players speeds up, and you're going to significantly increase your minimum hardware requirements as every player is running a server, effectively.

I would say, fundamentally, there's a reason that most FPS games are hosted on servers, and it's client-server works far better. If you can't afford to host your own servers, then get the users to host them- but don't go for BitTorrent-style mass peer-to-peer. That just won't work.

Develop as a client/server architecture, allow players to host both dedicated and non-dedicated, is the best way you can go. Most FPS games don't have significant server quantities provided by the developer themselves- it's nearly all third party servers. If you can't afford to host even a few servers for yourself, then it's time to seriously re-consider if you have genuinely considered the budgetary requirements for developing a first-person shooter.

Edit:

Ok, so hang on, let me get this straight. You can't afford to host a server for yourself, but you still want to have centralized server worlds, a'la an MMORPG. User hardware and user software configurations are not up to that kind of strain. I think that what you want is fundamentally impossible.