Blobs in Games

From Red Blob Games's Blog

Notes on line drawing on grid maps #

I'm not a fan of Bresenham's line drawing algorithm. I know, it's fast, and sometimes you want to complicate the code for speed. But these days, fast line drawing is going to be done by the graphics library. I only need line drawing for analyzing grid maps in my game. Line drawing performance isn't critical anymore for me, so I prefer using a much simpler algorithm. I decided to write up my notes about that.

I don't like that Bresenham's algorithm has separate cases for 8 octants. You can collapse some of these with a series of if statements, but I prefer interpolation, where there aren't different cases. I don't like that some presentations of Bresenham's algorithm handle only one octant and leave the rest as an exercise to the reader. I don't like that some implementations of Bresenham's swap the endpoints, which is fine for drawing lines, but not as good for game algorithms such as moving an arrow from the player's bow to the enemy orc.

I like that the linear interpolation algorithm reuses concepts that are useful for other parts of my games. I also like that the same line drawing algorithm works on 3d grids and hex grids. I like that interpolation as a concept can be extended to angles, times, spherical rotations, and other things. I like that linear interpolation leads to non-linear interpolation, often used for animation.

Interpolation is both more general and simpler than Bresenham's algorithm. I use it for lots of other things, so I use it for line drawing too, instead of using a different specialized algorithm for line drawing.

I wrote up my notes about line drawing using linear interpolation

What went right?

1. Org-mode
   

   I've been trying out emacs org-mode for some of my smaller articles. It worked really well in this case. I used org-babel, which lets me embed source code along with the article text. For each block I can choose whether it gets output as javascript, in the html, or both. The code I present is the same code used to power the diagrams (for the most part).

   You can see the org-mode source here.

2. Diagram class
   

   I wrote a small diagram class that let me turn on various optional features. I then instantiated it for each of the diagrams on the page, enabling different features for each.

   • All the diagrams show a grid.
   • Some diagrams show a single interpolation point, controlled through a number control on the page.
   • Some diagrams show many interpolation points. The number of points is either calculated automatically or controlled through a number control on the page.
   • Some diagrams show a "track" that contains the interpolation points
   • Some diagrams show draggable endpoints. In the end, all of them did, but during development I wasn't sure if I'd do that.

   I also have various hacks that aren't cleanly put into the diagram class. That's ok. I'm trying to make a pretty page, not make pretty code. I make pretty code only if it helps me make the pretty page more quickly. Unlike most software projects, there's not much maintenance over time, so that up-front investment usually doesn't pay off.

3. Draggable numbers
   

   I have a draggable number library that I haven't shared yet, but I've used for a few unfinished projects. I used it here. It's like Bret Victor's Tangle but uses D3 instead of MooTools.

4. Draggable markers
   

   I used draggable markers that I explained here and they worked pretty well.

What went wrong?

Scope creep was the biggest problem. It's just line drawing. I thought it'd be quick to write up. But I kept thinking of more things I wanted to add.

1. Scope - algorithms
   

   My original plan was to explain two line drawing algorithms, but the more I worked on those, the more variants I started finding. I added the supercover line drawing, but I had several more I wanted to add when I realized … I should just stop and publish the article.

2. Scope - topics
   

   As I got into interpolation for 2d grid lines, I realized that other aspects of interpolation are pretty cool too: non-linear interpolation (used in animation "tweens"), hex grid lines, 3d grid lines, interpolation in color space.

   I even had written interactive demos for interpolation in different color spaces, comparing RGB, HSL, HCL, Lab, but I ripped it all out when I realized I was going way outside the scope of the page.

3. Scope - interactivity
   

   Bret Victor had talked about how the technology of the printing press led us to separate images and text, and we keep doing that on the web even though we don't use moveable type anymore. That made me wonder what kinds of things I'd like to do for explanations that break out of my standard format of text separated from diagrams.

   What first came to mind was what I do on paper: I make arrows that point from one thing to another thing, even if it's not in the same "box".

   I started implementing this, and was quite happy with what I had, but decided it wasn't worth the effort for this article. I ripped it out, and will try it again for another article. It was a neat effect that I don't see people using. Try mousing over this paragraph, and you'll see an arrow pointing back to the section heading:

In the end…

I needed this small project. I've been sort of stuck since September, so this got me going again. I often find that when I'm stuck, I need to do something simpler, and then work my way up again.

Labels: grids , making-of

Implementing draggable handles #

People ask me sometimes how I make my interactive tutorials. I'm going to write some “making of” articles to share the techniques I use.

For some of my projects I want the reader to drag something around on a diagram. I use the position to control some aspect of the diagram. The curved roads page uses this. I want an easy way to constrain the ways you can drag something, and I also want a way to transform the variable being controlled into a position on the screen. Here’s an example of the kinds of things I want to be able to do:

Read more…

Labels: making-of

Touch events on the pathfinding pages #

