Targeting and Pathing Algorithm for RTS style

Unity Engine
, , , , , ,
1

I’m working on implementing a targeting and unit pathing algorithm for my RTS style game. I started with a few simple implementations and iterations but am stuck on how to improve the performance of it.

Here are few things I’ve iterated through:

  • Simple distance targeting (closest enemy)
  • Improved on distance targeting with quad tree
  • Target by priority (strongest enemy, weakest enemy, etc)
  • Formations for better movement (avoids clumping)

When it’s player vs player it looks okay, but when it’s just AI vs AI then the combat and movement is not great since the units tend to clump up and try to target the same units (e.g. the nearest ones)

Here’s a video of another game that gives an idea of the scale / type of AI I want to be able to make:

It’s a basic AI in a sense that units just move towards nearby enemy and then fight.

I’m having trouble figuring out how to get the targeting to be efficient and optimal. Using the diagram below as an example:

image
image1011×778 2.75 KB

The red rows are enemy formations, the blue is a player unit.
When targeting, the job receives the enemy formations in order of 1,2,3

So #1 targets the blue player. Then #2, then #3. Say we allow a max of 2 formations to be targeting an opposing formation at any given time (to avoid clumping). That means that #3 will have to go for the further player unit, since #1 and #2 would have taken the slots for the nearby one already.

This can be “fixed” by having #3 supersede the targeting of #1 during the calculation, but that requires keeping a sorted data structure of the distance of each troop to each opposing troop. Add in other heuristics such as targeting priority for focusing on stronger units, etc the it becomes more complex.

Is there a better way to approach this?

This is also just at a formation level, once the units get close enough, I haven’t solved it yet but there needs to be better targeting logic at a unit/model level. E.g. once a formation clashes with another formation, only the front line units should be actively trying to path to an enemy unit. The units in the back rows should just “follow” and wait until a front line unit dies to take it’s place in combat.

Thanks for any help and insight!

2

I’ll throw out the “hungarian method” in case you’ve never heard of it.

But really, this sounds more like a design and a behavior problem than a performance problem. Personally, I would first focus on getting the behavior you want, and then try to optimize it using clever code tricks. I can help you with optimizing a solution, but I’m probably the wrong person to suggest designs that influence the mechanics and feel of your game.

1 Like
3

arrCaution: bNot to be szConfused with pHungarian iNotation! :wink:

1 Like