Genuary 2021 Day 13 (early): "Do Not Repeat"

 

Euler's Cistercian Logarithmic Spiral (First 4800 decimal digits)

I did this one early, as I'm going to be busy tomorrow. I found a reference for digits of Euler's constant, 2.71828459045... that's as far as I know, which is more than I ever really need to know, of course. As e is an irrational number, I claim that it goes on forever without repeating. Like pi, or a bunch of those other irrational numbers. Phi. Square root of two.

To make things more interesting, I implemented a Cistercian number glyph renderer  based on what I read here: https://en.wikipedia.org/wiki/Cistercian_numerals - the Cistercian monks in the thirteenth century had a way of encoding 4 digit numbers (0 to 9999, though I'm not sure if they actually used 0). I took quads of digits from my stream of decimal digits of e and turned them into Cistercian numerals - the first glyph can be decoded as being 2718, and then the next glyph is 2845, and then 9045. After that, I gave up checking.

100 digits around the spiral, and we've got back to the top again, but at a smaller radius, and drawing our numerals just a little smaller. I did some math, where I knew I wanted each full loop to become a certain fraction smaller (around 5%, I forget what the final value was), so each loop of 100 digits, I'd have scaled by a factor of 0.95 - so the incremental scale factor from one digit to the next was 0.95 ^ (0.01). All that exponential math makes me feel like Euler might have been proud.

There are 12 loops here of 100 Cistercian digits each, so that's 4800 decimal digits of e. If you look long enough, you'll find any series of digits (your ZIP code, your PIN, your SSN) in irrational numbers like this. Because the Cistercian digits hold 1000x more information per digit compared to our decimal digits, it's going to take you 1000 times longer to find a series of digits of a given length.

The digits don't repeat, and they don't even come around very often.

Tools Used: DrawSVG, e

Languages Used: Python3

Development Time: ~1.5 hours

Drawing Time: ~45 minutes

What's Generative Here: The glyphs here represent the digits of e, which gives me an unending series of data.

Genuary 2021 Day 12 "Use an API" revisited

The nice thing with an API is that you can maybe hit the servers again and re-fetch the data. I had been caching the data locally, to not waste WSDOT's bandwidth or CPU. Maybe I had hit some sort of limit, maybe I downloaded some garbage, maybe I processed something badly, but this is the corrected version of today's creation. The Edmonds/Kingston ferry route were lines 4 and 5, and for some reason, they didn't show up in this morning's data. So I deleted my cached route data, refetched, and redrew.

Genuary 2021 Day 12: "Use an API"

 

The prompt says "Use an API (e.g. the weather)". I could have cheesed this one by claiming that my use of any of the APIs to my libraries (e.g. drawSVG, Pillow) counted.

Instead, I used the Washington State Department of Transportation (WSDOT) Ferry Schedule REST API, which I feel was closer in line to what the intent of the prompt was.

I fetched the ferry routes, decoded the sailing times for 19 different ferry terminals. In some cases, I had both departure and arrival times, other times, I just had the departure time, so I assumed the crossing time was 30 minutes.

I manually sorted the cities to make things make the most sense (to me) - Bainbridge Island / Seattle / Bremerton are the first three lines, then Edmonds/Kingston. For some reason, I have no sailing data for today for Edmonds/Kingston. I know there was a logging truck that spilled some logs a few days ago:

https://www.seattletimes.com/seattle-news/transportation/log-spill-blocks-edmonds-ferry-dock-monday-afternoon/

This feels more like an infographic, or just a "graph" than a piece of art, though the shapes for the San Juan Island ferries (bottom of the image) are pretty nuts.

Tools Used: DrawSVG, WSDOT REST API

Languages Used: Python3

Development Time: ~2 hours

Drawing Time: ~6 minutes

What's Generative Here: I pulled the sailing data and used that to generate lines in time between departure port and arrival port. Feels not very generative.

Genuary 2021 Day 11: "Other Source"

 

The prompt for this one kind of puzzled me. It reads:

Use something other than a computer as an autonomous process (or use a non-computer random source).

I guess there are a lot of ways to do generative art without using a computer as the autonomous process - like building a mechanical automaton that generates art - for instance, those mechanical drawing devices: https://en.wikipedia.org/wiki/Maillardet%27s_automaton

