Sign in to follow this  
Troodon

... identifing continues loops

Recommended Posts

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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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


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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this