UIs and Layout Managers Using HTML and CSS

For the past few years, I've decided to stop learning new UI frameworks and to make all my user interfaces using HTML5. Making user interfaces is HARD. The idea that I should constantly throw away my old UI code and rewrite things in scratch every few years using new, half-baked UI frameworks is preposterous. It takes ages to learn the ins and outs of a UI framework and figure out how to  get the behaviour "just right." Why would I want to discard code that works perfectly well and which I spent ages fine-tuning and replace it with new code based on a new, buggy UI framework? Since I do all my coding in Java, I went and ported GWT Elemental to JavaFx so that I could use HTML5 in my UIs from my Java code. I can now take my same UI code and reuse it on websites, on desktop applications, and for mobile UIs.

In the past, I've found using HTML for user interfaces to be problematic. HTML has traditionally used a word processor layout model. There's a central flow of text, and you can position pictures and other elements to the sides of the text. HTML really wants you to lay things out this way. If you try to do something different, you end up really fighting against the layout model and causing yourself grief. The standard components of a desktop UI -- widgets and toolbars that dock on the sides and status bars on the bottom -- really doesn't fit in well with HTML layouts.

HTML also often works at the wrong abstraction level for making good UIs.

• the UI engine has to be on guard against exploits by non-trusted code, so you can't easily capture the mouse or manage the clipboard or talk to other applications, etc
• you can't really do pixel fiddling. Sometimes, you just want to get in there and just tweak the pixels to get the perfect look, but since HTML is a retained mode UI, you can't easily do that. In the end, that has worked out ok because it made adding support for high dpi screens fairly painless. But you can't do things like make rounded buttons that have pixel-perfect shading without lots and lots of hoops to jump through. You can't take existing widgets and buttons and tweak the look a little bit by fiddling with the pixels. If you want to fiddle pixels on a button, you have to write all the logic for the button yourself (some of the accessibility stuff can get hairy!). You can't take an existing button and just fiddle with how it gets painted.
• HTML has poor support for text input and internationalization. Even after many years of studying it, it's still unclear to me how to do rich-text internationalized input in a web browser. Maybe it's easy, maybe it's not. There's just not much talk about it.
• HTML doesn't really have a concept of widgets. This is coming in the form of web components, shadow DOM and templates, but these things are very much a work in progress and it isn't clear when they'll be available for widespread use. In the meantime, HTML doesn't really support the idea of having self-contained UI components. If you make a custom UI widget, the "guts" of your widget are exposed in the HTML. Other components might accidentally, move things around in your widget or restyle their CSS because there is no way to modularize your own code to prevent accidental tampering by other widgets.
• the event model doesn't have easy hooks for doing common UI stuff like keyboard shortcuts, context menus, menu bars, enabling/disabling widgets, modal dialog boxes, file choosers, etc. Handling these things require awkward flows of events, so regular UI frameworks like win32 or Swing have special hooks that allow you to tap into this event flow without having to build your own convoluted event handling framework
• it's hard to lay things out at their "natural size." If you have a short form that you want people to fill in, it can get a little tricky to set its width and height set to the minimum size needed to hold the form. Often you simply need to guess at an appropriate size.
• since HTML is designed for making web pages, it does a poor job exposing platform dependent behaviour to the application. What's the default font on the system? What's the default keyboard button used for keyboard shortcuts? What keyboard events is it safe to intercept without destroying accessibility of the platform? What's the default language?
• you have to code the common UI widgets yourself because HTML doesn't come with any. Things like toolbars, menu bars, context menus, spin buttons, and scrollbars are all things you have to do yourself.

Despite all these major deficiencies in using HTML for traditional UIs (and I'm sure there's many more too), HTML does have many advantages over other UI frameworks.

• there are many more developers working on improving HTML5 than there are developers working on other UI frameworks, so it advances quickly
• it's well-supported on new hardware and is easily cross-platform
• it embraces certain features much earlier than other UIs (e.g. touch support and high dpi)
• it has easy support for printing
• it ages well, so old HTML code generally still works even on modern systems

So given that we want to use HTML for a traditional UI, how do we go about doing it? In the last few years, the layout options available using HTML and CSS have improved dramatically with endless new features that cater to people designing UIs as opposed to word processor print layouts. With all of these features though, it has taken me a while to figure out how to use those options to make a traditional looking UI. Here are some of the tricks that I've used.

The first thing is to make sure to zero out the margin, padding, and borders of all your html, body, div, and span elements. In the past, it was also necessary to set the height and width of the html and body elements to 100%, but I don't think that's necessary any more. I also don't think it's necessary to add "position: absolute;" or "position: relative" on the html and body elements any more. This is all necessary so that you can accurately stick things in the corners and sides of the page using absolute positioning. In a word processor layout, you want to have a margin on the sides, but in a proper UI, you want to have toolbars and menus there.

In the past, it was important to avoid using pixels for positioning because people with poor eyesight would increase the font size to make things easier to read. Most designers couldn't handle this, so the modern approach is to use pixel positioning, but let users with poor eyesight adjust what the size of a pixel is. I'm a traditionalist though, and I still try to use layouts based on font size where possible while resorting to pixel sizes when I actually need containers that hold images with a known pixel size. HTML5 now has new measurement units that make laying out resizable things easier.

The "rem" unit is the width of an "M" character on the body element. You can lay things out based on how many characters should fit in a certain area. Unlike the old "em" unit, which is the width of an "M" for the current element, you don't have to worry that you might be nested inside another element that changed the size of the font or something.

Similar to the "rem" unit, HTML5 also has the new measurement units "vw" and "vh", which express things in terms of percentage of the viewport width and height (i.e. width and height of the browser window). If you want your UI to resize when you resize the browser, then you need to express things in terms of percentages. Unfortunately, the old "%" unit was always a little confusing because it sized things in terms of percentage of the parent (and sometimes, it was not of the parent but of the first relatively or absolutely positioned parent). Often, you need to position div elements inside other div elements to get the right layouts, but you still wanted things to resize globally, so using "vw" and "vh" units lets you do that. There's even a "vmin" unit that's useful for making elements that have a certain ratio of height to width but that still resizes when you resize the browser. I suspect that "vw" and "vh" units might have similar problems to "%" when using things for widths. Sometimes, when you set two things with a width of "50%" beside each other, the actual size in pixels might be something like 500.5, and the browser might round those values up or down, meaning the final width might leave an extra pixel somewhere or it might overflow the width of the browser. I think modern browsers actual use floating point numbers for sizes and are a bit more generous about half pixels at the edge of the screen because I haven't had an issue with things like that in a while. There's also a "vmax" unit. That unit might be useful for scaling images when used in combination with max-width and max-height. I haven't had an occasion to use it yet though.

Using physical units like inches and picas are still ill-advised, I think. In the past, there was an issue where some browser makers would actually use real units there. So if you said you wanted something to be one inch, but you were using a 60inch TV, the browser would actually make your element only a few pixels wide because that was what one inch was on a large TV (whereas on a tiny mobile phone, one inch might be half the screen). I think most browsers just set one inch to be 96 "pixels" now, but if that's the case, you might as well just use pixels directly for sizing things.

Once you have your units figured out, you need to a way to stick things in different places in the window in order to make a traditional UI. To do that, you can use "position: fixed" or "position: absolute".

fixed positioning

In the past, Apple sabotaged fixed positioning because the iPhone wouldn't follow it, but modern iPhones do behave properly now. I just find absolute positioning to be more flexible and easier to use though. If your UI has a central resizable area, but some fixed sized things on the side, then you could possibly use fixed positioning. The scrollbars for the whole web page will only control the central area, but that might be what you want. When using a keyboard to control a UI, this is useful because using the the cursor keys to move around will always scroll the central area even if the keyboard focus is on one of the side panels. With absolute positioning, for example, your keyboard focus might be on a side panel when you first create your UI, so when the user tries using the cursor keys to scroll things, the central area won't scroll, contrary to their expectations. But this is fixable, so I'm not sure it's worth using "position: fixed" just for that. People might get confused by having the main scrollbar only control the central area too.

Funnily enough, in the past, Apple also sabotaged absolute positioning on the iPhone too. Sometimes, you wanted side panels in your UI that scroll, and the iPhone wouldn't show scrollbars on them, so people wouldn't realize that they scroll, and the iPhone gesture needed to actually scroll them was really confusing (some sort of two finger thing). That's fixed now though.

floating panel

Absolute positioning is obviously useful for free-floating toolboxes and windows, but you can also use it in UIs to provide the functionality of a BorderLayout layout manager. You can easily create one expandable center area, with fixed sized components above, below, to the left, and to the right of it. Unlike fixed positioning, elements with absolute positioning can be nested, so any element or UI component can, in turn, use absolute positioning to layout out its internal elements using this border-style layout. HTML's absolute positioning is also limited because you have to specify sizes for the elements that you place on the sides. You can't let those components be laid out "naturally" and let the UI automatically figure out a natural width and height for them. You must explicitly give them a size.

To use absolute positioning properly in this way, you need to watch for some things:

• By default, the width and height of an element given in CSS specifies the size of the content only and does not include the border and padding. This makes it hard to get boxes to line up properly beside each other because the size of an element is often given in different measurement units from the size of its border and padding. Typically, you would specify the width of an element in vw, its padding in rem, and its border in px. In the past, you would need to get around this problem by using nested div elements, but CSS now offers two better ways to deal with this problem. One is the calc() function in CSS that lets you calculate a measurement that mixes different measurement units. This is still a bit of a pain to use though, so the easier approach is to use the CSS "box-sizing: border-box" property to explicitly state that measurements should include the border and padding.
• You have to make sure that you've positioned everything perfectly to fit inside the browser window, or you'll end up scrollbars on the browser, which will throw the whole layout off. Sometimes, it's useful to sprinkle "overflow: auto;" and "overflow: hidden" on various elements to make sure content doesn't accidentally spill over and become larger than the browser window, triggering the appearance of scrollbars
• If you've worked with other UI frameworks or even drawing frameworks like the HTML5 Canvas, you get into a habit of specifying the sizes and positioning of things using left, top, width, and height. With absolute positioning, this can get you into trouble because you have to mix different measurement units, so things can get confusing really quickly. To get the most use out of your absolute positioning, you have to remember that CSS lets you specify the sizes of things in terms of right too (i.e. distance from the right side). So a sidebar on the left can be positioned using "left: 0; width: 20rem;", a sidebar on the right can be positioned using "right: 0; width: 30vw;" and the central array that expands as the window is resized can be positioned using "left: 20rem; right: 30vw;". Notice how a width isn't even specified for the central area. It's size is specified by simply giving the positions of its left and right sides, and different measurement units are used for the two sides too.

using absolute positioning for a border layout

Recent web browsers also support new layout tools such as flexbox. Flexbox is nice because it lets you do some nice things like vertical centering, aligning elements, mixing of different measurement units and making some limited use of natural sizes of elements when doing layout. Unfortunately, there's a lot of knobs that you need to adjust to get the flexbox to work, and those knobs have confusing names so I always forget what they are and have to spend a lot of times looking things up every time I want to use a flex box.

I sometimes end up using flexbox layouts for really mundane things that should be easy in CSS, but that I always forget how to do, like making a line of boxes or a line of images. I always forget to set the vertical-align property on those boxes, so they end up being positioned inconsistently depending on what their contents are. Flexbox uses its own alignment rules, so you can avoid that whole mess.

In the future though, I'm eagerly awaiting the arrival of grid layouts to CSS. Although you can sort of do the same thing using tables, grid layouts should provide much more layout power than flexbox while reducing the amount of confusing HTML verbiage you need to write. With grid layouts, you can actually align things both horizontally and vertically! And you don't need to put elements in your HTML just to designate how things should be laid out. You just specify the different pieces of content you want in HTML, and then the CSS is used to position them in a grid. There's a bit of a concern that Apple has no desire to add support for grid layouts to Safari, but hopefully, they'll be swayed in time.

LibreOffice vs. OpenOffice

If you're using Windows, use OpenOffice. If you're using Linux, use LibreOffice.

OpenOffice was stagnating a while ago, so I switched to LibreOffice. Both systems were a little sloppy back then, but LibreOffice seemed a little nicer. When OpenOffice was revived as Apache OpenOffice, I tried it out, but it seemed to have poor support for file formats and it couldn't import some of my old LibreOffice files (even though they're both supposedly using the same standard ODF file format), so I stayed with LibreOffice.

But LibreOffice has always been problematic for me on Windows with lots of features not working quite right for many years. I just tried OpenOffice right now, and it just "works." No rendering artifacts. No problems with PDF export. It just works. The download and installation experience isn't quite as polished as with LibreOffice, but it just works.

I think the LibreOffice developers are mostly Linux developers who work for Linux distributions, so it is just works better there and is better integrated with those distributions. OpenOffice is used in commercial Windows products, so the developers make sure it works properly on Windows.

Update (2018-3-10): Development on OpenOffice has mostly stopped, so I decided to try the latest LibreOffice 6. PDF export was still broken on Windows. Performance on Windows has now gotten so bad that it was painfully slow to just type up some text on some slides for a presentation. I went back to OpenOffice.

Comparing DRL Plans for Toronto

In my previous blog post, I mentioned that I was setting up some simulations to see if I could learn some insights into some of the proposals for downtown relief lines for Toronto. I've now finished running the simulations.

Baseline

Here is the baseline map from the previous blog post. It shows what the fastest route to King and Bay is from various points in the city. Yellow dots show that the fastest route involves taking the Yonge subway. Green dots show that the fastest route involves taking the Bloor-Danforth subway and then transferring to the Yonge subway at the Bloor-Yonge subway station. Orange dots show that the fastest route doesn't require the use of the Yonge subway or Bloor-Danforth subway on its busiest sections. A good plan for relieving pressure from the Yonge subway should involve turning as many yellow and green dots into orange dots as possible.

Downtown Relief Line

For the downtown relief line, I modeled the shortest possible line. It runs from Danforth and Pape southwards, then travels west until it hits Wellington and Bay. The simulation assumes six minute headways. Although the DRL will probably come less often than the Yonge subway, it is expected that people who would normally take the Bloor subway and then transfer onto the Yonge subway will prefer to take the DRL because it will be slightly faster due it having fewer stops than the Yonge subway. It will also be less crowded. As can be seen from the simulation results, the DRL does seem like it can intercept people who ride the Bloor subway to the financial district and redirect them away from the Yonge subway. Pretty much all the green dots become orange.

Regional Express Rail - Lakeshore

The provincial government has recently expressed an interest in upgrading its GO train service to a faster and more frequent regional express rail service. It seems that they are looking primarily at upgrading the Lakeshore and Weston lines initially. In theory, the provincial government has been working on this plan for more than a decade already, but they've recently implied that they're going to prioritize this improvement much higher than before. I modeled this improvement by taking the existing schedule of the Lakeshore GO train line and adding new trips so that it would come every 15 minutes instead of every 30 minutes like it currently does. The simulation shows that increased frequency of the Lakeshore line won't draw any riders away from the Yonge subway line. This might be due to a limitation of the simulation. With more frequent Lakeshore GO train service, the TTC might offer more frequent and better bus connections to the Lakeshore line's stations, which might alter the simulations results somewhat.

Regional Express Rail - Stouffville

The provincial government could potentially build a regional express rail on the Stouffville GO train line. I think this is unlikely because it requires double-tracking and other expensive track upgrades. Despite many small improvements to this track by previous governments over the years, I don't think any accommodation was made to make it easy to upgrade to a much higher capacity line. Also, current ridership on this line is poor, so it would be hard to justify increased frequency on the line. I modeled this improvement by taking the schedule of the Stouffville GO train line and adding new trips so that it would come every 15 minutes. The simulation results show that anyone who normally rides down to Kennedy station to take the Bloor subway to downtown would benefit from upgrading the Stouffville line to a regional express rail. One effect that I did not model was that of a possible extension of the Bloor subway to Sheppard. This change might affect the relative benefits of taking the subway vs. taking a less frequent regional train line, causing people to still prefer taking the subway.

SmartTrack

I don't quite understand the SmartTrack plan, so I wasn't sure how to model it. It's probably best understood as being equivalent to the Regional Express Rail - Stouffville plan shown above. Although the plan does seem very intriguing, I'm not actually sure it's within the power of the City of Toronto to actually build it. The plan seems to involve convincing the federal and provincial governments to pay for upgrades to a provincial regional train service that runs on track owned by private companies. I don't really see how the City of Toronto would have any power to actually get the thing built. The plan is also premised on the idea that there is room to add large numbers of trains onto existing track running through the city. It's not clear if that's actually the case. Those lines might already be packed with other trains. The province has already expressed an interest in building a new downtown train station or new downtown train tunnels due to bottlenecks in moving trains through downtown. And running frequent local train service through the city would impede fast, frequent regional GO train service, so the province might not be willing to make that sacrifice. As far as I can tell, the SmartTrack plan might not involve building anything at all. One possible interpretation of the SmartTrack plan is that Toronto will do absolutely nothing for 10 years, wait for the provincial government to build a Regional Express Rail, and then the city will retroactively call the Regional Express Rail as being "SmartTrack."

Compromise? Downtown Tunnel (DRL-lite?)

One problem with all of these different plans is that politicians will end up arguing over them for years and nothing will get built. All of these plans do have a common element though in that they all probably require new train tunnels through downtown. One compromise might be to start building a tunnel through downtown as early as possible that can later be repurposed for a subway, regional express rail, SmartTrack or whatever once a final plan is agreed on in ten years time. The tunnel can run from near Exhibition (the possible second downtown train station) to just east of the Don Valley (where it could later be extended to the existing rail right of way or north as a DRL). Since a short tunnel is probably useless on its own, it can initially be outfitted for streetcar use, so that the tunnel could actually be used until the politicians secure funding for some bigger plan.

Setting up Simulations of the DRL

With all the talk this year of transit issues in Toronto and the importance of building some sort of downtown relief line (DRL), I thought I would try to grab some open data and see if it's possible for amateurs to gain some insight into the problem.

The current argument behind the downtown relief line is that most people want to go downtown for work. Also, the population of downtown is exploding in itself because both the millenial generation and the aging boomer generation are favouring the downtown lifestyle over the suburban lifestyle. This is supposedly causing a number of problems. The primary means for getting into downtown is the Yonge subway, and it's always full. It's so full that one of the main arguments against extending the subway system in the suburbs is that these extensions would simply feed more traffic onto the Yonge subway, which can't handle the additional load. Since the whole system relies on the Yonge subway line to move people into downtown, if there are any problems on that line (which happens often), the whole transit system grinds to a halt. There is very little redundancy in the system to provide riders with alternate ways to get downtown if the Yonge line has problems. A related problem is that the Bloor subway feeds riders onto the Yonge subway at the Bloor-Yonge station, and supposedly that station is also becoming a bottleneck in the system too in that it's becoming physically difficult to transfer all the people from the Bloor subway to the Yonge subway because there's just too many people. And then there's also a concern that the primary means of moving people east and west through downtown--the streetcar system--can no longer handle all the people who have now moved downtown.

The primary goal of the DRL is to build a new north-south subway line to relieve the pressure on the Yonge line. Since people primarily want to ride the subway into downtown, this DRL will also have to go into downtown somehow. If the DRL also happens to relieve pressure on the east-west streetcar system, that's a bonus.

To gain some insight into different DRL plans, I've started setting up a simulation that shows who is riding the Yonge subway now. I took the GO Transit and TTC schedules for September 24, 2014, and I calculated the optimal route for people who need to get to work at Bay and King at 8:55am and 9:00am. I tracked whether the route used the Yonge subway south between Queen and King as an indication that a particular route used the Yonge subway. I also tracked which routes used the Bloor line through Bloor-Yonge station and also use the Yonge subway between Queen and King as an indication of riders who transferred from the Bloor to the Yonge subways. Since I calculated routes for two different times, it's possible that different routes are optimal for those two times. Since the two times are only 5 minutes apart, I assumed that riders would take the route that avoided the Yonge subway, if possible, and if not, then one that avoided a transfer from the Bloor subway to the Yonge subway.

The result of the simulation is shown below. The red dots show areas where people can get to downtown without needing to use the Yonge subway. The yellow dots are areas where people's optimal route to downtown involves taking the Yonge subway. The green dots are areas where people's optimal route to downtown involves riding the Bloor subway to Bloor-Yonge station, and then taking the Yonge subway into downtown.

As can be seen on the map, everyone in the west of the city can take the University-Spadina subway line into downtown, so that area is all red. Surprisingly, it is often optimal for people just to the east of the University-Spadina subway to still travel further east to the Yonge subway line to get downtown.

In southern east York, the fastest way downtown seems to involve taking the streetcar. In south-east Scarborough, I think the fastest way downtown involves taking a bus down to the Lakeshore GO train possibly? Or possibly TTC express buses direct to downtown? Or GO buses? It's hard to tell.

There's an area around the DVP where I think it's fastest to use express buses from the TTC or GO to get downtown rather than travel east or west to a subway line. Those also sporadic red spots in places around GO bus stations and GO train stations. These stations offer quick ways to get downtown, but they don't come often enough to make it worthwhile to take them if you need to get somewhere by a certain time unless you live really near to the stations.

Anyway, that's just a preliminary map of what I can calculate using the readily available transit schedule information. I'll later try plugging in some suggested DRL plans to see what effect they have on the map.

Which Casual Gameplay Mechanics are Good for Building Narratives

I was recently playing some computer pinball. I've always been fascinated with the narrative aspects of computer pinball. From when I saw my first pictures of Devil's Crush, I was captivated by the idea that you could have a pinball game with enemies that you could fight by playing pinball. I imagined that game designers could build whole war games and strategy games that you could control by playing pinball.

Anyway, I actually don't ever play pinball in real-life, but it was interesting to see how Pinball FX2 builds missions and progression inside its pinball games. That got me thinking about what sort of casual gameplay mechanics lend themselves to having narratives built on top of them?

For the last few years, there's been several games that have built narratives on top of match-three games. In games like Puzzle Quest or 10000000, you have a generally linear plot, and you control action by creating matches. Making matches of different colours results in different types of attacks or defenses. There are also RPG elements where you can upgrade to gain new powers and abilities. The problem is that the action of the match-3 game is tightly bound to the action of the narrative. The gameplay doesn't lend itself to letting the player make "choices" in the narrative, so choices must be made outside of the gameplay mechanic.