And a non-computer random source, well, that's shading into tomorrow's prompt, but it was easier for me to tackle. I downloaded "A Million Random Digits with 100,000 Normal Deviates" and used that as my number stream.  I also grabbed a million digits of pi, as a secondary number stream.

My generator takes a number of digits in x and y to draw, and draws them in a hand-drawn 4x4 pixel font that I made this morning. Many of the digits are legible, and if you squint and know you're looking at a digit, you can guess what the others are.

The more interesting, maybe, thing, is the background, which is a noise function that smoothly interpolates the colors, based on taking a 6 digit value starting at that point, interpreting those six digits as 00-99 in R,G,B. So, the first 7 digits are 1009732 - so the color for the top left of the first digit is (10, 09, 73) and the color of the top left of the second digit is (00, 97, 32), and so on, shifting in new digits as you go across the page.

10x10 random digits

10x10 digits of pi

20x20 random digits

20x20 digits of pi

100x100 random digits

100x100 digits of pi

256x256 random digits

256x256 digits of pi

I intended to do 1000x1000 for a million digits of both the "million random digits" data source and pi, but I'm hitting an exception, maybe an off by one error for one of the data sources. I could look into that, but already, the 256x256 images are pretty smeary and hard to look at.

Tools Used: Pillow (the Python image library, forked off of PIL)

Languages Used: Python

Development Time: ~2 hours

Drawing Time: ~1 minute

What's Generative Here: I use the digits of a digit stream to create a noisy color field, which I evaluate for each point of the background, and I render the literal digits as the foreground.

Genuary 2021 Day 10: "Tree"

 

Trees! Who doesn't love trees! So many fractally things to do with trees. Like L-systems! Or fractals that look kind of like trees!

I decided to explore an algorithm I wasn't super familiar with, and whose output I didn't entirely like, and whose name I didn't entirely like. I chose the "Space Colonization" algorithm, which I saw on Coding Train: https://youtu.be/kKT0v3qhIQY

