I've wanted to write a page about coordinate transforms, but I've started it and abandoned it several times.

The first version was about matrices. I had seen Nicky Case's interactive explanation and Max Goldstein's animated explanation but I wanted to write something more basic. I wrote out an outline showing how matrices could be used for translate, scale, rotate, and shear transformations, and how those could be combined or inverted to generate all the effects we want.

After struggling with this for a few weeks, I put the page on hold.

I returned to it after a friend of mine suggested that I take matrices out completely. I had to ponder that for a while. Surely, the whole point of the page was to show how matrices worked. How could I do that if I took out matrices?

I came up with a new outline that pushed matrices to the very end. I covered all the transforms first, with simple code to implement each. If you have a series of transforms A, B, C, and you want to transform point p, you can call C(B(A(p))). At the end I introduced matrices as a uniform representation of all the different types of transforms. They also offer a way to combine transforms together, so that you can call (C ∘ B ∘ A)(p).

I had implemented lots of interactive diagrams for this page (see the draft version), but in the end I was unhappy with that version too.

There's a technique called 5 Whys (or 3 Whys) that I should've tried.

Why do I want to explain matrices? Because they are a nice way of implementing transformations.

Why do I want to explain transformations? Because they are a uniform way of thinking about operations we need in games: translate, scale, rotate.

Why do I want to explain translate, scale, rotate? Because they are a clean way to solve problems with game cameras: scrolling, zooming, rotating, and isometric views.

Aha! Maybe that's the real problem: game cameras. Instead of starting with matrices and then explaining how they represent transformations and then explaining how transformations can be combined, I could start with game cameras and then work my way up to transformations and then matrices.

I'm going to make another attempt at an outline for this page starting with game cameras.

Labels:

There are some big things I want to change on my pages, but there are lots of little things too. The big things I keep delaying because they're "big projects" that need a chunk of time. But the small things I've been delaying too, because I keep telling myself I'll do them when I do the big one.

Right now I'm not working on any big projects so I'm tackling some small improvements. This week I improved the path reconstruction diagram on my A* introduction. It looked like this:

Low contrast diagram without end marker

What's wrong with this?

  1. The contrast is too low between the arrows and the background. I had been using a lighter background for "unvisited" nodes and a darker background for "visited" nodes, and I also separately had chosen an arrow color that matched the came_from variable in the example code.
  2. The start node shows the blob icon but the goal node shows no icon. This is inconsistent with other diagrams on the page that show both a start and goal icon.
  3. The tricky bit here is that the arrows point backwards from the goal to the start. It's easy to miss this.

I made some quick changes; it now looks like this:

Higher contrast diagram with start/end markers

  1. I stopped using the darker background to distinguish visited/unvisited because in this diagram everything is visited.
  2. I added a goal icon that matches the other diagrams.
  3. I added goal/start icons to the code to remind the reader that the loop starts from the goal, not the start point, and works backwards.

I think it'd be even better with an arrowhead along the path to show the direction, but I was unable to get something I liked, and I didn't want to spend a lot of time on it, so I abandoned the arrow. Another thing to try would be a small animated dot  •  following the path from the end to the start, color matched with the current variable in the code. That's something I'll consider later.

There are lots of little improvements I'd like to make to my pages, and I would probably be better off making them now instead of waiting until I have time to make bigger updates.

Labels:

One of the things that's bothered me about my Introduction to A* page and also my older A* pages is that I use grids everywhere. I fear that some of my readers will think that A* is only for grids or that it's best with grids. In my opinion it's worst when it is given grids, especially grids where every step has the same movement cost.

I decided the simplest thing I could do would be to change the grid map at the top of the page. That's the first impression a reader gets. Instead of showing non-grid maps halfway down the page, I should show a map that's not a grid. That way the reader immediately sees that we're not solving a grid problem. This was the first map on the page:

original-map with grid

I took some graph paper and came up with a polygon version of this map. I hand-coded it and got the A* page to show it:

new-map with polygons

Although making the initial version of this map with pen and graph paper wasn't too bad, iterating was quite a pain. I decided to make a quick & dirty tool to edit the shapes. I wanted to edit the graph connectivity too but didn't want to spend more than an hour writing the tool, so I didn't implement that. I put the connectivity in manually.

map-tool I used to edit the polygon shapes

The tool helped a lot! I made it output JSON, and then I copied-and-pasted that JSON into my A* page, where I wrote some code to turn that into the diagram. I spent a few hours on that map and also several others. The tool made it so much easier to edit maps that I ended up making more maps for the page.

After I had this new map up, the next step was to add a section to the page that described graphs. Although I have a link to another page that describes graphs, I think the input and output to an algorithm are too important to not explain on the main page.

I had implemented the A* diagrams with layers (see this); I was able to easily add new layers to show graph nodes and graph edges. With this I made a new diagram:

graph with room centers as nodes

I wanted to demonstrate two things with pathfinding graphs:

Completely different game maps might have similar pathfinding graphs. I drew a game map based on StarRaven's cartography brushes that shared the same pathfinding map as the main example.

same pathfinding graph but different game map

The same game map can be represented by different pathfinding graphs. I added two more pathfinding graphs for the same game map:

graph with doorways as nodes

graph with grid nodes

Comparing these, you can see how A* has to do a lot more work when the pathfinding graph is a grid than when the pathfinding graph is a navmesh or waypoint graph. If you're looking to optimize pathfinding on a grid, the first thing to try is to construct a non-grid pathfinding map.

With all of the new content on the page, I also wanted to simplify some of the other parts of the page. I decided that the contour maps were the least valuable concept, and removed most of the contour map diagrams. I think it's an interesting way of looking at things, but I was never quite happy with them, and they probably belong on an advanced level page, not on this introductory page.

While testing on iPhone and Android, I realized that I had never finished a touch version of the drag-and-drop maps. Until now, it didn't matter, because the diagrams were grid-based, and I had a touch version of the grid code. I had to fill in the non-grid touch event handlers. It doesn't work that well but it's good enough for now.

I'm much happier with the page now, although I still have some work to do on the wording. Take a look! There's still more I want to improve on this page.

Labels: ,

Popular Posts