An anecdote on recursion
Dec. 30th, 2006 02:02 pmHowever, 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? :)