Jump to content
  • Advertisement
Sign in to follow this  
impulsee

Formations in RTS (A* pathfinding)

This topic is 1085 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

Hey guys,

 

I'm trying to create an RTS but first making small programs that deal with different aspects of the type of game i want to create. Atm I have a 3d demo of one object that i can click and move around the map with the use of seek behaviour with A* (my map is gird/tile based) Now I want to be able to do the same but I'm having trouble thinking of a good way to move a group of units as a formation (im trying to move things as a box shape like in warcraft 3). 

 

For this I have seen that you can create a formation from the units you have clicked, pick a leader, and then "flock" (with an offset for each unit) the group to its target location with using alignment to keep the units going to its destination, cohesion to keep it in place in the formation, and separation for local avoidance from other units.

 

I feel like this would work OK for the most part (presuming i can get the formation algorithm working) but the problem I have is that I don't know how I would deal with collisions on the way to the location (as the a star would only be calculated for the leader not the group) and what if at the end location the formation is not possible (there is a wall in the way or something similar). 

 

Another way I was thinking was to simply project the formation at the mouse click location and make every unit path find there way there but i still run into the same problem with the end position. 

 

So my question is do any of you guys know a fix for this, or just a better way in general to do path finding for multiple agents. 

 

Share this post


Link to post
Share on other sites
Advertisement

I think a lot of games likely determine the position of the troops when you click to move them. Some games even have a little graphic to show where each of the units will be standing after you move them like:

 

OOOO

OOOO

 

or

oo
oo
oo
oo

 

If you know the start and end positions then you can have each unit do their pathfinding individually and use steering behaviors to keep units from running into each other.

Share this post


Link to post
Share on other sites

You really didn't provide us with enough information about your game. Is it discrete cell-based? If so, yeah, you might have situations where agents would block each other. If it is free-move, then local steering for collision avoidance will always be your go-to solution for any group scenarios -- this one included. Another option is to allow some penetration of the agents so that they can move through each other somewhat.

Share this post


Link to post
Share on other sites

You really didn't provide us with enough information about your game. Is it discrete cell-based? If so, yeah, you might have situations where agents would block each other. If it is free-move, then local steering for collision avoidance will always be your go-to solution for any group scenarios -- this one included. Another option is to allow some penetration of the agents so that they can move through each other somewhat.

 

Yer, I have a grid of tiles where each one is a waypoint for A* to use to get the unit where I want it to go.   There will be obstacles that set tiles as inaccessible (like trees, walls and other buildings), so I don't know if that means not free-move but I'm guessing it does. From this I don't believe that you have steering avoidance around objects like these (if im wrong please say) as I thought that's what the a star is for. This leads to my problem as I don't know if its not just best to project a formation where the mouse is clicked and path-find each unit using a* to one of the formation points while using avoidance to stop them colliding, or if there is some better way to do formations.  

Share this post


Link to post
Share on other sites

If you want a formation, generally the way it works is you run a quick calculation to project the position of the other troops. If an area is incapable of being handled for one point, you choose the next best option.

This is determined by what the formation is trying to achieve. Example, a box formation and fork formations are trying to keep troops close together. Stagger you are trying to gain some distance between troops. Circle formation is trying to cover your center target.


Since you have a cell grid, you test if the currently selected area is valid. If it is not, you let the game check for the next best option gradually with a cost system. The specifics are a little involved, but that is the basic concept.

Share this post


Link to post
Share on other sites


I don't know if that means not free-move but I'm guessing it does. From this I don't believe that you have steering avoidance around objects like these (if im wrong please say) as I thought that's what the a star is for.

 

It is NOT free move in that the agents have very specific points in space that they stand. They can't be in between those discrete points (the centers of your squares). 

 

Combining steering with A* pathfinding only works in an environment where agents are free to deviate slightly off of a direct path in order to get around another dynamic object that happens to be moving through the area. Normally, this would only be available in a navmesh situation where agents can move around freely inside larger polys.

 

In your situation, you are always going to have problems with coordinated multi-agent movement simply because you are using a discrete grid system. Sorry to tell you that. The best bet would be to allow multiple agents (of the same team?) to temporarily occupy the same space.

Share this post


Link to post
Share on other sites


In your situation, you are always going to have problems with coordinated multi-agent movement simply because you are using a discrete grid system. Sorry to tell you that. The best bet would be to allow multiple agents (of the same team?) to temporarily occupy the same space.

 

Arr ok that does make sence.

 

I guess I could instead of having a seperation Behaviour just have a stop system instead. Then for the formation just do what tangle and shadow said and project the formation where i click and send each unit to one (with more logic it would fit with there current position). Would this work better?

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.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!