An anecdote on recursion
Dec. 30th, 2006 02:02 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackHowever, 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? :)
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
Date: 2006-12-30 02:35 pm (UTC)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.
no subject
Date: 2006-12-30 02:46 pm (UTC)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.)
no subject
Date: 2006-12-30 02:47 pm (UTC)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 :)