Best way to create paths with multiple required nodes

General
1

Hi again

I’m currently implementing a system where I can provide a number of high-level nodes for a tower defense path. Something like this:

node system

Where:
[1,3,5]: Spawnpoints for creatures
[2]: A random waypoint somewhere in the map
[4]: The target/ final node

I’ve built the abstract layer, and I can map each of these abstract nodes to an actual GridNode in our A* GridGraph. Now I’m curious what the best way to force a path through the respective nodes would be. I’ve had 2 ideas so far:

1.: add a “Path” field to each connection in a node. Always only calculate paths between 2 nodes. If a creature reaches the end of a path, it checks the newly reached node and requests a path to a connected node. If no nodes are connected, it’s the end node. If a path is available, just reset path progress to 0 and swap to the new path, continue moving.

2.: somehow force the A* project to find a path through these nodes, and just create one A* path per traversal path through my node system.

If there’s a built-in solution for 2., I think that’s a bit easier (especially since my abstract graphs will never exceed 6 nodes and approximately 6 different traversal paths). Or did you encounter a similar problem and have a smarter solution?

Let me know! Thanks for the help :smile:

2

Just a quick note: I’ve solved this problem.

I’ve got an abstract, high-level unidirectional weighted graph in the background for the “bigger picture” (e.g., where certain movement paths would split and merge). This is then mapped unto A* graphNodes that fit some spatial criteria. Then I simply build a data structure that holds the pre-calculated A* paths within edges, and the engine can digest that to “chain up” the individual paths for large-scale movement.

1 Like
3

Nice solution.

There is no way to do 2 without quite some hacking into the core system.