GML Swarm Optimization & Collisions?

L

lindens

Guest
I'm currently developing a swarm that chases you around the map and just have a few questions regarding optimization and collisions which don't use the built in speed variables.

Optimization
Each alien member uses a position, steering, and velocity vector to update its x and y position. I plan on having at least 50-100 aliens active at the same time however the debugging overlay shows how intensive the calculations really are. Currently I have all the chase code inside the alien object and i'm wondering if there is a way to structure the code for better optimization (I've already eliminated duplicate code).

Collisions
For my second question, since the aliens don't use built-in speed variables (their x and y positions are simply updated resulting in movement) The wall avoidance vectors I've implemented are effective around corners but there is still a high chance of them going through the walls. How could i prevent them from ever passing through wall objects?

Here is a gif demonstrating the aliens passing through walls (and avoiding them :)), and the debug overlay:
https://gyazo.com/5c412d6f70732aac9e2f1984fbf46d5b

Here is my alien's step event:
Code:
// reset neighbour_count
neighbour_count = 0;

// determine target
target[1] = o_player.fp.x;   
target[2] = o_player.fp.y;   

// recalculate steering vector with seek(target), avoid(walls), and then max_force
steering = vec(0, 0);
steering = vec_add(steering, seek(target, 600));
steering = vec_add(steering, avoid(1000, 70));
steering = vec_trunc(steering, max_force);

// update velocity with steering, then seperation force, then max velocity
velocity = vec_add(velocity, steering);
velocity = vec_add(velocity, seperation(3));
velocity = vec_trunc(velocity, max_speed);

// update position vector
position = vec_add(position, velocity);

// update position
x = position[1];
y = position[2];

// slowly rotate towards vector direction
look_angle += sc_rotate(vec_dir(velocity, "origin"), look_angle, 10);
 

samspade

Member
I'm currently developing a swarm that chases you around the map and just have a few questions regarding optimization and collisions which don't use the built in speed variables.

Optimization
Each alien member uses a position, steering, and velocity vector to update its x and y position. I plan on having at least 50-100 aliens active at the same time however the debugging overlay shows how intensive the calculations really are. Currently I have all the chase code inside the alien object and i'm wondering if there is a way to structure the code for better optimization (I've already eliminated duplicate code).

Collisions
For my second question, since the aliens don't use built-in speed variables (their x and y positions are simply updated resulting in movement) The wall avoidance vectors I've implemented are effective around corners but there is still a high chance of them going through the walls. How could i prevent them from ever passing through wall objects?

Here is a gif demonstrating the aliens passing through walls (and avoiding them :)), and the debug overlay:
https://gyazo.com/5c412d6f70732aac9e2f1984fbf46d5b

Here is my alien's step event:
Code:
// reset neighbour_count
neighbour_count = 0;

// determine target
target[1] = o_player.fp.x;  
target[2] = o_player.fp.y;  

// recalculate steering vector with seek(target), avoid(walls), and then max_force
steering = vec(0, 0);
steering = vec_add(steering, seek(target, 600));
steering = vec_add(steering, avoid(1000, 70));
steering = vec_trunc(steering, max_force);

// update velocity with steering, then seperation force, then max velocity
velocity = vec_add(velocity, steering);
velocity = vec_add(velocity, seperation(3));
velocity = vec_trunc(velocity, max_speed);

// update position vector
position = vec_add(position, velocity);

// update position
x = position[1];
y = position[2];

