[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [computer-go] Storing Spatial Relationships

What do you mean by spatial relationship?

Many Faces keeps for each string, a list of the adjacent neighbor strings of
opposite color.
For each empty point it keeps lists of adjacent empty points, and adjacent
strings of each color.

At each point it has the distance to the nearest stone in each of four
directions, and the distance to the two nearest edges.

These are all easy to maintain incrementally.


> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Jason House
> Sent: Tuesday, October 18, 2005 8:49 AM
> To: computer-go
> Subject: [computer-go] Storing Spatial Relationships
> What algorithms are known or reference implementations available for 
> storing/tracking the spatial relationship between 
> stones/chains/groups/etc?
> I've seen some discussion about storing a list of neighbors of a 
> stone/chain/group, but have not seen anything about tracking 
> the spatial 
> dependency of such information.
>    When I initially think about this stuff, I think about a sparse 
> matrix implementation.  For each row/column storing a linked list of 
> members.  I don't quite like this because I can't pick an 
> element within 
> the sparse matrix and find its nearest neighbors with ease.  
> I'm almost 
> thinking I'd want to store the surrounding objects in some kind of 
> spatially significant way.
>    I almost wonder if there's a way to have a minimalistic 
> set of useful 
> neighbors and then being able to use the spatial significance of the 
> neighbor's neighbors to fill any gaps.  Of particular 
> interest to me is 
> up/down/left/right of the specified stone within +/- 1 
> row/column.  This 
> has the effect of directly catching the common jumps and approaches.
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx 
> http://www.computer-go.org/mailman/listinfo/computer-go/

computer-go mailing list