Jump to content
  • Advertisement
Sign in to follow this  
lucky6969b

What maximum amount of flood fill can a dijkstra handle?

This topic is 754 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I found on a 2500K CPU @ 3.2GHz, 16GB RAM.

With 700 nodes, it takes 6 seconds

With 7000 nodes, it can not withstand.... I just stopped it because it just took too long before it finished.

Does anyone know, in general, the amount of nodes a dijkstra can handle?

 

The algorithm is O(N^3)/3 for the time being

I can't express it, but it is like

with 700 nodes

for (int i = 0; i < _nodes.size(); i++)
   for (int j = i+1...
      for (int k = j+1

because I advance the count variable in each inner loop.

BTW, it is not optimized (debug build)

Thanks

Jack

Edited by lucky6969b

Share this post


Link to post
Share on other sites
Advertisement
Dijkstra's minimum path between a pair of points routine is the famous algorithm you are probably writing about, he had several major algorithms so you might mean another.

The single pair algorithm potentially takes quite a lot of memory when implemented naively, on the order of N^3 sounds correct. Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

Since you mention "flood fill", I'm guessing you are talking about an all-pairs shortest path algorithm? Those exist, but are much more memory intensive for anything other than just storing a binary reachable status. Using the single pair shortest path over and over for all pairs is a bit extreme.

You might also mean having a path that follows a space filling curve across an entire board. That can take as much resources as your path requires, entirely dependent on your implementation.

Finally, there are many implementations of these algorithms online, some quite efficient and others are terribly inefficient. Can you share what implementation you are following?

Share this post


Link to post
Share on other sites

Slightly off topic, but I want to ask.

 

Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

 

In which cases it would not be optimal? I thought it always takes the most optimal path.

Share this post


Link to post
Share on other sites

Slightly off topic, but I want to ask.
 

Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

 
In which cases it would not be optimal? I thought it always takes the most optimal path.

Given your heuristic never overestimates, it IS optimal afaik.

Share this post


Link to post
Share on other sites

Dijkstra's minimum path between a pair of points routine is the famous algorithm you are probably writing about, he had several major algorithms so you might mean another.

The single pair algorithm potentially takes quite a lot of memory when implemented naively, on the order of N^3 sounds correct. Most games use the A* (A star) algorithm, which is Dijkstra's single pair shortest path algorithm plus a small heuristic value to speed up the search a bit, at the cost of potentially not being optimal.

Since you mention "flood fill", I'm guessing you are talking about an all-pairs shortest path algorithm? Those exist, but are much more memory intensive for anything other than just storing a binary reachable status. Using the single pair shortest path over and over for all pairs is a bit extreme.

You might also mean having a path that follows a space filling curve across an entire board. That can take as much resources as your path requires, entirely dependent on your implementation.

Finally, there are many implementations of these algorithms online, some quite efficient and others are terribly inefficient. Can you share what implementation you are following?

 

As has been said, so long as your heuristic does not overestimate (the heuristic is always less than or equal to the actual optimal path cost) it is guaranteed to be optimal. Also, to note, A* can run faster if you do not require an optimal path, so that's also something to keep in mind... though if you really want greedy best-first search, don't use A* as that has the bookkeeping logic required to keep track of the length of the path so far which is what let's A* not be greedy.

Without knowing what exactly he's doing, though, it is impossible to recommend an ideal solution. Floodfill can be used for anything from pathfinding, to image editing, to determining if two voxel volumes connect, to other things. They're all just functionally graph-processing algorithms. There's other ways to do pathfinding as well (that generally couple with A*), including preprocessing certain pairs (jump point search - it basically identifies obstructions and preprocesses the pairs at the corners so you can get around blocking corners with 1 test), using hierarchical space above the nodes to quickly check path validity, and so on. That, and different algorithms are used if your map is dynamic vs static.

Edited by Ameise

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • 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!