3
\$\begingroup\$

I'm making a game which uses a 10x20 matrix to store the position of the objects.

I have a castle object, represented by a number in a matrix. It is randomly deployed in some cell of the matrix. I also have a wall object, represented by a different number, which the user will deploy into the matrix by clicking on cells. The idea is to surround the castle.

Basically it'll look like this:

0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 1 0 0 2 1 0
0 1 1 0 0 1 0
0 0 1 0 0 1 0
0 1 1 1 1 1 0
0 0 0 0 0 0 0

(2 is the castle, and 1 is the wall.)

How can I tell if the castle is surrounded by walls?

\$\endgroup\$
  • \$\begingroup\$ Can't you just check the 8 surrounding position of each castle ? \$\endgroup\$ – Emadpres Dec 17 '14 at 16:00
  • 1
    \$\begingroup\$ Sadly no, because the player should choose the way they deploy the wall. \$\endgroup\$ – Cafn Dec 17 '14 at 16:18
  • \$\begingroup\$ So you can use a DFS or BFS algorithm easily and check If you reach the border of your matrix or not. \$\endgroup\$ – Emadpres Dec 17 '14 at 19:57
7
\$\begingroup\$

Sounds like you're after something like a flood fill algorithm.

Basically, something like the following algorithm (you can see other examples on the wikipedia page):

 1. Add your castle to the Checklist
 2. Get the first item from the Checklist
 3. For each surrounding position
  4. If not on Complete list
    5. If `0` add to Checklist
    6. If `1` continue
 7. Add position to Complete list and remove from Checklist

If at any point you reach an outside boundary, your castle is not surrounded by walls. If you complete your Checklist without touching an outside boundary, your castle is surrounded by walls.

\$\endgroup\$
  • \$\begingroup\$ I'll try this one tonight and give a feedback! Seems to be the easier way! \$\endgroup\$ – Cafn Dec 17 '14 at 16:19
  • \$\begingroup\$ The alternative method you describe (following the walls) detects only whether the walls form a loop - it doesn't verify that the castle is inside that loop. Also, the single-wall-thickness constraint might not be enforceable given that the OP says "the player should choose the way they deploy the wall." The first flood-fill suggestion works just fine though. \$\endgroup\$ – DMGregory Dec 17 '14 at 18:52
  • \$\begingroup\$ @DMGregory You're correct. I tried to think of other ways to traverse the wall while ensuring the castle was inside, but couldn't think of any. Since the player can freely place the walls, the shapes can be concave or convex making a lot of the "contains" tests in geometry invalid (like traversing the edges clockwise and ensuring the castle is always to the right, which relies on convex shapes). \$\endgroup\$ – MichaelHouse Dec 17 '14 at 19:06
  • 1
    \$\begingroup\$ To know if the castle is inside the walls, you can simply traverse the grid, starting from the castle position, in any direction, and count the number of walls you traverse until you arrive at an edge of the map; even means you are outside, odd or zero you're in. This is assuming that your walls form a closed shape. But yeah, flood fill is the way. \$\endgroup\$ – sharvey Dec 17 '14 at 22:09
  • \$\begingroup\$ @Byte56, i've been trying to implement this algorithm, but being kinda failures.. Cant see how can i realize that the castel is inside the walls, can only see it to change the path around castel.. \$\endgroup\$ – Cafn Dec 18 '14 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.