Importing Spreadsheet data from Google Docs Sheets to Unity via Google Sheets for Unity Lite and JsonDotNet

No pretty pictures to accompany this one - just a workflow process that is useful, but a little bit painful to get set up the first time.

For several games that I've worked on, it's handy to use a spreadsheet to manage data, and then import that data into the game. Conceivably, you might do that import at runtime, but I get a little twitchy about games that require an internet connection without a compelling gameplay benefit.

So, this process starts with data in a Google Docs Spreadsheet (officially called "Google Sheets", because "Google Docs" is apparently just the word processing component of the Google office suite, which is nuts to me - a word processing document is a document, and a spreadsheet is a document, and a slide deck is a document). I'll be using Google Sheets For Unity Lite, which installs a web service script to serve up your data (password protected), which you pull down into the Unity editor as JSON data. Then, we'll use JsonDotNet to turn that data into C# instances of serializable classes, which you can use immediately. I'll also store a copy of the data in the resources directory, which is where the game will get the data at runtime.

Links

Google Sheets For Unity Lite - there are a few versions of Google Sheets For Unity, but for my purposes, the lite version on the Unity Asset Store suffices. It's a paid product, currently $19.99, for which you get code and good documentation. 

JsonDotNet - a free asset on the Unity Asset Store, I don't have a lot to say about it.

Workflow Video - I got a lot of this knowledge from this video by Sloan Kelly. In the video, he walks you through the basic process I detail here. It's from an earlier version of the GSFU tool, but the overall process is the same.

If all this documentation is so good, why the blog post? Maybe there's not a lot of value to be added, but I find that I can use information better sometimes when there's a two page checklist of a process, as compared to a 45 minute tutorial video. And my process isn't exactly the same as the GSFU documentation. Also, the GSFU documentation is in a PDF, which is fine, but is sometimes not as easy to work with. So, this is intended to supplement stuff that was already useful to me.

Process

1. [Optional] Watch the video linked above. I'm sure there will be details that are covered there that I'll miss
2. [Recommended] Read the GSFU doc. 
3. Go to the Unity Asset Store from within the Unity Editor to purchase and install both GSFUlite and JsonDotNet.
4. Drag the "Drive Connection" prefab from the GSFU/Utils folder into your scene. Verify that the Drive Connection prefab has a linked ConnectionData object, we'll be using it later.
5. Find your spreadsheet ID, which is the alphanumeric string between "/d/" and "/edit" when you look at the URL for your spreadsheet in Google Docs. e.g. if your URL is https://docs.google.com/spreadsheets/d/abc123456/​edit#gid=671966417, your spreadsheet ID is abc123456. It'll likely be a lot longer than that, like maybe a 40 character string. Security!
6. Fill in the spreadsheet ID into the ConnectionData object, above.
7. Create a file in Assets/Scripts/Editor that defines a class that derives off Editor. This class will define functions that are called by the Unity Editor UI. You'll want to have one or more functions annotated with a string like "[MenuItem ("MicroTwenty/Import Monsters from Google Sheets")]" which tells the Unity Editor to create a MicroTwenty menu option in the main menu, one item of which is to Import Monsters. You can add more levels of submenus by adding more slashes to your item name. The function can be named anything you like, but it should be a static void function.
   
