Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (494)
Games in Android Showcase (114)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Hexagon board  (Read 5811 times)
0 Members and 1 Guest are viewing this topic.
Offline Del-ONE

Senior Newbie





« Posted 2008-10-06 15:52:46 »

I've started planning out a hexagonal board/strategy game, and right now I'm working on the best way to lay out the board in memory. 

My first impulse was to throw it in array and give each 'half-step' its own row (so one square down on the board would be two rows down in the array), but I'm not going to write code that wastes about half the memory it allocates with the empty cells this produces unless I have to. 

My second thought was to force it to better fill the array by killing the white-space, however, this leads to problems distinguishing where to look for corners, which may possibly be solved by using mod 2 to figure out where the two side squares are.

Another possibility that I haven't written out would be to just layout the 'connections' between pieces...

Anyways, since I have class in a bit, I thought I'd ask here.  Has anyone done this, and if so, how did they do the board layout?
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #1 - Posted 2008-10-06 16:56:39 »

I would do links. Each one has a pointer to N, NE, E, SE, S, SW, W, and NW. Then just store the "root" room (i.e. the center) and draw them out from there. You don't want to have to use really kooky game logic to see if moves are legal and whatnot.

See my work:
OTC Software
Offline SimonH
« Reply #2 - Posted 2008-10-06 16:59:07 »

I used a square grid of nodes (simple array). If you interconnect each node with it's right, bottom and bottom-right neighbours - voila! A hexgrid! If you want to draw it on screen you'll need to skew the rows...

People make games and games make people
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Del-ONE

Senior Newbie





« Reply #3 - Posted 2008-10-06 17:27:46 »

What you guys say makes sense.  I think avoiding an array will also make certain part of the game (such as finding all the spaces in a straight line) much more intuitive.

Thanks  Grin
Offline ddyer

Senior Member


Medals: 5



« Reply #4 - Posted 2008-10-06 18:42:33 »

I have almost completely converted my games to a link based representation of the
board.  There are numerous advantages - scanning in a particular direction or from
a particular center becomes a very natural process.   Odd board geometry can also
be dealt with pretty naturally - for example, in my implementation of Fanorona,
the weak links are handled by simply removing the links, and in Tzaar, where the
center hex is not used, I simply remove it from the grid.  Also, if properly parameterized,
switching a game from square to hex grid becomes simple.  In my implementaion of
Volcano, normally played on a square grid, a version on a Hex grid is also available
which has almost no special cases to deal with the current board shape.  You can
play these games at Boardspace.net
Offline SwampChicken
« Reply #5 - Posted 2008-10-07 02:31:29 »

So you guys mean...

1  
2  
3  
4  
5  
6  
7  
8  
public class Hex {
  private Hex north;
  private Hex northWest;
  private Hex west;

...

}
Offline SimonH
« Reply #6 - Posted 2008-10-07 15:12:39 »

So you guys mean...

1  
2  
3  
4  
5  
6  
7  
8  
public class Hex {
  private Hex north;
  private Hex northWest;
  private Hex west;

...

}


Kinda... I used;

1  
2  
3  
4  
5  
public class Node {
  // neighbour ordering: 0=E, 1=NE, 2=NW, 3=W, 4=SW, 5=SE
 private Node[] neighbours=new Node[6];
...
}


because the links need to be reciprocal for pathfinding.

People make games and games make people
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #7 - Posted 2008-10-07 17:17:49 »

Yeah, but you definitely get the idea, I think. I've never done hex, but I've done N, E, S, W, up, down, and using links easily made the most sense.

See my work:
OTC Software
Offline Del-ONE

Senior Newbie





« Reply #8 - Posted 2008-10-10 16:23:45 »

I'm now working on the AI for path finding, but I want to do the specifics on my own (so I'm not posting the code).  All I want to say is that it makes use of the linked neighbors concept, and recursion is the best way to move through them. 

So if there is the possibility of missing/occupied hexes and there is a set limit of moves, any1 have a good suggestion for finding the shortest path without mapping out all possible paths?  I was thinking of finding a hex close to the midpoint mapping out an area around it that makes use of the moves available and then finding the path, but I'm not quite sure how I could do that and still ensure that, if a path exists with the given limit of moves, it will be found...

Ideas, examples, or even vague ramblings will all be appreciated Smiley

EDIT: Nevermind, I figured it out, and I'm an idiot.  I should have realized that as I got all the movable spaces, I could build paths (and only keep the shortest), because that's essentially what its doing anyways.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 793
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2008-10-10 20:41:05 »

So here is your average 5x3 hexgrid


1  
2  
3  
public int w = 5;
public int h = 3;
public Hex[] grid = new Hex[w*h];



Get the 2D coordinates of the cell at index N:
1  
2  
3  
4  
5  
6  
7  
public void fillPositionOfIndex( int n, float[] result )
{
   int row = n / w;
   int col = n % w;
   result[0] = col;
   result[1] = row + ((col + row) % 2) * 0.5;
}




References to neighbours of cell N:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
public static final int NORTH = 0;
public static final int NORTH_EAST = 1;
public static final int SOUTH_EAST = 2;
public static final int SOUTH = 2;
public static final int SOUTH_WEST = 3;
public static final int NORTH_WEST = 4;

