Path Symmetry

The past couple of weeks I've been wrestling with video editing in order to put together a very short video for my father's memorial service. The state of video codecs and containers (in terms of what can go in what, and which platforms support which) is truly awful. Go software patents, eh? Spurring innovation and so forth.

Windows Movie Maker also turns out to be truly awful. I wasted way too much time. You get what you pay for, I suppose. I ended up purchasing AVS Video Editor, which I'm not linking since it also seems to be only intermittently functional.

In the meantime I came across this interesting article about speeding up A* pathfinding on a grid: Jump point search.

Daniel Harabor makes an excellent point: Having lots of equally-good paths between start and destination just kills A* performance because it must examine every possibility on the chance that one of them turns out to be superior. Here's an example of a situation where there are multiple possible paths (one of which is highlighted):

The path must consist of four horizontal moves and three diagonal moves, but they can be made in any order. Imagine a deck of seven cards, four of which say go east and three of which say go northeast. There are 7! ways you can order those cards. Since there is no difference between the go east cards or between the go northeast cards you divide out by the number of ways you can order those. This is 7 choose 3 (or 7 choose 4), which is 7! / (4! * 3!). The end result is 35 distinct paths. (One of my programming interview questions is about this sort of thing, by the way.)

Daniel speeds up A* by navigating the search space in such a way that only one style of movement is ever used: diagonal moves first, followed by the horizontal or vertical moves. His article is a bit misleading because he is plotting only the nodes that go into the "open" priority queue, and this number is vastly lower with his approach than it is in the basic A* algorithm. However! His algorithm is still looking at all the same grid squares; it's just doing less work at each.

My pathfinding implementation is designed to pick from among all the available equally-good paths with equal probability (in order to make groups of moving units move a bit more chaotically), so it isn't compatible with jump point search. (You could also imagine a pathfinding algorithm that tries to interleave the moves in a way to most closely approximate straight-line movement, which would also not be compatible with jump point search.) It has got me thinking about ways to squash symmetry out of my pathfinding, though.

16x16 Tiles

New version of ThiefRL with 16x16 tiles instead of 8x16. The graphics are still fairly temporary. Sight and hearing is circular on the grid now instead of being twice as far horizontally as vertically (which was to make things come out visually circular). I split the difference so light/sound travels further vertically and less far horizontally as before. As a result the level is probably not the best balance.

Remembering my father

Yesterday my father would have turned 65. He died two weeks ago after having had a lung and its surrounding tissue removed, as an attempt to fight the spread of mesothelioma.