One of the cool things with pinball is that your actions *indirectly* affect the flow of the narrative. The story can involve quite deep stories and exciting interactions that you can influence with a limited number of levers (unlike match-3 where you have shallow scenarios that you directly control through your matches). You can have exciting scenarios that would be too complicated to build a casual game around (like controlling the events of a war, building an economy, controlling complicated machinery, being an archaeologist), abstract the mechanics so that a player can control these scenarios with simple gameplay levers (to the point that it's so simple that it would be boring if the player were given direct control of those levers), and let the player adjust these levers through the gameplay mechanic (thus keeping things interesting). Also you have choices in that the ramps and targets that you aim for allow you to choose different paths in the narrative. For example, in a pinball game, you can have a story where the protagonist needs to gather five hidden gems and combine them to defeat a boss. The player can control the locations to be searched by targeting different areas with their ball. That sort of plot can be represented as a pinball game.

The main problem with pinball though is that regular unskilled players don't have enough talent to carefully aim their balls, so the game ends up being mostly random. If you don't have enough control over the aim, then you can't really control the flow of the narrative. It might be possible to build a random narrative. For example, you could build a giant map that you can play pinball on (like in Snowball). Even though unskilled players won't be able to control where on the map that they go, the map can be used to represent a protagonist questing through life or through a real map.

But that got me thinking about whether there are casual gameplay mechanics that would be even better for building narratives on. Ones that provide more control, offer interesting narrative possibilities, yet are interesting to play in themselves.

A good game narrative for interactive games lets the player make choices. But we don't want the player to make choices directly. Choice can be represented as "aiming." Could a narrative game be built around Puzzle Bobble? Worms or Scorched Earth? Breakout? Marble Madness? Pachinko? Minigolf? Or maybe the pinball mechanics could be made even more casual? Instead of flippers, maybe you directly send out pulses or something to more directly influence the movement of the ball?

These games focus on a single ball, meaning they're great for narratives with a single protagonist who quests around. But what about a more complex tale? Is there a casual gameplay mechanic that lends itself to resource allocation? If so, you could build RPGs or simulations by letting players assign values to different resources somehow. You could build a game of civilization where you assign your populace to do research or wage war or grow food. Pachinko might work, but it's a bit too random and too slow. Puzzle Bobble? Peggle? Is there a game mechanic that is time constrained and that can become more difficult over time?

Anyway, I think there should be a way to build some more interesting narrative casual games if someone were to put enough thought into this topic.

Gradients 5: Refinement of the Precomputed Gradient

One issue with the precomputed gradient was that the triangle mesh was too coarse to capture the details of the gradient. To solve this problem, I progressively refine the triangle mesh until it is detailed enough to show the gradient in the detail that I want. What I do is I first find all the edges of the triangle mesh. I then go over them and look for one that can be split, which creates a new vertex, which can be assigned a new colour, improving the detail in the gradient. When scanning over the edges, I arbitrarily go over them in order from longest edge to shortest edge. I was hoping that doing it that way would help prevent the creation of "skinny" triangles, but in pratice it didn't seem to help too much. For each edge, I split the edge, recompute the gradient, and then compare the new gradient with the old gradient at the vertex points. If the colours of the vertices change by above a certain amount, I keep the split. Otherwise, I revert the split. Then, I move on to the next edge and continue the process until I can't find any edges worth splitting.

Below, I have the triangle mesh generated when splitting an edge doesn't result in any colours changes above 0.1 in any one component (where colours range from 0 to 1).

And here is a triangle mesh when I only split edges that result in a colour change above 0.05. Because I never split exterior edges, there tend to be very long and skinny triangles along the exterior. I guess it would make sense to develop some sort of heuristic to figure out when it makes sense to make a split there.

And if we remove the triangle mesh and just look at the resulting gradient, here is the final result:

The result isn't too bad. The gradient is clearly there, but the colour transitions aren't completely smooth (due to the triangulation). The effect of gouraud shading between edges of the triangle are also visible. The white of the center vertex seems to extend deeper into the polygon that it really should.

But if you compare the generated gradient with that calculated by diffusion or by pure mean value coordinates, the results are decently. Below, the precomputed gradient is in the middle. The diffusion gradient is on the left. The mean value coordinates gradient is on the right.

One of the main reasons for not using mean value coordinates directly in the gradient was that for concave polygons, it could produce illegal colour values that aren't in the range of colours specified along the border of the gradient. As we can from the concave polygon below, we don't encounter any illegal colour values like when using pure mean value coordinates.

Although we still mean value coordinates, because of the way we set them up, it shouldn't be possible to get illegal values. Suppose we have an interior vertex that we're computing mean value coordinates for. Since the vertices adjacent to each interior vertex can all be arranged in a nice clockwise order, the interior vertex ends up with a nice mix of the adjacent colours with all the weights positive and adding to one. So the interior vertex can't have a colour outside the colour ranges of the vertices it is adjacent to. As such you shouldn't be able to get any colour values for an interior vertex that is outside the range of colours assigned to the boundary of the polygon. The problem with mean value coordinates on a concave polygon is that the vertices sometimes run clockwise or anti-clockwise, resulting in negative weights, which can result in the illegal values.

So that's my gradient. The resulting precomputed gradient can be rendered quickly on graphics hardware and has all the nice properties we want from a gradient. The only issue is that it's still a little slow to compute. It would be better if there were a better policy that could be used to create the triangulation of the polygon and its refinement. If I were better at the math, it might be cool trying to develop some sort of process for the diffusion or generating the weights that would result in only local changes to vertex colours when an edge is split, but I'm not sure if that's actually feasible (but it would make the mesh refinement process much faster!).

Gradients 4: Precomputing Mean Value Coordinates and Diffusion

Although I have already shown two really good techniques for calculating gradients using diffusion or mean value coordinates, they don't quite do everything that I want them to do. One of the main benefits of vector drawings over raster drawings is that they are easier to animate, but mean value coordinates and diffusion aren't fast enough for real-time animation. Graphics hardware is optimized for displaying triangles on the screen, so the ideal gradient algorithm would be able to break down a gradient shaded polygon into a set of triangles that can be blasted to the screen quickly by the graphics hardware. We can use techniques similar to 3d animation where the animated geometry is precomputed: we'll try to break down the gradient polygons into triangles in advance, and those triangles can then be animated easily. This does mean that the gradients can't change during an animation, but hopefully allowing the geometry to change during an animation provides sufficient flexibility for artistic expression.

Precomputing a diffusion gradient is a little messy since it relies on a pixel grid instead of the triangles that we want in our final output. If I paid more attention in my classes on calculus and numerical methods, I might be able to rederive the diffusion equations for use on a triangle mesh instead of on a grid, but that's really beyond my mathematical ability at the moment. On the other hand, applying mean value coordinates to a triangle mesh is straight-forward, but mean value coordinates can potentially produce bad values when used on concave polygons. Instead, I've tried to combine both approaches. I'm precomputing a diffusion gradient by using the mean value coordinates as the basis for diffusing values through a triangle mesh. Basically, instead of finessing the problem, I'm going to bash this problem with a brute force hammer until I get something that seems to work. It may have no proper mathematical basis, but it should hopefully produce something good enough for real use.

The first step is to create a triangle mesh over which I can diffuse a gradient. The scientific computation community has all sorts of techniques for computing triangle meshes that are optimal for doing various things, but I don't know any of that work, so I'm just going to put together something hacky. The first step is to use some sort of bog standard polygon triangulation algorithm to create an initial triangulation.

The edges in a minimal triangulation of a polygon always go between corner points of the polygon (i.e. no new points or interior points are necessary). Since these points already have colours, we can build a gradient using barycentric coordinates for the triangles in the triangulation. The resulting overall gradient for the polygon has the correct colours along the exterior edges of the polygon but looks inconsistent and odd in its interior.

Since the main primitive in graphics hardware are triangles shaded using barycentric coordinates, if we want a different colouring at the interior of the polygon, we're going to have to add some new points to the interior of the polygon and change the triangulation. As a heuristic, I generate these new points in this way: I find triangle edges that join points that aren't adjacent in the original polygon, and I split that edge. This gives me extra point that I can use to control the colouring at the interior of a polygon.

From there, I calculate new colours for all the interior vertices I've created inside the polygon. I do this by diffusing colours inwards from the boundary of the polygon: I iterate over all the interior vertices, and I set the colour of each vertex by mixing together the colours of adjacent vertices using the ratio given by the mean value coordinates, and I keep doing that until I reach convergence. In actuality, the mean value coordinates of all the interior vertices actually form a linear system of equations that should be small enough to solve so that might be a better way of computing the final gradient than iteratively diffusing colours through the mesh (in fact, I'm not sure diffusing colours with mean value coordinates will actually converge to the correct values). But I already had code for diffusion but I didn't have code for solving a linear system of equations, so I went with the diffusion route.

