Tag Info

Hot answers tagged

32

To summarize and elaborate upon what has been said in other answers and in comments, triangles, squares and hexagons are the only mathematically possible regular tilings aka regular tessellations of the Euclidean plane. So yeah, this sucks. Triangles are completely useless here, squares suck because you can't move diagonally without having a somewhat ...


26

The solution is actually simpler than expected. The trick is to use Minkowski subtraction before your hexagon technique. Here are your rectangles A and B, with their velocities vA and vB. Note that vA and vB aren't actually velocities, they are the distance traveled during one frame. Now replace rectangle B with a point P, and rectangle A with rectangle ...


12

First of all, in the case of axis-aligned rectangles, Kevin Reid's answer is the best and the algorithm is the fastest. Second, for simple shapes, use relative velocities (as seen below) and the separating axis theorem for collision detection. It will tell you whether a collision happens in the case of linear motion (no rotation). And if there's rotation, ...


9

Have you tried Lloyd's Algorithm? The procedure is pretty simple, and will generate fairly regular looking regions (depending on how many iterations you run). Tile the map with blank hexes to start. Choose N hexes at random. These will represent the "center of mass" for each country. Tag each hex with the center hex it is closest to (Voronoi Diagram). ...


9

There are two ways to handle this problem, in my opinion. Use a better coordinate system. You can make the math much easier on yourself if you're clever about how you number the hexes. Amit Patel has the definitive reference on hexagonal grids. You'll want to look for axial coordinates on that page. Borrow code from someone who has already solved it. I ...


9

Basically what you want is a monohedral tesselation (or tiling), that is a coverage of the entire plane (assuming 2d) with a single shape where the tiles do neither overlap nor leave gaps. There are lots of shapes with which this can be done but when we introduce other constraints, usually orientation should stay the same or they should conform to a ...


9

The author of HyperRogue here. HyperRogue actually uses a tesselation made of hexagons and heptagons, here is the reason why this particular tesselation has been chosen, instead of only octagons or heptagons, for example: Hyperbolic geometry in Hyperbolic Rogue Basically, the octagons are too big. Also some consequences of using hyperbolic geometry in a ...


8

Before I answer the question you already asked, some notes: You can use A* with the original grid system you are using. The key things you need are neighbors and distance (for the heuristic). For neighbors with your grid system, you need to do something different for even and odd columns (as you mention); here's how: neighbors = [ [ [+1, +1], [+1, ...


6

