Cover Based Mechanic

Game Engine Game Engine Support and Discussion
1

So I have cover based mechanic that is slowing my game down. I think it’s just horribly inefficient.

so far it works kinda like this

at the beginning of the game a controller makes a list of all the cover

[SUB]covers = [cover for cover in objlist if “occupant” in cover][/SUB]

Only the cover objects I created have the “occupant” property which is a bool

then every space marine unit constantly runs a function designed to find other enemies and pieces cover
[SUB]
def locate_enemies(self):
[/SUB][SUB]…enemies_sorted = []
…enemies_unsorted = [enemy for enemy in objlist if ‘team’ in enemy and enemy[‘team’] != self[‘team’]]
…for enemy in enemies_unsorted:
…distance = [self.getDistanceTo(enemy), enemy]
[/SUB]…[SUB]enemies_sorted.append(distance)
[/SUB]…[SUB]enemies_sorted.sort()
[/SUB]…[SUB]self[‘closest_enemy’] = enemies_sorted[0][1]

[/SUB]Then i repeat the same process for finding all the closest piece of cover to the unit.

if an enemy unit comes to close then the space marine checks whether the closest cover or the closest enemy is closer to himself. If the enemy is closer then he runs at the enemy to engage in melee. if the cover is closer then he runs behind the cover to fire at a distance.

Does a cleaner system pop to mind on how to do the same thing with a simpler set up.

I’ve been thinking maybe i could make an empty that gets all the space marines. then just tells all of them who their closest enemy is and then those guys can all react to each other without each individual space marine making a list.

Does that seem right?

2

Ok, we can actually use 1 script, to operate all units…

use navmesh.findPath() moving from cover to cover,
if they are ordered by you to attack, then they know exactly where they are navigating to, otherwise move for enemy base, randomly stopping and looking around using a collision sensor vision cone object that is on the same collision layer as the enemy actors but not the terrain, of the cone detects a unit, cast a ray to target to make sure you can see the target, if it sees target, set navigation target,.

3

I don’t know your specific setup, but here’s some suggestions to “zoom out” and simplify:

  1. If each unit is close enough to each other, then you could just treat them as a single unit. Check and get the objects once, and then share the result for all of them.

  2. You only need to check for the closest cover or enemy in the immediate range of each unit. For example, have each entity (unit, enemy, cover, resource, whatever) place itself in a list for each area (say, 10x10x10 Blender Unit square) the entity is in. Then, each unit only has to check for cover or enemy objects in the current zone (or adjacent zones).

You can also add flags for each zone, so the unit doesn’t even have to check the zone unless it’s flagged as having cover, enemies, resources, or whatever.

  1. You likely don’t need to check every game frame.
4

In terms of code you can replace your ‘for loop’ with:

sorted_list = sorted(unsorted_list, key= lambda x: self.getDistanceTo(x))

sorted_list will be a list of sorted names based on distance to self, however you won’t have the exact numbers.

5

i dont need the exact values. i’ll have to try that. thanks. I got the initial code from Carlos. Just been using it since it got me that far.

6

You could create a ‘map’ of sorts, caching the nearest cover to a look-up-table.
You could use manhatten distance rather than euler distance to reduce CPU for calculating nearest
You could ignore bad guys far away from the player
You could only check every second or third frame
…
.

7

whats manhattan distance? i’m sure i could google it but i’m also sure you could give a more concise rundown

8

yep that worked just fine. you rock

9

you can use a KDTree to store the cover,

getting the closes x units is then very very cheap

but for things that move (enemies)(- sorted is the best way to go)

10

Manhatten Distance:


dist = abs(dist.x) + abs(dist.y) + abs(dist.z)

Euler:


dist = math.sqrt(dist.x**2 + dist.y**2 + dist.z**2)

DistanceSquared:


dist = dist.x**2 + dist.y**2 + dist.z**2

All of these will have the same result when used to sort a list, with the difference being the amount of computation required.

11

To be clear, these won’t have the same result when sorting a list. The latter two will, as the x->sqrt(x) mapping is just a transformation of the same value, whereas the manhattan distance is very different, and will give the same value for a diagonal path of x=x1, y=y1 as x=x1+y1.

Manhattan describes a path where the agent can only move along one axis at a time, whereas euclidean distances describe direct paths.

Always use the “length_squared” attribute of a vector when doing distance sorting, it’s faster.

12

Thanks, that’s a great tip. I’ve got a couple of cases where I can use that. What’s Vector.magnitude though? It describes it as being the same as Vector.Length, is there any difference?

@Skormeus
I’ve tried using manhattan distance before but it wasn’t faster than object.getDistanceTo().

When coding a solution to a problem like this it’s good to evaluate the easiest checks first and the more processor intensive checks last:

valid_enemies = []
for enemy in enemies:
    if not enemy.dead:
        if enemy.visible:
            if  enemy.team != own['team']:
               distance = own.getDistanceTo(enemy)
               if distance < 20.0:
                  valid_enemies.append([distance,enemy])

