What's an optimal procedure to create a connected cyclic grid of nodes and edges for A* pathfinding

Question

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!

Answer 1

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.