James Sr. (I was a Junior) was born in 1946, second of four. When he was thirteen his father died suddenly (most likely of mesothelioma), and Jim became the "man of the house." He had his impish streak but he was also very hard-working. He knew what he wanted and he got it. He worked his way through college since his mother did not have much money. He pursued my mother from high school, despite not being the favored suitor with her family, and married her following college. He bought a Piper Cub airplane in high school (under his mother's name) which he flew out of the field at the family farm. He did not want to go to Vietnam, so he went to medical school instead. He became a renowned ophthalmologist specializing in cornea transplants, and was the chair of the ophthalmology department at Loma Linda University for a decade. He founded the Inland Eye Bank for sourcing eye tissue.

My father was a meticulous (nay, obsessive) record keeper. Ophthalmologists are gadgeteers (as sure as neurosurgeons are egotists or pathologists are grim or orthopedic surgeons are fun-loving) and my father bought pretty much every generation of IBM PC as a means of keeping his own personal surgery databases. He let me play with them when he wasn't at home and as he saw my interest he kept me supplied with programming software. He gave me copies of IBM Logo, MS QuickBASIC, Borland Turbo Pascal, and eventually Borland Turbo C. I think I first encountered Rogue (the computer game) on a PC in the eye bank offices when I was hanging around there on a weekend with him. Being raised Seventh-day Adventist I had little exposure to pop culture of any kind. Rogue was riveting; I made a copy of it on a floppy disk, took it home, and played it furtively and obsessively. I wanted to make games like this!

After the university sold its ophthalmology department to a private practice, my father did some soul-searching and decided to move to the Pacific Northwest and join up with a "cataract mill," as they were derisively called by many ophthalmologists. To cut costs, these practices devolve most of the pre- and post-op care to a supporting network of optometrists, handling just the surgery bits that the optometrists cannot do. The optometrists love this because referring a patient to a traditional ophthalmologist typically means losing future business; the ophthalmologist will just absorb the patient into their own practice. With a cataract mill the optometrist stays in the game.

Focusing on just surgery meant that my father racked up incredible numbers of them: up to twenty-five surgeries a day, adding up to a lifetime total of over 55,000. (Remember the meticulous records?) He had two surgery suites. The nurses would prep a patient in one while he was operating in the other. He'd walk in, read the patient's name off a sign, and a few minutes later they'd have their cataract out and a plastic lens implanted. By then a patient would be ready in the other room and he'd swap gloves and start over again.

This is incredibly demanding performance work in the space of a square centimeter. There is no tolerance for error. Fortunately the high volume of surgery that he was doing meant he'd seen just about everything and could react appropriately. He experimented with making improvements to his instruments and ran studies on them to see whether the modifications were effective.

They say that when you have your mid-life crisis you buy the car you had when you were a teenager. Remember the plane? Yeah. My father bought a brand-new Super Cub and flew it all over eastern Washington, Oregon, and Idaho. Every time I would visit he'd get me out in his plane and we'd range all over. We dropped in on Red's Horse Ranch (now defunct) in Minam Creek; you can only get there by horse or by plane. We dropped in on a friend's wheat farm; the neighbor boy would come racing over on his quad to get a ride. We'd chase coyotes with the airplane, buzz herds of cattle, do touch-and-go landings at the Lower Monumental dam.

Surgical careers don't tend to run long. Retirement was looming. I think my father was waiting for his 65th birthday to start thinking about what came next.

What came next, last April, was mesothelioma: a cancer of lining tissue, in this case the lining around his right lung.

There isn't any particular reason that we know of why he would have gotten it: he wasn't a smoker and hadn't been exposed to asbestos (the two major causes). My father did several rounds of chemotherapy. I sat in with him on the infusion days and was reminded of how blunt our medical instruments still are in many areas. Chemotherapy is basically poison, to be absorbed by living cells. The cancer, being more vigorously alive than the rest of the body, will hopefully take the brunt of it. There is inevitably a lot of pain, which can be addressed with opiates at the cost of addiction and reduced mentual acuity. Taking the opiates results in constipation. Vitamins are getting destroyed. Sleeplessness is common. Before you know it you're taking a giant regimen of pills and patches around the clock.

The chemotherapy didn't do anything to the cancer. A surgeon at Swedish Hospital in Seattle wanted to have a go at removing the lung; my father was relatively young and in excellent health other than the cancer. After a lot of deliberation he decided to give it a shot. He made it through the surgery but could not sleep in the next few days, which made him paranoid and combative. After sedation he deteriorated steadily until his remaining lung could not supply enough oxygen even with pure oxygen being pumped in via a respirator. We took him off life support (he had not been conscious, I think, since he was sedated three days before) and he died quickly.

Given who my father was, and who I am, it was inevitable that I would disappoint him to some extent. I didn't go to medical school (despite plenty of urging). I didn't marry a nice Adventist girl (despite being sent to an Adventist college). I didn't pick a particularly respectable line of work (and started out in Las Vegas, at that). Nevertheless he was always very good to me and seemed to get on very well with the girl I did marry.

We loved him and we'll miss him.

Resizable Windows

I've just finished implementing a relatively mundane feature that's been on my to-do list for a long time: the ability to resize the game window in my Roguelike projects. I found myself always cranking up the window size during development so I could see more, and then reducing it back to 80x25 upon release. I suppose the next step would be to preserve the window layout in the registry but that comes with its own set of issues, and I want to avoid going into the registry just yet.

Here is the latest version of ThiefRL, my transplant of Thief-style stealth gameplay into a turn-based, grid-based world.

Here is the latest version of SpaceRL, my experiment in approximating zero-gravity movement through a randomly-generated, monster-infested derelict starship.

Both games are pretty simple at the moment; there's lots more that needs to be done.

Supporting resizing involved a fairly major change to the conceptual model of my roguelike framework. It used to have a virtual frame buffer of 80x25 characters. The game would write to this buffer very much like you might have written to the graphics memory in the DOS days, and the framework would display it. Now the game follows the model I more typically use in my non-roguelike games: the framework calls back to the game when it needs the screen drawn, including information about the window size. The game issues calls back to the framework to render glyphs at arbitrary positions within the window.

In ThiefRL I ended up swapping out the speech-bubble placement algorithm for something a bit simpler, in order to get it to behave well on resizing windows. The old algorithm was trying to avoid placing speech bubbles over NPCs. It used a sort of simulated annealing, but this resulted in totally different solutions every time it rendered. When resizing the window this looked pretty crazy. The new algorithm just tries to put each speech bubble on the opposite side of the player from its source, to keep a clear view of the space between the player and the speaker. If multiple NPCs say something on the same turn, though, it's possible for the bubbles to overlap.

I also took the opportunity to touch up some of the in-game note text to give it a bit more thematic flavor. There are still some notes that don't belong at all: the limerick in the heavily-guarded house, for instance. This really was just my test world for features, so it hasn't had terribly focused world-building done on it.

I received a couple of fan letters for these projects, which was very gratifying. I know I tend to lurch about from project to project as my whims dictate. ThiefRL feels like it's furthest along in terms of the quantity and quality of gameplay on offer, and in terms of it not having any particularly big technical challenges on the horizon. (Hierarchical pathfinding would be the next one I can think of.)

Next up, I think I will implement one-way windows in ThiefRL. I think I'd like to give the player more options for de-escalating a situation. One way might be to have "high windows" that you can jump out of to move from a heavily-guarded inner area to a less dangerous outer area. The guards would not be able to follow directly so you would gain some distance immediately. You would not be able to return through the high window, though, so it would preserve the difficulty of getting into the inner area.