There are many hex coordinate systems. The “offset” approaches are nice for storing a rectangular map but the hex algorithms tend to be trickier. In my hex grid guide (which I believe you've already found), your coordinate system is called “even-r”, except you're labeling them r,q instead of q,r. You can convert pixel locations to hex coordinates with these ...


4

You can just apply A*( A-star ). Compared to a uniform square grid the only difference is the way you collect the adjacent tiles ( aka your hexagons ). Each tile should have a table of booleans representing the bridges corresponding to their direction like so //Depending on your hexagon order enum Direction{ NORTH, NORTH_EAST, SOUTH_EAST, ...


4

I think Michael Kristofik's answer is correct, especially for mentioning Amit Patel's website, but I wanted to share my novice approach to Hex grids. This code was taken from a project that I lost interest in and abandoned written in JavaScript, but the mouse position to hex tile worked great. I used * this GameDev article * for my references. From that ...


3

In algorithm 1, you're using “even-q” but you should use “odd-q” instead. Your grid is flipped upside down relative to the one on my page, so you want to shift every odd column up instead of every even column down. Change + (x % 2) in coordOffset2Cube and coordCube2Offset to use - (x % 2) instead. Also, on diagonals, the line drawing algorithm will not hit ...


2

As Martin Sojka notes, rotations are simpler if you convert to a different coordinate system, perform the rotation, then convert back. I use a different coordinate system than Martin does, labeled x,y,z. There's no wobble in this system, and it's useful for lots of hex algorithms. In this system you can rotate the hex around 0,0,0 by “rotating” the ...


2

I don't think using the 'hexagon' is all that helpful. Here's a sketch of a way to get exact collisions for axis-aligned rectangles: Two axis-aligned rectangles overlap if and only if their X coordinate ranges overlap and their Y coordinate ranges overlap. (This can be seen as a special case of the separating axis theorem.) That is, if you project the ...


2

One simple way you could try. Randomly select n hexes. Each one will start a group. For each group try to expand the initial hex in a random direction. If all hexes around the chosen hex are occupied, mark as tapped, change hex. Repeat until each group is 20 hex long or have no more space to expand (all hexes tapped). I didn't test but this should ...


2

Let's consider a generic turn-radius constraint. It must consist of moving 'N' hexes in a straight line before a turn of 60 degrees is allowed. This can be incorporated by: Extending the definition of a path-node with a counter: StraightLineHexesRequired Decrementing StraightLineHexesRequired on each node expansion if EntryDirection == ExitDirection and ...


2

This is what I would do: Assign all cells to random players. On big maps this should be very likely to produce pretty even numbers of tiles for all players, on smaller maps you'll probably need to do some corrections. Break up chunks that are too large. The easiest thing to do would be take all tiles in chunks and again assign each tile randomly. In case ...


2

I actually found a solution without hex math. As I've mentioned in the question each cell saves it own center coords, by calculating the nearest hex center to the pixel coords I can determine the corresponding hex cell with pixel precision (or very close to it). I don't think it is the best way to do it since I have to iterate to each cell and I can see how ...


2

Here is the guts of a C# implementation of one of the techniques posted on Amit Patel's web-site (I am sure translating to Java won't be a challenge): public class Hexgrid : IHexgrid { /// <summary>Return a new instance of <c>Hexgrid</c>.</summary> public Hexgrid(IHexgridHost host) { Host = host; } /// <inheritdoc/> ...


1

Thanks for a fascinating puzzle! Yes, it looks like we can do better than a conversion through cartesian coordinates of hexagon centers. It can be done entirely with integer math, though I've included a rational in a matrix below to keep the notation concise. You're right that both the encoding and decoding processes require loops. Fortunately, because SHM ...


1

Assuming you have a hexmap of n cells in total, and p players, where p <= n, the best way to to tackle this is through round-robin distribution via cellular automata (CA). Initialisation Randomly (and/or using some or other heuristic, such as distance from map centre) pick a starting cell for each player. Since p <= n, this shouldn't be a problem. ...


1

I could fix it with a bit of algorithmics: public PositionArray getArcRange(int originx, int originy, int targetx, int targety, int range) { if (range < 0) { range = 0; } final PositionArray open = new PositionArray(gameMap); final PositionArray closed = new PositionArray(gameMap); final FloatPair direction = ...


1

One small note: you say 'looks like a real life map with countries of different shapes but equal sizes), but 'real' countries are vastly different in size even within certain regions — even the 'large' countries of Europe can vary hugely, with e.g. France being more than twice as large as Italy. With that said, there are obviously gameplay regions to ...


1

I definitely think some type of graph structure would make this possible. Basically create an edge between two Hex nodes if they are next to each other to simulate the whole map. However, I am not sure the exact algorithm for generating a "country" within that map. The thing is, depending on how you want the country to "look" you would need different ...


1

I don't think there is an easy way to calculate the collision of polygons with more sides than a rectangle. I would break it down into primitive shapes like lines and squares: function objectsWillCollide(object1,object2) { var lineA, lineB, lineC, lineD; //get projected paths of objects and store them in the 'line' variables var AC = ...


1

Consider this: public sealed partial class HexCoords { static HexCoords() { MatrixUserToCanon = new IntMatrix2D(2, 1, 0,2, 0,0, 2); MatrixCanonToUser = new IntMatrix2D(2,-1, 0,2, 0,1, 2); } protected HexCoords(CoordsType coordsType, IntVector2D vector) { switch(coordsType) { default: case CoordsType.Canon: _vectorCanon ...



Only top voted, non community-wiki answers of a minimum length are eligible