... identifing continues loops
Author
Hi!
I am working on a hobby-assignment, and I need help to find an algorithm that can identify if one or more of the opponent's tiles is surrounded by a continues loop. There may be empty spaces inside the loop, as long as there is at least one opposing tile.
I am currently using a simple 2D-grid-representation of the tiles, but any representation of the tiles is acceptable as long as there exists only two kinds of tiles (besided the empty spaces).
I have been thinking about this problem for weeks now, but I can't figure out any easy way to do it!
I would be very greatful if anyone could help me with this one!
Cheers,
Troodon
do a breadth first or depth first search through the tiles, if you ever hit a tile youve come to before you have a continous loop.
unless im not interpreting your problem correctly
unless im not interpreting your problem correctly
Author
Thanks ibebrett! I will clarify the problem a little. The problem is to identify if there exists continues loops that surrounds one or more of the opponent's tiles. Empty spaces may exist inside the continues loops.
Cheers,
Troodon
Cheers,
Troodon
A tile can have 3 states: enemy, yours, empty. Each tile has 4 neighbors (assuming 4 connected, easy enough to modify for 8-connected). A neighbor can have any of the 3 states, or be out of bounds (oob) if the original tile is on an edge.
There are 3 lists:
Open list initially contains all tiles.
Working list initially empty.
Enclosed list initially empty.
One bool: enclosed
The general idea here is that a region is not enclosed if there is a path to the edge of the grid which does not pass though any of your tiles. We use a simple flood fill to find regions, and mark the region as enclosed or not. In the end, the enclosed list contains a list of all enemy tiles enclosed in a loop.
There are 3 lists:
Open list initially contains all tiles.
Working list initially empty.
Enclosed list initially empty.
One bool: enclosed
While open list not empty { enclosed = true Pop next tile from open list If tile is yours discard and continue If tile is enemy or empty { Push tile on working list While working list not empty { Pop next tile from working list For each neighbor of tile { If neighbor is yours, remove it from open list If neighbor is enemy or empty, remove it from open list and add it to working list If neighbor is oob, enclosed = false } } If enclosed is true { Move each enemy tile on the working list to the enclosed list } clear the working list }}The general idea here is that a region is not enclosed if there is a path to the edge of the grid which does not pass though any of your tiles. We use a simple flood fill to find regions, and mark the region as enclosed or not. In the end, the enclosed list contains a list of all enemy tiles enclosed in a loop.
Interesting problem.
You are looking to find a way to detect if One player controls all the space around another player's position?
I wonder if you could get better results if you stored all unit positions in a quad tree or similar structure, then culled any cells out of your search patter if they didn't contain at least 8 units.
The problem I'm having with making this overly useful is finding a good way to deal with elements that overlap low level cells.
You are looking to find a way to detect if One player controls all the space around another player's position?
I wonder if you could get better results if you stored all unit positions in a quad tree or similar structure, then culled any cells out of your search patter if they didn't contain at least 8 units.
The problem I'm having with making this overly useful is finding a good way to deal with elements that overlap low level cells.
The old problem of flood fill.
You must only add a check for runaway pattern, in which case your area isn't properly enclosed, and you can terminate the search. You need to perform this each time a new tile is added.
Despite seemingly complex and expensive algorithm, this is the method that was used for filling regions before any kind of 2D and 3D acceleration, and it achieved solid running times. On today's CPUs, it's a non-issue, even when dealing millions of tiles.
Scanline pass might be more suitable, since it may allow for easier out-of-bounds check.
You must only add a check for runaway pattern, in which case your area isn't properly enclosed, and you can terminate the search. You need to perform this each time a new tile is added.
Despite seemingly complex and expensive algorithm, this is the method that was used for filling regions before any kind of 2D and 3D acceleration, and it achieved solid running times. On today's CPUs, it's a non-issue, even when dealing millions of tiles.
Scanline pass might be more suitable, since it may allow for easier out-of-bounds check.
Author
Thanks for all the help! I believe that a "flood fill" algorithm should do it!
I my case the board/space is infinite. What terminal condition would you recommend me to use?
Cheers,
Kim
I my case the board/space is infinite. What terminal condition would you recommend me to use?
Cheers,
Kim
Quote:Original post by Troodon
Thanks for all the help! I believe that a "flood fill" algorithm should do it!
I my case the board/space is infinite. What terminal condition would you recommend me to use?
Unless you're using a pure Turing machine with infinite tape, then your board is "arbitrarily large", not infinite. Also, from practical perspective, 500x500 will be almost unplayable, since it will require so much scrolling that people will get carpal tunnel syndrome. Also, for a 500x500 board, if every player performs one move every second, it will take 70! hours to fill the board. And probably, players will perform one move every 5-30 seconds.
Track the rectangular extents of tiles. Whenever a new tile is added, check if it expands the virtual rectangle. Then all you need to do is check for that.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