The basic idea is that you generate a pattern of "attractors" (referred to as "leaves" in the Coding Train video, but that's an error), and you grow your network of branches in the direction of the attractors. Each attractor exerts a "pull" on its closest tree branch node, and nodes with more than zero pulls branch off a new branch in the direction of the net pull. Add in some thresholds so that attractors shut off when a tree branch gets close enough, and you've got a pretty straightforward algorithm.

And, indeed, I got something working right away, but it wasn't fast enough for me. So I added quadtrees - which I realized, after I had them implemented and debugged, were more TREES. So, that's even better. There's a LOT of "find the closest <x> to the position of each <y>" going on in this algorithm, so having a spatial data structure to accelerate that made sense.

Giddy off of using spatial distance functions, I added SDFs to my quadtree implementation. There were two big queries that I did into my quadtrees:

• the closest object to this point
• all objects within <r> distance from this point

I was able to use the best distance so far along with the SDF of bounds of child quadtree nodes to quickly prune entire subtrees, and get a lot better performance - if the closest distance I had found so far was 100 units, and the closest point on the bounding box of a later subtree node was 120 units away, I'd know right away that I didn't have to look at any of the points in that subtree. Nice.

So, I got the quadtrees working - mostly? Seems like there were maybe a couple attractors that never got visited. Which I hacked around at first by just adding a count of how many attractors remained, and when that plateaued, I'd stop. Which was OK.

I added in a fancy flourish by adding a projection matrix so I could draw a shadow of the tree, too. Pretty.

And that was reasonably satisfying, until I went to draw it on the AxiDraw. I was getting a lot of tiny little branches, and the pen was jumping all around the tree. I had a bit of logic that would go from the end of a branch up to the root, but only draw branches that hadn't been drawn yet, so that eliminated overdraw at the root, and it gave the pen some longer paths when they were available, but I was starting from the ends of branches going in chronological order of when they had grown, not by any spatial ordering.

Spatial ordering? Aha! I've got a quadtree that I can use to order my branches, which helped keep the pen in one area better than before.

I also added in another hack where a branch could only have a bounded number of children. I picked 6, and the filesize of the generated SVG dropped from 1.2M down to something like 340k, which is a lot better.

I had spent ~35 minutes drawing the first version, before I grew frustrated with the crazy pen movements. The shadow wasn't complete after that time. After the above improvements, I  was able to draw the shadow and the tree in ~11 minutes.

There's still bugs in it - a lot of the circles seem to be drawn 6 times, indicating to me that something's wrong with marking the attractors as being visited. Is there a problem with my quadtree? I suspect probably, yes.

So. An algorithm I'm not a huge fan of, with perhaps the heaviest data structure I've used so far,  for results that are OK, and technical debt besides, if I want to reuse this quadtree class. ::ThumbsUp::

I'd kind of like to get this sorted out and use it to render 3d trees. But I'd need to have a good solid spatial structure for my ray marcher, because it's slow, too.

Tools Used: Pentel pen, printer paper, AxiDraw Mini

Languages Used: Python

Development Time: ~5 hours? I did a chunk in the morning, and then another chunk in the afternoon. It was basically working before I added in the quadtrees, which, I'm sure, doubled the development time.

Drawing Time: ~11 minutes on the plotter (with the v2 optimizations described above), ~2 minutes to generate the SVG.

What's Generative Here: The attractor nodes are randomly placed inside an ellipse of my choosing. The attractor nodes indirectly control the growth of the branches.

This is the abandoned v1 drawing - note a lot of super fine branches.

V2 - shadow drawn, tree in process.

Tree, Shadow against blue background. The shadow might make you want to believe it's 3d, but it's really a 2d shape drawn twice, with a projection to make it look like a shadow.

Genuary 2021 Day 9: "Interference Patterns"

 

One of the first two places my brain went when I was considering "Interference Patterns" was the double slit photon experiment, and the simpler version of that that we did in high school physics (shout out to Mr. Pearson, my physics teacher, and Troy and Becky, my lab partners).  The simpler version was done in a shallow basin of water, with two periodic ripple generators. It's pretty much what's explained here: https://www.physicsclassroom.com/class/light/Lesson-1/Two-Point-Source-Interference

The other thought I had was some sort of Moiré pattern: https://en.wikipedia.org/wiki/Moir%C3%A9_pattern

So, I made two drawable objects, one which made an expanding ripple pattern, and one which made a rotating starburst of rays. I made two of each, and put all of the drawables on their own lissajous curves (which feels sort of interference-y in a different way; complex motion from two sine waves not in sync).

I drew a bunch of frames of this, which I made an animated GIF of, and the above YouTube video, and I also drew one frame out on my AxiDraw. I don't know how easily consumed each is - I like to think that the best version of this is the animated GIF, but the others are probably more accessible.

Genuary 2021 Day 5: "Code Golf"

The full prompt text is:

Do some code golf! How little code can you write to make something interesting? Share the sketch and its code together if you can.

I pushed myself to make something small, but without taking a lot of time to make it smaller than my first working version. I started with a version that just printed a string to the console:

which outputs this:

                  🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲🌲  🏌             ⛳                                  🌳🌳🌳🌳🌳🌳🌳           🌴🌴

(depending on how good your Unicode support is)

I then extended that to output a PNG:

Which takes the previous code's output and renders it to a PNG using PIL and a Unicode font. Not minimal, but relatively tight.

Tools Used: um, Unicode?

Languages Used: Python3

Development Time: ~90 minutes

What's Generative Here: I place 3 different forests of size and position specified by a random number generator. I then place the golfer and hole at random places.

 

Genuary 2021 Day 4: Small Areas of Symmetry

 

600 small spiders, each with left/right symmetry of the pose of their legs.

I've wanted to draw something based on a spiral on my AxiDraw for a bit, so here we are. 

For each spider, I generate a list of four numbers [-1, 1] that describe how "forward" one leg is. I then use that for both left and right legs to draw lines for the legs. I was thinking that I'd randomly let some spiders be L/R symmetric, others be rotationally symmetric, but the rotation code didn't work the first time, so rather than debug it, I just fell back to L/R symmetry.

The spiral is a simple archimedean spiral: r = k * theta, but I'm trying to take steps of roughly uniform distance along that spiral, so my step in theta is based on figuring out the radius of a circle going through the current point, and dividing a target step distance by that. This math was hard for Monday morning brain.

I started drawing this on the AxiDraw Mini, and estimated that each spider took around 4 seconds to draw, which didn't feel like a lot, but there are a lot of spiders, so I added a counter to my spider drawing loop, which counted 600 spiders exactly, which is unexpected.

I've been drawing on normal printer paper, folded over four ways to fit on my AxiDraw Mini, which sometimes led to the paper bowing upward during the print. This time, I ripped the paper down to 4.25" x 5.5", which reduced bowing. I think the better solution will be to get some drawing paper, which will have a more interesting texture and a little more thickness. 

I should also try to draw to a smaller region; this image is 15cm x 10cm as generated, but my AxiDraw Mini drew off the edge of the paper, bumped into the binder clips, and drew off the edge of the board. So, maybe 12cm x 10cm next time. 

Tools Used: AxiDraw Mini, InkScape, DrawSVG

Languages Used: Python3

Development Time: ~60 minutes

Plotting Time: ~60 minutes

What's Generative Here: for each spider, for each leg, that leg's pose is generated using a random number generator

Genuary 2021 Day 3: "Make Something Human"

 

Maybe I'll call this "84 Little Computer Friends"

I was kind of dreading this prompt, as humans are complex and difficult to draw. So, with thanks to Randall Munroe and Rich Burlew, I set out to draw a bunch of simple humans. I've got an idea for a picture I want to render someday of a hundred, a thousand superheroes, all just standing around. This is not that picture. Or maybe it is. Well, no. 

I used the Python drawSvg library to draw this image as a SVG,  and then I used the AxiDraw to draw the SVG from within InkScape. The pen-and-ink version lost the racial diversity in the original image, which might be a theme. If you want.

Each stick figure has their own proportions, based around an average stick figure that I drew on some graph paper.

Tools Used: AxiDraw Mini, InkScape, DrawSVG

Languages Used: Python3 (SVG?)

Development Time: ~90 minutes

What's Generative Here: each stick figure's proportions, pose, and skin tone are generated using a random number generator

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.

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 the sad state of inline images

In part, this post is a gratuitous effort to add juice to my "Shapeshifting RPG" project, which you can find at the Shapeshifting RPG website or at the Shapeshifting RPG GitHub repo. I really want to get that "done" in the next few weeks, which includes "writing" a few more chapters, a bunch of layout, and some iteration with DriveThruRPG to get it purchasable by the end of the summer.

If you're not familiar with the Shapeshifting RPG project, allow me to explain. I'm a big fan of computer-generated art, whether that's Harold Cohen's AARON project, or computer music, or even computer-written books.

OpenAI recently released a computer language model "GPT-2", trained on a big chunk of Internet text, which does a surprisingly solid job of generating prose passing for human-written. It still seems a little weird, but it does a subjectively better job of passing the Turing Test than, say, Weizenbaum's ELIZA.

To make it easier to interact with GPT-2, Adam King hosted a webpage https://talktotransformer.com/
which allows you to use pre-generated prompts or your own text and get a couple paragraphs of generated text.

Also, about this same time, the "Prismatic Corpse" game jam project drifted across my consciousness - people getting together to make an old-school RPG without working "together".

The ingredients were mise en placed, the table was set, it seemed like the only thing I could possibly do was to create my own RPG ruleset.

And so, for the past couple months, I've been prompting the TalkToTransformer AI with various bits of RPG rules, and it's been giving me big boluses of vaguely readable text, which I proceed to edit into chapters.

Where the AI totally wins is in generating lists of things. Hat tip to Janelle Shane, whose https://aiweirdness.com/ blog can consistently make me laugh out loud, with AI generated lists of things that begin on the weird side of plausible, and quickly descend into crazy-wrong space. So, I asked GPT-2 to make lists of monsters, and weapons, and armor, and NPCs. It loves lists. And a RPG rulebook is often a lot of pages of tables. Which are like lists.

To make my book borderline "useful", I decided to index my list of monsters, each with a 4-digit number from one to six. This gives you an easy way to roll up a foe to fight against, if you wanted to. Just roll 4d6, and look on the table for that die roll. So, all I had to do was to put a picture of four 6-sided dice in front of each element in my monster table.

I'm using Scribus to do the layout of my book, which is mostly doing what I need it to - it's WYSIWYG layout, without being a word processor, which is fine. It's even got the ability to run Python scripts, so you know I like that. I poked around a lot with trying to put an image inline into a bit of text, but it seems like Scribus prefers to have images exist outside of text flows, which is great if you want your paragraph text to flow around an image like this:

To be clear, I don't think that's how I want my text to flow, but it's super cool that Scribus makes it easy to do that. (And, somewhat amusingly, I had a hard time getting the image of the text flow to get placed where I want it in Blogger's layout. Layout is hard. Layout of images relative to text is doubly hard.)

