Boid Behavior and Optimization for a Pikmin-Like

Help Programming
, ,
1

Godot Version

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!

2 Likes
2

I found your post while looking for quadtree/octree implementations for a similar project. Have you found any answers to your questions so far?

If that can help:

  • I tried with regular nodes, which pushed the physics engine to its knees (5 entities => 120 fps, 50 entities => 7 fps).
  • I switched to Jolt physics, and that didn’t help.
  • I implemented boids-based behavior like the example in niceeffort1, with unbounded grid partitioning, exclusively on the CPU and that gets me 200 entities => 90FPS at the moment. That’s enough for my prototype, but I’m planning on moving to C++ and maybe eventually to Computer Shader.

Don’t take this as a “must follow” recommendation; I might have made some mistakes on day 1 that messed up my results.

I have similar questions regarding perfs, as in “can you move in and out of the GPU 1000 vectors every frame to run gameplay code”. I’m worried the answer is “spend 3 days implementing it and learn by yourself”.

Regarding gathering behind (following) behavior:

I’ve implemented it with Boids using simple math. Dropping this in case deciphering that code helps you make some progress :slight_smile:

# is the other boid in front of us? (us -> them vector is aligned with our velocity)
var a = s2.transform.origin - s.transform.origin
var dot = a.normalized().dot(s.velocity.normalized())

# is the other boid moving away from us? (us -> them vector is aligned with their velocity)
var moving_dot = a.normalized().dot(s2.velocity.normalized())

if dot > follower_dot_threshold and moving_dot > 0.5:
	# importance: if dot is 1 => importance = 1, if dot is threshold => importance = 0
	# This means we tend to follow boids in front of us, but we'll heavily favor the one most in front of us.
	var importance = 1 - (dot - follower_dot_threshold) / (1 - follower_dot_threshold)

	# create a vector that points behind the entity
	var dest = s2.transform.origin - a.normalized() * BOIDS_RADIUS
	a = dest - s.transform.origin

	steer += a * importance

Regarding stopping:

if you go with boids, I think you’ll need some friction when you do the average speed thingy (I think it’s called alignment in regular boids lingo) else they’ll never stop behind your player.
You might even be able to use the speed of the player as the average speed used for alignment.

1 Like
3

Hey!

For the stopping behaviour check out this: 5. Autonomous Agents
It’s an amazing resource with step by step explanations and implementation of the systems. A lot of times there is also an accompanying video solution.

The whole chapter is about boids.

If you’re interested in acceleration structures to boost your algorithms efficiency take a look here 5. Autonomous Agents

Admittedly I don’t know if it’s just a toggle in Godots menus, but I doubt it.

I can’t upload videos yet, but I have written an implementation in Go that handles up to ~7.5k at 60 fps when they shoot at each other, chase and escape.
It goes down to around 6k when you include circular field of views for friend & foe comparisons though.
It’s suboptimal as it’s mostly limited by the speed of the rendering enginge at this point. Each boid and bullet is drawne separately, I believe the numbers can be pushed way higher with the use of MultiMeshInstances.

Here’s another nice writeup (and another great resource as a whole) https:// gameprogrammingpatterns. com/spatial-partition.html about the spatial partitioning specifically. Weird formatting because new users can’t post two links at a time.

It would be a good exercise to just create it on your own in my opinion :slight_smile:

Good luck, happy to talk it over should you need more pointers.
I would not recommend going the GPU direction not before you understand how the structures work fully :slight_smile: