HOW-TO make a fish scale / mermaid / bun pattern

 

A friend of mine prompted me to make some "nautical" bookmarks, and that drifted off towards fish. I like fish - largely for their dynamic aggregate behaviors (my thesis had to do with flocking behaviors of dinosaurs, not that different from tropical fish, at least in my simulation). 

So, I had this idea of making an organic-looking fish scale design. It was super quick, and it turned out pretty nice, according to me and the people on Twitter who liked my post. This will be a high-level description of how to make something like the above pattern, along with tips on things to try changing.

Step 1: Generate a "grid" of points

If you were here last time for my flow field how-to, you'll recognize this step. I've got a library, or maybe a toolbox, of routines that I like to turn to when I make my plotter drawings. Robert Bridson wrote a short, but super useful (and readable!) paper about generating points that feel organic, but have nice distributions. Read it and come back, it's worth it, and it's short!

https://www.cct.lsu.edu/~fharhad/ganbatte/siggraph2007/CD2/content/sketches/0250.pdf

I'm going to trust you read the paper, but the takeaway is that you make a grid where each square in the grid is sized so that you know that no two points that you generate can be in a single grid cell. And then you can check a neighborhood in O(1) time, which is like the best time. 

Bridson's paper doesn't assume you're working in 2D, but I don't know about you, I do almost all of my drawings in 2D. Sometimes 3D, so it's good to think about a 3D grid, but a 2D grid gets the job done 99% of the time.

So, if you're ok with 2D, there's this variation, which is what I actually use for my plottering:

http://extremelearning.com.au/an-improved-version-of-bridsons-algorithm-n-for-poisson-disc-sampling/

This is faster, and a little bit more tightly packed, which seems good for my stuff. If you decide it's not for you, and you use Bridson Classic, that's cool. The improved version walks the edge of a disc around each point, generating points as tightly as it can, which you'd think might lead to some hints of repeating patterns, but I find it looks good.

Step 2: Sort your points in x

I'm going to trust that you've got this one. Take the points generated by Bridson, and sort them based on their x-coordinate. You could do any other sorting, but what I'm doing here is basically putting all of the points on a slanty surface in x AND Z slanting away from the viewer, so that the points on the right look farther away than the points on the left.

Mix it up, though. Maybe you can do something fancy to get some "wiggle" in the scales. Or an Ouroboros pattern where the scales loop around. Let me know what you come up with.

Step 2a: Let's draw some debug circles

This is just drawing a circle around each point with the radius I used for the Bridson algorithm. You can see that the points are all pretty tightly packed. Nearly a triangle grid, but with some noise in there that makes it feel more interesting.

The thing we're going to do next is some hidden line / hidden surface elimination, which kids for the past 25 years plus have been able to do with hardware z-buffering. But we're not going to do that, because I'm writing in Python, and vector art feels like it's not meant to be all pixel-shader-y. 

If you disagree, maybe you can do something more efficient than I'm doing here, but I'm going to walk the class through use of "The Painter's Algorithm", which is what we had when I was your age.

Step 3: Let's draw some circles one segment at a time

If you looked at that above illustration and reproduced it with a circle primitive in your drawing environment, that's fine. I actually drew it as a "polyline", a series of vertices connected by straight lines. I used a lot of vertices (around 45 for each circle), which is pretty good. Bear in mind that my target is a 6 inch by 1 inch bookmark, so I can get away with not being pixel-perfect.

I'm not here to teach you trigonometry, but a for loop and some sines and cosines, and you can get a polyline that plots to look like a circle.

But not so fast!

We've sorted our circles so that we'll be drawing the circles from left to right. I've got a routine that takes one of these polyline representations of a circle, and "clips" it against another circle, so that any vertices in the polyline that are inside the second circle get removed. It's a simple function, and I don't want to load this post up with code, but since you asked so kindly:

Yeah, that's a picture of code, which makes it hard to just cut and paste. I'm not sorry. You get syntax highlighting this way.

You can probably see what's going on here, I pass in a "path", our polyline of vertices. Also a center and a radius which describe the circle we're clipping against. I keep consecutive sets of verts in "current_path" until I run out, or until I hit a vert that's inside the second disk, at which point, I move "current_path" into "out_paths", and carry on. At the end, I return each little snipped up piece of the polyline. Maybe I could have been smarter, knowing that my path might end up having 0, 1, or 2 pieces, but I was lazy, and this seemed easy.

With this routine, I can take each of the circles to the left (which, recall, are "in front") of this circle and "hide" the parts of the circle that are obscured. It's almost like I'm some sort of oil painter, hence "Painter's Algorithm".

Except that a painter that uses an opaque paint (Bob Ross) would work from the back and move forward, so it's maybe not a perfect analogy. We're sort of manually cutting up each new circle and only drawing the pieces not obscured by those to the left/forward of it.

I could be clever, use the Bridson grid approach to do an O(1) neighborhood check to find previously drawn circles to clip against, but again, I was lazy when i did this, and I just clip against every circle I've already drawn. It's quick enough for what I need, right now.

Step 4: You're done

That's all there is to it, just draw circles, clipped against earlier circles. I thought about doing fancier masking, drawing a bitmap to a temporary buffer, and then clipping my polylines against that - I might do that, too. 

Or, you could do some fancy Signed Distance Field (SDF) stuff, which would be pretty similar to what I did, above. But SDFs are cool, so maybe there's some neat effects you could get from doing it that way.

Step 5: You're still here?

If you turn the picture sideways, maybe it looks like steamed buns or xiao long bao (soup dumplings). 

Maybe not. But if you like the image of dumplings and/or buns, stretching off to the horizon, maybe my work here is done.

HOW-TO make a flow field drawing on a plotter

 

In January of 2021, I took part in a month-long daily set of challenges to draw things on my plotter. One of the challenges was "curves", so I set out to draw a bunch of non-overlapping curves. I call this technique a "flow field", and it's inspired by a number of things I've seen elsewhere, and I'm sure other people have similar approaches, but this article talks about how I've been making these kinds of drawings, including some things I've learned as I go along.

Step 1: Generate a "grid" of points

My first step is to make a (roughly) evenly spaced grid of points, using Bridson's algorithm. I like this implementation here: http://extremelearning.com.au/an-improved-version-of-bridsons-algorithm-n-for-poisson-disc-sampling/ which uses Bridson's technique of keeping an array of buckets for generated points, but then walking uniformly around a "live" point to generate new points where possible. Quick, easy, and a useful tool for your toolbox.

You could use any other technique for generating your points; a square grid, a hex grid, or something else.

Step 2: For each point, generate a random direction

This is pretty straightforward - at each of the points in the grid (from step 1, above), pick a random direction. You could do this by picking a heading in degrees between 0 and 360 or in radians between 0 and 2*pi. That works, and it's basically fine, but I prefer to generate a random vector of unit length, by picking x and y values from -1 to 1 and throwing out x,y pairs that are outside of the circle. If they're inside the circle, I scale x and y so that the magnitude of the vector is 1.

This is a little more work, and you could get the same effect by picking a random heading and then using sine and cosine to get x and y. One thing that's nice about generating vectors this way is that it's easy to use the same ideas to make a random 3d vector on the unit sphere. Or 5d or whatever. If you have need for such things.

Step 3: Smooth the directions

I don't know how important this step is, I think it's worth doing, but I don't know how much work is worth doing here. What I do is loop for a couple (maybe 5?) times over all the points from step 1, and adjust the directions by a weighted average of the nearby points' directions.

This is a place where it's handy to have the directions as vectors; you can sum a bunch of direction vectors, scale them as you need, maybe normalize on the way out, and you've got a well-behaved vector sum. It's trickier to make sure that angle measures wrap around properly, and doing weighted sums is harder.

So, I do some smoothing to get points sort of lining up with their neighbors.

Step 4: Trace some paths

Now you want to generate a set of starting points. Maybe use Bridson or whatever you used in step 1. Or use something else.

For each starting point, create a path, a series of points, stepping in the average direction of the nearby neighbors. I use an inverse square falloff to weight the nearby points, but different ways of determining the local direction are possible. Take a step, find the local direction, take another step. If you go past a maximum number of steps, probably stop. If you go off the edge of the paper, stop.

I have noticed that there's a strong possibility of having paths getting dense on the page, to the point that when I physically plot the lines on paper, I bleed through the paper (with felt-tipped pens) or tear holes in the paper (with ball-point pens). So, one thing that I do is keep track of areas that I've visited, and if my new path is close to an already-drawn path, then I stop my new path.

Variations

Some ideas that I've played around with, and some ideas I haven't tried:

• Vary the color - I've picked a different color for different paths. Maybe other color selection algorithms would be useful. If you're drawing to a screen with more than 256 colors, you can be pretty flexible. With plotters, you might have a much more limited set of options.
  
  
  
• Use a mask for where the paths can be - there's no real reason to use a rectangle as your boundary. I used a pair of circles here to stop tracing my paths. You could use Signed Distance Fields or other ways of determining a boundary.
• non-unit direction vectors - All of my directions are normalized to be length 1. I do a weighted average of the nearby direction vectors, and again, normalize to be length 1. Maybe don't do that? You could have paths that have "velocity" and "momentum" in a way that these paths don't. Maybe that's interesting?
• Other forces - you could have other ways of influencing the direction that a path moves, by simulating gravity, or by generating a twist around your points.
• Other generating shapes - I use points, but you could use squares or donuts, or other shapes.

This is all pretty high level, but gives some ideas for how you might generate your own flow field drawings. Have fun!

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.

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.

Going from a grayscale image to an image with transparency in GIMP 2.10.8 on Linux

I've searched for this in a bunch of places, and I've found a technique that works for me - I think my requirements are a little different from maybe what other people are looking for, so I'm writing this up for my own notes, and maybe somebody else can benefit.

Problem Statement:

I've got some black-on-white grayscale art (possibly pen-and-ink line art) that I'd like to turn into a layer of a single color, but with the grayscale value in the alpha channel.

If I was writing a Python script using PIL, I'd expect the incoming image to be a grayscale format, with 8 bits of lightness information (0 = black, 255 = white), no alpha channel, and the output image is RGBA, where every pixel is (0, 0, 0, A) where A is 255-L, L being the lightness value of the input image.

Why not make a Python script to do this? It sounds like 5 lines of Python or less, right?

Yeah, maybe.

Still, this is how I do it in GIMP. Maybe I want to do additional processing in GIMP, and having it already open might be handy. Or something.

Step 1

Ok, I'm starting with my image loaded in GIMP. I'm not going to help you get to this point.

Optionally, crop the image - for this image, I tried "Image > Crop To Content", which didn't get as tight on the left hand side as I expected, so I followed up by using the rectangular selection box from the toolbar, selected a generous box, and manually pulled in the left side to where I wanted it. And then "Image > Crop To Selection".

I suppose you could do a bunch of other stuff here, too, like resizing the image. Live your best life.

Step 2

Duplicate the layer

This can be done by right clicking on the layer in the Layers panel.

Step 3

Invert the layer. I had best results with "Colors > Linear Invert". You could try the normal invert, I suppose.

Step 4

Right click on the new layer, select "Add Layer Mask"

Select the Grayscale copy of layer. (Why is it grayed out AND selected?)

Step 5

With the paint bucket tool, fill the layer (not the mask) with black, using "Fill whole selection", making sure your selection is all or none of the image.

Step 6

No, there's no step 6. You're done. Make a sweatshirt or whatever it is that you were going to do with your grayscale Half-Elk Fighter-Master. Or whatever.

Lulu + ReportLab = unembedded fonts, by default - FIXED

I use ReportLab's PDFGen Python library to generate PDFs. I use it for a lot of different stuff, including my line of Kakuro books. It's not tricky to get it to do what I want, most of the time. When I generated the PDFs for those Kakuro books, I submitted them to lulu.com and immediately got an error complaining that my books didn't properly embed the Helvetica font.

I did vague digging around and some sort of hacking (so many years ago, I don't recall the details), and got something gross that didn't have a reference to Helvetica.

I also shelled out money to Adobe for their commercial PDF tool, and massaged the output.

Neither of these solutions were really satisfying, but they each seemed to work at various times.

Fast forward to today, and I wanted to make a notebook of hex grid paper:

I uploaded the PDF of my graph paper, and got that same error again. To be clear, the entire book was graph paper - no fonts were being used. I poked around in the PDFGen documentation (there's a user's tutorial, not so much a reference manual), and found some information that was useful for importing TTF files and embedding them, but nothing for an unused Helvetica font.

I poked around inside the source again, and discovered the initialFontName and initialFontSize arguments to the canvas object, so now, my canvas creation looks like this:

ttfFile = os.path.join('.', 'UniversalisADFStd-Regular.ttf')  

pdfmetrics.registerFont(TTFont("Universalis", ttfFile))

c = canvas.Canvas("hex_book.pdf", initialFontName='Universalis', initialFontSize = 24, pagesize=pageSize)

c.setFont('Universalis', 24)

And there's no dangling use of Helvetica, and Lulu's happy, and I'm happy. Maybe this is useful to you, maybe it'll be useful to me, next time I run into this particular weirdness.