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!

  • \$\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

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.