If we remove the triangle mesh, we arrive at the final result.

The result is similar to the gradient created by diffusing colours, but it still needs more refinement. The area around the white vertex in the middle of the polygon has too much white because the triangles mesh is too coarse there.

Gradients 3: Mean Value Coordinates

Although building gradients through diffusion produces nice results, the actual computation of these gradients is slow and cumbersome. Ideally, we want something like triangle barycentric coordinates but for arbitrary polygons: we want a nice simple equation that can be computed at arbitrary points inside a polygon that provides a nice gradient for us.

Fortunately, such an equation exists. It is called Mean Value Coordinates, and it was constructed/discovered by Michael Floater a few years ago. If you want to calculate the colour of any point in a polygon, you just take the colours of all the corners of the polygon, feed them into the equation described in the paper, and it will tell you how to mix the colours together to get the final result. The equation generates nice smooth gradients with practically all the properties you could want from a gradient such as linear transitions of colours along edges etc. What this means is that instead of having to iterate over the pixels of a polygon repeatedly to diffuse colours over it, you can just compute the gradient in a single pass over the pixels. Below is a picture of how a gradient computed using Mean Value Coordinates looks like. Notice that it is almost identical to the gradient produced using diffusion.

Mean value coordinates seem like the perfect solution for solving all gradient problems. In most cases, they are, but there are still a few tiny issues. One is that the gradients are supposedly not bilinear for rectangles. This means that if you map an image onto a rectangle using mean value coordinates, the image will be warped and won't perfectly reproduce the original image. Although this may be true, my tests with mean value coordinates seemed to indicate that this effect is hardly noticeable.

Another problems arises with concave polygons. When dealing with concave polygons, the colours of the gradients might not stay within the range of colours given to the corners of the polygon. In the image below, a gradient is constructed over a polygon where all the corners of the polygon have a grey value of 0.1 except for the two middle points, which are assigned a white value of 1.0. Although the gradient looks quite nice, some parts of the polygon end up being coloured with grey values less than 0.1. In the right image, pixels with grey values less than 0.09 are coloured in red, showing the region where the gradient is outside the range of colours given at the corners. This is worrisome. For concave polygons, the gradient might contain illegal colour values (like colour values less than zero). This effect also prevents you from creating a gradient of texture coordinates because the coordinates might be mapped outside the range of the texture.

Lastly, although mean value coordinates are much faster than diffusion, you still can't use them directly in real-time animation because they are too slow. Calculating mean value coordinates for a pixel requires merging in all the colours of a polygon's corner points, but there could potentially be a lot of points, especially when trying to recreate a curve using polygons. Trying to do these calculations in graphics hardware would be difficult for polygons with large numbers of points. So some sort of precomputation is needed to use mean value coordinates in an animation.

Gradients 2: Diffusion

The main way of understanding gradients mathematically, is to view them as a 3d surface or 3d patch. The surface is bounded by the 2d shape you are filling, and the height of the surface corresponds to the colour of the gradient. So for a black and white image, the height of the surface function would refer to the grey-level of the gradient. For an RGB colour image, you might have three different surface functions for each of the red, green, and blue values of the gradient.

Finding a gradient then comes down to finding an appropriate surface function or height map that matches the properties that you want for the gradient. This is why many 2d vector drawing programs include support for gradient meshes. The gradient meshes map directly onto well-known mathematical shapes such as coons patches or bezier patches that can be used as a surface for the gradient. Unfortunately, when trying to build a gradient for an arbitrary polygon, gradient meshes are sometimes cumbersome to use because they might not fit into the shape of an arbitrary polygon and they have many control points that need to be adjusted to get the desired effect.

In the last few years, there has been a lot of talk of using diffusion curves for drawing images with lots of smooth shading. Diffusion curves can form a suitable basis for drawing gradients in arbitrary polygons. The main algorithm for actually determining the height map of the surface that forms the gradient is described in Sketch based coding of grey level images. The basic idea is that you specify that certain points have to be certain colours, and the algorithm then tries to interpolate the colours between the points. Since you want the shading to be "smooth," the algorithm should try to minimize how quickly the colour changes across the surface. Since this is a surface, the change in colour at any point can be expressed as ∂f/∂x and ∂f/∂y. Since you want to minimize the change in colour across the whole surface, you should integrate those changes over the surface and minimize that value: ∬(∂f/∂x)² + (∂f/∂y)². If you want to minimize that value, you just have to take the derivative, set it to zero, and try to solve. Solving it requires the use of discrete calculus, the Laplacian, and various numerical techniques.

It all sounds messy, but you can actually skip over all the math and jump right to the punchline. In the final algorithm, all you have to do is, first, set colours for certain points in your image that you want be fixed. Then you repeatedly go over the image, and for each pixel, you set it to the average value of the adjacent pixels. If you keep doing this, colours will eventually diffuse throughout the image, and you will get your gradient.

Below is a gradient I created for a concave polygon with different colours at each point:

Although the gradient is very smooth, the diffusion is too uncontrolled. For example, the colour from the white point at the center of the polygon diffuses to many of the edges of the polygons. This is problematic because it means that the colours along the edges of the polygon are dependent on colours used throughout the polygon. This makes it hard for users to create two polygons beside each other with the same colour along their edges.

The diffusion curves paper solves this by strictly defining what the colours along the edges of the polygon should be. Along the edge of the polygon, the colours should be a linear mix of the colours at the points on each end of the edge. So when doing the diffusion, not only do we set the colours along the ponts of the polygon but along the edges as well. Below is a picture of the result. Notice that the white colour of the point in the middle no longer influences the colours of polygon edges that it isn't adjacent to.

So that's how you can build gradients using diffusion. The main problem with this technique though is that it's slow. Diffusing colours throughout an image until you reach convergence can take a lot of iterations. You can use multigrid techniques to get reasonable speed, which basically means you start with a very low resolution image, and slowly up the resolution as you diffuse your colours. Unfortunately, it's still too slow for real-time graphics like what you would want in a game, for example.

The Gender Politics of 1+1=2

Last weekend, I tried making a little romance game for a game jam. Surprisingly, the hardest part in the design was avoiding all sorts of gender politics minefields that I didn't realize were there. I guess there are so few games centered around romances, that I didn't understand that it's really easy to make an insensitive romance model. There are so many games centered on violence that the minefields in those games are well known: make sure your game isn't exclusively about white people killing non-white people and throw in a token mix of genders and you're generally pretty safe. With romance games, these sorts of politics haven't been worked out yet.

Terminology
Even figuring out something as basic as terminology was really difficult. I wanted to make a regency romance game, with Darcys and Elizabeth Bennets, who you are trying to get married. So the two types of characters in the romance simulation would most easily be named men and women. Of course, a computer simulation doesn't really care about genders, and given my proximity to San Francisco, there's no reason that my simulation shouldn't support the option of men-men, women-women, men-women, women-men, ?-? pairings. But what terms should I use for the two types of characters then? One way to get around this problem would be to only have one type of character, but I was making a tower defence game where the "attacking" characters are distinct from the "defence" characters. I decided to call the "attacking" characters suitors. But what would an appropriate term for the "defence" characters be? After much digging online, I couldn't find anything good. Terms like defendant, target, or wooed just seemed too adversarial or awkward. It's weird that I couldn't find a nice simple term to express the object of one's affections. Finally, after an hour of searching, I just gave up and decided to move on.

Romance Statistics
Since I was building a tower defence romance, the romances needed to be represented numerically so they could be simulated instead of using a hand-crafted narrative that might be possible in a work of interactive fiction. Now in a traditional tower defence, the units have various stats like hit points, attack power, defence power, etc. But what are appropriate stats for a romance? Some stats like social station or income level are considered politically incorrect today, but they can be included in an ironic sort of way. But if you look at a novel like Jane Eyre, beauty and looks do influence romances, so that should be modeled in the simulation somehow. But is it really politically correct to have a game that gives advantages to the good-looking in romances? On the other hand, people would object if someone made a Jane Eyre game where she were depicted as beautiful instead of as plain. After much brainstorming, I figured out that I could use "fashion" as a statistic instead of "looks." Although fashion can be used to model the difference between a plain Jane Eyre and a handsome Emma Woodhouse, it's considered palatable to modern sensibilities because "fashion" is something that can potentially be changed whereas "looks" are considered as more innate.

Romance Model: 1+1=2
After coming up with a few basic stats for the characters in the game, I then had to come up with a model for how romances would work in the simulation. In real-life, romances are quite complicated. Since my tower defence game was intended as a silly little casual game, I wanted to find as simple a romance model as possible.

So suppose you have two characters attending a music concert.
Character A has a music rating of 5.
Character B has a music rating of 3.
How much should the love between A and B increase during the concert?

A*B: Initially, I was thinking of multiplying the two numbers together. The most obvious interpretation of this romance model is that A's interest in music is 5/5, and B's music ability is 3/5. Multiplying 5/5 by 3/5 gives you the amount that B's music ability is able to satisfy A's interest in music. Although the math is symmetric, the interpretation is not. It seems like B exists solely to satisfy the interests of A. I didn't want people to come away with the idea that the "wooed" existed solely to catch the interests of the "suitors."

A+B: Adding the numbers does result in a stretched, but plausible interpretation that's also symmetric. Love between the two characters increases by A+B because their enjoyment of the music concert is dictated by their combined backgrounds in music. By sharing this enjoyable experience, their love for each other increases. The problem with this model is that it results in weird characters statistics as the game progresses. As players get deeper into the game, the game should get harder. You want to make it harder for characters to fall in love as the game progresses to increase the challenge. Characters fall in love slower if their stats are lower. So as players go deeper into the game, they will end up encountering lamer and lamer characters, which doesn't seem right. The characters should get more interesting and have higher statistics as the game progresses not have lower statistics and become less interesting.

-abs(A-B): Taking the negative delta of the two numbers results in a symmetric interpretation that doesn't require characters in later levels to have lower statistics. The interpretation of this approach is that two people who share a similar interest and background in music will fall in love. People who have a disparity in their interests will not. This works, but I was worried that this interpretation might be too complicated for casual gameplayers to understand.

Overall, this whole game ended up being complicated in a way that is more annoying than fun for me. Perhaps my underlying approach to modelling romances in fundamentally wrong. Perhaps I should have gone for a like/dislike model instead like Miss Management. Ugh. Very frustrating.

Gradients 1: The Problem of Gradients

When I learned math and geometry in school, I always got the impression that it was invented by the Greeks hundreds of years old. So when I got to university, I was fascinated by the fact that many mathematical concepts that we were taught in schools were actually fairly recent discoveries. Then, as I studied things even more, I discovered that there are some pretty basic geometry operations that we still don't know how to do. It boggled my mind that researchers were still trying to work out how certain key building blocks of computer graphics should work. One of those areas is gradients.

Gradients sound like they should be simple. How do we shade in a shape? If we assign colours to the different points on a polygon, how do we colour in the inside of that polygon?

For triangles, we can use barycentric coordinates. If we want to colour a point in a triangle, we draw lines from the corners of the triangle to this point. That creates different areas. The ratio of the sizes of these areas gives us the ratio we should mix the colours at the corners. The bigger the area, the more of the colour at the opposite corner should be used. This technique for colouring triangles is so simple and so elegant that modern computer hardware is designed specifically to draw these gradient-shaded triangles.

Just moving to four sided shapes immediately causes problems. You would think that you could simply cut a four-sided shape into two triangles, and then use barycentric coordinates to colour the two triangles. Unfortunately, this leads to inconsistent results. Depending on how you cut a four-sided shape into triangles, you get different colourings. Below, in the center square, the middle of the square is a mix of red and blue with no yellow nor green: a purple. In the square on the right, the middle of the square is a mix of green and yellow with no red nor blue: a light-green.

Once you move to five-sided shapes or shapes with curvy sides, things become even more complicated. Gradients should be a basic building block for 2d graphics, but in most computer programs only support simple gradients like linear gradients where one side of a shape is one colour that smoothly blends to another colour on the other side of the shape. So that is the gradient problem that still needs solving: how do we colour a multi-sided shape with different colours at its corners?

Observations about Teaching Programming to Kids

For the past year or so, I've been acting as an assistant at various events that teach programming to kids. As an assistant, I don't actually directly teach anything up front, but stay in the back helping the kids, which allows me to see what material the kids seem to enjoy and understand and what material the kids find boring or complicated. It turns out that teaching programming to kids is tough! There are a lot of complications and constraints that you need to keep in mind when designing a programming for kids. So I'm using this blog post to gather together some of my observations so far.

Setup

• Programming courses are often taught as "one-off" enrichment opportunities for kids. As a result, you only have 1-2 hours to teach everything that you're going to teach. You can't really teach material that gradually builds up to something advanced and cool. You have one go to teach kids enough to be self-sufficient in some task and you need to inspire them to pursue additional learning on their own.
• The kids are usually fairly young, definitely pre-highschool. High school kids are usually "too cool" to get dragged off to such events (they'd be scared away by all the younger kids anyway), and are usually mature enough to simply learn programming on their own anyway.
• Kids are often ok with installing all sorts of weird crap on their computers, so as long as you're there to help with the installation, you can install all sorts of weird IDEs if it helps.
• On the other hand, some of the kids have really old, crummy computers laden with viruses, so it's better to stick with simple, well-tested things that will work even on old computers. Definitely don't write your own software for such an event because you won't have time to test it on all the weird bizarro configurations that the kids are going to come in with. 10 year old Macintosh, Chromebook, IE5, iPad, Linux-boxen, brand-new ultra-locked down versions of Windows that they don't have the password for, etc.

What to Teach

• There isn't enough time to learn any advanced concepts, and kids aren't impressed by the inherent "beauty" of certain programming concepts. You need to teach them how to do something concrete that gives them constant feedback on their progress. Teaching things like HTML or graphics works well. 
• Kids can't draw, so teach them how to use images. Better yet, teach them how to include random images they find on the Internet, then they can really customize things and make their creations more personal to them.
• Although kids will often find displaying text on the screen boring, kids are easily amazed at stuff that programmers find boring and trivial. Drawing circles, displaying text on the screen, changing the headline on the webpage of a newspaper, putting stuff on the Internet that other people can download. This provides kids with a sense of empowerment. Professional programmers have lost this sense of wonder a long time ago.
• Kids will have different levels of experience and will progress at different rates. If you only have a single "project," some will finish quickly while others will fall behind. Ideally, you should have an open-ended project where kids who finish early can keep adding their own stuff to their project while other kids are still working through the more basic material. It might also be possible to have a mix of both basic and advanced material in the same course (those who fall behind can skip the advanced material), but I'm not sure how well that would work.
• Kids are willing to accept things on blind faith and are ok with using stuff they don't understand. They're fine with blindly typing in a magic recipe that makes the computer do interesting things. Most of the things they encounter in life are already like that, so it's ok to them. Cars move around as if by magic, babies are delivered by storks, monsters are under the bed, typing in five lines of incomprehensible math magic makes the computer do something cool. Whatever. Often, you can use this as a short-cut to teach them how to do something cool even if the material is way too advanced for them to understand.
• Do you know what's even better than displaying some text? Cat pictures. With a teddy bear background. And flashing text. And the images move five pixels to the left when you put your mouse over them. And there's a dinosaur that randomly zips around the screen. And let's have some background music. Awesome. These are kids. They aren't interested in publishing essays on the Internet about saving the environment. They want ninja cat pictures with jetpacks. Give it to them.

How to Teach

• Teach concepts concretely--don't teach things as abstract concepts. Don't go from abstract to concrete. If possible, try to go concrete to abstract. Get them to type something and see what it does. Then help them generalize the concrete instance to the abstract.
• It's important to break things down to be as simple as possible. And kids often don't know a lot of math at this age either (don't include math or algebra or decimals or possibly even negative numbers)
• Try and avoid building advanced material on top of simpler material. Some kids will fall behind on the simpler material and will just be lost for the advanced material.
• Kids learn by doing, so don't lecture. They'll zone out and get bored. I'm an adult, and even I often zone out and get bored if a lecture goes on too long.
• Children are pretty trustful of authority, so they'll make an honest attempt to follow along with your lesson regardless of how ill-prepared and incomprehensible you are. So even if you botch things up, it's ok because the kids will blame themselves and not you if they find that they can't understand the material. I'm not sure if this lack of meta-learning might extend to an inability to do self-assessments as well.
• Kids often don't ask for help if they fall behind. Instead, they'll just sit quietly and fumble along. Along these lines, telling kids to "put their hands up if they're behind or need help" isn't going to work. Many kids would die of embarrassment if they put up their hands. It might be better to ask kids the opposite (put up your hands if you've finished), but I'm not sure if that would be effective either.
• Be flexible and be observant. Often, the class falls into complete disarray after the first hour is done. There's no need to punish everyone further by plowing ahead. Adapt your material, or if that's not possible, just end it.
• It's ok to let kids just do their own thing. Kids learn by doing, and if they're happy taking a few things you've taught them and making it their own by using those few small elements to make something meaningful to them, that's great. You've only got an hour or two, there's no need to push them to do harder stuff. Try to adapt your material to what they're doing.
• Source code is hard to understand (but this is true of adults too). When you show source code, you must SLOWLY go through every single line and statement
• Many presentations involve the presenter typing up code live on the screen. Doing this helps you slow down and helps kids know where to type things. But the text is usually too small (IDEs often falls apart when you make the text big enough to read from the back of the room), and you still type much faster than a kid can type, so they will usually fall behind.
• Young kids can't really type. Programming environments like Scratch that have very little typing are great. I can't recommend Scratch enough. It's very consistent and discoverable. If you show kids a few small tricks, and just let them loose, they can usually work their own way into figuring out how to do cool stuff on their own. You only need to intervene every once in a while to show them more advanced tricks they can use or to direct them into building more fruitful things.

Scarborough Subway Plans

During the last few months, talk about building a subway in Scarborough has been cropping up again. Personally, I find this a little worrisome. Although my usual philosophy towards transit is that is that building anything is better than building nothing, building a subway is Scarborough just seems like a big waste of money that will sap money away from more important projects. Subways exist because they provide capacity and speed for transit users. There is no evidence that Scarborough is in need of either. If there were capacity problems, the TTC would be running high capacity buses in dedicated bus lanes, but they're only starting to consider deploying high capacity buses now. If speed were a problem, the TTC would offer a highway 401 bus or have special buses to redirect people to GO train stations, but they aren't. The reality is that suburbs are designed for cars and building a mass transit system there for moving hundreds of thousands of people would be a waste of money. In order to achieve increased capacity and speed in a transit system, you need space. In high density areas, there's no space, so you need to build subways. In the suburbs, there's plenty of space, so there's no need to build subways to achieve capacity and speed goals. For the price of a subway, you could probably just buy out whole suburban neighbourhoods, plow them under, and build a fast surface bus or train instead.

But to make sure I wasn't judging anything unfairly though, I decided that maybe it would be good idea to run some simulations to see what the effect of different subways plans would be. Following the same experimental methodology from my previous simulations, I ran some simulations of the effect of different plans on transit times to downtown. I believe that all of these plans would end up costing around $1bn-$2bn. Following the METROLINX guides, surface LRTs are modeled as having an average speed of 22km/h while grade-separated LRTs and subways are modeled as having an average speed of 32km/h. The future Eglinton LRT is included in the simulations even though it does not offer any benefits to people in Scarborough going downtown (though it would useful for people going to midtown).

Current System

As a baseline, here is a map of transit times of the current transit system in Scarborough. This system is actually unsustainable because the Scarborough RT line from Kennedy station to Scarborough Town Centre is obsolete, over-capacity, and needs replacement.

Transit times to downtown.
Data, imagery and map information provided by MapQuest,
Open Street Map and contributors, CC-BY-SA. 

From the map, it can be seen that most transit users in Scarborough need about an hour to reach downtown. Most transit users don't live near a transit line, so they need to take a bus to the Scarborough RT line or to the Yonge line in order to reach downtown (people north of the 401 who don't live on Sheppard generally don't take the Sheppard subway because it only comes once every 7 minutes, so it's faster and more convenient for people to take an express bus direct to the Yonge line). Scarborough is laid out as a grid of major roads. Inside each grid square is a tangle of residential roads that are generally impassable by buses. As such, a transit user must walk to the nearest major grid road and take a bus from there. I suspect that this is part of the reason for the short distance between bus stops (as compared to suburban bus systems in other cities). Although this results in slower buses, transit users already have to walk some distance to reach a major road where buses run, and it would be unfair if they have to walk another half kilometre along the road to reach a bus stop. Buses in Scarborough generally run along these major roads, forming a grid pattern. One exception to this pattern is that many buses are rerouted to Scarborough Town Centre, which is intended as a transit hub for Scarborough.

Sheppard LRT with SRT Revamp and Extension