8. In your new static void function, register a callback like so: "GoogleSheetsForUnity.Drive.responseCallback += HandleDriveResponse;" and then ask GSFU to request your sheet data like so: "GoogleSheetsForUnity.Drive.GetTable (_monsterTableName, false);". The HandleDriveResponse callback will be a function you write (soon). The _monsterTableName is the name of the specific sheet within your spreadsheet. This might not be case sensitive. 
9. Your HandleDriveReponse function (if you haven't already auto-generated it) will be a static void function that takes a Drive.DataContainer. First, you want to deregister for the callback (seems like a lot of work for each menu action, but that's Unity. "GoogleSheetsForUnity.Drive.responseCallback -= HandleDriveResponse;". Then test that you're getting the expected data back: " if (dataContainer.QueryType == Drive.QueryType.getTable) {
       string rawJSon = dataContainer.payload;
     if (string.Compare (dataContainer.objType, _monsterTableName) == 0) {"
10. At this point, you've got an array of JSON objects, but what you might like is a JSON object that contains an array of JSON objects. So, we wrap the JSON by wrapping the json with "{\"monsters\": " and "}", which gives us JSON that we can deserialize into a C# object.
11. [Optional] We use JsonUtility to deserialize the JSON: "var monsterSheet = JsonUtility.FromJson<MonsterSheet> (wrappedJson);" where MonsterSheet is a C# class we'll write shortly. Perhaps Debug.Log the first monster from the monsterSheet to make sure that things have downloaded and parsed as expected: "Debug.Log ("monster 0 " + monsterSheet.monsters[0].Name);"
12. Save the JSON into the game's resources by making a path: " var path = System.IO.Path.Combine (UnityEngine.Application.dataPath, "Resources/JSON/weapons.json");  " and then writing the wrapped JSON out to that location " System.IO.File.WriteAllText (path, wrappedJSON);  ".
13. Now we need to make the MonsterSheet class, which is a C# object that is a container for monster data. This class should be defined in the main assembly (i.e. not the Editor assembly, where your fetcher script is). It should define a Serializable class MonsterSheet with an array of MonsterRows. We'll call this array "monsters", to match the name we added when wrapping our JSON, above.
14. Now we need to make the MonsterRow class, which is a C# object that is a container for data about a single monster, a single row from our spreadsheet. This should have a public variable for each column in the table. You can use strings, ints, floats, and probably other data fields, too. Make sure this class is Serializable.
15. Now we need to set up the Google Cloud deployment. For this, find the "Deployment/Server Side" section of the GSFU doc. There's a link there to a Google Cloud script. Make a copy of that script (my copy of the docs says that clicking on the link makes a copy, but I don't think that it does). Rename your copy something useful that has no spaces. I don't know why that's an issue, but it apparently is.
16. Go to File / Project Properties to open a properties dialog, and from that dialog, go to the Script Properties tab. You'll get a UI where you can add properties. Add a row with a key "PASSWORD" (no quotes) and a value of a password that you like. I won't look. Keep a copy of the password in a safe place.
17. Go to File / Manage Versions, and "Save New Version".
18. Go to Publish / Deploy as Web App. There will be several steps making sure you want to allow this script to access your data. This is perhaps the scariest part of the whole process, but the script is there for you to look at, you can convince yourself it's not downloading malware, or uploading your personal information. Copy the script URL to a safe place.
19. Back in Unity, in the ConnectionData object, paste in the web service app URL and the password.
20. Create a "Resources/JSON" folder to receive your downloaded JSON objects.
21. At runtime, load the data like this: "             var monsterJSON = Resources.Load<TextAsset> ("JSON/monsters");
                var monsterTable = JsonUtility.FromJson<MonsterSheet> (monsterJSON.text);
    ". Note that Unity will add on the .json extension for you. (Magic!)

Phew. As simple as that. Hopefully, that will supplement the other documentation out there for this process. Enjoy!

MicroTwenty: Using Hex Grid math to select correct orientation of arrow sprites

Left of the white circled unit are 4 pixels that constitute an arrow. That's what we're talking about today.

Longtime readers of this blog may know that I've got a long-term project of making a computer role playing game (CRPG) in my spare time. I've made many many versions of this game already, in various forms, which I liken, in a way, to painters doing "studies" of a work before doing the full project. Call them tech demos, or vertical implementations, or just small versions.

One might hope to put those projects together into one big game, but a) that's not how my projects work b) they're all written in different languages.

My current take on this project is what I'm calling "MicroTwenty" - a small amount of content, but as feature-complete as I can make it. Content always runs away from me, and I love adding in new maps, new monsters, new weapons. So, we'll see how "micro" it is when I walk away from it.

The particular (ha - there's a related block of code called ParticleOrder, but that's not what I'm talking about here) bit of code that I wanted to touch on today was using hex grid "cubical" coordinates to figure out which of six arrow sprites (or three, if you're being lazy and using back-to-front symmetrical arrows) to use when one unit is shooting at another unit.

In a higher-res (read: not retro pixel) graphic style, you could just find the vector from the attacker to the target, and get a quaternion or using arctan to get an angle. And I could do something like that here - I know the target location (in tile space) and I know the shooter's location (also in tile space) - I could totally convert those locations into screen space, find a screen space vector, and do some trig.

There's an easier way, though. If you're familiar with Red Blob Games' Hexagon Grids page, you'll already be comfortable using an integer triple to represent tile coordinates. By subtracting the target coordinates from the shooter's coordinates, you get a vector, again in integer triple space.

