An anecdote on recursion

Many of you will remember the Winnie-the-Pooh flash game I wrote. Here is a puzzle for you.

The world is a grid of squares, containing (level 1) grass or pit or wall and (level 3) Chris or Pooh or Piglet. Continuous motion is represented by a series of discrete steps. So every 400ms, the "tick" function runs, which updates all positions at the same time, the map changing instantly from eg. "space, Pooh, Pooh, space, Chris, space" to "space, space, Pooh, Pooh, Chris, space" if too Poohs were running toward Chris.

The animation is chosen to show movement from one square to another, so although logically the second state of affairs takes over instantly, in fact the pictures are internally displaced 3/4 of the number of pixels in a square to the left, and then 1/2 and 1/4, before 300ms later being centred on the square they are actually "on" (in fact, moving towards).

But although the Poohs positions are all updated at the same time, in fact, that function must calculate where to put them in some order. In fact, there is a function representing Pooh's thoughts, which directs the direction he tries to run, and then a function representing movement which runs for every character, even CR, which actually updates.

A brief thought will show potential pitfalls -- the same that Dungeons and Dragons faces when it tries to sequentially represent concurrent events. For instance, if Pooh1 and Pooh2 are trying to move into the same square, which does? In fact, it's essentially arbitrary -- whichever move function happens first moves, and the other then tries to but finds the way blocked. This almost never makes a difference -- one will be in the square closest to you, and the other will follow next click, so there's only 4/10 of a second when the game could be in two states. In fact, it is deterministic, it depends on the initial position of the characters, from which they are read into an array of all moveable things at initialisation.

When CR interacts with Pooh it makes a difference. CR moves first, then other animals. Animals "think" before CR moves, (except that some, including Pooh, think both before and after). This means that if you pause the screen, when you continue, Pooh will move towards where you are now, not where you're moving to. Eg. if CR and Pooh are both moving into the same square, CR will move first, and then Pooh will be blocked. Except that then one or the other will die, but this will be shown with a slight jerk, as CR move-into-new-square animation is replaced by a kill or die animation in the new square

OK, that was long, it may be of interest to amateur programmers, the interesting bit will go in another post

An anecdote on recursion

However, when many Poohs are moving close to each other, the processing can be more complicated. If you have "Pooh, Pooh, space" and both Poohs run right, you would naturally expect that the second would move into the empty square, and the first into the second's square. If the second's move function happens first, this is indeed what happens. However, if the first's move function happens first (as it would if the Poohs start moving right, not left), the square it moves into is blocked. (Or, it moves regardless, overwriting the contents of the next square!)

This manifests as in the first tick, only the second Pooh moving forward, and thereafter them always having a blank square between them. In fact, this looks quite good, but it isn't what the logic demands: in real life, they'd both move a fraction of a centimetre, and the one ahead wouldn't block the one behind, it only does because they move in a square jump at once.

What can you do? It's hard to know the best order to process them in beforehand, you'd have to keep shuffling the array.

Make the first check if the second is moving, and if so, move? But then if there second were moving sideways but in fact was blocked by a wall it would stay where it was after all. Check if it's able to move? But it might be unable to move for many many reasons not even coded yet -- next year I may include sticky mud.

You basically need to do the entire movement routine on the second Pooh, once you realise the first one is blocked. But that's exactly what you want. The answer: The move function checks if movement is blocked by another character. If so, it calls the move function for that character, and when it's complete, checks then if the original movement is still blocked or not.

If you have a line of five Poohs moving left, this never happens. If they're moving right, the first tries to move, tells the second to move before it completes it's move, the second tells the third, and you get recursion five-deep, ending with the rightmost completing the move first, then the next-rightmost, etc.

I thought this was a pleasingly elegant solution. (Of course, you don't need recursion, you could permute the array instead.)

The thought occurs to me, I invented the solution, it's not *necessarily* obvious. But everyone writing a characters-moving-on-tiles games must have done something similar. (Admittedly, mine depends on character interactions more than many. If you have a thousand characters, you fudge this sort of thing. If you have two, they're practically AIs anyway.)

So, experienced programmers, tell me. Was that obvious to you? Had you seen it before? Where should I have been reading/hanging out to have heard of it myself? :)

(no subject)

Over the Christmas holidays I have had *several* new books to enjoy, *many* of which have been classic enough for me to want to recommend them and buy everything else by the author.

Temeraire is Hornblower with dragons. That says it all really. If you're not off reading it now, you never will. But for those of you reading on, I'll mention some of the good, the bad, and the ugly in my opinion.

* The good. Hornblower. With dragons. And it represents it well. Captain whatsit isn't Hornblower -- he's happy, for one thing -- but definitely from the same world. The alternate history -- Dragons have been bread for various uses, mainly military superiority in parallel to navies, the Chinese have overwhelming air superiority if they ever chose to use it, and the most intelligent, charming dragons, though others have bread for size, flame, poison, etc. The tactics used all sound plausible and Napoleonic, in that dragons are useful and dangerous, but not overwhelming.

* The bad. The first book doesn't really seem to go anywhere. It's lovely to read, but there's no substance, no unfolding plot, no tension, no revelation, no anticipation. People who recommended it to me, did you think that? How did you feel about the rest of the series?

* The other. Of course, a dragon is a gigantic honking stonking Mary Sue. That's what dragons are. Some people may complain about that, but it's like complaining that some science fiction explores laws contrary to reality, or that romances have a happy ending. That is the genre, and if you don't like it, reading is not recommended, but it cannot be changed without destroying it :) As I ranted about an ex-depressed post, Dragons are metaphors, expressions of some human emotion or other, as often as not, which is why they're cool. OK, I may be stretching things, but I wanted to say it. The fact that of course he turns out to be one of the most important breeds of dragon, and of course at the end of the book saves everyone, is perhaps over the top, though I'm not surprised. But that he's so wonderful isn't a flaw, it's the reason for the book :)

In fact, the entire review can probably be summed up by the conversation it was first recommended to me in.

Naath: It's Hornblower! With Dragons!
Ian: But it's not very good. Egan--
Me: No! Thank you both. I, of course, very much appreciate any recommendations for good good books. But Naath, please continue to recommend good books that are just like other good books, but with dragons, how can that be bad?

Sorry to both :)