The default transit extension that will be built by the Ontario government if there is no political interference is an LRT along Sheppard and an extension of the SRT to Sheppard and Markham. The Sheppard LRT is modeled as coming with a six minute frequency, similar to the frequency suggested by METROLINX for the Eglinton LRT. The frequency of the SRT was not adjusted (I think it has a 3-4 minute frequency during rush hour) even though it will likely come less frequently after the revamp because newer high capacity trains will be used on the line after the change.

Transit times to downtown with a Sheppard LRT and SRT extension.
Data, imagery and map information provided by MapQuest,
Open Street Map and contributors, CC-BY-SA. 

The Sheppard LRT does not provide any benefit over the existing system. Current Rocket express buses already reach an average speed of around 20km/h, which is similar to the speeds expected to be achieved by the LRT. The Rocket express buses also come more frequently than the LRT, so the LRT won't provide any benefit over the existing bus system in terms of transit times. The LRT will likely be cheaper to run than the bus system though. The SRT extension does seem to save transit users living on Markham south of the 401 about 10 minutes. People who live along Sheppard in Malvern will also see savings of about 5 minutes in transit times. These time savings might disappear though if the revamped SRT is run at a lesser frequency than it currently does since all the time savings of having a faster mode of transport will be lost by having to wait longer for the train to arrive.

Sheppard Subway Extension to Victoria Park

Historically, the long-term plan for a subway in Scarborough is an extension of the Sheppard subway to the Scarborough Town Centre. This would be prohibitively expensive, so current suggestions are that an extension of the Sheppard subway to Victoria Park could be used as an intermediate step to demonstrate the benefits of a full subway.

Transit times to downtown with a Sheppard subway extension to Victoria Park.
Data, imagery and map information provided by MapQuest,
Open Street Map and contributors, CC-BY-SA. 

A subway extension to Victoria Park provides a ten minute in transit times for people who live at Victoria Park. People who live on Victoria Park near Sheppard will see a 5-8 minute improvement since they don't have to change buses at Sheppard in order to get to the Sheppard subway at Don Mills. People living on Sheppard west of Agincourt will see a modest improvement in transit times since they can transfer from a bus to a subway at Victoria Park instead of having to cross the 404.

OneCity Subway

Recently, there has been a suggestion that the SRT should be scrapped and the Bloor subway should be extended to Scarborough Town Centre and then up to Sheppard. This will supposedly result in faster travel through Scarborough because no transfer from the SRT to the subway will be needed at Kennedy subway station.

Transit times to downtown with the OneCity extension of the Bloor subway to Sheppard.
Data, imagery and map information provided by MapQuest,
Open Street Map and contributors, CC-BY-SA. 

Eliminating the SRT results in a sharp reduction in service in the area around the SRT. There is also a surprising increase in transit times for people living in Agincourt since they no longer have a short bus ride to the SRT. Instead most of the transit benefits of having a nearby transit line are pushed east to the Scarborough hospital and Malvern West.

"Subway" to Pacific Mall

Out of curiosity, I decided to model the effect of scrapping the SRT and building an LRT along the train corridor from Kennedy to Pacific Mall in the north. One problem with building rapid transit lines in Scarborough is that the main transit hub for the area, Scarborough Town Centre, is in the middle of nowhere. It is not near the major transit corridors of Scarborough, so many buses actually have to be redirected from their natural routes in order to reach there. The only major transportation corridor that the Scarborough Town Centre is near is Highway 401. As can be seen from the 2006 strategic plan for the SRT, 75% of SRT users ride a bus to reach it with users mainly coming from Malvern, Malvern West, and the Milliken area. So instead of designing a squiggly line of a system, I decided to see the effect of building the longest, cheapest, grade-separated "subway" possible that would intersect as many existing bus lines as possible--i.e. an LRT along the current train corridor from Kennedy to Pacific Mall. Such a line has more potential for provincial and federal government support since it serves multiple regions (Markham and Scarborough) at a modest cost, can be easily extended later on to the Highway 7 BRT, and much of the electrical infrastructure will be needed in the future anyway for the GO train network. This LRT was modeled as having a frequency of six minutes. Unfortunately, it's not really possible to model the effect of such a transit line accurately since many of the current bus lines are designed to send people to Scarborough Town Centre; whereas, in this system, buses would mainly run east-west so as to dump people off at the rapid transit line running through the middle of Scarborough.

Transit times to downtown with an LRT along the train corridor to Pacific Mall.
Data, imagery and map information provided by MapQuest,
Open Street Map and contributors, CC-BY-SA. 

Unfortunately, the simulations show only modest benefits from such a system. Near Sheppard, the train corridor is a little too far from Kennedy and Midland to make walking there worthwhile as compared to taking a bus down to the SRT. At a frequency of every six minutes, transfers to the line take too long, and transit users will often find it easier to simply take a bus directly to the Yonge subway. Arguably, the same thing will happen in a revamped SRT if it has a six minute frequency as well though. I think this scenario is too difficult to simulate using my current approach, so it's impossible to compare it with other approaches.

Conclusion

The pressure to build a subway in Scarborough seems to be based primarily on politics than on a genuine need. They feel that they deserve a transit showpiece comparable to what's available in northern and south-western Toronto. This is not a bad thing, but it means that potential transit plans should be evaluated primarily in terms of minimizing construction and operating costs. The cheapest transit line that satisfies the political needs without damaging the existing transit system too much.

For this reason, I actually think the Sheppard LRT and SRT extension project is probably best. Surprisingly, this project will actually result in worse transit times for people living in Scarborough because the increased capacity of the new lines will mean that transit will likely be less frequent than the current system. The project will likely have lower operating costs than the current system, which is the main benefit of building it. The grid spacing of Scarborough also seems to favour east-west transit lines over north-south transit lines because it's often a shorter walk to get to a north-south bus line (which can then take you to an east-west rapid transit line) than to get to an east-west bus line. To save even more money on construction costs, it might even make sense to abandon the Sheppard LRT and only build the SRT extension since the Sheppard LRT doesn't actually do anything interesting from a transit perspective.

Of the two plans that actually involve building real subways--the OneCity plan and the Victora Park extension--I actually prefer the Victoria Park extension. The OneCity plan is more expensive and the expense mostly goes towards shifting an existing transit corridor 2km to the east for no particular benefit. Overall though, I think both plans are bad because they are expensive, unnecessary, and will likely increase operating costs for the TTC. In any case, neither of these plans are feasible because neither the city nor the province have the means to pay for it. The province has run out of money, and my understanding is that they can only find money for new construction through the use of accounting tricks. They are mainly interested in building self-contained new transit lines that can be leased to private industry or mortgaged, thereby allowing the province to hide the cost of the construction by spreading it over many decades instead paying for construction upfront or something complicated like that. Subway extensions aren't self-contained, so they can't be owned and operated independently by private companies, so they don't qualify for accounting trickery, so the province can't fund them.

I'm still partial to my idea of building a "subway" to Pacific Mall. It's a big transit showpiece that can be built at a modest cost, the surrounding area are likely good candidates for densification, and I believe it would be eligible for provincial funding. Unfortunately, it's hard to simulate the effect of such a massive change to transit, so its effects on transit usage is unclear. It might be a little bit too close to the Yonge subway line, so people might still prefer taking a bus to Yonge and riding the subway downtown as opposed to taking a bus to the train corridor, taking a train to Kennedy, taking a train to Bloor, and then taking the Yonge subway line down into downtown. Also, the abandoning of rapid transit to Scarborough Town Centre is likely too politically controversial for politicians.