What I ended up doing, which feels like failure, but it gets the job done, is to find a font that has the numbers 1-6 as the faces of dice, and then I add that to my list of monsters, like so:

It turns out, it wasn't completely that easy - what I ended up doing was writing one Python script to walk over a monsters.txt file that I had prepared, doing some light sanity checking and cleaning up (but, clearly, not fixing case-consistency; Ice-Eared Goblin should probably be all lower-case, like everything else). That script outputted a CSV with the indices in their own fields. Then, I had another Python script, this one inside Scribus, which pulled in the CSV and wrote out the text, one line at a time, but switching fonts along the way, switching to my dice font for the index, then switching back to the text font for the monster name. This is a surprisingly time-consuming script to run, taking several seconds to generate around 18 pages of monsters.

It works, it's sufficient for this project, but it feels like yet another hack along the same lines as hacks that I've done in game development to get, for example, the PlayStation "X" button to render as an image in a tutorial text display. This feels like it doesn't need to be this hard, especially with the Unicode Consortium spending time on frowning poop, and Apple bowing to user demands for shapely peach imagery.

Making a G+ Sendoff

I'm in the last few hours, as I write this, of Google+, the community-oriented social media site. Google will be (will have, by the time you probably read this) closing it down. The site never got a huge following, though there were people who really enjoyed using it.

