# Tag Info

67

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

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

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:

37

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

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

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

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

7

This is most intuitive way that I can think of.

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

There's a useful isomorphism we can exploit between hex grids and square grids: with a simple shear transformation, we can transform one into the other. We'll use this in two ways: We'll use the regular tiling of these square tiles (and their symmetries) to chart out the hexagonal grid lines we need to draw. We'll use the square grid layout to store our ...

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

5

(1) You may be able to adapt an algorithm used for creating word clouds. Here's one example algorithm, based on Wordle's strategy. This works by choosing a start position/size/orientation for each object (generally starting with the biggest/most important ones), and trying to place it there. If it collides with an already-placed object, move it ...

5

Blue's idea is good, but the implementation is a bit clumsy. In fact, you can easily do it without sqrt. Let's assume for the moment that you exclude degenerate cases (BeginX==EndX || BeginY==EndY) and focus only on line directions in the first quadrant, so BeginX < EndX && BeginY < EndY. You'll have to implement a version for at least one ...

5

First of all, unless you have an exorbitant number of entities, assigning them to a sector on every logic frame is most likely performance-wise negligible. That said, it sounds like you are in over your head. Either your game doesn't actually need spatial partitioning, or what you are trying to create is too advanced for your level. The point of spatial ...

5

It's called a flood fill, and it's what you see in paint programs. It's very fast. Pseudocode: declare visited list //the results you want declare unvisited list add current element (where red dot is) to unvisited list while unvisited list not empty get current element from unvisited list add current element to visited list for all (8) neighbours ...

5

On tracking Your current simulation behaves pretty well, I would say. Because a rail wagon that is halfway a sharp bend, will indeed exhibit the behaviour that the wagon's center is no longer above the track, but next to the track. Center of the tile Traveling over the exact middle of a 32x32 tile: This is easily accomplished if you were to draw the rails ...

5

How do you approach Canvases in Unity? It's possible to use more than one screen-space canvas in Unity, but it's uncommon. There is usually no reason to do that, unless you want different UI elements to use different basic canvas settings. If you want your game to support multiple resolutions, then you want to avoid absolute positioning. You usually anchor ...

5

One of the creators of HAA* (a generalization of HPA*) wrote a very accessible article explaining how it works on aigamedev.com. Unfortunately that site seems to be dead, but fortunately archive.org has the article archived. I highly recommend reading it, but to summarize: HPA* breaks the map into chunks. In each chunk, you identify the possible entrances/...

4

Well, you don't exactly need to treat to shapes as one if there's a distinction between shapes that are moving and shapes that are at rest. A shape (A) could detect a shape (B) directly below it and if it's moving, then the B shape could then see if there's anything directly below it, and if there's an resting shape, then A and B are now resting, and if ...

4

As was approximately pointed out in comments, the simplest way to do what you're after is to test the center of the square, rather than all of the corners. This isn't exactly equivalent to a majority of the square's area being within your circle, but the latter is a Hard Problem, and it should be close enough for your needs. But note that this doesn't take ...

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