Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

How to implement Dijkstra's Algorithm pathfinding? C#

Discussion in 'Scripting' started by LukaKotar, Aug 3, 2012.

  1. LukaKotar

    LukaKotar

    Joined:
    Sep 25, 2011
    Posts:
    394
    Hi.

    I was looking for some pathfinding solution for my AI, and I found the Dijkstra's Algorithm. I found this site, which should have the script already converted for use with Unity 3D, but I get some strange errors, and I don't know how to fix them.

    Can someone help me with this, or any other good pathfinding method (in C#)?
     
  2. UnlimitedEdition

    UnlimitedEdition

    Joined:
    Feb 27, 2012
    Posts:
    287
    If you specify what you're asking for you may get more responses, are you asking for help converting the script, fixing errors, or finding another algorithm altogether. I like that you found something that isn't A*, I must admit that I have been wanting to see something new. Look at how they script the algorithm and see if you can apply it yourself. If you can do that, you will be a much (much, much, much) better AI programmer.
     
  3. Chuckalicious

    Chuckalicious

    Joined:
    Jul 28, 2012
    Posts:
    51
    You might check out this AI FSM solution http://forum.unity3d.com/threads/133180-AI-Behaviors-Made-Easy!-(Walker-Boys) or Aron Granbergs A* pathfinding http://forum.unity3d.com/threads/145719-A*-(AStar)-AIPathfinding-Implementation-Examples (C#). Good stuff. At the very least it helps to see the approach others take allowing you to formulate your own solutions.

    Hey Pikrat, I am also always looking for new algorithm's for managing AI pathfinding behavior, but don't rule out A*. It has it's place for sure. You might otherwise use a good heuristic function. I believe it depends on the input data available to you and the overall goal.
     
    Last edited: Aug 4, 2012
  4. UnlimitedEdition

    UnlimitedEdition

    Joined:
    Feb 27, 2012
    Posts:
    287
    I think A* is a great algorithm but it's the only pathfinding algorithm I ever see. There's obviously a reason people use it and I assume that's because it's good. I'm not a good AI programmer but I am interested in it and I agree with you, that it matters more about what you're trying to get out of the code than what algorithm you use. I know Google uses a (or something similar to) pathfinding type algorithm that could be implemented in a game.
     
  5. andererandre

    andererandre

    Joined:
    Dec 17, 2010
    Posts:
    683
    Last edited: Aug 4, 2012
  6. gfoot

    gfoot

    Joined:
    Jan 5, 2011
    Posts:
    550
    Dikxstra's algorithm is good if you need to direct a lot of units to the same location, or if one unit needs to check accessibility of a lot of different locations (e.g. so it can use the path costs to weight a high level behaviour decision, such as choosing a sniping point).

    It's also easier to implement in a fully dynamic, incrementally updated manner, amortizing the cost and reacting to changing circumstances. It's essentially what I used in this thing: http://www.gfootweb.webspace.virginmedia.com/Swarms/WebPlayer.html (click or shift-click to move different teams)

    In terms of different algorithms, last year I implemented a system to pathfind for objects in a continuous infinite space, with no discrete grid. It was not very sophisticated though, as it was only in a prototype and the prototype really ought to have had a grid. I guess I was just looking for something to do. :)
     
  7. LukaKotar

    LukaKotar

    Joined:
    Sep 25, 2011
    Posts:
    394
    Sorry for no response yet... Thank you all for your replies! To explain this a little better, the question is about fixing the errors I get when I put the script in my project. They say it is already converted for use with Unity, but it looks like it needs a little more optimization.

    So if you could help me, I'd greatly appreciate that. I will check more often from now on...