In this case if the enemy is dead, it won’t do any of the other checks, saving the need to waste time on measuring its distance. AFAIK list comprehensions can do this too, but there’s a problem:

valid_enemies = [[own.getDistanceTo(enemy),enemy] for enemy in enemies if not enemy.dead and enemy.visible and enemy.team != own['team'] and own.getDistanceTo(enemy) < 20.0]

You have to calculate the distance twice in order to return a list you can sort or you have to get the distance again during the sort. So it’s maybe better to do the for loop since the time savings of using a list comp are not likely to compensate for having to calculate distance twice. Or do a multiple levels of list comps:

first_list = [valid_enemies] ### not dead or invisible etc...
second_list = [[distance,enemy] in first_list]
last_list = [[distance,enemy] in second_list if distance < 20.0]
last_list.sort()

Each level will filter the list further until you’ve got a final shortlist to sort.

BTW, If your line of sight check is more expensive than your distance check you should do that one last just before sorting.

13

Just a thought to think about:

Would you constantly think about what cover to use, or would you decide one and take the necessary actions to use it unless you are forced to review the previous decision?

If you say yes, you would be able to do anything rather than staying around thinking what cover fits best in exactly this moment. You will be too busy thinking, rather than protecting yourself ;).

I suggest to do a similar thing with your NPC logic. They can decide once, create a plan and follow the plan. Some events could force them to do this process again. This events can occur during the “action” or after it. But unless they are not too much, you would get a pretty efficient system.

14

so Smoking mirror I’ve been using an AFAIK list just like that. It reads as enemies_unsort = [enemy for enemy in obj_list if “threat” in enemy and enemy[‘team’] != self[‘team’] and enemy[‘threat’] > 0 and (enemy[‘locked_in_combat’] == ‘none’ or enemy[‘locked_in_combat’] == self)]

So thats the list sorted_list = sorted(enemies_unsort, key= lambda x: self.getDistanceTo(x)) is pulling from.

And Monster I’ve been thinking the same thing but so far all I have as a deciding factor on cover is where the nearest is and what side of the cover is further than the closest enemy. I think I am going to have to have them go to the nearest cover. decide if they can see any enemies. then go to another one of the current one is lackluster. Does that sound right?

15

Also would it be less intensive to have one cube do a couple for loops and assign every unit an enemy and cover then have them all decide what to do with the targets they’ve been assigned?

16

you don’t have to do it every frame,

you just march an index

proccessed = own[‘ListOfUnits’][own[‘index’]]

and just march through a few units each frame, assign them navigation targets,
and have them contain the line of site and navigation themselves.

(you can set a target for them to navigate to, but if they spot a hostile change their behavior)

so ‘commander’ gives orders if orders don’t exist, unit orders override commander orders, but player orders overide unit behaviors.

so they run where they need to be, and fight who they see, unless you tell them otherwise,

17

well I’ve done it and i think I’ve improved my framerate. Unfortunately I wasn’t paying attention to my specs before.

from bge import logic
scene = logic.getCurrentScene()
cont = logic.getCurrentController()
obj_list = logic.getCurrentScene().objects

logic.covers_unsort = [cover for cover in obj_list if “occupant” in cover]

#print(logic.covers_unsort)

units = [guy for guy in obj_list if “threat” in guy]

for model in units:
…try:
…enemies = [enemy for enemy in units if enemy[‘team’] != model[‘team’] and enemy[‘threat’] > 0 and (enemy[‘locked_in_combat’] == ‘none’ or enemy[‘locked_in_combat’] == model)]
…sorted_list = sorted(enemies, key= lambda x: model.getDistanceTo(x))
…model[‘closest_enemy’] = sorted_list[0]

…except:
…pass

…try:
…my_cover_list = [cover for cover in logic.covers_unsort if [cover[‘occupant’] == ‘none’ or cover[‘occupant’] == model]]
…covers_sorted = sorted(my_cover_list, key= lambda x: model.getDistanceTo(x))
…model[‘closest_cover’] = covers_sorted[0]
…except:
…pass

18

Running for cover can usually be a decision that’s evaluated prior to the execution. In some cases, you might have to handle dynamic cover (e.g using your team-mates as cover(!)), in which case you should be able to quickly perform culling tests to determine relevant parties.

For example, if such a feature existed, there would come a point where it is performant to have an AI manager build some kind of partitioning structure (e.g a quadtree) that allows fast near-neighbour lookups, or for simple games, just use a coarse grid.

For best results, AI needs to be a system unto-itself - there’s a lot of theory behind the subject.

19

what about a invisible lamp? any shadow of the lamp placed at a enemy unit, is cover? bigger patch of shadow = better cover?

20

the shadow thing might work for the assassin guy. but its a battlefield so the average enemy is very alert