public void fillNeighboursOfIndex(int n, Hex[] hexagon)
{
   hexagon[NORTH] = isValid(n-w) ? grid[n-w] : null;
   hexagon[SOUTH] = isValid(n+w) ? grid[n+w] : null;

   int x = ((n%w)%2)*w;
   int y = w-x;

   hexagon[NORTH_WEST] = isValid(n-x-1) ? grid[n-x-1] : null;
   hexagon[NORTH_EAST] = isValid(n-x+1) ? grid[n-x+1] : null;

   hexagon[SOUTH_WEST] = isValid(n+y-1) ? grid[n+y-1] : null;
   hexagon[SOUTH_EAST] = isValid(n+y+1) ? grid[n+y+1] : null;
}

private boolean isValid(int n)
{
   return n >= 0 && < w*h;
}



(Not tested, not even compiled!)

And the prize for least readable code goes toooo..... persecutioncomplex

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11
Exp: 10 years


Game Engineer


« Reply #10 - Posted 2008-10-12 03:11:39 »

I'm now working on the AI for path finding, but I want to do the specifics on my own (so I'm not posting the code).  All I want to say is that it makes use of the linked neighbors concept, and recursion is the best way to move through them. 

So if there is the possibility of missing/occupied hexes and there is a set limit of moves, any1 have a good suggestion for finding the shortest path without mapping out all possible paths?  I was thinking of finding a hex close to the midpoint mapping out an area around it that makes use of the moves available and then finding the path, but I'm not quite sure how I could do that and still ensure that, if a path exists with the given limit of moves, it will be found...

Ideas, examples, or even vague ramblings will all be appreciated Smiley

EDIT: Nevermind, I figured it out, and I'm an idiot.  I should have realized that as I got all the movable spaces, I could build paths (and only keep the shortest), because that's essentially what its doing anyways.

A* ?

See my work:
OTC Software
Offline 8ballj

Senior Newbie





« Reply #11 - Posted 2009-01-28 18:44:51 »

If you establish the hex grid solely through linking from a central spot, can you still do pixel - hex coordinate conversion for mouse events and such?  What about finding the viewable hexes for efficient drawing?
Offline Del-ONE

Senior Newbie





« Reply #12 - Posted 2009-01-28 20:22:04 »

If you establish the hex grid solely through linking from a central spot, can you still do pixel - hex coordinate conversion for mouse events and such?  What about finding the viewable hexes for efficient drawing?

For my purposes, keeping a master list of hexagons and iterating through them to find any 'hits' for the mouse event was perfectly acceptable, though that might be too slow in very large lists.  Changing how that was stored (say a 2d array or what Riven posted rather than an ArrayList) could conceivably speed that up to O(1) (assuming theres a correlation between location and index) and allow for clipping unseen hexes for drawing, though populating the list would be more complicated.  Basically you would be supporting both methods of map storage (b/c laying out the master list like this would support finding neighbors etc. from it) and using the links for faster interaction operations (like moving a piece) and the master list for global events (drawing, updating, and mouse events). 

However, the whole reason I went with the links was to avoid populating that list (so that I could throw together arbitrary boards of various shapes and sizes by removing neighbors w/o worrying about null pieces). 

If, as you said, you only stored the links, you could find mouse hits by recursively* stepping through the list from the center the same way you would 'grow' the array, but I feel that would end up having more overhead than even an ArrayList.

*A question occurred to me while working on this project and I never found the answer. Is it still recursion if you call the same Class.method() but using different objects, as in calling neighbor.grow(n-1) within Hex.grow(int n)?
Offline 8ballj

Senior Newbie





« Reply #13 - Posted 2009-01-28 20:31:44 »

I'm planning on large (1000+) hex maps, so iterating through them is definitely not an option.  Like you said,  I'll probably index the hexagons in an array so they map quickly to pixels, but then use the link mappings for movement.  I was just wondering if there was a clever way of using the "link" method for all of my needs Smiley
Offline Del-ONE

Senior Newbie





« Reply #14 - Posted 2009-01-28 20:46:03 »

Oh, here's an idea that might make stepping through the links faster than iterating through a master list.

You start from the center and instead of spreading out in all directions you just step in the direction to get closer to the mouse event point (assuming you have the coordinates of the hexes). You'd have to be careful of cases where the mouse didn't click anything (may or may not be possible in your game) and how you determined the next step direction (otherwise you might end up circling).  Also, you would want to store the neighbors in a way that lets you know the direction the neighbors are in (as in an array with index correlating to specific directions, or whatever you could come up with).

That's about the 'cleverest' thing I could think of, but I wouldn't be surprised if someone came along and blew my mind out the back of my skull with awesomeness, lol.
Offline rdcarvallo

Senior Member


Projects: 5
Exp: 15 years


2D Java games forever!


« Reply #15 - Posted 2009-02-03 13:46:01 »

In my Hexodama (J4K) game, I used the skewed 2D array, really good to check for rows of objects.

See the attachment.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Dwinin (21 views)
2014-09-12 09:08:26

Norakomi (55 views)
2014-09-10 13:57:51

TehJavaDev (66 views)
2014-09-10 06:39:09

Tekkerue (33 views)
2014-09-09 02:24:56

mitcheeb (54 views)
2014-09-08 06:06:29

BurntPizza (38 views)
2014-09-07 01:13:42

Longarmx (24 views)
2014-09-07 01:12:14

Longarmx (30 views)
2014-09-07 01:11:22

Longarmx (28 views)
2014-09-07 01:10:19

mitcheeb (37 views)
2014-09-04 23:08:59
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!