I wanted a function that took in a HexCoord (that is, an integer triple), and returned a "Hextor" index; an integer value in the range zero to five indicating the "facing" that the vector was pointing in (starting at East = 0, Northeast = 1, and proceeding counterclockwise, as you'd expect).

My first implementation is this:

        private int CalcHextorForVectorSlow (HexCoord vec)
        {
            List<HexCoord> bases = new List<HexCoord> {
                new HexCoord(1, -1, 0), // East
                new HexCoord(1, 0, -1), // NE
                new HexCoord(0, 1, -1), // NW
                new HexCoord(-1, 1, 0), // West
                new HexCoord(-1, 0, 1), // SW
                new HexCoord(0, -1, 1)  // SE
            };

            int maxDot = -1;
            int bestHextor = -1;
            for (int i = 0; i < 6; ++i) {
                var b = bases [i];
                int dot = vec.x * b.x + vec.y * b.y + vec.z * b.z;

                if ((bestHextor == -1) ||
                    (dot > maxDot)) {
                    maxDot = dot;
                    bestHextor = i;
                }
            }
            return bestHextor;
        }


Which is pretty easy to read - it just does a dot product against each of the six "basis" vectors. If you wanted to change things around to have the facings oriented slightly differently, you could rewrite the bases list, and the logic would remain the same.

I reached out to Amit Patel (the man behind the Red Blob Games site), and asked if there was an easier way. He pointed me to this "directions" page which uses simpler math, though trades heavily on the characteristics of cube coordinates.

My implementation of that looks like this:

        private int CalcHextorForVector (HexCoord vec)
        {
            // from https://www.redblobgames.com/grids/hexagons/directions.html
            // Thanks, Amit!

            var xmy = vec.x - vec.y;
            var ymz = vec.y - vec.z;
            var zmx = vec.z - vec.x;

            var axmy = Math.Abs (xmy);
            var aymz = Math.Abs (ymz);
            var azmx = Math.Abs (zmx);

            if ((axmy > aymz) && (axmy > azmx)) {
                // E or W
                return (xmy > 0) ? 0 : 3;
            } else if (azmx > aymz) {
                // SW or NE
                return (zmx > 0) ? 4 : 1;
            } else {
                // NW or SE
                return (ymz > 0) ? 2 : 5;
            }
        }

It's fewer calculations, but maybe a little harder to understand what's going on when you look at it. I mean, documentation is good, and that's part of why I'm writing this blog post.

So, now I can choose the correct 4-pixel sprite of an arrow in flight to get within plus or minus 30 degrees of the arrow's trajectory. Seems good enough for this game.

Python to Google Sheets to Unity to JSON resource to runtime - nothing but net

I just uploaded a Unity app at http://bigdicegames.com/CWGSparks/index.html that draws this picture:

Which, if you've been following along, and are a little forgiving with my projection, could look like a highway map of the US. It's incomplete, and it's low res - the only vertices are at cities, and I have just shy of 500 cities in my database. Also, I've been manually connecting up cities based on my interest in them, so there's a lot more cities in Texas, Florida, and California, and a lot more highways that will someday be coming in to this picture.

Previous posts have talked about doing pathfinding from city to city, and I've been using Python for that part of the project. To help me visualise what's going on, I use Reportlab to draw PDFs, which sometimes I print out.

This is all intended to be in service of a game. (A computer game? Maybe playable on the web? I also have ideas of a choose-your-own-branching path gamebook, but that doesn't require as much pathfinding.) So, it makes sense to start porting the data into Unity.

In talking to my friends about this project, I talk about having a highway database. That's clearly putting on airs, as really what I have is two Python arrays of tuples. One array is the city array, and each line in the file has a city name and lat/lon coordinates. The other array is the road array, which links up cities by name. Simple as that.

Well, yeah, but a little gross. There's no error checking, and it's super easy to get duplicates in there. Greeley, Colorado was in my "database" twice, with two different spellings. That seems like it's cleaned up now.

Python's great, but it's not the best data repository. I've been kind of itching to move my data to a Google Sheets spreadsheet. This ties in with some desire I have to try to embrace a data-driven, "Entity/Component/System" (ECS) style for a personal project of some size.

Aside: http://bigdicegames.com/ECSteroids/index.html is a small game I made, trying to play around with ECS maybe a year and a half, two years ago. arrow keys steer, CTRL shoots.

So, anyway, I wanted to port my Python-based data to Google Sheets. That's super easy, I just wrote out a CSV file by hand for each of my tables. If I actually had to think about commas inside my data values, I'd probably go so far as to import csv from Python and use a writer provided. But no time for that.

So, I imported my CSV into a Google Sheets, um, sheet. Looks great, all my data is there, and even some fancier stuff, where I generate a unique key for city and roads, as if I was using a real database.

For what it's worth, a lot of those cities were scraped from Wikipedia's article on most populous cities in the US. So that got me started, but I've been adding extra cities to give my roads useful places to turn. The original Wikipedia article had 314 cities, and I've been adding extra places so that now the spreadsheet has 498 lines. Anchorage, Alaska and Honolulu, Hawaii are problematic, but I'll get to that later.

So, the data's in Google's hands now. Fine. I want to be able to use it inside Unity. I poked around a number of similar tools, and ended up using Google Sheets for Unity Lite, which does the job I need right now. There's a non-lite version on itch.io, but it's unclear to me what the value added is.

Watching and rewatching A YouTube video where a guy is using GSFUL to import data, I managed to pull the data out of Google Sheets, and down into JSON data in my app. Cool, so far.

Except I don't really want the users to be hammering Google Sheets to pull data at runtime. I'd much prefer to bundle that data into the app itself.

Unity has several ways to make this sort of thing work, but what I chose to do is that my Google Sheets pull happens as an editor extension, pulling the data as JSON, and then I write it into my Assets/Resources/JSON folder. "Resources" are data that get bundled up inside the app through Unity magic.

A little dead end banging around, trying to read from the Resources folder directly, I ended up using Resources.Load<TextAsset>, like so:

And the JSON is now in a CityArray and RoadArray object, each of which is a simple (if annoying) wrapper around the array of JSON objects for cities and roads. Boom.

At that point, I just used Vectrosity to draw the lines. There was a little bit of math to jam the map onto the screen rectangle, but that's just a bounding box and some scaling. Nothing fancy.

I sort of want to put some virtual cars on the roads driving from state to state. (No papers, Vasili!) That can come later.

Also, maybe a little more Texas, it looks lonely.

I agree with Google Maps on Cannonball Route

As a test of my contraction hierarchy code, and of an expanding database I'm building of US highways, I asked both Google Maps and my code to find a path from New York, NY to Los Angeles, CA. 

Looks like Google recommends going through Indianapolis, to Oklahoma City, then due West.

 My map isn't as extensive as Google Maps, but let's see what it decides to do:

New York, NY -> Indianapolis, IN -> Oklahoma City, OK, and on west to Los Angeles, CA. 

Better than I expected. I'll take it!

Contraction Hierarchies vs A*

You may recognize the above map as a crude highway map covering (parts of) California, Nevada, Utah, Wyoming, and Colorado.

You might even have heard of a project that I've got on my back burner, a branching, choose your own path, adventure book and/or computer game, which I might be calling "Sparks and Rusty" or "Sparks and the Wheelman" or some other goofy pairing that evokes 1980s action road adventures.

In this adventure, you have a semi tractor, and are asked to use it to tow a semi trailer from Mountain View, CA to Colorado Springs, CO. The interesting (hopefully) bit is that the semi trailer houses a supercomputer, on which is running a super-intelligent, sentient AI. That's "Sparks".

So, yeah, get from point A to point B, with your newfound buddy / damsel, across presumably hostile territory.

Also, as this is a Cars With Guns joint, the hostile territory will have lots of violent folks on the highways. Murderous cycle gangs. Folks with machine guns mounted on the hood of their cars. Ambushes. Gorse bushes. Perhaps not the last one.

If you're familiar with the Steve Jackson Games gamebook "Convoy", you're thinking along the right tracks - it's an inspiration, to be sure.

So, you've got a map, and you've got a destination. It should be easy to pathfind to the destination, right?

Well, sure. Let's first of all get out of the way that my map is fairly small - 70 cities, some of which I added, just to make the highways bend in approximately the right places (I'm looking at you, Muddy Gap, WY). So, it's not too hard to exhaustively search that, Dijkstra is actually pretty good for this sort of thing.

Also, let's concede that my city-to-city distance is an approximation, using pythagoras and a mercator projection onto a flat plane. Real highways are wigglier, and this is coming up on big enough to actually care about the curvature of the Earth. All of that can be refined later, if I need to.

So hey, A* (pronounced "ay-star"), that's a thing, too, right? Yep, sure is. Can be faster than Dijkstra, and is fewer characters, though it might be problematic as a filename, or a class name, depending on your OS and your language.

So, I wrote a quick little A* implementation - I've got "AI Engineer" on my resume for a reason, I should be able to knock this out in a page or less of Python, right?

Turns out, sure, something like that. And A* tells me that the way to navigate my map to get from Mountain View to Colorado Springs is:

['Mountain View, CA', 'Pleasanton, CA', 'Walnut Creek, CA', 'Vacaville, CA', 'Sacramento, CA', 'Placerville, CA', 'Reno, NV', 'Ely, NV', 'Cove Fort, UT', 'Green River, UT', 'Grand Junction, CO', 'Rifle, CO', 'Lawson, CO', 'Denver, CO', 'Colorado Springs, CO']

Which is maybe not what I would have chosen, if I was just wandering the highways of the Western US without a map by my side, I might have gone through Reno, staying on I-80 through West Endover, and turn right at Fort Collins, CO, and down to Colorado Springs. But I trust this is shorter. It doesn't take cycle gangs or refuelling into account, which players will need to think about.

Sidebar anecdote: years ago, my father asked me how Google Maps can do continent-scale navigation so quickly. I shrugged and said I didn't have access to the Google Maps source code, but I imagined that if somebody asked Google Maps for turn-by-turn navigation from, let's say Bremerton, WA to Boston, MA, Google Maps would be smart enough to know that you can get from Seattle, WA to Boston, MA, by taking I-90 (pretty much) without turns, and so that's a subproblem that can be "shortcut". Not saying that you're taking a shorter physical path, but not considering all segments of I-90 incrementally; that's thousands of potential exits off the interstate that you might not care about.

And, in fact, you actually can do a little better than saying on I-90, if for no better reason than to detour around Chicago and Minneapolis. At least, that's what Google Maps says right now. So, it has some knowledge of times when the interstate isn't the best answer.

I've taken some online courses to keep my brain full, and one of the AI courses I took had a short section on highway navigation, with a visiting guest from Microsoft/Bing Maps, talking about "Contraction Hierarchies" / Node Labels.

The short version of the "Node Labels" technology is that you store at every location a "label", which I'll just call a "dictionary" of intermediate locations, along with the shortest distance to that intermediate location. The amazing bit is that this dictionary ends up averaging something like the log of the number of points in your map. So, I look up Bremerton, and find a bunch of cities including St Louis, New Orleans, and Chicago. I look up Boston, and find a different bunch of cities, including New Orleans, Memphis, Miami, and Chicago. And so I find the intersection of these dictionaries, and find that I can route from Bremerton to Boston via Chicago in 3096 miles, or Bremerton to New Orleans to Boston in 4250 miles. I'll take Chicago today, thank you.

If you've got these labels preprocessed for a bunch of locations, you can do this midpoint thing very fast.

I'm a little fuzzy on what the Microsoft guy said (if he did) about how you turn this in to navigation - maybe he was just presenting a "distance oracle", which is still something.

Maybe you recursively do this, and find a midpoint between Bremerton and Chicago, and so on and so on. I'd be concerned, though - in my example, Chicago is in my "label" for Bremerton, so there might be edge-case issues going on, where I can't get a good divide-and-conquer solution.

Or, maybe inside your label, you store not only distances, but a path. That's a lot more data.

Or, instead of storing all of this label information, you store some small information in the cities on your map that helps you reconstruct the label quickly. That seems good, especially since I'm not actually in the business of doing server-side computation of this stuff for lots of queries per second.

And it's this small information approach that Contraction Hierarchies uses to give you a solution.

Imagine I assign each city in my map a unique integer index. Could be assigned randomly, could be alphabetical, it doesn't matter at this point how I come up with these indices. Now, in that order, I'm going to start simplifying my map, removing one city at a time, which should make things incrementally simpler. But I still want the remaining map to contain correct information about shortest paths. This is where "shortcuts" come in. Again, shortening the computation work, not shortening the physical, map, distance.

So, let's say I decide that I'm looking at my map, and I decide to simplify it to remove Bozeman, MT.
May map says that I can go from Belgrade, MT to Bozeman, MT, and from Bozeman, MT to Livingston, MT. I would add in a shortcut from Belgrade to Livingston, and add a note on the shortcut saying "also, to take this shortcut, you'll pass through Bozeman". And we do this for each city in our graph, adding shortcuts where the city is required for shortest path calculations to remain correct.

So, we make a new graph, which we'll call G* which has all the original cities and all the original edges, but also these new shortcuts. Depending on the connectedness of your graph, a lot of cities can go away and not have any shortcuts at all.

The neat trick at this point is to navigate G* by only going "up" in indices, including using our new shortcuts. So, for a known good path from Bremerton to Boston, we will have contracted the various cities along the way in some order, which you can visualize as a jagged mountain range - each contraction yields a shortcut, allowing us to "fill in" a little valley between neighboring points (that are later in the contraction order, so therefore are "higher" on our mountain visualization). So, the points late in the contraction order become "hubs" that traffic want to go through.

So, we figure out these best hubs, reachable from our start location and our destination location, each going up. In the Bremerton and Boston example, we can imagine that Chicago is a good hub (O'Hare is maybe not a great experience for air travellers, but as a highway crossroads, it's useful), contracted late in the preprocessing, and so "up" from both Bremerton and Boston.

And the path to get from Bremerton to Chicago has a few shortcuts along the way, probably including when we contracted Bozeman, so when we come to unroll our directions, we replace shortcuts with paths through their contracted cities.

And that's just about it.

So, I wrote a Contraction Hierarchy solution for my game map (Mountain View to Colorado Springs, if you recall). I put in Mountain View, and asked it where I could get to going "up" my graph, and it said:

St. George, UT
Walnut Creek, CA
Bakersfield, CA
Modesto, CA
Salinas, CA
Vacaville, CA
Paso Robles, CA
Fort Collins, CO
Mountain View, CA
Reno, NV
Pleasanton, CA
Tonopah, NV

I asked it where I could get to by going "up" from Colorado Springs, and the list was:
Denver, CO
Cove Fort, UT
Pueblo, CO
Colorado Springs, CO
Walsenburg, CO
Rock Springs, WY
Salt Lake City, UT
Fort Collins, CO
Reno, NV
St. George, UT
Tonopah, NV

For each of these destinations, I got the city, a real highway distance, and a path with shortcuts to get to that city.

So, I found the places I could get to from my start and from my destination, which narrowed things down to:

(1092.933032328154, 'Reno, NV')
(1187.1179961380471, 'St. George, UT')
(1329.8134461278964, 'Fort Collins, CO')
(1570.1329202911515, 'Tonopah, NV')

That's the cities along with their combined distance (start to city to destination), so it looks like our travellers are going through Reno. My two graph searches give me shortcutted paths, which combine to look like:

['Mountain View, CA', 'Pleasanton, CA', 'Walnut Creek, CA', 'Vacaville, CA', 'Reno, NV', 'Cove Fort, UT', 'Denver, CO', 'Colorado Springs, CO']

which seems about right, though Vacaville to Denver is a pretty short distance on the page, and a pretty big chunk of our travel distance. That's the shortcuts, so let's unwrap those:

['Mountain View, CA', 'Pleasanton, CA', 'Walnut Creek, CA', 'Vacaville, CA', 'Sacramento, CA', 'Placerville, CA', 'Reno, NV', 'Ely, NV', 'Cove Fort, UT', 'Green River, UT', 'Grand Junction, CO', 'Rifle, CO', 'Lawson, CO', 'Denver, CO', 'Colorado Springs, CO']

Which is the same solution that we got from A*. This is reassuring. If they were different, I'd go back and try to figure out what's going on. I can imagine that if we were trying to find shortest paths across Manhattan, there might be many routes with similar (map) distances, and in that case, maybe A* and CH would give different answers. One thing about A* is that there's a heuristic function that is used to prioritize expanding paths based on expected distance remaining, and if I got that wrong, I could see A* giving a slightly wrong answer.

But they're the same, and they're both lightning fast on my map of 70 cities. I would expect that if I had a lot bigger of a map, I might start caring, but for my game, it probably doesn't matter.

One thing that might make me go for A* in my game is that my map might be dynamic enough that I won't want to redo the processing - let's say our heroes hear that a bridge is out, and the road from Reno to Rachel, NV is blocked. (Or, maybe there's some other reason why the U. S. Army is rerouting traffic around Rachel?) In that case, using A* on the (dynamic) map data might be more convenient.

Spoiler: it's probably aliens at Area 51. Maybe some got out, maybe the army is bringing new ones in, maybe there's a shipment of alien materials that overturned. I've calculated a path from Rachel, NV, to Devil's Tower, WY, just in case.


This stuff isn't super hard, but it does take a little work to get right. I watched (and re-watched, and read and reread the slides from) a German AI course on navigation:

http://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012

Particularly, lectures 6 and 7.


So, Dad, if I wanted to go from Bremerton to Boston, or vice versa, I'd use shortcuts.

On making a book, when one isn't really the author - the process behind "Shapeshifting"

Over the summer of 2019, I put together a book, using OpenAI's GPT-2 algorithm, as running on http://talktotransformer.com . It's currently available in physical and electronic formats, and literally dozens of copies have been printed, and over a hundred copies have been downloaded. These are not terrific numbers (yet), but just getting the book onto Amazon is an accomplishment.

This post talks about much of the process in making this book, including many of the pain points that I would try to avoid if I did something similar again.

The Influences

I've been trying to go back and identify what pieces other people's AI projects banged together in my head to spark this process. Janelle Shane's "AI Weirdness" blog was certainly one piece; she posts an experiment each week, ranging from naming ice cream flavors to Dungeons and Dragons spells. So that feels like it probably set my mind in motion.

I also read about "Prismatic Corpse", a rewrite of D&D crowdsourced from group memory. I signed up to be a part of that game jam, but didn't get around to submitting anything - probably because I decided I was too deep in working on the book by the submission deadline. Also, I was concerned that the participants might be offended at my use of AI in their presumably human project.

Around the same time, I read "Maze Rats", a print-and-play RPG that's super light, with a lot of mileage from a couple of 2d6 table lookups.

Also, years ago, I read some of John Hodgman's books, including one with hundreds of hobo names. Cumulatively, this stuff's a riot.

I've also had a long-term project simmering on the back burner, to make a computer role-playing game, and that's a somewhat terrifying project, involving many moving parts, and lots of different dimensions of creativity.

The Book

What I ended up delivering, and this feels out of order, but it helps to understand where I ended up, which was roughly where I was aiming. With this in mind, a lot of the rest of the process makes a little more sense (and I'll take whatever sense anybody can find).

The final book is over 100 pages, with a cover that evokes mid-1970s role playing games, and internal content looking like early 1980s rulebooks. I cut my RPG teeth on J. Eric Holmes' Basic Dungeons and Dragons (the edition with a monochrome blue cover), which was a step up from the "little brown books", themselves a rewrite of Gygax and Arneson's home rules.

In my experience, each of these are pretty spindly skeletons, evoking what role playing could be, rather than prescribing how you had to play the game. The players (including the dungeon master) had to contribute a great deal to make the experience work.

I find myself describing Shapeshifting as somewhere between a parody and an homage, something not really a rules system, but more than just an accessory or players aide. It's probably correctly placed in some gray area between each of these points.

There are descriptions of attributes, including strength, dexterity, and luck - but no real rules on what those attributes do in gameplay. There's no discussion of whether you roll 3d6 six times in order, or if you do some sort of point-buy system. Somehow, attributes are important, though.

Also, there's discussion of different races, from Humans to Elves to Dwarven to Half-Elk to Half-Halflings. No stat modifiers, just flavor text. Usually, when I encounter flavor text in a game, it's the stuff that I ignore, but with Shapeshifting, it's 100% of the book.

Well, not quite 100%. There's a few tables (hat tip to Maze Rats) for weapons, armor, monsters, and magic items. If you get nothing else out of the book, maybe a big table of over 1000 monsters is useful to you. Granted, a lot of the monsters are weird, so be prepared for the tone not to match your existing campaign. (If my monsters fit into your campaign, write me and let me know, I'm very interested.)

In order to make my tables line up on clean page boundaries, I got a bunch of stock art (some free, some paid for) and used it to shim the otherwise ragged ends of my pages.

The Technology 

Most of the technology required for generating the text came in the form of OpenAI's GPT-2 text generation engine. This is a neural net that was trained on a corpus of text found on the Internet, found by following links from any post on Reddit with three or more upvotes.

The text generation software is what's called a "Transformer" (not the Cybertronian robots), and I don't entirely understand how it works. But you don't have to! Adam King posted an implementation of the algorithm at talktotransformer.com that allows a user to prompt the AI with a sentence, a list, or even just a sentence fragment, and the AI will continue the text from where the prompt leaves off.

So, I entered an awful lot of half sentences that I figured would belong in a RPG book, like "Elves are a race that..." and "When a player has initiative...", and the AI would give me a couple paragraphs at a time of text more or less on-topic. Mostly not on-topic, so I'd try again. The stuff that seemed usable would go into a big text file, and I'd keep going. In time, I had enough for a few chapters, and I'd focus on another part of what I needed for my book.

For the big lists (again, thanks to Janelle Shane), it turns out that GPT-2 loves making lists. So, I'd give it a list like:
1) sword
2) dagger
3) mace
and the AI would proceed to give me a long list of weapons, complete with numbers. The ordered list tag was one of the first things I learned when learning HTML, and it's strongly represented in GPT-2's training data, it would seem.

I would categorize stuff that worked - sometimes I'd get armor in with my weapons, or magic items in with my monsters, but collating and curating was easy, if a little numbing.

I proceeded to organize my lists to try to help the de-duplication process, as well as giving players a little opportunity to fudge the rolls, or roll on a convenient neighborhood (rolling 2d6 around the shark section of monsters, maybe).

The Formatting

Having most of the text, most of the lists, I opened up Scribus, an open-source desktop publisher, and proceeded to dive in to doing layout. I briefly considered using Python tools to generate a PDF by hand, but I decided that I wanted more variability and uneven layout, which Scribus afforded me. Here, I was aided by some documents by Sine Nomine Publishing that talked about how TSR's layout changed over time. Turns out, there was a lot of variability, so I felt free to take inspiration, rather than follow a strict set of layout rules.

Scribus makes it easy to create layouts of page layouts to reuse (heading here, page number there, column A, column B), which went a long way to making stuff flow together with a minimal level of cohesion and professional layout.

One of the tricky bits that I wanted to get right was to have inline dice images on all my dice tables. I was prepared to use my copious drawing skills to generate dice images, but I couldn't figure out a way to get Scribus to flow an inline image as part of paragraph text. (If you've ever written tutorial text for a console game, and are required to embed an icon of the XBox "X" button, you'll know what I'm talking about.)

