- Home /
Unit local avoidance in RTS type games
I am working on a RTS type of game and ran into a problem that I am not sure how to deal with. I have a setup where you can select multiple units and issue order to all of them. Whenever I order units to move somewhere I give them a single point to go to and I use A* Pathfinding project to figure out the path there. Problem arises when units arrive to the destination or rather attempt to do so, but can't because they all can't occupy the same point. What would be the best approach to solve this?
I guess I could check if the destination point is occupied by another friendly unit and then pick locations at random around it, then determine if there is a path to it and then move there while checking if some other unit decided to move there. That would be the case for simple move. If it is an attack, I would imagine I would have instead of looking for a random nearby point, i would figure out some random point certain distance away from the target. This seems like a solution that could potentially be slow and prone to long searches.
Or I could keep a grid representation of the world and flag cells as occupied or not, and have units move to the closest nearby grid cell that satisfies the requirements (ie firing range).
What is the proper way to do this kind of stuff? Is there a clever technique for doing something like this?
Search the term unity flocking algorithm
A couple of quick links :
http://wiki.unity3d.com/index.php?title=Flocking
http://forum.unity3d.com/threads/boids-simple-flocking.36239/
Thank you, that's interesting. I started looking into that and discovered Flow Fields. I guess I'll take a stab at it :)
Answer by Reinholdt · Sep 15, 2014 at 12:38 PM
A nice solution would be to solve this with steering behaviors, Flocking is one, steering is quite a large topic, I'll suggest you look in the direction of Flee and Arrival behavior, but you will properly also like to control how your units/agents get there, behaviors like Follow Leader, Pursuit and Evade etc.
Hope this get's you in the right direction.
Thanks! I don't know much about steering behaviors, so this is really interesting.
Just be aware that steering behaviours (and any other agent based system) get very expensive to calculate as the number of agents increases. That's one of the key reasons why RTS games traditionally have a population cap.
Flow field type management may be a better way to manage high numbers of agents.
this is true, but i don't think i will have too many units... nothing like Supreme Commander or StarCraft, more like WarCraft 2.
Do you have any resources for learning about flow fields? I would like to know more this kind of stuff.
Answer by DanSuperGP · Jan 06, 2015 at 11:45 PM
The simplest thing to do is not to send them all to exactly the same point. That is, when a user clicks on a destination, you send the first unit to that point, and then offset the remaining units destinations. This can be done a number of ways, the simplest way would be to offset them by distances relative to their starting positions and radius. More complex solutions are to generate formations around the clicked location
One of the best ways I've seen was in the game Rise of Nations. When you click on the destination, you could hold the mouse button down and drag and it would make little circle icons of the formation they would make, and your drag would aim the formation in different ways. It had smart systems too where the melee would be in front, the ranged behind, with artillery behind them.
Obviously those take varying amounts of engineering.
RTS pathfinding is a deep subject. There's an excellent article about the Flow Fields in Supreme Commander in the book Game AI Pro, and there's a pretty good academic paper here http://grail.cs.washington.edu/projects/crowd-flows/
Flow fields aren't going to solve the shared destination problem however, it's just an alternate way of doing pathfinding that works better for larger groups of units. You will still need to work out some sort of formation solution around destinations or your units will fight over the same position, only in more swirly ways.
thanks for the reply, it might be too complicated for a single developer game :( maybe some day :)
In general, I think an RTS may be too complicated for a single developer game. That's one of the lessons every indie developer needs to learn, how to pick a doable scope.
However, flow fields on their own are totally doable. I've personally implemented the Continuum Crowds system that's described in the paper I mentioned in Unity.
You might also want to check out http://arges-systems.com/blog/category/unitysteer/ for a decent implementation of steering behaviors you can just drop in and use.
However... navmesh, steering behaviors, flow fields... they're all going to have a problem with sending more than one unit to the same destination. The fact that they can't share locations is irrelevant to your path planner.
You're going to have to figure out some sort of formation system if you want to issue move orders to multiple units.
Answer by jpthek9 · Jan 07, 2015 at 01:15 AM
The Perfect Solution
When an object gets to the target destination (or close to it), set some sort of boolean to true to identify that it's at the target destination. Stop its movement and freeze it. When another unit moving to the same destination collides with that stopped unit, stop it too and set the same boolean to true to identify that it's at its destination. When you have a whole flock of units the first unit to reach the target destination will trigger a chain reaction that stops every unit in its flock.
An example (You'll probably want to optimize this):
using UnityEngine;
using System.Collections;
public class GameManager : MonoBehaviour {
public bool TargetReached = false;
Vector3 destination;
float StoppingDistance;
void Update()
{
StoppingDistance = collider.bounds.extents.z;
if (Vector3.distance (transform.position, destination) < StoppingDistance)
{
TargetReached = true;
}
if (!TargetReached)
{
//MoveToTarget
}
else{
rigidBody.isKinematic = true;
}
}
void OnCollisionStay (Collision col)
{
if (!TargetReached)
if (col.gameObject.GetComponent<RTS_Unit>().TargetReached == true)
TargetReached = true;
}
}
There's no need for complicated flow field behaviors, etc.. You only need those if you have to navigate around narrow passageways.
this is actually similar to what i did so far. i added a gird component that uses data from Aaron's A* and it stores flags. If destination grid cell is occupied, my current unit waits for the other unit to move or whatever. I noticed that this is how WarCraft 1 does it (at least looks like it). You still have an issue when units are walking towards each other, because then they wait forever.
Oh, true. To solve this, you can have a variable called 'StoppingDistance' that increases based on the command group the unit's in and cap it at a certain value (I.e. a single unit will move almost exactly on the target destination while the leading unit in a flock will stop at ~3 units away or whatever it needs to. I can't remember the exact formula I used but it has something to do with the units in the flock's collision size capped at the unit's collision size.
Just wondering, is this RTS multiplayer or single player?
I would like to make a multiplayer, but in reality... I dunno. There is a lot of moving pieces and each problem turns out to be much more complex then I initially anticipated. :)
If you want to make it multiplayer, you're probably gonna need a lock-step model (http://zoo.cs.yale.edu/classes/cs538/readings/papers/terrano_1500arch.pdf) and an easierly controlled physics engine like uPhysics that gives you the source code (http://forum.unity3d.com/threads/released-uphysics-uphysicspro.210855/page-6). If that's a bit over your head, just go for a single player RTS. There's a lot of them that are very fun. In a single-player RTS game, because you won't need to worry about deter$$anonymous$$ism, you have many options for crowd controlling and other tidbits RTS's need.
If you're commited though, definitely read up on the 1500 Archers essay (first link) before worrying about how you're going to implement crowd control because some of them might not work.