# Boid Behavior and Optimization for a Pikmin-Like

4.2.2

### Question

Background:
Hi, recently I’ve been trying to hash out the mechanics for a game similar to Pikmin. One of my primary goals is to have more engaging group movement in the game, and to start, I want to optimize to handle at least 1,000 boids comfortably. I’ve found some good advice to help with this, but I’m relatively new to Godot and am still unsure of a good way to accomplish some of this. The current code I have was based loosely off of this example by Kyrick and is public on Github here

For checking if two boids are close enough to be neighbors: Is it always going to be better to use my own algorithm using grid based spatial partitioning and distance than to use godot’s built-in CollisionShape2D? I suspect the answer is yes, but in my version of godot, I can’t figure out how to tweak the settings for collision, so I can’t test to make sure. I’ve seen several posts mention “project settings → physics → cell size” but I only find things related to gravity there. The spatial partitioning would likely be similar to Kyrick’s other boid example. Apparently quadtrees would be an alternative to the grid-based spatial partitioning; I’m curious how that would work, but am skeptical as to whether it is better in this scenario.

I’ve seen at least one post mentioning that a manager would help because you can reduce the number of distance calls each loop by storing them (if A neighbors B then the distance A → B is the same as B → A). This makes sense, but I’m struggling to figure out what data structure would be useful here/how to implement it.

Is it worth looking into GPU based computation? There’s this really interesting project by niceeffort1 where he simulated 100,000 boids via the gpu. This is interesting, but I’m skeptical as to whether it is useful here since the boids/pikmin will have to interact with other things in the world like walls and enemies. Would it still be possible to offload some of the pikmin calculations to the gpu? Is that even a feasible/useful practice? What are your guys’ thoughts?

Gathering behind a “captain” and stopping:
This is less about optimization and more about what you guys think the best way to do this is. In the Pikmin series, when the captain stops, the Pikmin will form a group behind him and stop moving. I’ve got a few ideas stirring for how this might be done, but I’m having a hard time coming up with a method that:

• ensures that boids actually stop (this is especially important for animation purposes)
• they fill in from the player back rather than stopping prematurely
• the group isn’t exactly the same every time it stops

End Note
I know this is a lot, but any advice is much appreciated! I’m sure there’s other useful techniques/info I’ve missed, so please let me know. Also, if you’re interested in this project, feel free to reach out (I’m not sure if I’m allowed to put my email here…), I’m always interested in working with others, learning more about his kind of stuff, and connecting with other like (or differerent) minded individuals. Thanks in advance!