(On this blog I'll sometimes go into the “making of” the game programming tutorials I post on my site.)

For my pathfinding pages I wanted to support "painting" on the map to make or erase walls. When you change the map, the pathfinding algorithm updates the paths. Here's how paint works:

Set up mousedown, mousemove, mouseup event handlers on all the tiles.

1. When you press the mouse button, I toggle the tile you're pointing to.
2. When you move the mouse, I set the tiles you pass over to match the tile you first clicked on.
3. When you release the mouse, I stop tracking the mouse.

For example, if there are three tiles A B C and you are over A without a wall, then press the mouse button, I put a wall at A (toggle). If you then move the mouse over B, I make B a wall (set to whatever A has). And then if you release the mouse over C, I'll set C to a wall as well.

When I first published the Introduction to A* article two weeks ago, I still had an item on my bug list to fix map editing on a touch screen. I wasn't sure why it wasn't working. I figured the touch events touchstart, touchmove, touchend would map cleanly to mousedown, mousemove, mouseup. But they didn't. After some debugging, I figured out that the touchmove and touchend events get sent to the object that received the touchstart event. That means instead of seeing A.mousedown, A.mousemove, B.mousemove, C.mousemove, C.mouseup, I am seeing A.touchstart, A.touchmove, A.touchend. I don't receive events on B or C at all.

To fix this, for touch events I look up the x,y position of the touch and map that back onto a tile. This is sort of annoying, as I figure browsers already have a way to map pixel locations to SVG DOM objects, but I don't know how to harness that lookup. Fortunately, most of the diagrams are simple square grids, so the code to map pixels to grid locations is easy.

There are some more tweaks for the page to work well on touch screens, but it should mostly work now.

Labels: making-of

Pathfinding on isometric grids #

People sometimes ask about pathfinding on isometric grids. This is the wrong way to look at it.

You're finding paths in the game world. Isometric is not part of the game world. Isometric is how you look at the game world. Consider the shortest path from New York to San Francisco. Does the shortest path depend on how you hold the map? No! The person looking at the map does not matter. The shortest path is the same no matter how you are looking at the map.

Labels: grids , pathfinding

New Introduction to A* page #

I've been working on updating my pathfinding articles with interactive diagrams. While doing so, I realized that I don't like the way I've presented information in my pathfinding articles. Instead of just updating them in-place, I'm writing new tutorials and will eventually figure out how to stitch everything together.

A big one I've been working on is the introduction to A*. I started writing these notes in 1997 and have updated them over the years. The past few months I've been working on a replacement for this page. The page compares Breadth First Search, Dijsktra's Algorithm, Greedy Best First Search, and A*. Differences from the old page:

• All the diagrams are interactive (of course)
• I mention non-grids a little more (still not enough)
• I use contour lines to compare the algorithms (not sure if this will make sense to people)
• I show working Python code for each of the algorithms
• I have supplemental material that includes the helper functions and classes needed for the search algorithms
• I give some guidance on which algorithm to use

There are lots of little things (smoother animations, touch screen support, better code highlighting, better contour line visualization) that remain, but I decided to publish it 90% complete instead of delaying it to polish all those little details. Take a look at the new introduction and let me know what you think. Is it understandable? Do the contour lines help? Is it enough to help you implement A* yourself?

Labels: pathfinding

Dijkstra's Algorithm and reprioritizing nodes #

I'm working on a tutorial showing how Breadth First Search, Dijkstra's Algorithm, Greedy Best-First Search, and A* are related. I'm focusing on keeping the code simple and easy to understand. {Note: this blog post is a shorter version of a page on my site}.

While tracking down a bug in my Dijkstra's Algorithm code, I realized I had forgotten to implement the "reprioritize" case. That led me to wonder why my code seemed to work without handling that case. It turns out that case is never triggered by the graphs I'm searching over. Let me explore this …

Labels: pathfinding , programming

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.

Labels: design , ideas , math

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.

Labels: design , maps

Writing more by writing less #

I have a long list of things I want to write about, but the list is getting longer instead of shorter. I've been thinking lately about my writing process: writing down ideas, fleshing them out, learning a topic, writing a blog post, and making diagrams.

It's fun to write code for diagrams but it takes a long time. Bret Victor's talks make me painfully aware of how limited my tools are. Munificent Bob says he draws his illustrations by hand to save time. LostGarden has beautiful diagrams but it takes me a long time to use those tools. I've pondered a Wacom Cintiq or a Surface or a Galaxy Note or even a regular drawing tablet but I think paper and pen is simplest.

• Big pages: 1-4 months, learning + writing + interactive diagrams. These include Curved Roads, 2d Visibility, and Polygon Map Generation. The Noise Functions page was mostly learning, but I had very few interactive diagrams, so it went quicker. The Hexagons Guide was some learning and some things I already knew, and the interactivity is low, so it went quicker.
• Medium pages: 1-4 weeks, for topics I know, writing + interactive diagrams. Tower Defense Pathfinding and Probability for Damage Rolls would fit in this category. I knew the topics well, so much of the time was figuring out how I wanted to explain it, and implementing the diagrams.
• Small pages: 1-4 days, writing + non-interactive diagrams.

I'm pondering doing more of the small pages. I can upgrade them later if needed.

Labels: making-of

Pathfinding algorithms on grids #

The usual pathfinding algorithms I use — Breadth First Search, Dijsktra's Algorithm, A* — run on graphs. In my previous post I described how grids can be viewed as graphs. Most of the time, pathfinding on grids is fine. However, if you need more performance, grids contain additional structure that standard graph algorithms don't take advantage of. I wrote up some notes about this, either transforming your grid into a smaller graph, or modifying the pathfinding algorithm to harness the structure of grids. It's not something I've had to do in my own projects so if you have additional references or words of advice, I'd love to hear how I can improve that page.

Labels: pathfinding