What's new
By:
  • Visit Rebornbuddy
  • Visit Resources
  • Visit API Documentation
  • Visit Downloads
  • Visit Portal
  • Visit Panda Profiles
  • Visit LLamamMagic

Question to Random Dungeon Pathing

L

LastCoder

New Member
Joined
Dec 4, 2011
Messages
86
Reaction score
2
This question is directed towards the developers: Are you planning on using the AStar, Bellman Ford, or Dijkstra algorithm for random dungeon solving? Just curious since I have previous experience with all 3 algorithms (except with the Java language) and I would like to know which (or if you pick a different algorithm) you chose to use for future references with pathing.
 
iuser99 said:
This question is directed towards the developers: Are you planning on using the AStar, Bellman Ford, or Dijkstra algorithm for random dungeon solving? Just curious since I have previous experience with all 3 algorithms (except with the Java language) and I would like to know which (or if you pick a different algorithm) you chose to use for future references with pathing.
Click to expand...

I was wondering this as well. I study algorithms, and this would be fascinating to know.
 
apox stated before that he had first good results with the travelling salesman problem algorhytm
 
germanbuddy said:
apox stated before that he had first good results with the travelling salesman problem algorhytm
Click to expand...

The Traveling Salesmen Problem is just a problem that asks what the shortest route is when visiting a bunch of nodes exactly once and then returning to the origin. There isn't just a generic algorithm, there are a ton of algorithms used to solve it.
 
We're not looking for a single-path type algorithm for random dungeons. In order to explore. we need to visit segments of the dungeon. TSP solves this perfectly for us.

Our implementation doesn't make use of genetic algorithms (such as an ant-colony approach), but we also need to ensure that we have the speed required. Our node set is likely to be less than 100-200 per dungeon, so a simple euclidian heuristic is good enough to get the job done, with minimal backtracking. We do include some parameters to increase the "node" size, as well as navigable tolerance for each node to be included in the TSP algorithm. You'll see this with our test releases that we'll be doing soon.
 
Apoc said:
We're not looking for a single-path type algorithm for random dungeons. In order to explore. we need to visit segments of the dungeon. TSP solves this perfectly for us.

Our implementation doesn't make use of genetic algorithms (such as an ant-colony approach), but we also need to ensure that we have the speed required. Our node set is likely to be less than 100-200 per dungeon, so a simple euclidian heuristic is good enough to get the job done, with minimal backtracking. We do include some parameters to increase the "node" size, as well as navigable tolerance for each node to be included in the TSP algorithm. You'll see this with our test releases that we'll be doing soon.
Click to expand...

Nice. This is exactly what I was looking for.
 
Apoc said:
We're not looking for a single-path type algorithm for random dungeons. In order to explore. we need to visit segments of the dungeon. TSP solves this perfectly for us.

Our implementation doesn't make use of genetic algorithms (such as an ant-colony approach), but we also need to ensure that we have the speed required. Our node set is likely to be less than 100-200 per dungeon, so a simple euclidian heuristic is good enough to get the job done, with minimal backtracking. We do include some parameters to increase the "node" size, as well as navigable tolerance for each node to be included in the TSP algorithm. You'll see this with our test releases that we'll be doing soon.
Click to expand...

I agree with championcake, thank you Apoc :) I'm looking forward to trying the test release.
 
You must log in or register to reply here.
Back
Top