I wanted to make a send-off in one way or another. I was thinking about using my AxiDraw pen plotter machine to draw a picture to G+, but that didn't click for me. And then I thought that it'd be fun to have an Apple ][ welcome G+ into the afterlife, a place where systems go after they're shut down for good.

First, I started up LinApple, an emulator of an Apple //e, and wrote a test program into it that would print some text to the screen, one character at a time, reminiscent of reading chat on an old BBS system at maybe 1200 baud.

Aside: years ago, I bought a 1200 baud modem for my family's Apple IIgs, and Dad was suspicious of what purpose I'd put it to. I pointed out that I could dial in to the county library and reserve books. Also, there were BBS systems where I could send messages and play games, but I knew that those purposes would be less compelling to Dad. So, Dad, I bought that modem so that I could remember using it and remember using Google+ and see the similarities. Probably still not compelling.

Listing 1

As you can see here, I first clear the screen and set the cursor to the upper left corner of the screen (Line 10), then I take two lines of text, assign them to the string variable A$ and call out to a subroutine. (Lines 20-50). That subroutine iterates through the line, printing one character at a time, then calling an additional subroutine (Lines 1000-1020), which simply spins, slowing down the program, making the text scroll onto the screen at a readable rate. (Slowdown from lines 2000 to 2020).

Interestingly, there's a bug in this code - the subroutine at 2000 doesn't return explicitly. I guess that it reaches the end of memory, knows that it needs to return, and goes back to line 1030.

At 1030, we continue on to the next character in the string, then at 1040, we print nothing other than a newline, terminating our printing to that row of the screen, automagically moving to the left and down one row. Later, we'll see scrolling, as well. All handled by the system. BASIC had a lot going on that I took for granted as a kid.

So, that structure seemed to work. I set out to write a blort of text that would be long enough to be fitting, short enough to be readable. I knew I didn't want to do text editing in my emulated Apple, so I copied this code out of the emulator and onto my Linux machine. Well, it was already ON my Linux machine, just in a disk image that the Apple emulator could read, but my Linux machine couldn't usefully edit.

So, I used AppleCommander to "export" the BASIC program to a text file, which I saved as reference.

The text file I wrote in emacs, because a) of course I did, and b) emacs is pretty good for editing fixed-width text files, which is the sort of thing that I wanted. It's got word wrapping, which made my life easier, too.

So, I wrote a page and a half or so of text, saved that out as a text file.

This next bit is perhaps unnecessary, but I wrote a Python script (again, because of course I did) that read the lines of my text file and wrote out a BASIC program that would print those lines to the screen. Sort of a compiler of sorts, that compiled a text file to BASIC.

