Explaining the Hexagon Layout class #
On the Hexagon Implementation page I have a Layout class that controls how to convert back and forth between hexagonal coordinates and screen coordinates. It has parameters (size.x, size.y, origin) that aren't explained on the hexagon concepts page. That's in part because they complicate the explanation and aren't hexagon-specific. The size is a standard scale transform and the origin is a standard translate transform. Although I have some explanation on the implementation page, it's not very good. I made some improvements:
Introduction to hexagons, part 3 #
In part one, I described how I was making a new diagram for my hexagon grid guide, but that I didn't know how to evaluate the design choices I had to make. In part two, I described how I looked at the introductory section of the page to decide the purpose of the new diagram and how it fit in with the others.
Introduction to hexagons, part 2 #
In part one, I described how I created lots of variants of a diagram to try to figure out which one to use on my hexagon guide.
Introduction to hexagons, part 1 #
When I started making interactive diagrams the hard part was making them interactive part. But over the years I've gotten much better at that. Now the problem is designing the diagrams. A few weeks ago I was looking at the beginning of my hexagons guide to see what I could improve. I noticed this paragraph had no corresponding diagram:
In math, the "circumradius" is the distance from the center to a corner (I call this size); the "inradius" is the distance from the center to the middle of an edge, sqrt(3/4)*size. The "maximal diameter" is twice the circumradius; the "minimal diameter" is twice the inradius. Wikipedia has more.
My first thought was to add a diagram for this. I already have a diagram about angles, so I could add a diagram showing the inradius and circumradius:
Redesigning my circle diagrams, part 2 #
In the previous post I described how I redesigned some of the diagrams on my circle drawing page. I found that I had been reusing code in ways that made the diagrams worse. I switched to more copy-paste programming to make the diagrams better.
Labels: design
Redesigning my circle diagrams, part 1 #
Linus Arver's post about circle drawing reminded me that I wanted to add circle outlines to my circle fill page. My page is focused on circle fill rather than outline, but one of the fill algorithms can be adapted to generate outlines instead. I added a section on circle outlines, reusing the code from the circle fill diagrams. Unfortunately … I didn't like the result.
Labels: design
Hex diagram labels #
A few weeks ago a reader suggested the labels on my hex diagrams for the "cube" coordinate system could be improved. I took a look at what I had:
Pathfinding diagram improvements, part 2 #
In the last post I described improving the diagrams on my Tower Defense page. Once I finished that, I moved on to my other pathfinding pages, starting with the A* page.
Labels: design , making-of , pathfinding
Pathfinding diagram improvements, part 1 #
Back in April I wrote about some pathfinding diagrams I was unhappy with. Last month I wrote about reimplementing the diagramming code.
I started with the Tower Defense page. It's smaller than the A* page and I wanted to try out some ideas there before adopting them on the more popular page.
Labels: design , making-of , pathfinding
Sliders on 2d visibility article #
While investigating a report from a reader, I realized that the sliders on my 2d visibility article are a little messy. There's a fade out animation that goes from here:
Labels: design
Graph search diagrams and reusable code #
Every once in a while I revisit my pages to see how I could improve them. This is one of the reasons I prefer text to video: I can keep improving it instead of treating it as "published" and then never changing it. I have been updating some of my pages for over twenty years. I started thinking about the Introduction to A* page again when I read a page about online interactive learning and a page about the expertise reversal effect. I made a list of some things I could improve in my diagrams, but also why I had done them the way I did.
Website updates #
Over the last few years I've been trying to increase the accessibility of my site. I have 25 years of web pages that I maintain so it was a lot of work to do all at once. I split it up into multiple phases:
- Phase one: I converted 85% of my pages to use a "responsive layout", which takes into account the reader's browser size. I converted pages that had a 600px width and were relatively easy to convert to a variable
pxbased layout. My focus was to write responsive CSS rules that smoothly varied the layout and font size based on browser width. I wrote my notes on how to do this. - Phase two: I tackled the 15% of pages that were more difficult to convert, because of their use of non-standard layout, or interactive diagrams, or iframes, or anything else that made it difficult. I wrote a blog post about this. I still used a
pxbased layout. - Phase three: I'm ready to switch from a
pxbased layout to arembased layout.
This is how I often make progress past "analysis paralysis": I break the problem down into smaller, simpler ones and then work on them one at a time.
Labels: design
Printing my pages #
Occasionally someone will want to print one of my web pages, even though it means losing access to all the interactive parts. There are a few things I do to make this work better:
- I try to start all my interactive diagrams in a state where it's informative without interaction. This is not only helpful for printing, but also for people skimming the page. I haven't always done this in the past so I've been trying to go back through my older pages and change them to work this way.
- I have a "print stylesheet" using @media print { … } that changes the page style when printing. It changes the font, removes background colors, removes text shadows, and instructs the browser to avoid breaking the page inside a diagram.
- (Added today) When printing, I display the URLs for the links on the page. Since you can't click the links, it's useful to display the URLs.
Website updates, part 3 #
While updating my website build process over the past week (part 1, part 2), I decided I should also revisit my page layouts. Last year, I started learning about responsive design, studied the theory, and implemented it on my site. I converted 514 out of around 600 pages, and said “The rest are either unimportant or impractical to convert.” Of the ones I didn't convert, some were in a 450px width and most in a 600px width. I wanted to see if I could convert the 450px pages to 600px at least.
Labels: design , infrastructure
Website updates, part 2 #
In my last post I said I was going to update my website layout. I've been working on it for the past three weeks . The main change is responsive design: the page will adapt somewhat to the size of the browser window, including phone and tablet sizes.
Of approximately 600 web pages, I have 514 converted to the new layout. The rest are either unimportant or impractical to convert.
To help myself understand the issues, I made some diagrams:
I wrote up my notes about how I made the pages responsive.
I also fixed some glitches on my pages, and switched from downloaded fonts to system fonts (to make the page load faster).
For testing, Firefox's screenshotting tool and Chrome's screenshotting tool were both useful. I took screenshots before and after a change, and then reviewed the pages when screenshots changed.
# Firefox
/path/to/firefox \
-screenshot \
--window-size=$width,4000 "$url"
# Chrome
/path/to/chrome \
--headless --disable-gpu \
--window-size=$width,4000 \
--screenshot "$url"
Labels: design , infrastructure
Global optimization applied to game design #
Outside of games or even product development, there's a broad problem called global optimization in which you are trying to find the maximum of a function in some space. If we think about a “space” of all possible game designs, then we're trying to find good places in that space. Hill climbing is the simplest approach to function optimization — in each iteration you make a step to improve. The problem with hill climbing is that you run into “local maxima” — you are at the top of your little hill but there's somewhere far away in game design space that's even better. You can't see that far away so you never find those other game designs. Metaheuristics are different approaches to dealing with this for function optimization; some of these ideas also seem to apply to game development:
- Simulated annealing says: start with big steps early on, make smaller steps later on. This already happens with many games, with early development making larger changes and post-launch being smaller changes.
- Swarm optimization says: explore multiple places at once. Early on, you can prototype many different related games, and then see what works well and what works poorly. Later in development it's impractical to build many different games but you can explore small variants with A/B tests.
- Genetic algorithms says: explore lots of places at once, randomly mutate them, and make copies of the best solutions. This seems like what the modding community provides. Let them explore many alternative sets of game rules, and then incorporate the best features into other mods or into the base game.
- Variable neighborhood search says: alternate between making small changes for a while and then making a few big changes every once in a while. This could mean periodic patches and also bigger changes in the form of expansion packs.
- Graduated optimization says: first optimize a simpler problem, then use the solution to simpler problems as a starting point for exploring a more complex problem. This happens in games that start small and grow more complex over time.
Are there other techniques you use to avoid your game design getting "stuck" in a local maximum?
Labels: design
Outside the box #
I write interactive explanations; I'm always looking for simpler ways to explain things.
Think back to every technical paper you've read. The text connects to diagrams by using text such as "see figure 4". Maybe it's more specific and says "in figure 4 see circle 24". Maybe it's a hypertext link. However if I look at how I take notes on paper, I don't do that! I just draw an arrow to the thing I want to point to.
From an early age we have invisible boxes around text and diagrams, keeping them apart. It doesn't have to be this way. Pointing is the simplest way to direct attention to something. Why don't we do it more? I don't know, but these are the kinds of things I'm exploring on the web.
How did I implement this? The first guess would be that I'm using
a giant SVG overlay that covers the area between the pointer and
the target. I'm not! That's
the only SVG element in this blog post. What's the trick? By default, the overflow for an SVG element is set to hidden; in some versions of IE it was visible and
I had to set it back to hidden. That keeps the content inside its
bounding box. But the IE situation made me wonder — if I set it to visible,
what happens? It turns out you can draw outside the box! This
seems to work across the browsers I've tried.
The second thing I need to do is construct an arrow path. The
source and target of the arrow may be in different SVG elements,
or they might not be SVG at all. For this page I use
an invisible span
in the text as the anchor. I use getBoundingClientRect() to
get the coordinates on the page. Then I pick the midpoint of one
side of the rectangle as the arrow source or target. I need to
translate all the coordinates into the coordinate space of the SVG
I'm drawing into.
For this demo I hard-coded the size, curvature, and directions of the arrows. I don't adjust them when the page is resized. For a reusable library, I think it'd be cleaner to have one svg per arrow anchor.
Prospect theory and utility functions #
(Note: I'm going to try writing more unpolished things on this blog and leave the polished articles to redblobgames.com.)
The utility functions I learned in economics are history-agnostic. They look at the current state of the world and calculate a “utility”. For example, you might say the utility of money is the logarithm of the amount of money you have.
Prospect Theory says that this view of the world does not match how people actually behave. Instead, the history of how you got to a certain point matters in how you value it. There's an asymmetry around a “reference point”:
(credit: Wikipedia, Prospect Theory page)
Consider these scenarios:
- You get $200 and have a 90% chance of losing $100 of it.
- You get $100 and have a 10% chance of gaining an additional $100.
These are mathematically equivalent. Both have a 90% chance of giving $100 and 10% chance of giving $200. However, they are not equivalent to humans. That's because humans consider not only the final result but how it was reached. Having $200 and then losing $100 feels different from having just the $100 in the first place. Even though the outcomes are the same, the reference point is different, so it feels different. Prospect theory takes this into account somewhat.
In game AI, I've only used regular utility functions. However, it seems reasonable to try using prospect theory in some way. Even prospect theory isn't complete; there are more human behaviors in decision making and valuation that it doesn't account for. Maybe FTT or something else. But sometimes you want to balance simplicity and comprehensiveness. In any case, it's something I'll want to ponder the next time I'm writing AI evaluation functions for NPCs.
Map homunculus #
Suppose I’m telling a story about someone walking through the woods to get to grandma’s house. Let’s look at how much time is spent in each activity:
I don’t write the same number of sentences in the story on each minute of the adventure. The sentences might be distributed like this:
Let’s look at how interesting each part of the story is over time:
If the storyteller were forced to match the pacing of the story with the amount of time each actually took, we’d have long periods of boring story.
Instead, the storyteller can stretch out interesting times and compress boring times to more evenly distribute interesting events:
Let’s look at where the events occur on this distorted timeline:
They’re much more evenly distributed.
Think about every story you have read and every movie you have watched. Most of them will stretch and shrink time by omitting or elaborating various details. They also use flashbacks and replays to further disconnect the time you experience from the time in the story.
We want to do this in many types of games.
In a game that directly tells a story, you can follow the technique used by storytellers. But what about more open ended games?
If you can’t stretch and shrink time, try to stretch and shrink space.
Let’s look at some games that stretch and shrink game maps.
Ultima IV-VII
Ultima 4 and 5 have a continental map that’s almost all wilderness. In Ultima 6, the towns were integrated into the world map. Surrounding areas were shrunk to make room for the towns. In Ultima 7, the towns grew even larger and boring parts of the wilderness shrunk even more. Here’s a rough sense of how that looked:
Ultima 4
Ultima 6
Ultima 7
If you want to see the actual maps, there’s a high resolution map of Ultima 4 from Nick Moore, and there are high resolution maps of Ultima 6 and Ultima 7 from Ian Albert. You can find some scans of the cloth maps that came with these games on Xe Dragon’s site.
Let’s look at the path from Trinsic to Britain. In Ultima 4, most of that time is in the wilderness, which I found relatively uninteresting in that game:
Ultima 4 and 5 solved this problem by having a separate map for towns. When you entered the town on the main map, you were taken to a more detailed map with the town. Ultima 6 and Ultima 7 solve the problem a different way, by changing the world map:
By stretching and shrinking the map, the Ultima series made the walk from Trinsic to Britain more interesting, but less realistic.
Skyrim and World of Warcraft
Ultima not only shrinks the repetitive areas between cities but also repetitive areas within cities. Most buildings have something interesting inside; other buildings are omitted.
The same is true in many other open-world games. Skyrim’s towns have very few people. Wowwiki says World of Warcraft’s Stormwind City has 200,000 residents. Walk around and you’ll see fewer than 100 buildings and people. Both games also shrink wilderness areas relative to cities. Stormwind City is as large as Elwynn Forest. Towns are much smaller than realistic towns would be; wilderness areas are extremely small compared to realistic counterparts.
Civilization and Age of Empires
We see this same pattern in conquest games, but it manifests differently. You’re not an adventurer walking across a map but you instead control military units walking around. Repetitive elements include wilderness, natural resources such as trees, military units, and town buildings. Each of these is reduced in size or number. A large army may consist of tens of “soldiers”.
Civilization also has a slowing of time. At the beginning of the game, a turn might mean 50 years. At the end of the game, a turn is only 1 year.
Transport Tycoon
In a transportation game the repetitive elements will be vehicles. A freight train in real life might have hundreds of cars but in Transport Tycoon will have fewer than ten. This makes cars easier to manage. A freight track might be 100 trains long; in Transport Tycoon distances between resources are shrunk so the track to train length ratio is much smaller than in real life. This also alters the balance for gameplay. Relative to real life, trains meet each other much more often. Double tracks and complex junctions are needed far more often than single track, making the layouts far more interesting and fun.
To ponder
Look at the player’s experience in your game. Identify the repetitive elements, both things the player has to look at and the things the player has to do. Shrink repetitive elements in time and/or space. Expand interesting gameplay elements to occupy more of the time and space. These changes will reduce realism but increase fun.
Update: [2015-06-25] Added chart showing relationship between reader's time and story's time.
Auction Houses #
(image from NecroRogIcon on Flickr), CC BY 2.0
I used to play the auction house part of World of Warcraft. I noticed that when I want something as a trader, I'm often willing to wait the 24-48 hours with a “bid” offer. But when I'm crafting or just wanting to play, I'm less patient, and I prefer the immediate gratification of the “buyout” offer. When I was selling, I'd just set the bid to be slightly below the buyout, but I'd also have multiple overlapping offers at different prices, different time periods, and different stack sizes.
There's an asymmetry between the buyer and seller in WoW's auction house. Sellers don't need immediate gratification. Buyers do. The “buyout” feature is used a lot. There's no corresponding “sell immediately” feature.
This isn't a new observation. EBay started as an auction site but now has a lot of traffic using “buy it now”. The difference is that in WoW, buying something is even more immediate — you walk to your mailbox and have a shiny new sword waiting for you — with no waiting for shipping.
If I were designing an efficient marketplace for a game focused on the buyer, I'd simplify. If all I want to do is buy a Fire Sword, what do I need to know? The lowest price. I don't need to know all the listings and who made them. I don't need to know the listing time period. I don't need to know all the higher prices. I don't need the complexity of bidding and the waiting time.
What do I do with the following table? Decide which item I want. Also, decide whether to pay more to get an item now or wait a bit and pay less. Also, if waiting a bit, there are multiple options for how long to wait and what the price is. Also, estimate the risk that I may not win the auction because someone outbids me. Also, should I buy two at a discount and then re-sell one of them?
| Item | Number | Level | Low bid | Current bid | Buyout | Time Left | Seller |
|---|---|---|---|---|---|---|---|
| Fire Sword | 1 | 3 | 31 | 37 | 45 | 14:31 | Stoneplanter |
| Fire Sword | 1 | 3 | 23 | 39 | 51 | 9:27 | Azlishan |
| Fire Sword | 1 | 3 | 18 | 61 | 78 | 1:35 | Morianna |
| Fire Sword | 2 | 5 | 33 | 74 | 88 | 38:03 | Flyv |
| Fire Sword | 1 | 3 | 34 | 38 | 60 | 8:53 | Sven |
| Ice Sword | 4 | 1 | 81 | 103 | 130 | 4:39 | Linkshot |
| Ice Sword | 4 | 1 | 10 | 105 | 149 | 10:30 | Mordn |
| Ice Sword | 4 | 1 | 95 | 109 | 145 | 3:46 | zxcv |
What do I do with the following table? Decide which item I want and whether I'm willing to pay that price. That's all.
| Item | Level | Lowest price |
|---|---|---|
| Fire Sword | 3 | 45 |
| Ice Sword | 4 | 130 |
On the other hand, complexity adds friction. And friction adds inefficiency. And sometimes you want inefficient markets because they're more interesting for gameplay. The trading game is fun! You can play with multiple prices, different stack sizes, overlapping time periods, cornering markets, hedging, reselling for profit, etc. It's just not a great interface for someone who just wants to buy a sword. Unless trading is a big part of the game, I'd want something really simple. Tell me what I can buy and what the price is.
Labels: design