WebSocket RFC 6455 Handshake

I think I got the request/response bit figured out (it was actually simpler than the draft 76 method). This is my test using headers from the RFC document:

from hashlib import sha1
from base64 import b64encode

WS13_GUID = b'258EAFA5-E914-47DA-95CA-C5AB0DC85B11'

REQUEST = (
    b'GET /chat HTTP/1.1\r\n'
    b'Host: server.example.com\r\n'
    b'Upgrade: websocket\r\n'
    b'Connection: Upgrade\r\n'
    b'Sec-WebSocket-Key: dGhlIHNhbXBsZSBub25jZQ==\r\n'
    b'Origin: http://example.com\r\n'
    b'Sec-WebSocket-Protocol: chat, superchat\r\n'
    b'Sec-WebSocket-Version: 13\r\n'
    b'\r\n'
    )

RESPONSE = (
    b'HTTP/1.1 101 Switching Protocols\r\n'
    b'Upgrade: websocket\r\n'
    b'Connection: Upgrade\r\n'
    b'Sec-WebSocket-Accept: {}\r\n'
    b'Sec-WebSocket-Protocol: chat\r\n'
    b'\r\n'
    )

CORRECT_ACCEPT = b's3pPLMBiTxaQ9kYGzzhZRbK+xOo='

def parse_request(request):
    req = {}
    lines = request.split(b'\r\n')
    line = lines.pop(0)
    items = line.split(b'\x20',2)
    if len(items) != 3:
        raise BaseException('Malformed WebSocket Request Method.')
    req[b'method'] = items[0]
    req[b'request_uri'] = items[1]
    req[b'http_version'] = items[2]
    for line in lines:
        if line:
            parts = line.split(b':\x20', 1)
            req[parts[0].lower()] = parts[1]
    return req

if __name__ == '__main__':
    req = parse_request(REQUEST)
    salted_key = req[b'sec-websocket-key'] + WS13_GUID
    sec_ws_accept = b64encode(sha1(salted_key).digest())
    assert(sec_ws_accept == CORRECT_ACCEPT)
    print RESPONSE.format(sec_ws_accept)

Step two is to get the VERY DIFFERENT message protocol working.

WebSockets

Naturally, the Overlords of the Internet have obsoleted my WebSocket code for the third time. Hopefully things will settle down now the current draft has been submitted as a proposed standard (one step away from an adopted standard).

Pointing my browser (Chromium) at http://websocketstest.com tells me that it's ready for RFC 6455, so I guess I need to get coding.

Zomborgs

Known to use transmat beams to take brains directly from crewfolk skulls.

Failure is an Option

This is the icon for a dead player

Character Work

I have a notion of how I'd like the chat windows to flow using character portraits. Player and crew would appear left of chat boxes and encountered NPCs to the right. I suspect I'm channeling some Japanese RPG.

This is a Kthogin -- a Lovecraftian inspired hostile. I'm leaning towards giving each race a unique color for easy recognition.

Thoughts on Serialization

The problem domain is short and sweet;

1. We need to write game data.
2. We need to read game data.

The only real snag is, being single threaded, we need these operations to block as little as possible -- as in thousandths of a second. I've even toyed with the idea of reading everything at server start and only performing writes during execution. That would cut our blocking problem in half but removes our ability to modify data externally.

The model in my head calls for very little of the R in RDBMS. Heck, MUDs have managed very well for decades using flat files on systems with less processing power than your dishwasher.

Lastly, given that this hobby-coding, I have the luxury of asking, 'is the solution fun?' Let's set a couple goals;

1. I don't want a crash to lose the overall state of the game -- which precludes saving writes for an extended period, or even worse, until server shutdown.
2. Simple to install. Freely available software that does not require a DBA to manage.
3. Simple to operate. No fretting dirty caches, scheduled housekeeping , etc.
4. I would prefer back-ups and restores to be file copies. Tar'ing a directory or two is fine.
5. Some external method to futz with the data while the game is running.

Flat files are certainly doable (and made crazy easy with Python's Pickle module). They meet goals #2, #3, and #4 but I cringe at the amount of runtime file-io needed to cover goal #1 and supporting goal #5 means we have to perform constant reads as well (plus some form of file-locking mechanism). Ick.

A lightweight dbms like SQLite would work except for goal #3. Wrapping Python CRUD in SQL statements is soul-destroying tedious. Yeah, I could tap a ORM like SQLAlchemy but let's look at that new sexy, NoSQL...

When I was a kid, one Christmas I got this electronics kit with 150 projects. It was awesome. You could build things like a crystal radio, lie detector, and light activated room alarm.

Python holds that same appeal for me. It's a big toy. Another one I've found is Redis -- a dead simple NoSQL data store. The distinguishing feature is all data is held in-memory which makes it wicked fast.

I'll admit, when I first read that it holds everything is RAM it struck me as rather pointless. I mean, wasn't I already doing that in my program? And who wants to hold everything in memory whether you need it or not?

Having played with it, the utility and genius starts to shine through. Redis has a clever system of serializing to a file based on the frequency of updates and you can copy this file at any moment without fear of corrupting it. The author also provides a really nice CLI tool with history and auto-complete similar to a Linux terminal.

We're pushing goal #2 a bit since it requires installing three packages, Redis, Hiredis, and Redis-py but they all loaded with minimal fuss. Hiredis needed the Python development libs you can get on Ubuntu using:

$ sudo apt-get install python-dev

...to be continued

Crawling a Graph

I got the sector crawling code done. Then I used it to walk a sector and add every linked one to a set. This set is also added to a master set of visited sectors. I step to the next sector and, if it's not in the visited set, crawl it. Repeat for all sectors to generate a collection of sets. Each set contains either a group of linked sectors or a single orphan sector.

Here's a diagram of crawling from sector 12:

Next, I take the collection of sets, pop one off, and work through the remaining trying to find two sector that are adjacent. Once I do, I give them exits to each other and merge the popped set into the target set. I repeat this until the collection only contains one set -- the entire universe:

Lastly, I got my A* path finder working. This is the first time I've experimented with path finding. I tried a variety of heuristics and had the best luck (shortest path + least crawled sectors + fastest time) with the simplest one; Chebyshev. This is comparing ABS(X1 - X2) to ABS(Y1 - Y2) and use which ever is greater. One source I read said to add the number of hops from the starting point but, again, just Chebyshev alone gave the best results. Weirdness. Could have a glitch somewhere.

I had a funny bug during my testing. I was using random.seed() so that I'd generate the same initial links every time. I ran my path finding test; 24 hops. Ran it again; 20 hops. Again; 48 hops. What the heck? I neglected to consider that sets are unordered and was linking the orphaned sectors in varying sequence. Changing the set to a list fixed this.

Two options that I have not explored are one-way exits and links between non-adjacent sectors (wormholes). Not sure if the added complexity has value.