Efficient Pathfinding for Large Number of Entities

Community Showcases
1

Thought I’d share some work I’ve been doing with pathfinding within Unity. I was heavily inspired by this article on Gamasutra http://www.gamasutra.com/blogs/TylerGlaiel/20121007/178966/Some_experiments_in_pathfinding__AI.php . If anyones interested in the project please let me know and I might work on it some more and throw it up on the Asset Store.

Webplayer Link: http://dl.dropbox.com/u/3801106/Pathfinding/WebPlayer.html

2

Nice works!

Feedback: sometime some green point are jammed within walls.

3

Thanks for the feedback. Still a work in progress so there are a few minor issues with obstacle avoidance that still need to be worked out.

4

I found this to have quite bad performance, is that just my computer or are others experiencing it?

5

Not exactly a large number of entities :stuck_out_tongue:

6

it looks cool for me;
how you managed it ? A* ? waypoints ? raycast? navmeshes ?
my only point is : sometimes they can Push me ?!
i think they should reach me only…not pushing me;

m;

7

@jaybennett I get a consistent 75fps on my machine. I’m still working on optimizing the project in order to get a much faster result

@CrazySi it’s just a simple proof of concept right now. If the number of entities was increased substantially there would be a minimal decrease in performance. I’ll upload another example soon with a much larger number of entities.

@mamoniem The algorithm uses a diffusion map from the point of the player. All the AI entities then test their position against the diffusion map and determine what direction to go in. It’s well explained in the article I linked to in my original post. I’ll upload another version with the diffusion map visible.

8

Here’s a version with the diffusion map visible http://dl.dropbox.com/u/3801106/Pathfinding/diffusion%20map/WebPlayer.html

9

Thank you for posting that article. That is an interesting concept to try out.

It would be great when you need a large amount of entities. Not worth it if you are only needing a few entities.

10

Great thank you. The biggest limit of this proof of concept is that all the entities need to have the same goal. and that they can’t “trap” the player.

Really nice of you to show the webplayer with the diffusion map visible.