The structure of the output file was the same as my test BASIC file (Listing 1), I just had a lot more calls to the line printing subroutine; one each for each line in the text file.

Listing 2

With this, you can see a few things. For one, you can see that emacs is happier providing syntax highlighting for Python than it was for BASIC. Maybe I don't have the Applesoft BASIC major mode installed. The structure is pretty simple - read all the source text file into memory, write a preamble, write out instructions to handle each line, and then write the closing matter, particularly the subroutines.

The header is super straightforward:

Listing 3

All it does is use the HOME command to move to the top left of the screen and clear it. You'll see that I also increment the line number by a healthy 10 numbers and return that.

Kids these days with their IDEs and their structured programming languages, they don't appreciate the value of leaving a healthy amount of space between line numbers, so that you could go back and add in extra commands if you needed to later.

Listing 4

This simply takes a provided string of text (which I had read from my text file) and generate a line of BASIC that assigns that string into the A$ string variable, then on the same line (something done more in BASIC than any other language I've ever seen) invoked the print subroutine. Again, I increment the line number and return.

Listing 5

And that wraps up the BASIC output, and also the Python script. I just write out the code to print one character at a time, placing that subroutine at line 5000, because that seemed like a safe space. Just to be sure, though, I assert that my text printing body of the code hasn't pushed us past 5000 before we got here. Similarly, I have the delay subroutine at 6000.

So, I ran the program, and ran into a few bugs - I had forgotten the semicolon on "PRINT MID$(A$,I,1);" - the semicolon means "print this string, but do not move the cursor afterwards", which achieves the teletype incremental progress. I had also forgotten the carriage-return (again, the kids don't remember typing on a typewriter where there was a physical lever that would RETURN the physical cylinder (the CARRIAGE) such that the typewriter would go on from the left margin.

I fixed those things up, tweaked the text, and output my WELCOME.BAS output file.

I struggled a bit with AppleCommander, trying to get the BASIC code back onto the disk image that the emulator would use. The tricky bit was that Applesoft BASIC is stored on floppies in a "tokenized" format, not in plain text. This takes one step off the job of the interpreter at runtime, and it makes it more efficient to save BASIC programs to a 140k floppy.

So, I needed to figure out a way to take my plain-text WELCOME.BAS file and tokenize it, and store the tokenized output onto the disk image.

Turns out, AppleCommander has a command-line version with a -bas option that does exactly this. Almost exactly this. It isn't perfect about carriage return / line feed combos, so I tinkered with that, and eventually got my WELCOME.BAS onto a disk image.

I actually had some shenanigans with getting it onto the disk image that I wanted to use, which took some rebooting of my emulator, but in the end, I got the program running as expected.

I fiddled with the display options to get the green monochrome monitor effect, and set out to record the results. The first recording I did was using byzanz, a recorder that outputs an animated GIF. This has been effective enough for many of my previous projects, so I fired it up, and got pretty good results. I loaded the output into GIMP, and cropped the image to the size I wanted, and this was the outcome:

Figure 1 - Animated GIF

Good enough for a post to Google+. But I'm never sure if an animated GIF is really going to make it all the way to the viewer without being resampled, reprocessed, and ultimately de-animated. So, maybe that's not good enough. Also, somehow, there was a glitch of random white rectangles. I don't know what that was.

So, I used SimpleScreenRecorder to capture a movie (MPEG?), suitable for upload to YouTube, in case a GIF (appropriately enough, super old technology) doesn't work into the future. SimpleScreenRecorder has a lot of good options, including allowing me to tweak my recording window, turn off recording the mouse, turn off sound, all good things for this project. And, boom, I uploaded it to YouTube, and by the time that I had filled in the metadata, the upload and processing were complete, and my little bit of remembrance was ready to go live.

Figure 2 - Video on YouTube

At this point, I used the following technologies in this project:

• LinApple
• Ubuntu Linux
• emacs
• Python 2.7
• Applesoft BASIC
• AppleCommander 1.5.0 (GUI and command-line)
• GIMP
• byzanz
• simple screen recorder
• Google+
• YouTube
• Blogger

Seems like a lot, and a big part of writing this blog post was to capture the workflow in case anybody (mostly, my later self) could re-use a part of that flow for later projects.

Because I am putting myself to the fullest possible use, which is all I think that any conscious entity can ever hope to do.

Farewell, G+, we will miss you.