// slowly rotate towards vector direction
look_angle += sc_rotate(vec_dir(velocity, "origin"), look_angle, 10);
The second problem is likely happening because there is enough steering force from the surrounding objects to force some into the wall. At that point, the object's steering limitation probably keeps it close to straight long enough that the wall's force either isn't enough to turn the object out of it or depending upon where the sprite origin is (as that is where the vector's directions will be calculated) might even start forcing the object to go through it (e.g. if the all is centered, once the instance is half way through the force will continue to push it through to the other side). You could increase the avoidance force, or start the avoidance force sooner, have the objects try to mimic the movement patterns of other nearby objects (so that when an object close to the wall starts to be repelled by the wall, objects close enough to that object, but not close enough to the wall will also start to turn so that they don't crowd the first object into the wall), have fewer objects, lower the separation force, increase the allowable steering force, etc.

The first problem is one I learned a solution to and then forgot. I don't even remember where I learned it. The basic principle though is that you divide the map up into a grid and only do collision checking for objects in the same grid, rather than against all other objects. I don't remember how to code it though.
 

NightFrost

Member
Have you looked at boids?
Judging by the code, steering behaviors is already being used. One can't really return to previous position in SB without messing up its functionality. What I remember from testing out SB, it might be that separation force applied by surrounding agents is overpowering the avoidance force applied by walls. Avoidance like any other force is circular, radiating out of the center point, and it seems the agents are slipping through from points between the centers. Because SB is all about forces, there are no absolute behaviors, like absolutely always avoiding walls - with enough opposite force, any force can be overcome.

EDIT: You are truncating steering with max_force after adding avoidance. Shouldn't max force truncation be part of the seek behavior, to control maximum acceleration? And technically avoidance should be getting added to steering (the sum of accelerating forces) before it gets applied to velocity, but since you're just adding together vectors the order doesn't really matter as long as it happens before max speed trunc.
 
Last edited:

Bingdom

Googledom
This is where the YYC compiler comes in handy. It helps when you have multiple of the same instances in the room.
 
L

lindens

Guest
Thanks for all the replies. To prevent the agents from going through walls, i ended up using my velocity vectors to influence my hspeed and vspeed which then allowed me to use this collision script:
Code:
if (hspeed != 0) {
    if (!place_free(x + hspeed, y)) {
        if (hspeed > 0) move_contact_solid(0, hspeed)
        if (hspeed < 0) move_contact_solid(180, -hspeed)
        hspeed = 0;
    }
}

if (vspeed != 0) {
    if (!place_free(x, y + vspeed)) {
        if (vspeed > 0) move_contact_solid(270, vspeed)
        if (vspeed < 0) move_contact_solid(90, -vspeed)
        vspeed = 0;
    }
}

As for optimization, i decided to scrap my entire approach. I've just developed a heat-map using the Breadth First Search algorithm which will influence a vector in each cell of the grid. The entities would then refer to the vector they are near and thus be moved. This is what it looks like if anyone is interested. However, even this is extremely CPU intensive lol... I'm really not sure what to do at this point, I've optimized it to the best of my ability and i'm not too much closer to a large, efficient swarm of at least 100+ entities.
 
Last edited by a moderator:
P

ph101

Guest
I can't answer what the best approach is, depend on your game needs, plus I'm sure I'm not expert enough. Some ideas, you could just have one leader doing the more CPU heavy and the rest just moving towards the leader using basic GM collision masks for walls perhaps. Another thought was, though you possibly already saw this there is a tutorial thread by @amusudan about steering behaviours might give some ideas and which seems pretty comprehensive. https://forum.yoyogames.com/index.php?threads/steering-behaviours-the-ai-system-everyone-needs-for-their-game.23370/#post-151296
 

NightFrost

Member
I misremembered above by the way, so for posterity: the max force trunc is operated on the steering vector as you did, but you must perform it last. That is, the separation force must be applied to steering before that. In the code fragment you gave, separation is now unconstrained and likely overpowers other forces when enough is applied (depending on strengths they operate on).

As for your new approach, heatmap / flow field driven pathfind should be more effective with large number of agents as every agent can use the same field to steer, so you generate it only once for all of them. However it is very intensive operation as you first must iterate (breadth first) through the grid to valuate the cells, then go through them again to calculate their flow direction. I've been idly wondering if a shader could be used to do this... I can see how the flow field could be generated but I've yet no idea how to run a breadth first search with a shader.

A few optimizations can be applied to the heatmap approach in case you haven't done these yet. Firstly, you need to recalculate it only when target moves to another cell. There's usually only one target, the player, so it can be bound to observe their movement and recalculate on demand. Secondly, you don't need to calculate the entire flow field after heatmap generation. You can check if the grid cell where enemy stands has already been calculated and do the math only if it hasn't been yet. Other enemies can reuse the result, and cells where no enemy is standing don't need get calculated.
 
L

lindens

Guest
Firstly, you need to recalculate it only when target moves to another cell. There's usually only one target, the player, so it can be bound to observe their movement and recalculate on demand. Secondly, you don't need to calculate the entire flow field after heat map generation. You can check if the grid cell where enemy stands has already been calculated and do the math only if it hasn't been yet. Other enemies can reuse the result, and cells where no enemy is standing don't need get calculated.
Thanks for the advice, I've implemented your first part in my project. As for only generating the flow field vectors where an enemy stands, this is a good idea and i'll do it if i stick with this approach.

Here is my current result 1 and 2. I'm not sure if i'm happy with it. The previous swarm looked much more realistic to me. :( I'll be trying a combination of flow field and target-based path finding, so that when the agent gets close to the player, it chases them directly rather than continuing to use the velocity vector in their cell.

EDIT: I know I have a bug in the flow field where some cells point directly at a wall, ruining the agent's path.
 
Last edited by a moderator:

NightFrost

Member
If flow field is pointing to wrong direction check that the calculation uses local cell value instead of neighbour when the neighbour is a wall tile. Also watch out for local optima: this happens there are several equal length paths from the cell to target cell, so the heatmap to flowfield translation gives its vector a length of zero. This freezes enemies in the cell as they have no direction to go. One solution is to pick randomly from lowest value directions when this is detected. Other is to avoid it entirely by doubling the resolution of the flowfield grid and defining the target as four target cells.
 
Top