I never figured out embedded images, but what I did find was a font with dice, so all I needed to do was to dump my table content into a text file, run a python script on it to turn it into a CSV with the die roll "index" in the first column, and the rest in the next column - except I didn't end up using commas to separate the values, because I had some phrases with commas inside them. I think I ended up using tab delimiters.

I then wrote a Python plugin script to import my CSV (TSV?) in, line-by-line, switching to the dice font as needed, and then back to the body text font. This took a few seconds to run for the longer tables, but was basically painless.

The Last Bits

I knew I also wanted to have a sample adventure, which included a right-angles corridors and rooms level, and a caves and caverns level.

For the corridors-and-rooms level, I wrote a Python script inspired by a lot of "Wave Function Collapse" samples that I've seen around, which honestly, I find a little annoying, because I was doing this sort of stuff decades ago, calling it "constraint propagation". The fancy bit that WFC has going for it is that, if you do it right, you can give it something that looks like your desired output, and it magically extrapolates that single input into infinite outputs. Sort of. It works better if your input is easy to parse into tiles, and then it's able to identify duplicated tiles, which lets it infer the relative frequencies of which tiles can go next to which tiles.

I tried a few existing implementations, and didn't get anywhere, so I wrote my own constraint propagation implementation from scratch, using a set of hand-drawn tiles in a little grid journal I happened to have with me when I was waiting for my car to get serviced.

