Looking for a matrix algorithm

Question

I'm trying to make a game I'm finding myself trying to reinvent a wheel that probably already exists.

Here is a sample of the problem I'm trying to solve. I'm trying to check if any board pieces fall within the territory of another player, in this case, the black piece is captured.

W W - - 
- - W - 
- B W - 
- - W -

Any advice to go about solving this would be appreciated.

What is considered "within the territory of another player"? — Dan W
– Dan W, Commented Aug 27, 2012 at 14:58
Sensei's Library has a list of algorithms that tackle this problem. — Gareth Rees
– Gareth Rees, Commented Aug 27, 2012 at 15:00
That looks like a variation of a flood-fill algorithm (v en.wikipedia.org/wiki/Flood_fill) often used in image segmentation. — High Performance Mark
– High Performance Mark, Commented Aug 27, 2012 at 15:07
Determining what constitutes the territory of a player is a very difficult problem, even for humans, since it requires you to determine which stones are dead or alive. — interjay
– interjay, Commented Aug 27, 2012 at 15:09
Thanks, Mark - Flood-fill was exactly what I was looking for. — Dan
– Dan, Commented Aug 27, 2012 at 18:07

High Performance Mark · Accepted Answer · 2012-08-28 10:01:37Z

2

Oh well, if one of my comments is taken as an answer, might as well whore for rep:

It looks as if a variation of a flood-fill algorithm (often used in image segmentation) would be useful to you.

answered Aug 28, 2012 at 10:01

High Performance Mark

78.6k7 gold badges109 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Marcus Hedenström · Accepted Answer · 2012-08-27 15:07:25Z

0

This sounds like a reachability problem to me.

The position the black piece is on is obviously reachable. It could move up, down or to the left, but not to the right. Moreover, it could never reach the top right position (unless it can move diagonally).

A queue of open positions contains the position of the piece itself.
While there are open positions:
- mark the position as reachable, and
- add neighbor positions to queue of open positions.
If there are still unreachable positions, you could consider the piece "trapped".

answered Aug 27, 2012 at 15:07

Marcus Hedenström

615 bronze badges

1 Comment

interjay Over a year ago

If the black piece was outside white's territory, the positions inside white's territory would be unreachable and your algorithm would consider the piece to be trapped.

Collectives™ on Stack Overflow

Looking for a matrix algorithm

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related