Algorithm for labeling same-colored regions in a 2D array?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Algorithm for labeling same-colored regions in a 2D array?

Steve Trout
(Apparently joining the list through the Google Groups interface doesn't work, but the post still shows up there. Sorry if you see this twice!)

For fun, I'm writing a rules engine for the board game Go (in Haskell obviously). I have a board, which is a grid of spaces that can contain a black piece, a white piece, or nothing. Part of what i need to do is to detect regions of the same "color" (black, white, or empty) and get information about them like their size, the color of the bordering spaces, etc. Regions are bounded by other colors or the board edges in cardinal directions. I'm just starting on this so I haven't picked my data structures yet, but Vector (Vector _) or Map (Int, Int) _ are what I've toyed with.

I have a vague idea of how I would go about this in an imperative language with mutation. I'd iterate over the board, keeping lists of points contained in the same region, combining (relabeling) regions if they happen to connect later on. (I realize there are probably better algorithms in those languages, but that would be my first attempt.) I know i could cobble something like this together in the State monad, but I have a feeling that there ought to be a better (more "Haskellish"/pure-functional) way.

What would a Haskellish algorithm for this kind of thing look like? I wouldn't mind a complete answer or just a nudge in the right direction.

Thanks,
-Steve

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Algorithm for labeling same-colored regions in a 2D array?

Bob Ippolito
I've done this before with a data structure inspired by Union-FindĀ https://github.com/etrepum/exercism-exercises/blob/master/haskell/go-counting/Counting.hs


On Mon, Jun 30, 2014 at 8:17 PM, Steve Trout <[hidden email]> wrote:
(Apparently joining the list through the Google Groups interface doesn't work, but the post still shows up there. Sorry if you see this twice!)

For fun, I'm writing a rules engine for the board game Go (in Haskell obviously). I have a board, which is a grid of spaces that can contain a black piece, a white piece, or nothing. Part of what i need to do is to detect regions of the same "color" (black, white, or empty) and get information about them like their size, the color of the bordering spaces, etc. Regions are bounded by other colors or the board edges in cardinal directions. I'm just starting on this so I haven't picked my data structures yet, but Vector (Vector _) or Map (Int, Int) _ are what I've toyed with.

I have a vague idea of how I would go about this in an imperative language with mutation. I'd iterate over the board, keeping lists of points contained in the same region, combining (relabeling) regions if they happen to connect later on. (I realize there are probably better algorithms in those languages, but that would be my first attempt.) I know i could cobble something like this together in the State monad, but I have a feeling that there ought to be a better (more "Haskellish"/pure-functional) way.

What would a Haskellish algorithm for this kind of thing look like? I wouldn't mind a complete answer or just a nudge in the right direction.

Thanks,
-Steve

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Algorithm for labeling same-colored regions in a 2D array?

Bryan Gardiner
Good to see other Go projects here.

I'm currently just taking the easy route and using bucket fill to
compute groups and their liberties.  So far I'm just dealing with
playing individual moves, and it runs acceptably for that; no scoring
or boards large enough for this to matter yet.  I'll probably switch
to something like union-find eventually.  That's a better idea and it
sounds like you want something with good asymptotic performance,
anyway.

computeGroup here:

http://khumba.net/git/?p=goatee.git;a=blob;f=src/Khumba/Goatee/Sgf/Board.hs;hb=HEAD

Cheers,
Bryan


On Mon, 30 Jun 2014 20:23:50 -0700
Bob Ippolito <[hidden email]> wrote:

> I've done this before with a data structure inspired by Union-Find
> https://github.com/etrepum/exercism-exercises/blob/master/haskell/go-counting/Counting.hs
>
>
> On Mon, Jun 30, 2014 at 8:17 PM, Steve Trout <[hidden email]> wrote:
>
> > (Apparently joining the list through the Google Groups interface doesn't
> > work, but the post still shows up there. Sorry if you see this twice!)
> >
> > For fun, I'm writing a rules engine for the board game Go (in Haskell
> > obviously). I have a board, which is a grid of spaces that can contain a
> > black piece, a white piece, or nothing. Part of what i need to do is to
> > detect regions of the same "color" (black, white, or empty) and get
> > information about them like their size, the color of the bordering spaces,
> > etc. Regions are bounded by other colors or the board edges in cardinal
> > directions. I'm just starting on this so I haven't picked my data
> > structures yet, but Vector (Vector _) or Map (Int, Int) _ are what I've
> > toyed with.
> >
> > I have a vague idea of how I would go about this in an imperative language
> > with mutation. I'd iterate over the board, keeping lists of points
> > contained in the same region, combining (relabeling) regions if they happen
> > to connect later on. (I realize there are probably better algorithms in
> > those languages, but that would be my first attempt.) I know i could cobble
> > something like this together in the State monad, but I have a feeling that
> > there ought to be a better (more "Haskellish"/pure-functional) way.
> >
> > What would a Haskellish algorithm for this kind of thing look like? I
> > wouldn't mind a complete answer or just a nudge in the right direction.
> >
> > Thanks,
> > -Steve
> >
> > _______________________________________________
> > Haskell-Cafe mailing list
> > [hidden email]
> > http://www.haskell.org/mailman/listinfo/haskell-cafe
> >
> >



--
Go game editor :: http://khumba.net/projects/goatee :: AGPL, Haskell
I: [pulseaudio] main.c: Fresh high-resolution timers available! Bon appetit!
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe