Skip to main content

Hexagonal tile map

Posted by malenkov on February 26, 2009 at 1:00 AM PST

To supplement the posts about the triangular and square tilings, let's consider the third type - the hexagonal tiling. This is my favorite one. Each hexagon has more non-diagonal neighbors than a square. It simplifies calculating distance between two tiles. The main disadvantage of this tiling is that the axes are not orthogonal.

A hexagonal tile map can be easily converted from a square tile map with shifted rows:


Let me introduce several definitions to be used in further calculations:

The tile size defines distance between the central points of neighbors. The size is set during a map initialization and is used to calculate other values.
Coordinates of a point.
Indices of a tile.
r = size/2
Radius of the inscribed circle.
w = size
Width of the corresponding rectangle.
h = 3×r / 2×sin 60°
Height of the corresponding rectangle.

Calculating the central point of a tile by its index

x = (2×i - j + 1) × w/2

y = (j + 2/3) × h

Calculating the index of a tile by a point inside

j = (int) y/h

i = (int) x/w + j/2

dy = y - j×h

dx = x - i×w - w/2

The following calculations should be made if dx×h/3 > dy×w/2 and dy < h/3:


i--     only if x < 0

Calculating distance between two tiles

di = |i1 - i2|

dj = |j1 - j2|

d = di + dj     if (i1 ≤ i2)&(j1 ≥ j2) or (i1 ≥ i2)&(j1 ≤ j2)

d = max(di,dj)     otherwise

Running the example

The following example shows an implementation of the hexagonal tiling map. Each tile contains information about its indices and a distance from the selected tile.

Java applets are not supported...

The source code is available, though, it is not optimal. It is diff-optimized.

Related Topics >>


Edges Up?

This is very good work but the only problem is that usually in games, the tiles are arranged so that an edge is on top, not a vertex. That way game pieces can always move one unit in the six directions: up, down, upper-left, upper-right, lower-left and lower-right. Of course, you could always do a rotation on the tiles or the tiled plane using an affine transformation but I was wondering if there is an easy way to modify the code that creates the arrays of points to produce this effect?

JavaFX is bloated take for instance these small applets that use Swing are fast too or JavaFX loads too much stuff why would I need to load all the jar and dll files just to display a hello world applet. The culprit is the deploy.js

Very impressive work!

@mikeazzi: There are JavaFX JIRA bugs for startup improvements, see RT-2041 "Improve startup time on Windows with 6u10 by not initializing Nimbus Look and Feel", it's apparently not trivial. They actually have a prototype fix, but it's not considered low-risk. IMHO, a perception of bad performance is in the high-risk category as something that can kill JavaFX, so I would put extra priority in ANY enhancement of startup time... In the competitor with other RIA platforms, notice that the other guys don't typically eat their dogfood. Flash loads fast and uses less memory, but Flash is not implemented in ActionScript; it's all native code. Same goes for Silverlight. But JavaFX (except for media codecs and acceleration of the Effects system) is a mix of Java and JavaFX. JavaFX Mobile uses more native code. The file javafxrt-stub-cldc.jar (found in the emulator SDK) has a suggestive name. If you decompile the classes you'll found many dummy methods; for example, in SplineInterpolator, all calculation methods (eval(), interpolate() etc.) are just "return 0.0F". (The desktop version of the same class contains lots of math code, as I'd xpect.) That means these methods are somehow substituted by native code -- CLDC doesn't support JNI, so I guess this stubbing technique is a workaround. But I think in JavaFX desktop, use of native code for fine-grained operations wouldn't pay, due to the higher JIT overhead, and also the fact that JIT compilers can often produce much better code for calls into small API methods (thanks to inlining). Overall, it seems like Sun has already made the right tradeoffs in each runtime, without any PureJava fanatism. Which means that further startup improvements must come from solutions other than native code.

Hi Osvaldo, good observation, I noticed that too, and I too was wondering what kind of applets are these that they achieve such instantaneous loading, and rendering. If it weren't for the tray icon, I would not have suspected that these were applets. So yes, I agree, the flash-level start up experience is there, and java as a RIA platform is alive and well, only if Sun can get that same seamless loading experience to happen with JavaFX applets as well. Like you said there is so much crap that gets loaded every time a JavaFX applets loads, that doesn't need to. These are low hanging fruits as far load time speed up, if you ask me, and I am surprised that they haven't knocked them off yet.

I've been following all your blogs (superficially, I admit: didn't check the sources) and I didn't notice that the example was a Java Applet; I initially supposed it was a static graphic, until the first time I moused over it, then I thought it was a cool JavaScript/DOM hack. Since the applet doesn't appear until I scroll down the page, I didn't see the applet loading animation. Even if I enter the page and immediately scroll down, the loading is very fast (~1 second?) so it would be a great idea to remove that animation completely. And I'm talking about cold-start of course; in a warm start test (browser and Java plugin already started, applet resources already cached, open a new tab with the "Discuss" link so it jumps straight to the end of the page and I don't even need to scroll-down), the applet appears immediately. In both cases, this is Flash-level startup experience, if you ask me. So much for "Java is dead for RIA" FUD! The secret, of course (now that I see the code), is that your applet is a small program that uses only AWT. Result, instant loading time. Now thinking towards Swing and JavaFX, both obviously need some extra work to achieve this kind of quasi-instant loading. Better CDS; looser coupling (JavaFX loads 200+ Swing classes including the Nimbus LAF even if you never use any Swing component); lazier initialization, etc.

Done. Thank you for pointing this...

Any chance of providing an applet that supports Java 5 (the applet classes are v6) ? Not everyone has access to 6 in their browsers. Alternatively, package it with Webstart. Yes, I know I can download the source, but I imagine you don't want to put up unnecessary barriers for your audience!