Jump to content
  • Advertisement
Luqman Ibrahim

R&D Survey regarding which AI 2d pathfinding and what method is easy to use

Recommended Posts

Hello guys, I just registered this site and heard from my lecturer that this a good site to talk about certain topics since my research topic are mostly programmer who are experienced with AI can answer the survey.

 

The reason of the survey below is to understand which is suitable solution for 2d platformer pathfinding for AI and which one is easier to implement for 2D platformer. 

 

I would appreciate if you guys give your responses for the survey link shared and thank you for spending time answering the survey. Sorry if the survey is a bit hard to understand, I tried to make it understandable as best as I can. Again, thank you! :)

 

https://goo.gl/forms/S0etAlAAHL6S5kTI2

Share this post


Link to post
Share on other sites
Advertisement

lol. no. you could've just asked - not gonna click that. and would you have asked, the answers would have probably revolved around "a*-ish, but depends on actual navigational domain."

Share this post


Link to post
Share on other sites

Wait, you need to know my age and my gender to get some information about pathfinding in 2D platformers? My age is a private matter, and the details of your human biology doesn't match us Martians.

That being said, if I had to implement pathfinding in a 2D platformer (not that most 2D platformers need this), I would probably use A*, because it's fast and not that hard to implement.

 

Edited by alvaro
typo

Share this post


Link to post
Share on other sites

I started to take your survey, but can't ring myself to do it.

Why is age required? Why is gender required?  Why is "degree or diploma" required, and what does it mean?  Why are you asking about program of study? Many people on the board are industry professionals who finished such programs many years ago.  Why are these single-answer questions, can I not have experience with Unity AND Unreal AND other engines?  

You also seem to misunderstand the relationship between A* and Dijkstra's two-point shortest path algorithm.  (Note that Dijkstra created several famous algorithms for graphs and concurrency, this is only one of them.) A* is a proper implementation of that algorithm. The only difference is that in A* the work queue is sorted as an optimization, the classic algorithm neither specifies nor precludes ordering the work queue.  Classic implementations of Dijkstra's two-point shortest path generally work through the queue in a FIFO style rather than priority queue style, but they are not required to.  

 

Share this post


Link to post
Share on other sites

Thanks for the reply

 

Sorry, the reason for the age and so on is because I had to fulfill the requirements for my research methodology subject. I didn't intend to offend anyone here. Because I try to find an AI programmer audience so it kind of needed to explain when I had to present my findings and understanding. Sorry about the survey thing, I tried to make sense and it seems it turning people off.

 

@ninnghazad

I did ask some of the experienced people from my school. They seem to say mostly using A* method is the best choice. Since most industry use it, the optimization is better since it used a grid method and it is faster. But if the game don't have any grid, I have to use different method to apply for the game.

 

@alvaro

What if the game don't have any grid then I use a raycast method in unity? Since I mostly use unity since unity is much more easier to use to make game not sure about other game engine like unreal or cryengine.

 

@frob

yeah, a bit. I don't quite understand the difference. Based on the simulation I watch on youtube and other sites and a bit of reading from the articles, I got a bit confused. A* is seem an informed version of Dijkstra and find the best route to reach the destination, while Dijkstra is keep detecting the path until it found the destination. Also A* using a heuristic function while dijkstra only use one cost function.

 

I hope I make sense and thanks again for explaining something I just find out in detail. :) 

Share this post


Link to post
Share on other sites

Wow... a lot of facepalm here. I can't see how you would need to do "research" on a topic that 30 minutes worth of Googling would solve for you. Dijkstra is uninformed and therefore kind of wandery. A* is informed with a heuristic and therefore more directed. It is also guaranteed to find you the shortest path if a path exists provided an admissible heuristic. It also supports arbitrary geometry shapes such as navmesh polys so you don't have to be entirely grid based. You can also arbitrarily change the edge costs between polys to represent something other than distance -- for example terrain type -- so you can bias the results easily to match the world. There are plenty of optimizations as long as the environment fits. e.g. if you are grid based, you can use things like JPS (Jump Point Search) and JPS+.

Trying to do a survey and "research" on this is like polling the Math and Physics forum to see what the best way to find the area of a circle is.

Share this post


Link to post
Share on other sites
1 hour ago, IADaveMark said:

Dijkstra is uninformed and therefore kind of wandery. A* is informed with a heuristic and therefore more directed.

Doesn't have to be "wandery". Adding a cost to moving diagonally is enough to address that in either implementation.  The only math difference is that A* uses a priority queue for which work to do next rather than a more classical FIFO queue, and A* stops at the first match. The first match should be the ideal path assuming the priority was sorted correctly since the shortest/best path is at the top of the queue. 

The original shortest path algorithm does not say anything about sorting the work queue, nor does it prohibit sorting the work queue.  That's why A* is a proper implementation of Dijkstra's pairwise shortest path, but implemented with two performance optimizations.

Share this post


Link to post
Share on other sites

So, what type of game use Dijkstra then? Lets say, based on @IADaveMark said, A* is better than dijkstra. And from what I understand, A* is just an informed version of dijkstra while dijkstra is an uninformed version. But why some people still using Dijkstra? Just want to understand more

Share this post


Link to post
Share on other sites

A* is Dijkstra augmented with an admissible heuristic (i.e., a function that gives you a reasonable lower bound on the distance from an intermediate node to the goal). There might be situations where you don't have one, and then you are back to using something like plain Dijkstra. This probably only applies to very abstract cases, like finding a sequence of gem exchanges that reaches a desired configuration in the board game Bazaar.

Also, Dijkstra can be used to compute the distance from a node to all other nodes. This might be useful if you have a lot of agents trying to reach the same goal (e.g., Desktop Tower Defense).

 

Edited by alvaro

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!