About 'Types Of Pathfinding'!

Unity Courses Talk
, ,
#1

In this video (objectives)…

  1. Look at Breadth First Search (BFS)
  2. Compared to Dijkstra's algorithm and A*
  3. Why A-Star isn't always the best best

After watching (learning outcomes)…

Discuss the basic differences between three pathfinding algorithms.

(Unique Video Reference: 8_RR_CU2)

We would love to know…

  • What you found good about this lecture?
  • What we could do better?

Remember that you can reply to this topic, or create a new topic. The easiest way to create a new topic is to follow the link in Resources. That way the topic will…

  • Be in the correct forum (for the course).
  • Be in the right sub-forum (for the section)
  • Have the correct lecture tag.

Enjoy your stay in our thriving community!

#2

So, what’s your take on A* vs. BFS from what you’ve seen?

#3

Can’t comment yet on A* vs BFS, but would love to see more training on algorithms, using the same format style in these series of lectures (i.e. by building actual apps, rather than explaining what each command/ algorithm does). Perhaps this course (which is really well structured) can be a pre-requisite for additional more advanced courses.

More advanced courses such as building a draughts, Oriental GO and chess game from scratch (along with more in depth explanation of various algorithms. The algorithms would start from basic, but playable algorithms (like the algorithm used to write a 1k chess game for the ZX81), were it is easy to beat the AI, or where the AI behaves rather stupid, but still within the rules, to more intensive algorithms were beating the AI is tougher, as the AI is working on better choice of move.

In summary, I think you guys have a winner here - a well thought out, well structured and well organised course.

#4

PS - could you provide the slides as done so far. I keep a book with my notes, and once in a while print out a table to glue into my notes (such as the trigger/ collision table). I would like to add your table on path finding algorithms to my notes book.

#5

Sure, the slides are linked from every lecture, and here here for your convenience.

#6

My initial assumptions about A* vs Breadth:

Breadth should be our default algorithm unless there are terrain/movement changes along the path, or if processing speed is a problem. If those two things are involved then A* is our go to algorithm.

Breadth appears to be simpler and works “Out of the box”.

#7

I would love to see more on Dijkstra’s algorithm. BFS is great, but when I look at games like Civilization, Prison Architect or Rimworld they have to take into account terrain be it floor tiles, rivers, forests or mountains. Not sure if A* supports that too, but I could see using that in my games.

Always wanted to make a city builder.

#8

Toss me in the lot who would love to see a good section on Djykstra’s algorithm (I know we’re 1/2 way there with BFS already).

#9

Thanks guys, probably no Dijkstra’s algorithm in this beginner’s course, but me or Penny will be creating more AI content soon.

#10

Can I post the script from the BFS that I’ve changed slightly so it is a Dijkstra Pathfinder on this forum or is it possible non-students can see it and therefor not wanted? I guess it might help others that really need a cost based pathfinding further in their project.

Edit: I posted my script with comments in the Q&A of lesson 133 “Reversing a list”. As only students can access it, I thought it would be ok.

#11

I think it’s fine to post it here, personally… (Or post a link to your git). Incidentally, all of the source code for everything Ben does in these lectures is available to the public, as the repositories on GitHub are open, not private. The important stuff from the course is the knowledge Ben is imparting as he goes, not the actual code itself.

Privacy & Terms