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?

Improve this question
\$\endgroup\$
3
  • \$\begingroup\$ Can't you just check the 8 surrounding position of each castle ? \$\endgroup\$
    – Emadpres
    Dec 17, 2014 at 16:00
  • 1
    \$\begingroup\$ Sadly no, because the player should choose the way they deploy the wall. \$\endgroup\$
    – Cafn
    Dec 17, 2014 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, 2014 at 19:57

1 Answer 1

Reset to default
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.

Improve this answer
\$\endgroup\$
7
  • \$\begingroup\$ I'll try this one tonight and give a feedback! Seems to be the easier way! \$\endgroup\$
    – Cafn
    Dec 17, 2014 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, 2014 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\$
    – House
    Dec 17, 2014 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, 2014 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, 2014 at 21:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .