1
\$\begingroup\$

like the title says, I'm trying to create a grid of nodes that hold edges or connections to each other so I can perform A* algorithm to have objects traverse across them as seen in your standard RTS.

I want to know if there is a general structure and algorithm for this node grid data structure as I can't find a good resource online. For instance, I will be moving my objects via position (Vector3) so I will have to calculate my edge weight to be the magnitude between two nodes. Is this a standard practice?

Could anyone perhaps guide me to the rough basics on how this is achieved in a standard RTS? I would greatly appreciate any information!

\$\endgroup\$
2
  • \$\begingroup\$ Grids and navmeshes are two common ways to approach this problem. There are many many ways these are implemented though - without knowing more about your game it would be tricky to pick out just one to recommend. \$\endgroup\$
    – DMGregory
    Jun 26 '16 at 12:13
  • \$\begingroup\$ What is the topology and geometry of your world? Do you have a planar geometry with contours? A spherical planet? A galaxy with no curvature? All of these would be modelled in dramatically different ways. \$\endgroup\$ Jun 26 '16 at 18:45
1
\$\begingroup\$

There's not much mention of the nitty gritty because basically this is the hard part, and it depends on your situation. A* is an easy algorithm to implement but translating from real world maps to actual data nodes is not a pleasant problem.

The approach I use in my game is to use collision detection to fill up a big 2d grid with the unblocked areas. But this would have to be adjusted for 3d.

For other games I have seen people manually place nodes onto the terrain in their game worlds and then have their program pick up and process the nodes into a graph.

For some I have seen something similar to what I did above except in 3d. Using collisions AND gradients to tell if an area is walkable - ie you can walk up a hill but you can't walk up a cliff. Basically you are flood filling outward and accept any location without too much of a gradient as a valid step.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .