Tufty
09-10-2004, 02:46 AM
Hi guys, for one of my simple projects I'm doing to ease me into DirectX programming, I'm doing a remake of the old Amiga game Outfall - I don't know if any of you ever encountered that.
I believe it was based on Columns, but basically the idea is, sets of 3 coloured balls drop from the top of the screen, and you have to make chains of 4 or more with them. You can rotate them in any direction 90 degrees at a time, much like you could with Tetris blocks. A successful chain drops rocks into the other players area, and eventually they can't play any more - again, like Tetris.
Basically what I'm looking for, and it's got me slightly stumped as to how to implement it, is a search algorithm I can use to detect the chains of blocks.
What I've come up with so far is this:
1. Step through array of blocks, one row at a time. Probably from the bottom-up.
1.a. Scan for a neighbouring block of the same colour. If no match is found, make a note of that and continue to the next neighbour. If a match IS found, make a note of it, and move to that block to begin the search again. Obviously you'd also make a note of which direction you came from, to avoid an infinite loop where you're moving back and forth from one block to another.
1.b. If a neighbour is found, add the two blocks positions to an array (or list) which is keeping track of chains.
2. When every block has been scanned through, check the list of chains and remove any chains of less than 4 blocks. This will leave us with a list of the blocks that need to be deleted.
3. Delete the blocks relating to those chains, add the points to the players score, and increase the number of rocks to be dropped on the other player.
4. The next step is to check for combos. At this point, all the blocks in chains have been deleted, so there's gaps in the play area. We need to close those gaps by dropping the blocks above them down, so we do that. Then we scan through the array again and check for chains. If none are found, we're done. If we find any, we need to destroy the blocks again, apply gravity again, and keep going until we don't find any more.
5. Then we pass control back to the player - basically all this should have happened in a matter of milliseconds anyway, aside from the animating effects.
I was hoping you guys could help me come up with a better algorithm than that. I'd be the first to admit that it's not my strong point, and I'm sure there's a more efficient way to do it. Any suggestions?
I believe it was based on Columns, but basically the idea is, sets of 3 coloured balls drop from the top of the screen, and you have to make chains of 4 or more with them. You can rotate them in any direction 90 degrees at a time, much like you could with Tetris blocks. A successful chain drops rocks into the other players area, and eventually they can't play any more - again, like Tetris.
Basically what I'm looking for, and it's got me slightly stumped as to how to implement it, is a search algorithm I can use to detect the chains of blocks.
What I've come up with so far is this:
1. Step through array of blocks, one row at a time. Probably from the bottom-up.
1.a. Scan for a neighbouring block of the same colour. If no match is found, make a note of that and continue to the next neighbour. If a match IS found, make a note of it, and move to that block to begin the search again. Obviously you'd also make a note of which direction you came from, to avoid an infinite loop where you're moving back and forth from one block to another.
1.b. If a neighbour is found, add the two blocks positions to an array (or list) which is keeping track of chains.
2. When every block has been scanned through, check the list of chains and remove any chains of less than 4 blocks. This will leave us with a list of the blocks that need to be deleted.
3. Delete the blocks relating to those chains, add the points to the players score, and increase the number of rocks to be dropped on the other player.
4. The next step is to check for combos. At this point, all the blocks in chains have been deleted, so there's gaps in the play area. We need to close those gaps by dropping the blocks above them down, so we do that. Then we scan through the array again and check for chains. If none are found, we're done. If we find any, we need to destroy the blocks again, apply gravity again, and keep going until we don't find any more.
5. Then we pass control back to the player - basically all this should have happened in a matter of milliseconds anyway, aside from the animating effects.
I was hoping you guys could help me come up with a better algorithm than that. I'd be the first to admit that it's not my strong point, and I'm sure there's a more efficient way to do it. Any suggestions?