One way to get rid of this problem once and for all could be to generate a movement dependency tree, and then use a longest path algorithm or somesuch. There would still be an initial movement order (which could be handled by LtRTtB), but it would be much less noticable.
Technical mumbo jumbo coming up
Actually, never mind longest path. I think a "
lazy"
dependency approach with dynamic relabeling/reordering would be better for our purposes (it's maybe not as good, but should be more efficient). Let's see... Here's some roaches (A-G), Beethro (O), Beethros sword (\\), and a bit of wall (#):
*12345678
1
2 BAC
3 DE
4 FG#
5
6 \\
7 O
Beethro waits. A moves first, then B, etc. A monster moves as soon as it's able to, and dependencies aren't found before they're required (hence "
lazy"
).
A can't move straight away, though. It wants to move to (4,3), but that square is occupied by D. For now, we don't bother about the other possible moves, note that A depends on D, and move on to B. B can move straight away, as (3,3) is free. As it's the first monster that moves, we relabel it as a (lower case indicates a monster has moved):
*12345678
1
2 AC
3 aDE
4 FG#
5
6 \\
7 O
C depends on E, D depends on G. E depends on G as well, though (as (6,4) is a wall). Obviously both D and E can't both move into the same space, so there's no point in adding E as a dependency of G as well. In stead, we try to add E as a dependency of D. However, A already depends on D, so we add E as a dependency of A (old label) in stead. Nothing else depends on A, so we're good.
Next to move is F, which can move right away (relabeling as b). G is next, and can also move (c). This leads to a chain of new moves: D depended on G, so D moves (d). A depended on D, so A moves (e). E depended on A, however, it can't move to (5,4) as that square is now occupied by d. In stead, E tries its third movement option, (6,3), which is free. Now that E has moved (f), C can move as well (g), and we're done:
*12345678
1
2
3 aegf
4 d#
5 bc
6 \\
7 O
Now, Beethro waits again.
*12345678
1
2
3 AEGF
4 D#
5 BC
6 \\
7 O
A moves first, and can move straight away (a). B too (b). C is blocked by Beetrhos sword at (7,6), and b at (6,6), but (7,5) is free, so it moves there (c). D moves (d), followed by E (e), F (f), and finally G (g). Thanks to the relabeling/reordering, this time there were no dependencies. The result:
*12345678
1
2
3 g
4 ae#f
5 dc
6 b\\
7 O
No holes!
larrymurk wrote:
I appreciate everyones comments. Of course I still think it's nothing more than an interesting topic since even I feel there's no way the movement order criteria should be changed now that all these holds have been created.
Exactly. If something like this was actually implemented (let me just point out here that
this is not up to me, at all), it would have the potential to break rooms that rely even
slightly on movement order. Monster bumping wouldn't work anymore, either.
- Gerry
