# 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:

33

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

28

This is Matt, the creator of Trainyard. @DMGregory summoned me here! :) It sounds like you're working through the same issues I had to deal with. It's a tricky problem where there isn't necessarily a perfect solution. One thing to consider is the constraints of the problem. I was targeting a 50mm wide screen on the early iPhones, and Apple's recommendation ...

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

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

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

8

Eric Lippert wrote a series of blog posts about using "shadow arcs" to only iterate over visible cells in linear time without having to search for obstacles in each cell's visibility check. The blog series is archived, but you can find some of it at Microsoft's MSDN blog archive or check the Internet Archive. I've adapted the scanning logic and ...

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

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: $$d_{\text{Euclidean}} = \sqrt{ \left(\vec b - \vec a\right)^2} = \sqrt {(b_x - a_x)^2 + (b_y - a_y)^2}$$ distance = sqrt((end.x - start.x)^2 + (end.y - start.y)^2) In a discrete square ...

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

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

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

I have implemented the algorithm suggested by Jimmy. Video of the code in action here: https://youtu.be/lIlPfwlcbHo /* What this code does: Rasterizes a single Field Of View octant on a grid, similar to the way FOV / shadowcasting is implemented in some roguelikes. Clips to bitmap Steps on pixel centers Optional ...

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

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

I think you can solve the two pain points you indicated with a few heuristics. One is a little hysteresis: once the player is drawing in a particular row/column, keep their drawing cursor locked in that row/column until their mouse/touch point strays more than ~30% of the way into the next row/column. That gives more tolerance for error, so the player has ...

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