Timeline for How to divide hex grid evenly among n players?
Current License: CC BY-SA 3.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 20, 2013 at 7:04 | comment | added | manabreak | @NickWiggill I'm not quite sure what you mean by "expected territory size", do you mean the total amount of cells (all areas combined), or do you mean the single areas that are limited to four cells each? The main concern for me is not the total amount of cells per player, it can vary a bit, it's the size of the areas that cannot be more than four (preferably random between 1 and 4). This relates to my second concern, where two already-made areas may become joined when new areas are randomly created, I don't see this being noted in your algorithm. | |
| Oct 19, 2013 at 10:19 | comment | added | Engineer | @manabreak No, as I said to fnord, look at the line in the pseudocode that says, "if player has not yet reached expected territory size in cells": You can set a fixed limit for all players before the algorithm runs, OR you can even set the limit per player (eg. randomly or via a slider in the game lobby, based on player handicap). As for your second concern, please describe more clearly what you mean so that it forms part of the question, and I'll add to my answer. | |
| Oct 18, 2013 at 15:11 | comment | added | manabreak | @NickWiggill This does look nice, but doesn't this strive to maximize the island size, producing maximum-size islands until there is no room for them? I'd like the island sizes to be roughly even between 1, 2, 3 and 4 cells. Another concern I have is that when the subsequent rounds begin, isn't there a chance that two separately created areas become connected? | |
| Oct 18, 2013 at 1:09 | history | edited | Engineer | CC BY-SA 3.0 | added 213 characters in body |
| Oct 18, 2013 at 1:01 | comment | added | Engineer | @StevenStadnicki The OP notes "it doesn't have to be spot-on accurate". As to your argument, fair logic, but aside from being only loosely relevant (or rather, relevant only when the hexmap is of extremely limited size), given a hexmap's additional constraints it would in any case be rather difficult to enforce this, whether for 4-cell or for 20-cell groups, whether on a large map or a small one, due to jagged-edged groups. Not quite the same as a rectilinear grid! | |
| Oct 18, 2013 at 0:52 | comment | added | Steven Stadnicki | @NickWiggill Once your groups have grown to this state there's no consistent way of coloring the center cell at (3,3) that doesn't violate the size constraint on one of the groups. | |
| Oct 18, 2013 at 0:51 | comment | added | Steven Stadnicki | @NickWiggill You miss my point: the constraint that groups be no larger than e.g. 4 units in size means that cells might wind up unfillable before you've finished filling the board. Imagine e.g. a case where you're on a 5x5 square board (with 4-way adjacency) and a restriction that no group be larger than four units; now suppose that your algorithm has started by growing four groups: a red group at (2,1), (3,1), (2,2) and (3,2); a green group at (4,2), (5,2), (4,3), and (5,3); a blue group at (3,4), (4,4), (3,5), and (4,5); and a yellow group at (1,3), (2,3), (1,4), and (2,4). | |
| Oct 18, 2013 at 0:28 | comment | added | Engineer | @StevenStadnicki Not at all, because the algorithm can keep randomly picking from the neutral list until all cells have been assigned to some player, as noted in my last paragraph, since the neutral list does not rely on cell adjacency. OTOH, if you wish to restrict players to a certain count each, that is fine, and you may then end with some unassigned cells if you so wish. | |
| Oct 17, 2013 at 21:36 | comment | added | Steven Stadnicki | It's possible for the approach described in the last paragraph to 'get stuck' without filling the entirety of the board; imagine a scenario in which we've randomly 'grown' regions of all four colors to maximal size, all of them adjacent to a single hex (which, after all, has six sides) which hasn't been assigned a color yet. Then that hex will remain on the neutral list forever. | |
| Oct 17, 2013 at 17:56 | comment | added | fnord | I would edit my comment above, but it is too late. "I do not see a way in your algorithm". though you do mention the concept in later text. | |
| Oct 17, 2013 at 17:37 | comment | added | Engineer | @fnord Your logic is at fault. In your final sentence, you admit that my algorithm stops at island size n, and thereafter contradict yourself by saying that you "do not see a way" yet that I do "mention [how to get islands] in later text". Have I or have I not answered the question? This generalised algorithm may be used to either scatter cells (by limiting n to 1) or to create islands (by setting n > 1). So you have, in one single algorithm, not only the ability to scatter, but also to group. How does this not answer the OP's question? How is it worthy of a downvote? | |
| Oct 17, 2013 at 17:24 | comment | added | fnord | The question asks to have "no more than four adjacent cells", yet for each user to have an expected portion of the map. This, to me, implies e is going for something more akin to how Risk games randomly apportion the map out for all of the players. Your answer divides the map into "maximally-sized 'home territories'". True, your algorithm stops when the expected territory size limit is reached, but I do not see a way for that player to get new "islands", though you do mention it in later text. | |
| Oct 17, 2013 at 17:06 | comment | added | Engineer | @fnord No, it doesn't. You did not read my answer properly. I explicitly put a limit in the pseudocode: "if player has not yet reached expected territory size in cells". Please remove your downvote. Feel free to check the revision history on the question to satisfy yourself that this was the case since before your comment and downvote. | |
| Oct 17, 2013 at 17:05 | comment | added | fnord | While you provide excellent documentation and pseudocode for your algorithm, I am not sure this matches what the questioner asks about. The question mentions 'biggest "chunks" cannot be more than four cells each', whereas your algorithm creates as large a connected group as possible. | |
| Oct 17, 2013 at 16:55 | history | edited | Engineer | CC BY-SA 3.0 | added 326 characters in body |
| Oct 17, 2013 at 16:44 | history | edited | Engineer | CC BY-SA 3.0 | added 14 characters in body |
| Oct 17, 2013 at 16:37 | history | edited | Engineer | CC BY-SA 3.0 | deleted 67 characters in body |
| Oct 17, 2013 at 16:30 | history | answered | Engineer | CC BY-SA 3.0 |