Visualizing Data

To create the game space, I'm going to need to assign random sector connections, tweak those into usefulness, and eventually write an A* path finder. I really need some way to SEE this hooey.

Scaled Vector Graphics are an XML-based image format that I really like. Google suggested a couple of Python libraries but I ended up writing my own based on code to generate XHTML from a previous project. A few hours later I had my universe mapper. Here's a 25 sector uiverse with some random pathways. Notice that sector 23 is an orphan, with no way in and no way out. That's the issue I'm working on now.

You might notice the absence of NE and SE jumps to fit the hex paper scheme from my previous post. I decided that the center-most sector (in this case, 12) would be the hub, which will always get 6 exits. More on using this to cure orphanism later.

Just to be stupid, I generated a map with 40,000 sectors. The script ran for only a second or two but my image viewer choked so bad that I had to go read a book while it chugged through and finally produced this (zoomed out) mess:

The Universe is a Diamond

Now that I've got the websocket server working I've got the itch to write a space rpg inspired by the classic BBS game Tradewars.

I especially liked the spatial system they used where sectors formed these baffling, mole-tunnel chains. Lucky exploration might find you a highly profitable port or, better yet, a nice dead-end sector to hide your ships and planets in.

Let's say we want each sector to link up to six others, proving a movement pattern like hex paper;

Internally, I plan on using a bog-standard XY array. Why? Because it feels like it would make things like pathfinding and NPC distribution easier. We'll see.

So let's say we're in Sector 54 (yellow) and can move to six adjacent sectors (blue):

I'm thinking that if I rotate the player's orientation slightly and omit Northeast and Southwest movement, I can fit the hex over the grid like so;

To the player's perspective, he's flying around a diamond-shaped space. Here's an example of moving from Sector 53 to 01. It was important to me that the sector you came from retain the proper orientation.

Virtual hex paper. Next step is to break all the links into twisty little passages -- not alike.

Python 3

I've been ignoring Python 3K.

I code under Linux and have been perfectly happy with the 2.x versions that most distros include by default. But Python 3 nags at me like a late property tax of uncertain size.

A while back someone filed a bug that Miniboa didn't work with Python 3. "Get off my lawn", I thought to myself.

To switch gears for a second -- I've found that deleting big chunks of code (murder your darlings) is usually a sign that you're on the right track. I deleted the unfinished Telnet, co-routine, and character-at-a-time code from Netboa. Knowing that the codebase will never be this slim again, I thought it was a good time to take a shot at Python 3 compatibility and issued an 'apt-get install python3'.

Like the five stages of denial, I bet there's a sequence that Python coders go through to port their code to 3K that starts with "keep adding parenthesis", takes them mindless cutting and pasting from googles of error messages, and finishes with them sobbing over byte encoding. Python 3 has two types of strings; bytes and unicode. Oddly, byte sequences are very like Python 2 strings minus any formatting options but with all kinds of gotchas. Take this weirdness for example:

>>> '\x20\x20'[0] == '\x20'
True
>>> b'\x20\x20'[0] == b'\x20'
False

Following the advice of Armin Ronacher, I switched most everything to byte sequences as those play nice with sockets and the keys needed for handshaking. After a bit of import hackery, Netboa seems to work under both 3+ and 2.6+. Due to a change in exceptions using the "as" keyword, I lost 2.5 compatibility.

WebSockets

UPDATE: THIS IS CODE FOR AN OLD VERSION OF THE WEBSOCKET PROTOCOL HANDSHAKE AND IS NO LONGER VALID.

Yes, long hiatus. Hi.

WebSockets have amazing potential for browser-based gaming. Unfortunately, they are also in a constant state of flux, partially because the draft spec keeps changing and partially because browser makers want to minimize the amount of dickery that internet doofuses can inflict on you. Firefox and Opera have temporarily dropped WebSocket support but they should be back in again in Firefox 6.

The last few nights I've been trying to fix a handshake bug with my implementation of draft76 handshaking. This is the version currently used by Chrome and Safari. Finally got it working again after writing the following test case:

#!/usr/bin/env python
#------------------------------------------------------------------------------
#   netboa/websocket/sanity_check.py
#   Copyright 2011 Jim Storch
#   Licensed under the Apache License, Version 2.0 (the "License"); you may
#   not use this file except in compliance with the License. You may obtain a
#   copy of the License at http://www.apache.org/licenses/LICENSE-2.0
#   Unless required by applicable law or agreed to in writing, software
#   distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
#   WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
#   License for the specific language governing permissions and limitations
#   under the License.
#------------------------------------------------------------------------------

"""
Wrote this to test that I'm correctly generating the responses for draft76
websockets.
"""

import struct
import hashlib


## From the draft76 docs:

