Jump to content
  • Advertisement
Sign in to follow this  
captain_crunch

How do you avoid trapping units in an RTS game

This topic is 3775 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 making an RTS-style game on a 2d tile grid. I am looking for a way to avoid units being trapped/surrounded by placement of buildings by the player or the AI. My preferred way would be to prohibit the placement of a building in a spot that would complete an enclosure on the map by linking other buildings and terrain features (could be water). That way it will still be possible to line up buildings next to each other but units should never become trapped. Now I am looking for a smart algorithm to perform this test - any ideas?

Share this post


Link to post
Share on other sites
Advertisement
wouldn't it be faster to check for units inside buildings (after the user has placed any new buildings) and then just move them outside ? Also if users can place buildings shouldn't they be in charge of making sure they don't trap units ?

Share this post


Link to post
Share on other sites
Quote:
Original post by ndatxcod
wouldn't it be faster to check for units inside buildings (after the user has placed any new buildings) and then just move them outside ?

I don't want the teleporting effect when the user tries to place a building on top of a unit. So that is also prohibited.

Quote:

Also if users can place buildings shouldn't they be in charge of making sure they don't trap units ?

Maybe, but I will be using this algorithm when the AI places its buildings too.

Share this post


Link to post
Share on other sites
Just remember, as the makers of AoE discovered, also to make a solution for detecting and resolving the problem of trapped units, as it is bound to occur sooner or later.

Share this post


Link to post
Share on other sites
Well there is always the obvious solution.

Each time you are looking to place a building, enumerate out all the spaces that would surround the building, so that spot N can be reached in one move from spot N -1, and the last spot can reach the first spot in one move. Walk an imaginary unit around the building to see which of the possible spots are valid moves. Use this to split the tiles around the building into a few groups where each tile within a group can reach some other tile within the group in 1 move, and no tile in a group can be reached in 1 move from any other group's tiles. Then you've got a few disjoint groups of tiles... Find a path from one group to the next. If no there exists some group N that cannot reach group N+1, then you have a building whose placement would split the map into disjoint zones, and this would be a violation of your rules.

And of course as with most obvious solutions, it has an obvious problem, which is to say that this would potentially cost you several path discovery tests, which are expensive for large maps. If you are concerned that a unit may be trapped, you might want to only perform this sort of expensive checking in cases in which there are actual units around that may be trapped.

Sure there is a better solution....

Share this post


Link to post
Share on other sites
You could make an exception for units to travel past buildings from their own team under certain conditions. I couldn't see any players having a problem with this - it definitely beats the alternative.

Though I think the real question is what kind of trapping are you trying to avoid? There can be several kinds of ways units can be blocked off. If you mean like in Starcraft where your building can end up stuck in a non-blocked segment surrounded by blocked segments after making a building, or being able to make units come out in a blocked area, how do you want to define this area as a blocked area? Placing defensive buildings on the only path to your main base, while blocking your units from leaving, would block the enemy units from entering, so your units probably shouldn't be able to get by. So maybe you can allow any unit stuck in an area with X possible tiles to travel to, to pass through their own team's building if allows for them to access at least 2X segments, where X is constant. For example, if a unit is stuck in a 2x2 area, and X is 8, the unit can move through the building as long as the movement will result in them being able to access at least 16 tiles. This will prevent people from going both ways through buildings to get into little safe areas. You could also combine this with a little warning that the unit is possibly stuck, and only allow them to move through the building for a certain amount of time after the warning. If they don't move their unit, they're stuck for good.

Either way, whatever you do, I think being able to move through the buildings would be one of the better solutions. Having the units auto-move could result in undesirable behavior, such as if you are trying to defend one of your special units by building strong buildings around him so nothing can get in (or out).

Share this post


Link to post
Share on other sites
It's not really a solution to your problem as much as a workaround.. but you could always have the area surrounding each building walkable, kinda like a road encompassing the entire thing. If you require the road to occupy land that can be built on then no units can become trapped. You can make exceptions for certain buildings, like walls and such, of course.
I've seen this in a few games and it works quite well.

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!