How would you write an AI rocket pilot? This is what I've been thinking about for the past few months in my spare time. I've been reading some books and papers about optimal control, and am still learning and collecting my thoughts, and writing code. So this is just a brief update.
A few years back I did some work in this direction. The rocket is treated as a point mass that can instantaneously accelerate in any direction, with a limit on the acceleration. One control problem is: given a starting state (position and velocity) and a desired final state (position and velocity), fly the rocket between the two states in minimum time. (No gravitational acceleration in this simple scenario.)
When I wrote that last page I conjectured that the optimal route would consist of accelerating in one direction for a duration and then (if necessary) accelerating in a second direction for an additional duration. (Flying two parabolic arcs, essentially.) I based this on an attempt to extend the one-dimensional optimal control, which is to accelerate in one direction at maximum for a duration, and then potentially reverse direction and accelerate for an additional duration.
Since reading some optimal control theory I've worked out enough to realize that this is not the optimal control. The optimal control turns out to be to thrust (with maximum acceleration) in the direction of a point that is moving along a straight line. The point is moving through a "control space" and you basically normalize the vector toward it and multiply that by the maximum acceleration to get the acceleration vector. You can see how the one-dimensional case extends to this, but in the two- or three-dimensional case the rocket potentially pivots through a range of directions as it accelerates. The trick, then, is to come up with the equation of motion for the control point that results in the rocket getting from the initial state to the final state.
That's all I have for now; hopefully more to follow.
Sunday, May 13, 2012
Sunday, January 22, 2012
iOS: New Orbit
Just ran across this iOS release. It's a brief space game called New Orbit, from a guy in Austria named Markus Hofer. I had a blast playing it for the couple of hours it took to get through it; it's currently priced at a dollar so if you have the appropriate device and like space games do check it out.
Control is straightforward; touch the screen and your rocket will accelerate in that direction. Physics is Newtonian, so there isn't any drag or maximum speed. The missions keep things fairly focused, though, so you don't have huge velocity changes. The rocket displays its current velocity vector and has a trail display. Asteroids exert gravity, so it's possible to enter stable orbit or land. Other space-game staples like mines (both the ore-extraction and munition sorts) make appearances as well. One of the nice interface touches is that off-screen asteroids are indicated with a bar on the edge of the screen. The bar's length represents the asteroid's subtended angle, so it gives you an idea (assuming you know how big the asteroid is, roughly) how far away it is.
New Orbit has the feel of being the tutorial for a much bigger game; a game that isn't made yet, unfortunately. You don't ever acquire weaponry of your own, for instance, and mining equipment is introduced in one mission and then never used again. What's there is quite polished, though.
In contrast to a lot of the 2D space games (like Flatspace or Captain Forever or Escape Velocity) this one's very story-oriented. It takes you through a linear sequence of missions without room for running around. I thought the story was very entertaining: well-written and well-voice-acted (so far as I could hear with the volume turned low); the whole game sounds like it's being acted by Arnold Schwarzenegger and his buddies since it's all read in Austrian accents. I liked that quite a bit, actually.
Hopefully Mr. Hofer and crew will develop further chapters in this game. In the meantime it's still well worth playing.
Control is straightforward; touch the screen and your rocket will accelerate in that direction. Physics is Newtonian, so there isn't any drag or maximum speed. The missions keep things fairly focused, though, so you don't have huge velocity changes. The rocket displays its current velocity vector and has a trail display. Asteroids exert gravity, so it's possible to enter stable orbit or land. Other space-game staples like mines (both the ore-extraction and munition sorts) make appearances as well. One of the nice interface touches is that off-screen asteroids are indicated with a bar on the edge of the screen. The bar's length represents the asteroid's subtended angle, so it gives you an idea (assuming you know how big the asteroid is, roughly) how far away it is.
New Orbit has the feel of being the tutorial for a much bigger game; a game that isn't made yet, unfortunately. You don't ever acquire weaponry of your own, for instance, and mining equipment is introduced in one mission and then never used again. What's there is quite polished, though.
In contrast to a lot of the 2D space games (like Flatspace or Captain Forever or Escape Velocity) this one's very story-oriented. It takes you through a linear sequence of missions without room for running around. I thought the story was very entertaining: well-written and well-voice-acted (so far as I could hear with the volume turned low); the whole game sounds like it's being acted by Arnold Schwarzenegger and his buddies since it's all read in Austrian accents. I liked that quite a bit, actually.
Hopefully Mr. Hofer and crew will develop further chapters in this game. In the meantime it's still well worth playing.
Tuesday, January 17, 2012
Lead, Follow, or...
(map 'map-leader-test.tga')
(player (pos 17 12))
(torch (pos 19 11) on)
(torch (pos 19 13) on)
(torch (pos 46 34) on)
(torch (pos 54 34) on)
(torch (pos 68 68) on)
(torch (pos 68 76) on)
(lamp (pos 58 51) on)
(lamp (pos 63 51) on)
(leader (patrol (pos 13 12) (pos 49 36) (pos 72 72)))
I've been plodding along on work with ThiefRL. Mostly stuff that didn't add any new gameplay. Pathfinding is a bit faster, for instance. (I cut out a ton of heap allocation during path computation.) A level loads from a combination of a bitmap and a text file now, instead of being compiled into the executable. The bitmap (an enlarged sample shown above) specifies the base ground tiles, and the text file (also shown above) specifies the rest of the objects. It's much easier to lay out a level in a bitmap editor, although I will probably eventually have to break down and write my own level editor to gain additional productivity.
Via Harry Connolly's blog I encountered an essay by author Rachel Aaron: How I Went From Writing 2,000 Words a Day to 10,000 Words a Day. I follow a bunch of writers' blogs because they deal with similar productivity issues to mine. This article has inspired me. The thrust of it is:
- Plan what you will do before you do it
- Keep productivity records (and examine them for trends)
- Find something to be enthused about in each session's work
I've decided the most crucial thing to do right now is to prototype the gameplay elements I'm considering for ThiefRL but haven't yet nailed down. Think of them as the “verbs” of the game. This will enable me to figure out which things will work together which will then enable me to organize a game.
To that end I have put together a leader behavior (aka Call of Duty mode). I'm thinking that, in the early parts of the game, you might have a friendly character lead you around as part of training in how to hide, evade guards, etc. They might also point out the locations of compounds you'll be infiltrating later and give a bit of story about what they are.
The basic behavior is that the AI wants to get to a particular spot but they also want to be close to the player. Being close to the player takes priority, but once they're close enough they will head toward their goal. Once they arrive at their goal the player has to speak to them (by bumping) to trigger the next thing.
Next I'm going to adapt this into a frog-march behavior. The idea is that a guard has hold of the player and is forcing them to walk in a particular direction. It might be tremendously un-fun but I'm going to try it as it represents a possibility for softer failure conditions. It might also work as a movement tutorial in the very beginning of the game.
Monday, January 16, 2012
Circle of Enemies
Harry Connolly's third Twenty Palaces novel Circle of Enemies came out in August. As usual I read it pretty much in one go. I was dealing with my father's cancer and shipping a game for Halloween, though, and didn't get my review out at the time.
Connolly's series pits Dashiell Hammett's lowlifes against Lovecraft's horrors. Every blood-free page racks up a tab that will be reckoned before long. The monsters are inventive and varied. They're not evil, just higher than man in the food chain. Let one into our plane and you let a fox loose in a hen house. There is always someone who is willing to make gamble that they'll be able to control a monster for personal profit, though.
Ray Lilly is an ex-con who, between stints working at a supermarket, serves as muscle for a shadowy association of wizards (the eponymous Twenty Palaces society) dedicated to the undercover eradication of eldritch incursions. His wizard boss has outfitted him with some protective tattoos but doesn't otherwise place a high value on his life. Ray looks out for himself, though; a peek into a spell book at one point allowed him to construct a ghost knife, which is a laminated piece of paper inscribed with a spell. It's a bit of a “Deus Ex Pagina” in the stories but overall the magic system in this world seems well-though-out without being explained to death.
In Circle of Enemies Ray is drawn back to LA from his home in the Seattle area. Someone or something is killing the members of his old gang and they blame him (with cause). It's good to see deeper interpersonal relationships in the book. Connolly is a lot like Hammett in not romanticizing anyone; they're all just people and none too good.
I've followed Connolly since the publication of his first novel (I discovered him through the great Big Idea essay he wrote for it). He's published a prequel novel for this series which I haven't gotten to yet, and is working on a fantasy novel at the moment. I've read a bit of his short fantasy fiction and it's deliciously dark, so I'm looking forward to seeing what he comes up with.
Monday, October 31, 2011
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.
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.
Wednesday, October 12, 2011
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.
Sunday, October 9, 2011
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.
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.
Subscribe to:
Posts (Atom)