REQUEST1 = (
    'GET /demo HTTP/1.1\r\n'
    'Host: example.com\r\n'
    'Connection: Upgrade\r\n'
    'Sec-WebSocket-Key2: 12998 5 Y3 1  .P00\r\n'
    'Sec-WebSocket-Protocol: sample\r\n'
    'Upgrade: WebSocket\r\n'
    'Sec-WebSocket-Key1: 4 @1  46546xW%0l 1 5\r\n'
    'Origin: http://example.com\r\n'
    '\r\n'
    '^n:ds[4U'
    )

CORRECT_RESPONSE1 = "8jKS'y:G*Co,Wxa-"

REQUEST2 = (
    'GET /demo HTTP/1.1\r\n'
    'Host: example.com\r\n'
    'Connection: Upgrade\r\n'
    'Sec-WebSocket-Key2: 1_ tx7X d  <  nw  334J702) 7]o}` 0\r\n'
    'Sec-WebSocket-Protocol: sample\r\n'
    'Upgrade: WebSocket\r\n'
    'Sec-WebSocket-Key1: 18x 6]8vM;54 *(5:  {   U1]8  z [  8\r\n'
    'Origin: http://example.com\r\n'
    '\r\n'
    'Tm[K T2u'
    )

CORRECT_RESPONSE2 = 'fQJ,fN/4F4!~K~MH'

def parse_request(request):
    req = {}
    segments = request.split('\r\n\r\n', 1)
    assert(len(segments) == 2)
    header, payload = segments
    lines = header.split('\r\n')
    line = lines.pop(0)
    items = line.split('\x20',2)
    assert(len(items) == 3)
    req['method'] = items[0]
    req['request_uri'] = items[1]
    req['http_version'] = items[2]
    for line in lines:
        parts = line.split(':\x20', 1)
        assert(len(parts) == 2)
        req[parts[0].lower()] = parts[1]
    req['payload'] = payload
    return req

def get_word(key):
    digits=''
    spaces=0
    for char in key:
        if char.isdigit():
            digits += char
        elif char == '\x20':
            spaces += 1
    assert(spaces)
    assert(digits)
    keynum = int(digits)
    assert(keynum % spaces == 0)
    wordval = keynum / spaces
    assert(wordval < 2 ** 32)
    return struct.pack("!I", wordval)

def create_token(req):
    key1 = req.get('sec-websocket-key1', None)
    assert(key1 is not None)
    word1 = get_word(key1)
    key2 = req.get('sec-websocket-key2', None)
    assert(key2 is not None)
    word2 = get_word(key2)
    salt = req.get('payload', None)
    assert(salt is not None)
    assert(len(salt)==8)
    return hashlib.md5(word1 + word2 + salt).digest()    

req = parse_request(REQUEST1)
print create_token(req) == CORRECT_RESPONSE1

req = parse_request(REQUEST2)
print create_token(req) == CORRECT_RESPONSE2

Please note that this version is scheduled to be replaced by a draft called Hybi-08 which features a way simpler algorithm (which I *think* I have it nearly ready to drop in).

My interests are clearly taking Netboa towards being a browser-based game server. The combination of HTTP + WebSockets is quite appealing. It's really time to knuckle down and learn some Javascript -- or, more likely, lots of JQuery.

Chrome WebSocket Protocol Update

Just making a note here;

http://blog.chromium.org/2010/06/websocket-protocol-updated.html

HTTP Server

In my previous post, I mentioned the goal of separating protocols from the client object. As an experiment, I started writing a HTTP service using the new code. This would let me run a light web server as a service in conjunction with something like WebSockets on the same, single-threaded server.

You definitely don't want to waste time serving big files in a single threaded application because it blocks but for little things like a login page it could be handy. Plus, I've written web based apps for years but never fully understood what was happening under the hood and here was a chance to find out.

The actual HTTP protocol is pretty simple. It only has eleven commands (or methods); HEAD, GET, POST, PUT, DELETE, TRACE, OPTIONS, CONNECT, and PATCH. Currently, I only support one, GET (which is easily 99.9% of the web). All other methods are responded to with a status code 501 Not Implemented.

Here's my index.html rendered on Chromium:

This actually represents three separate HTTP GET requests; the index.html file, the skull image, and the tiny skull favicon shown on the tab.


The skull is a compressed SVG, to get Chromium to display it I had to add Content-encoding parameter to my HTTP Response;

Netboa

I've started the total re-write of my asynchronous network library Miniboa. The new code, in addition to being cleaner, is different in several ways.

What's New

• No longer Telnet-centric; my aim is to keep connections generic and wrap them in protocol handlers.
• Services; you can now run multiple services under a single server. Each service listens on a different port and can have unique protocols and events.
  
• Added hooks for coroutine-based, character-at-a-time protocol handlers.
• No longer line-based; the new API has get_ch() to get one character or get_input() to retrieve the entire input buffer. This is support users that want to write features like text editors and command completion.
  
• New event; on_input() that is called when the data is received from the client.
• When run under Linux, it uses the Epoll API introduced in Linux kernel 2.5.44. All other platforms user Select().

I kept the server polled from within the user's game loop. I know that event and callback driven designs are more efficient, but I really like the approachability of that pattern. It can be hard to think in terms of callbacks.