Jump to content

  • Log In with Google      Sign In   
  • Create Account


#ActualOlof Hedman

Posted 22 October 2012 - 10:42 AM

That doesn't sound much to me... thats just a grid of approx 90x90 nodes.

If the map is relatively open and interconnected, an A* shouldn't have to visit much more then a few hundred in average, and that is when navigating from one end of the map to the other. If start and end is relatively close to eachother, you will just visit a handful of nodes, should be very fast.

DFS will in average visit half the nodes, even when start and end is just next to each other (if you are unlucky and start searching the wrong direction, you might have to visit _every_ node before you find the goal in your neighbor node...)

I think there might be something funky in your A*
unless you have a very high number of agents pathfinding...

Another optimization is to have different levels of pathfindning, a coarse one to find (for example) the "rooms" to visit, and then a finer to navigate through each "room".

#3Olof Hedman

Posted 22 October 2012 - 10:36 AM

That doesn't sound much to me... thats just a grid of approx 90x90 nodes.

If the map is relatively open and interconnected, an A* shouldn't have to visit much more then a few hundred in average, and that is when navigating from one end of the map to the other. If start and end is relatively close to eachother, you will just visit a handful of nodes, should be very fast.

DFS will in average visit half the nodes, even when start and end is just next to each other (if you are unlucky and start searching the wrong direction, you might have to visit _every_ node before you find the goal in your neighbor node...)

I think there might be something funky in your A*

#2Olof Hedman

Posted 22 October 2012 - 10:31 AM

That doesn't sound much to me... thats just a grid of approx 90x90 nodes.

If the map is relatively open and interconnected, an A* shouldn't have to visit much more then a couple of hundred in average, and that is when navigating from one end of the map to the other. If start and end is relatively close to eachother, you will just visit a handful of nodes, should be very fast.

DFS will in average visit half the nodes, even when start and end is just next to each other (if you are unlucky and start searching the wrong direction, you might have to visit _every_ node before you find the goal in your neighbor node...)

I think there might be something funky in your A*

#1Olof Hedman

Posted 22 October 2012 - 10:29 AM

That doesn't sound much to me... thats just a grid of approx 90x90 nodes.

If the map is relatively open and interconnected, an A* shouldn't have to visit much more then a couple of hundred in average, and that is when navigating from one end of the map to the other. If start and end is relatively close to eachother, you will just visit a handful of nodes, should be very fast.

DFS will in average visit half the nodes, even when start and end is just next to each other (if you are unlucky and start searching the wrong direction, you might have to visit _every_ node before you find the goal in your neighbor node...)

PARTNERS