Boom, instant dungeon crawl. Except that I had Escher-like stairway loops that bothered me. I proceeded to add more information to tiles, including that this stairway tile had an entrance that might come in on level <x>, and then the other side of the tile might exit on level <x+1>. Which was more or less fine, but the constraints were a lot tighter than most WFC samples, so I'd get trapped in inconsistencies, and the system would recognize a dead end and give up.

I tried adding in backtracking, but that wasn't going well, either. I used up lots of memory and lots of time, and still wasn't getting good results.

So, I just threw away all the stairway tiles. I sort of miss them, but not enough to go back to rewrite my dungeon generator right now.

After getting the dungeon generator working, I wrote a super simple generator that made ragged shapes that I assert are caverns, and then the generator connected them with jagged shapes that I tell you are cave passageways. After the long fight with getting the corridors-and-room level working nicely, this went super quick. Or, maybe, my standards had been lowered. But it looked like a lot of what I've seen as one page dungeons. So, in it went.

The Publishing

At this point, I had a PDF (really a couple different PDFs, one that had the whole book, including front and back covers, and fancy maps on the inside covers, one PDF with just the outside cover art, one PDF of just the inside) and I was ready to start uploading to places to get them into the hands of people.

I uploaded to DriveThruRPG, an obvious place for a person with an RPG PDF that they want to get into the hands of people who might want to read it. This was right around the time of GenCon, and they said "hey, we'll review your submission, but c'mon, it's GenCon", which was totally fair. I marked it as "pay what you want", with a suggested $5 price tag.

