Saturday, October 8, 2016

c++ - 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:


Xcom's implementation


...

(source: gameinformer.com)


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:


Line dilemma


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.



Answer



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: Algorithm Explanation


This is the in-engine result: Algorithm Result


No comments:

Post a Comment

Simple past, Present perfect Past perfect

Can you tell me which form of the following sentences is the correct one please? Imagine two friends discussing the gym... I was in a good s...