# Tag Info

71

Octogons: Hexagons: The gaps in the octogons make for an unappealing game world. Typically, if you wanted to allow for eight directions of movement, you would just use squares.

67

Dungeons and Dragons 3.5 (pen-and-paper RPG) has a solution used for both movement and grid-based radius calculations: diagonal movement costs 1.5 what orthogonal costs. Since the diagonal of a unit square is approximately 1.414, 1.5 is pretty close. Because D&D 3.5 only supports integer movement, the way this is actually calculated is that orthogonal ...

66

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 ...

66

You need to change the shape of the field of view. So that when you move in any direction, the same number of new squares become visible. Here is one possibility:

32

X = x*cos(θ) - y*sin(θ) Y = x*sin(θ) + y*cos(θ) This will give you the location of a point rotated θ degrees around the origin. Since the corners of the square are rotated around the center of the square and not the origin, a couple of steps need to be added to be able to use this formula. First you need to set the point relative to the origin. Then you ...

29

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 ...

26

To have diagonal and orthogonal movement reveal approximately the same area, you need two things (each of which, alone, has already been suggested in another answer or comment): Approximately circular view range: On its own, this won't give exactly the same revealed area for both types of movement. For example, in the image above, orthogonal movement ...

24

A hexagonal ring with the radius of N consists of 6 straight lines, each with length N - see my extremely crude example below :) For N=2: The arrows cover 2 hexes each. I assume you have some functions which give you the neighbouring tile in a specific direction, like north(), southeast() etc. So your algorithm, in pseudocode, should be something like ...

20

I created a system similar to the one you're after in 3D. I have a short video demonstrating the simple mechanics of it here and a blog post here. Here's a little gif I made of the pressure mechanics behind an invisible wall (played at high speed): Let me explain the data involved, to give an idea of some of the features of the system. In the current ...

14

getBodiesToCheck() There could be two problems with the getBodiesToCheck() function; first: if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b); This part is O(n2) isn't it? Rather than checking to see if the body is already in the list, use painting instead. loop_count++; if(!loop_count) { // if loop_count can wrap, // you just need to ...

12

There's a number of pieces to this puzzle, each of which will provide a deep and interesting rabbit hole of exploration. Some of them are: Level of Detail -- automatically (or "manually") choosing detailed or simplified models, or even sprites or just dots, or for objects as they are further away. Culling -- choosing to only draw what's needed. This might ...

11

Since you are using a grid and know which direction the user is proceeding there is nothing constraining you from adapting the prior answer and using a different fields of view depending on the direction. For example you could extended the field to include the corners when you travel in cardinal directions and shrink it down two squares on each end in your ...

10

You are looking for a grid traversal algorithm. This paper gives a good implementation; Here's the basic implementation in 2D found on the paper: loop { if (tMaxX < tMaxY) { tMaxX = tMaxX + tDeltaX; X = X + stepX; } else { tMaxY = tMaxY + tDeltaY; Y = Y + stepY; } NextVoxel(X, Y); } There's also a 3D ray-...

9

The parallelogram coordinates you're using are easier to work with, but they do have the drawback of being weird for rectangular maps. One approach is to store it with the offset coordinates but actually use parallelogram coordinates in your game logic. Observation: in each row of the map, the grid data is contiguous. All the wasted space is on the left ...

9

Fascinating question. I think one of the first issues you have to address is whether you want the patrolling behavior to be "optimum" patrolling or "lifelike" patrolling. I'm just making up these words, but what I mean is: Optimum: The agents move about in a manner that perfectly distributes their coverage area for the system as a whole. Lifelike: The ...

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 ...

8

You could try casting "shadow arcs" to cover larger areas at once. While the actual details are a bit involved, Eric Lippert has a very in-depth explanation (with live Silverlight demo) at http://blogs.msdn.com/b/ericlippert/archive/2011/12/12/shadowcasting-in-c-part-one.aspx.

8

Complete vs. incomplete information What you are looking to do is path finding without complete information. The conceptually sound way to do this would require you to keep track of all of your non-playing character's information state (i.e., the parts of the map they already have discovered). Local information A more workable solution in your case might ...

8

This is based on my speculation and skimming through Celestia's source code. Celestia allows you to fly around a planet and zoom out to see the whole galaxy. I browsed its source code and found it used an octree, a structure to recursively divide space into 8 octants. The renderer would render the environment by traversing the octree, and don't traverse ...

8

I will present a general concept and three solutions using that concept. Concept is an Influence map: For each location in the map, you are going to store a number that represent the distance to each color point. That way, for each position you can query how far it is from blue, red, green, etc. We call the result is the influence map. For more detail on the ...

7

Ray casting is a very fast and efficient way to determine line-of-sight. It basically involves sending a ray (think of it like an infinite laser that can't be redirected) from a certain position in a certain direction. Using this ray, you can determine things like which point(s) it intersects and how far away from the origin it was when it crossed a certain ...

7

One of the popular ways to do this, as Doorknob says in their comment, is Bresenham's line algorithm. The example image of which looks nearly identical to you requirement example: It's commonly used to draw lines on the computer screen deciding which pixels to use to represent that line. In your case, you'll use it to decide which grid spaces to check. ...

7

Judging from a quick look at the libgdx wiki's SpriteBatch entry, alpha blending is on by default. Blending is enabled by default. This means that when a texture is drawn, translucent portions of the texture are merged with pixels already on the screen at that location. This means that you can do what you said: open the Hero texture in Paint .NET and "...

7

How about, rather than having a fixed viewing range, have the player's visibility area depend upon what direction the player was facing, as well as perhaps the direction the player faced in the last few turns (a player who was moving north might be able to immediately take a step south, but might take a few turns to get maximum viewing distance in that ...

7

I start with coordinate systems — the coordinates for grid locations are (x,y) but as Krom mentioned in a different answer, for walls there can be up to two walls for each grid location. That leads to a second coordinate system, for edges between tiles. In this article I used West and South so the edges can be (x,y,West) or (x,y,South), but you can pick two ...

6

Personally, I would prefer simplicity over saving memory. Don't optimize until needed! If you're still bent on saving a few bytes, here's how you can do it: Slice the parallelogram in half to form two right triangles Rearrange the two triangles to form a rectangle. (Note I added the green buffer strip so the math works out nicely.) Python code to map ...

6

Note that I've never done this; these are only ideas which may help. Or might be totally bogus. I'd been wanting to tackle this problem ever since Terraria but am not currently working on such a game. A way I've considered trying is to give each surface water block (any block with water in it and with no water block above it) an initial pressure value ...

6

Without details of your existing algorithm, it's hard to say, but in pretty much any case involving a line over a grid, I've found the answer to be Bresenham's, or a variant thereof. In this case, I'd recommend looking at the Midpoint Circle Algorithm. That can give you a set of outer-bounds tiles, and then just fill it from there.

6

If you don't need to navigate around obstacles along the way, you can do this with a simple formula. Just like in continuous space we can use the Euclidean distance metric: distance = sqrt((end.x - start.x)^2 + (end.y - start.y)^2) In a discrete square grid we can use the Chebyshev distance metric (if we can move on diagonals): distance = max(abs(end.x - ...

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