Autonomous agents behaviours

GresilleSiffle

Hi everyone :)

I'm new to game development and I'm currently experimenting with autonomous agents steering behaviours in 2D environment. My goal is to simulate the flocking behavior of birds described in the nature of code book, and at the end I would like to have something like this.

Step by step I've learned basic behaviours such seek and flee, pursue and evade, wander, etc. I'm going to publish everything on Bitbucket, one repository for each behaviour. I think it can be useful for newcomers like me, or in fact anyone interested, to see a behaviour in action and tweak some values in Godot to see what happens !

Here is my implementation of seek:

https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_seek/src/master/

... and it looks like this:

It's a little raw for the moment, and there is no way to interact with the boids except moving the mouse to change their direction. I've also made a UI (keyboard only) allowing to display and hide the forces, the targets, and the UI itself.

Feel free to download the project and take a look, I'll be glad to receive comments on everything, and specially on the UI scene. It's my first UI so maybe the wrong control nodes :blush:

See ya

GresilleSiffle

I just published the pursue behaviour:

https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_pursue/src/master/

The two red agents pursue the yellow one by anticipating its future position, instead of just following it. The prediction is made by adding to the current target position its velocity, multiplied by an anticipation factor. The more the target is far, the more the factor is big.

On the image above, the yellow vectors represent the desired velocity of each agent. We can see that the red agents are not targetting the yellow one position but a predicted future position.

I think I'm going to implement some group behaviour now, like "separate" described here. It will be more fun than just seek and pusue a target position :p

GresilleSiffle

And today, the separation behaviour ! Code available here.

This behavior gives an agents the ability to maintain a certain distance from others nearby. As you will see bellow, all agents start really close to each other and try to flee as fast as possible.

Next, I'm going to add some UI control in order to change the separation distance and the agents' maximum speed on the fly. Also it would be cool to be able to control the number of agents, and create really big crowd.

After that, they can live their own peaceful life without touching each other.

Haplotyper

Nice work. The Nature of Code is a very good resource. Looking forward to see how you progress =)

GresilleSiffle

Thanks ! I've just implemented a complete flocking behaviour today, I didn't find the time to publish it on Bitbucket but it's coming soon (tm) :) I also want to publish some sliders to play with the previous separation behaviour (in fact the sliders are ready but I'm not really satisfied by the UI right now).

I don't know if my code lack of optimizations or if I've reached the GDScript limits, but flocking need a lot more ressources than the individual behaviours. It will be a good exercice to figure out what happen exactly.

Haplotyper

It definitely needs optimization. I didn't want to focus on that as you are still learning. Using your separation project as an example..I would say that the main performance killers are the following:

1) The separation function is looping through every other agent in each agent. That is something like 64⁶³ checks per frame. ;P Each agent only needs to be concerned with the agents that are/might impacting him. Something like an area 2D for closer agents and raycasts for further agents will be better.

2) Try to use distances squared when possible. Square roots are cycle demanding.

3) When dealing with a lot of agents, try balancing out the frames that agents do their logic in. For example, half the agents use even frames and the other use odd frames. You are trying to mimic life so reactions aren't instantaneous (every frame) anyhow.

Keep up the good work =)

GresilleSiffle

1) Yup, you are right. The algorithm complexity is in fact quadratic O(n²), in our case that means 64 * 64 = 4096 operations per frame. I tried to run the simulation with 256 agents, and as expected the application just crashed : P As you say, Area2D and RayCast2D will be great improvements, but I didn't want to use Godot specific nodes. For the moment I prefer having a "pure" algorithm that reflects exacly what is going on the screen, and that can be easily translated into other languages if needed. BUT using more adapted Godot nodes is definitely something I will do, but not right now. Now it's time for... sssliders!

2) Good advice! I use it only in the seek_and_arrive(target_position) method, I will fix this.

3) Wow I didn't know that was possible, we need to try this.

To improve perf a little bit, I removed a lot of intermediary Vector2() creation. As a result, the code is... less readable : P

I also want to try the "bin-lattice spatial subdivision" described here.

Thanks for all the tips

Haplotyper

Glad ya noticed my mistake. I was thinking about it after I posted, but I had logged off and was away from the computer all day. =)

GresilleSiffle

I didn't notice the first time I read but I did the math, and with 64⁶³ operations, my computer would litteraly burn \m/

Here are some graphics representing the complexity: https://www.desmos.com/calculator/uzym7z8src 1/2 * x² the blue curve, the complexity if I use even and odd frames to balance the load x² the blue curve, the current complexity of my implementation * x^y the red curve, just for fun, don't do this at home

This morning I just pushed a new interface for the separation behaviour. Now there are four sliders, allowing to control the agents' maximum steering force, the maximum speed, the separation distance and the number of agents.

(code available here)

I'm going to read more about grid based 2D space in Godot and bin-lattice spatial subdivision to reduce the number of operations per frame. Also I will update the flocking behaviour with the new interface, adding more sliders to control the cohesion and aligment distance.

Zireael

This is great, my current project is also mostly about learning steering behaviors. I haven't yet gotten as far as you did, though!

MagicLord

Multi threading would help Raycast2D when there is a lot for performance (i don't know if Raycast2D is fast).

GresilleSiffle

Hi everyone,

@Zireael, thank you! If you are still working on steering behaviours, feel free to share it with us if it's not a private project ; )

Hello @MagicLord. Thanks for the advice. I don't know neither how RayCast2D would improve the simulation performance. I don't think I will have enough time to test ray casting and multi-threading in the near future, but at some point I will.

Finally, I did have the time to implement a simple bin-lattice spacial subdivision for the separation behaviour. The program is a lot more faster now. Instead of checking all agents position, the program is able to perform a locality query that returns only the neighborhood of the desired agent. Because the agents maintain a minimum separation distance, and so a maximum density, the number of agents within a bin is bounded. So, the algorithm complexity evolve from O(n²) to O(nK), where K is a constant representing the maximum number of agents in a bin.

The bin-lattice code (in fact, in a 2D environment it's a simple grid): https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_separation/src/master/scenes/grid/grid.gd

The program main loop is now in the agents.gd file: https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_separation/src/master/scenes/agent/agents.gd

And of course, the separation algorithm is here: https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_separation/src/master/scenes/agent/agent.gd

GresilleSiffle

Aaand, the flocking behaviour: https://bitbucket.org/gresille_siffle/godot2d_autonomousagents_behaviour_flock/src/master/

This group behaviour is the combination of the three individual actions: cohesion, alignment and separation. You can find the implementation in the agent.gd file.

Zireael

The project that uses steering behaviors is https://github.com/Zireael07/Space-Frontier

It is, however, not limited to just exploring those, but actually using them in a game.