Jump to content
  • Advertisement
Sign in to follow this  
Oida

RTS Pathing Issues (A*)

This topic is 2639 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a similar game to a normal tower defense, where you can also build units that will walk along the lane and attack anything they see.

I'd like my units to walk along a path (currently realised via A* and working with a few tweaks) and surround other enemies. They should NOT collide with each other while attacking (might seperate when they reached the target). This is where my problems start. I got some basic pathic with A* working, but I doubt I'm using it correctly.
At the moment I'm saving my final map grid at the start and generate a copy of it every update. Then I'm adding additional nodes at every units position to the copy and use this one for pathing.

Apart from some performance issues that I might be able to fix, I don't know when to calculate which paths. Currently I generate a path for the normal movement at the start of the game and then I'm waiting for units to come close to each other and aquire a target. This is where it gets complicated and my fps drop a lot. Since there are a lot of units walking close to each other, I have to generate a new path every few updates, so they won't all reach the target at the same place, but they still do it.

Is there a better approach to avoid units attack from the same angle?

Share this post


Link to post
Share on other sites
Advertisement
1. Only draw one sprite of them when they all reach the node, have a death sprite for when one dies and regenerate another sprite for however many there are.

2. Someone had a similar problem which can be viewed here: http://stackoverflow...-a-pathing-code
I think that when you are looking for the next "currentNode", you should not start with lowestF = (nodes[currentNode].g + nodes[currentNode].h); because that value, in principle, will (always) be lower-or-equal-to any other nodes in the open-set. Just start with the value of std::numeric_limits<int>::max() or some very large number, or use a priority queue instead of an std::vector to store the nodes (like std::priority_queue, or boost::D_ary_heap_indirect).

I'm pretty sure that is the problem. And since your heuristic can very often be equal to the actual path-distance obtained, there is a good chance that following nodes in the open-set turn out to have the same cost (g+h) as the currentNode. This would explain why certain paths get explored and others don't and why it gets stuck.

[/quote]
And thanks for pointing me in the direction of 'std::priority_queue' and 'boost::D_ary_heap_inderect'.[/quote]

Share this post


Link to post
Share on other sites
The general method here is to split your unit control into pathing and steering, aka path-finding and path-following. You use A* to get a high-level overview of where to go, then coordinate your movement and such using a basic steering system. I believe the AI Forum FAQ has some good resources on this.

Share this post


Link to post
Share on other sites
For traversal to a given target or destination, you might want to do a single A* search which ignores transient (moving) obstacles, and periodic "local" A* searches (limited to a short range) to path around local transient obstacles, as the unit traverses its larger scale path. Of course, if it's possible for paths to become blocked for significant periods of time, you'll have to re-path on the large scale occasionally as well.

To solve the "everyone-chooses-the-same-destination" problem, you might want to allow units to choose an intended landing spot as they approach their target, and to "plot" a special transient obstacle into the A* data at that point. This obstacle would block other friendly units, about to come into that landing spot selection range, from aiming for the same spot as they get close.

The frequency of refreshing a path is a tuning issue. Every frame is too often, and every several seconds is probably not often enough. Start off refreshing every several seconds. Then, when this causes obvious anomalies, dial down the refresh period until path traversal behavior starts looking "less stupid".

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!