An anecdote on recursion

[jack]

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? :)

Comments

[geekette8.livejournal.com]

What happens if you have a sequence of characters in a square, such that the recursive function will never terminate (until it runs out of stack :-))?

[simont]

My general approach to this sort of thing is to try to design right from the start in a way that doesn't depend on non-deterministic details of implementation. (Well, conceptually nondeterministic, that is; obviously it's not literally nondeterministic. But if someone else trying to implement the same rules will be forced to mimic your internal storage and enumeration algorithms instead of being free to use one of their choice, it's bad enough.)

So in this case, I'd have arranged for all the characters to move as if simultaneously, with the possible exception of the human-controlled character moving before or after the computer-controlled ones. That is, each Pooh thinks independently and works out which square they'd like to move to, and then if no two Poohs' target squares clash they can all move as they'd planned, and if they do then both the Poohs who were aimed at that target square have to do something different.

(Or alternatively there could be a fixed rule that says which one wins: the Poohs could carry around invisible priority numbers on their foreheads, or the rule could be that a Pooh moving downward into a square beats one moving sideways or upwards, or something else. But it should be fixed by some reasonably simple and externally trackable property of the Poohs rather than fiddly implementation details such as which one happened to end up first in a hash table or linked list.)

I'm generally not a fan of processing things in an explicit order if I don't absolutely have to. I like simultaneity; it's easier to prove things about.

[ewx.livejournal.com]

I'm tangentially reminded of Python's handling of mutually recursive imports, where there is no right order and you just have to put up with partially initialized modules for a while.