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

[geekette8.livejournal.com]

Sorry, that really wasn't very clear.

I mean like this:
A B
C D

A wants to move into B's square, but can't because it's blocked by B. So run the B function - that wants to move into D's square, but is blocked by D, so run D's function, which in turn is blocked by C which in turn is blocked by A which in turn is blocked by B... :-)

Basically you need a flag to say "I'm already trying to move, don't run me again" and then some clean way to break out.

[cartesiandaemon.livejournal.com]

Basically you need a flag to say "I'm already trying to move, don't run me again" and then some clean way to break out.

Yep, exactly. That's what I did. There's a "am recursing/moving" flag as well as a "have already moved" flag, and if so it breaks out. At that point we know that we have a closed loop of animals, and you can either return "ok" (to make the square endlessly rotate) or return "no" (to make them all stop blocking on each other). That pleased me too.

In fact, I made them stop because it's almost never going to come up unless I specifically design it, and then I *do* need a way of caching one Pooh while I shuffle the next into his square. (Though I only need to cache the coordinates, the objects are independent in memory, with just an index stored in the actual map.)

[cartesiandaemon.livejournal.com]

At that point we know that we have a closed loop of animals, and you can either return "ok" (to make the square endlessly rotate) or return "no" (to make them all stop blocking on each other).

PS. And obviously one of those two cases must be chosen -- it's not an implementational detail, in the physics of that world, one or the other must happen, and I hadn't previously decided which, so I fiat-ed it then :)

[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.

[cartesiandaemon.livejournal.com]

Thank you. I basically agree. Certainly, anything which people will observe should be constructed so they can have a model in their heads which says "this depends on that" or "this is random" depending¹. Otherwise it is a horrible un-immersion in the world.

When I was first designing, I spent some time thinking about priority so there would always be a sensible thing to happen. (For instance, the interaction between CR and Pooh is pretty elegant.)

However, I chose this as the edge case. In almost all of the levels I have, Pooh never *does* conflict with Pooh, and I felt that if A and B try to move into the same square, breaking the symmetry arbitrarily was the right thing to do. Something else would be jarring, and in almost all cases, letting one through resolves itself in one tick to the same situation, because both Poohs will be going to the same place (the one behind will follow the one in front if he can't see CR himself), so the mental model isn't "one pooh [here] and one [there|there]" but "two chasing through [here]" which is fine. The Poohs are identical, so it doesn't matter.

The beetles have direction, and there I *did* add a tie-breaker. A beetle moving transverse to CR has priority, so a beetle moving from a side-passage can always block one chasing you. (If two are moving in from side-passages, again, it makes little difference.)

[1] In fact, in my world, everything *is* deterministic. So you should never have to depend on "random" behaviour to win a level (they are designed to avoid depending on the differences in such cases), but if you choose to do so, at least it will be the same every time, so even though you won't work out the invisible numbers in advance (unless you know how the game is coded), you can remember what happens in the specific case you're interested in.

[cartesiandaemon.livejournal.com]

PS. I have been writing a little new behaviour and ten more levels over Christmas (nearly, not quite done). As you thought so much and so clearly about the game before, I wondered if you might like to see and offer any comments you might like to about controls/game-play/plot/metaphysics before I publicise the instalment? (Beta-test, I suppose.)

[simont]

Sure, I'd be happy to beta-test :-)

[cartesiandaemon.livejournal.com]

Thank you, I appreciate it! I have some new behaviour and logic tweaks, piglet, and nine more levels. When I've got level #18 working and done some more graphics tweaks I'll send you a link.

[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.