And then I turned my attention to Amazon. I pushed my PDF(s) up to them, going through their multi-page submission web wizard process. Seems like I got pulled backwards and re-entered information more than once. It's Amazon, they aren't in the job of making good web UX, right?

And, I got to the end of the flow, and got a button to request my submission be reviewed. So, bam, sent it off.

And while I waited for those things, I thought about maybe also doing a Kindle eBook. Turns out, you can upload a PDF which they'll turn into a Kindle eBook, but they prefer you upload a proprietary Kindle formatted version, to take advantage of the Kindle platform's features. Which makes sense, just feels a little up-sell-y.

Oh, and to author the Kindle formatted version, you have to use their desktop software. Maybe there could be a web version of it? But it's Amazon, they aren't in the job of making good web development tools. So, I downloaded the Windows version of the software. Onto my Linux machine. I didn't really expect it to work. Also, it did not work. So, I dusted off an underpowered, overused Mac laptop, and downloaded their Kindle authoring tool for that. And cut and pasted the text in, bit by bit. The pictures mostly didn't survive, but most of the pictures were there to make the page layout fit well, so in a land of auto-flowing text, I let go my responsibility for worrying about page breaks.

I did keep my two dungeon maps - they were more important to the content (in as much as anything really is important). I did a pass to add in keyword linking, because it's a Kindle feature.

