Search Unity

  1. Click here to see what's on sale for the "Best of Super Sale" on the Asset Store
    Dismiss Notice
  2. Good news ✨ We have more Unite Now videos available for you to watch on-demand! Come check them out and ask our experts any questions!
    Dismiss Notice

Efficient Pathfinding for Large Number of Entities

Discussion in 'Works In Progress' started by foobar, Nov 2, 2012.

  1. foobar

    foobar

    Joined:
    Jan 28, 2010
    Posts:
    90
  2. kenshin

    kenshin

    Joined:
    Apr 21, 2010
    Posts:
    924
    Nice works!

    Feedback: sometime some green point are jammed within walls.
     
  3. foobar

    foobar

    Joined:
    Jan 28, 2010
    Posts:
    90
    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. jaybennett

    jaybennett

    Joined:
    Jul 10, 2012
    Posts:
    165
    I found this to have quite bad performance, is that just my computer or are others experiencing it?
     
  5. CrazySi

    CrazySi

    Joined:
    Jun 23, 2011
    Posts:
    538
    Not exactly a large number of entities :p
     
  6. mamoniem

    mamoniem

    Joined:
    Jul 23, 2012
    Posts:
    174
    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. foobar

    foobar

    Joined:
    Jan 28, 2010
    Posts:
    90
    @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. foobar

    foobar

    Joined:
    Jan 28, 2010
    Posts:
    90
  9. Darkhazard

    Darkhazard

    Joined:
    Oct 4, 2010
    Posts:
    105
    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. yls

    yls

    Joined:
    Apr 13, 2012
    Posts:
    195
    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.
     
unityunity