# How to order points on a 3D grid such that we can connect them in a line loop correctly

I want to recreate an effect as close as possible to X-Com: Enemy Unkown's movement range feedback: The blue line delimits the tiles which the soldier can reach using a single action. We also are using a 3D grid approach in our game. We are not developing this with a pre-built engine, so I'd like some sort of algorithm which I am not aware of, not some engine's feature (unless it is well documented). We've discussed using things like quickhull, but quickhull generates a convex contour, while this contour can be concave or convex.

Any thoughts or ideas? Thank you for all your input

Edit: Yes, we already have the centers of the tiles which are the "edge" or outermost tiles of the walkable area. What we're not sure about is the following: From the green center, given just the points, we could draw both the red and yellow contours. How do we know which one is the correct one? What data would we need?

Final edit: One of the programmers on my team figured out something which is good enough for our purposes. It is not exactly the same as the output of whatever X-Com is using.

We take the whole tiles given to us by the Dijkstra pathfinding algorithm on the set of tiles and start at one which we can guarantee is an edge. We define a forward direction and a perpendicular vector to that direction. The direction vector is the one used to walk between tiles and the perpendicular vector is used to check whether there is an adjacent tile in that direction to which the forwrad direction must be rotated to. If none of those point to a valid tile, we rotate away from the perpendicular vector. An accompanying image will follow so that we can explain it better for anyone else who wants to accomplish a similar effect.

• You do a floodfill now right to get all the valid tiles? Dec 4, 2014 at 14:27
• If I understand correctly you already generated the points, and you want to connect them correctly in a line loop? Dec 4, 2014 at 14:34
• We're using Dijkstra. It's what seemed like the most useful at the time due to its circular expansion pattern. Dec 4, 2014 at 14:34
• Yes, we pretty much have the points which are farthest. However, we don't have the order, as a random set of points can be connected several ways. Dec 4, 2014 at 14:35
• You need to have a criteria of which is the correct one, otherwise the result will be artibrary. What I mean is in the graph you showed both are valid line loops, you put the criteria of how to connect them, for example taking the next nearest vertex. Dec 4, 2014 at 14:50

• Create your points so they form a solid line on a 2D plane.
• Walk the line starting with a point that's on ground level, for each point:
• If the ground is above or below the current position, add a new point, and shift the existing point and all remaining points up or down to meet the height of the ground. -Continue until all points have been touched.

You can think of this like projecting the line down from above the world.

First of all, I think the grid is pseudo-3d: 2D movement area, but create vertical lines when the height changes. Given that, check this answer, as the same principle applies.

• Thank you, this is helpful. However, they stopped short when discussing the ordering of the points, which is the main issue at hand. Dec 4, 2014 at 14:53

Hmm... like the other answerers, I'm going to make some guesses about unclear information in the question.

My assumptions:

• Your map is essentially 2d, and projected downward onto the walkable surface
• Your map is represented as a set of polygonal areas
• Adjacent areas share 2 (or more) vertices

If that's true, one approach is to:

• Collect the edges of the accessible areas, including the one you're on (if you're allowed to stay there)
• Count duplicates (edges used by more than one area polygon)
• Throw away edges used more than once

The remaining edges form the 2d accessible outline. You could join them to make a closed loop if needed. Project downward to walkable areas. Draw.

Bonus feature -- works even if the accessible area is noncontiguous, for example if you're not allowed to stay where you are, or there are wormholes in the map.

One of the programmers on my team figured out something which is good enough for our purposes. It is not exactly the same as the output of whatever X-Com is using.

We take the whole tiles given to us by the Dijkstra pathfinding algorithm on the set of tiles and start at one which we can guarantee is an edge. We define a forward direction and a perpendicular vector to that direction. The direction vector is the one used to walk between tiles and the perpendicular vector is used to check whether there is an adjacent tile in that direction to which the forward direction must be rotated to. If none of those point to a valid tile, we rotate away from the perpendicular vector.

Image with explanation: This is the in-engine result: 