And I uploaded that version. And, perhaps not entirely surprisingly, it was the Kindle eBook that got approved and available for downloading first. A Friday in early August, if my memory serves me, which I don't actually trust. And not too long after, the Drive Thru RPG download went live. The paperback version went live, long enough for me to order a copy, and then it went to "ON HOLD", with a little message "to find out why your book is on hold, contact us", with a link going to a big page of FAQs about the publishing process, but not any super obvious discussion of what would make a book be put on hold.

I figured some flag got tripped somewhere in the process, perhaps having to do with DPI settings or margins. I found some means of contacting the customer service team, and asked them "hey, the UI told me to contact you, what's up?", and the customer service team said "oh, hm, we'll have to check with the tech team. We'll get back to you in like three days?". So, sure. I sat and waited, and got a response from the customer service team, relaying a message from the tech team saying "we can't print the book until he replaces the Quentin Caps font". Which, all right, I get that fonts can be tricky. No discussion about what was tricky about this particular font. Maybe it was a bad format, maybe my use of it wasn't clearly within the rights of my license, so I found a similar font, paid a somewhat reasonable amount for that font, and re-submitted. And waited. And after several days, I reached out again, asking why my book was still on hold. And again, customer service had to contact the tech team to find out why the book was stuck. And again, it was a font issue. This time, my new font. Still no indication about what the issue is, or how to fix it. No guidance on what to do other than to replace the font.

So, and if you've read this far, which presumably you have, or maybe you're skimming, because it's been a lot of words up to this point, maybe this is the one takeaway that is of use. When you're working with a print on demand service, and you give them a PDF, you can embed fonts in the PDF, or you can convert fonts into outlines. Or, and this is the grossest option, you can take the fonts into let's say Photoshop, make an image (maybe a PNG) of the text, save that out, pull it in to your desktop publishing app, and paste the image in place of the text using the problematic font.

This is bad because it increases your filesize. It's bad because the layout is all kinds of sloppy. It's bad because it's caving in to a workflow that flags problems without offering solutions.

But it worked. My book is (currently) in print. You can buy paperback or two different formats of electronic versions. Or all three. You can send copies to your favorite game master for the holidays.

I'm tempted to make a Kickstarter option for the boxed set. I haven't fully imagined what it would entail. A box, certainly. More art? Better art? A bigger adventure. Better rules? Little cardboard standee figurines? Dice? Seems like at a minimum, a project this random needs some dice.

People ask me if I've played the game, and I laugh at them. This isn't a game for playing, this is a book to laugh at. Or, if you do play it, let me know. I'd be delighted to hear.

Taking off the "editor" hat, putting on the "publisher" hat

It's not like my projects really have well-defined role boundaries; I take on projects where I get to / have to do a lot of different things. For this book, I did a small amount of writing, more editing, some art direction, page layout, and now I'm shifting in to the boring tail end of finishing up a project.

I don't mind the tedious tasks at the end of this project very much, because it marks an actual finish line, actually completing a thing, which I'm not very good at. I start a lot of things, and I get distracted, hey! Let's ride bikes!

I uploaded some version of the "release candidate" PDF to Drive Thru RPG last night, some version to Amazon this morning, a slightly different version of the PDF to FedEx/Kinko's last night, and now, to reference Alton Brown, I just walk away. This book is like scrambled eggs. Just walk away. Let it firm up, let it rest, let the heat even out so that the center is done.

Drive Thru RPG says that it'll take a while to validate my upload, and I imagine this week is worse than normal, because GenCon is right around this time.

Amazon says it may take 72 hours to do their verification, which takes me into the weekend. Maybe into next week, depending on how those 72 hours fall.

It feels good to be powerless, in a really weird way; again, this is the finish line of this project. Just walk away.


Oh, also, shout out to Danielle at the Woodinville, Washington FedEx/Kinko's for making sure that my "release candidate" draft looks the way I wanted it. It's not important, but I'm glad to have a one-off edition that I'm proud of.