Creating collaborative whiteboard drawing application

Question

I have my own drawing program in place, with a variety of "drawing tools" such as Pen, Eraser, Rectangle, Circle, Select, Text etc.

It's made with Python and wxPython. Each tool mentioned above is a class, which all have polymorphic methods, such as left_down(), mouse_motion(), hit_test() etc. The program manages a list of all drawn shapes -- when a user has drawn a shape, it's added to the list. This is used to manage undo/redo operations too.

So, I have a decent codebase that I can hook collaborative drawing into. Each shape could be changed to know its owner -- the user who drew it, and to only allow delete/move/rescale operations to be performed on shapes owned by one person.

I'm just wondering the best way to develop this. One person in the "session" will have to act as the server, I have no money to offer free central servers. Somehow users will need a way to connect to servers, meaning some kind of "discover servers" browser...or something. How do I broadcast changes made to the application? Drawing in realtime and broadcasting a message on each mouse motion event would be costly in terms of performance and things get worse the more users there are at a given time.

Any ideas are welcome, I'm not too sure where to begin with developing this (or even how to test it)

Answer 1

Making any real-time collaborative tool/game boils down to efficiently synchronizing changes on a minimal shared data structure between clients. Network bandwidth is the bottleneck. Send only information absolutely needed to synchronize the shared data. You are on the right track by storing shapes instead of individual pixels. However, the shapes should not handle mouse events. As you noted, broadcasting mouse events will quickly saturate the network bandwidth! Instead, pass deltas of how the shapes are altered by the mouse events. For example, instead of sending mouse_motion() send the final position [x,y] after a shape has been moved.

I suggest splitting your drawing program into a server part and client part. The server keeps the authoritative version of the shared data. A client never manipulates the shared data structure directly; it only sends network messages to the server. This may seem silly when both the client and server are in the same process/PC, but there are some good reasons:

1. Shared code path for both single-user and multi-user
2. The network overhead between a client and server in the same process is next to zero when using local sockets

In addition, editing does not have to be limited to the owner of that shape. Since the server is the final authority, it resolves any conflicts when two people grab the same shape simultaneously and send the results back to the clients. (Undo gets a little tricky, though.)

Although a centralized server is best for network discovery, clients can use other methods to find a server:

1. Send or listen for network broadcast packets.
2. Connect directly via an IP address. (The server IP address will have to be communicated via other means: chat, cell phone, shouting across the room, carrier pigeon, ...)

Finally, look at how other multi-user applications are designed. Here are some examples:

• Zoidcom Multi-player game programming libary (C++). Much of this answer is based on information from Zoidcom documentation. There are even sample programs that demonstrate server discovery via network broadcast.
• Operational Transformation algorithm behind Wave, Google Docs. (article discussion on Hacker News)
• Etherpad Open-source real-time collaborative text editor.
• Source Multiplayer Networking Explains how an FPS like HAlf-life is designed. Gets into tricks for reducing lag/latency.
• Google Wave (Apparently the documentation is stil pretty poor...)