Suggestions on internal representation/data structures
Hi all,
this is going to be a long one. I hope some of you will read through it anyway and come up with a solution. I''m programming a clone of a board game in Java and I''m not sure how to represent the board internally (data structures no gui issues) in a way that the following rules can be implemented easily:
1) The board consists of 10x12 fields, all empty in the beginning
2) Fields adjacent to each other either vertically or horizontally but not diagonally are connected
3) Each field can be either empty or occupied by one of four colours
4) Each turn an empty field is occupied by a colour
5) A coulor can only occupy an empty field connected to empty fields (see 2) or to one or more fields occupied by the same colour
6) 2 or more connected fields of the same colour make a chain
7) Colour 1 can only occupy an empty field connected to one or more fields occupied by colour 2 when the field in question is also connected to a field occupied by colour 1 and the thereby extended or newly created chain of colour 1 consists of more fields than (each of) the neighbouring chain(s) of colour 2
7b) In this case the weaker chain (colour 2) is eliminated from the board and the fields occupied by it before become empty
So much for the rules. Now I''m looking for a data structure representing the board which allows me to do the following things efficiently and in accordance to the rules listed above:
a) set or eliminate the colour of a given field at any time
b) always know how many fields are occupied by a given colour
c) always know how many fields of a given colour are connected to each other as chains
d) always know of how many connected fields a given chain consists
e) always know which of two given chains of different colours is stronger
f) always know if a given field can be occupied by a given colour
g) always know whether an occupied field belongs to a chain
h) be able to calculate the distances between chains and occupied fields so that NPCs will be able to perform some kind of risk analysis
My first thought was to use a 2d-array to represent the board but that would make it hard to keep track of the chains if I don''t want to recalculate them each turn. Has anyone a better idea on how to do this?
Thx,
Profus
------------------------------------------------------------
"To a computer, chaos is just another kind of order."
I don''t pretend to have followed all the details of the rules, etc., but I think a 2D array is where you''ll want to start, as it allows quick queries for a lot of the rules you mentioned. If you don''t want to re-find the chains repeatedly (which, with a board of this size, probably wouldn''t really be a problem), you could create another data structure to keep track of the chains.
This is just off the top of my head, but maybe it''ll help in some way. You could maintain pointers for each field that, if non-null, refer to the previous and next fields in a chain. Or, you could maintain a dynamic array of all active chains, either as a set of linked lists, or simply an array of indicies.
Without understanding all the rules, it does strike me that if each field were represented by a struct or class which holds various information such as whether it''s part of a chain and who its neighbors in the chain are, and then make a 2D array of those structs or classes, you''d have what you need.
This is just off the top of my head, but maybe it''ll help in some way. You could maintain pointers for each field that, if non-null, refer to the previous and next fields in a chain. Or, you could maintain a dynamic array of all active chains, either as a set of linked lists, or simply an array of indicies.
Without understanding all the rules, it does strike me that if each field were represented by a struct or class which holds various information such as whether it''s part of a chain and who its neighbors in the chain are, and then make a 2D array of those structs or classes, you''d have what you need.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement