Sign in to follow this  

Shipping Simulation ( Dijkstra / Floyd-Warshall / ? )

This topic is 811 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

Hi,

 

 As title suggest, I intend to implement a shipping simulation into a multiplayer browser game, basically calculating cheapest route from vertex A to B something like,

 W7luVsy.png

 

As there are several options for transportation, actually vertices are not as shown here but for each transportation method (Greece - Land / Greece - Railroad / Greece - Seaport / Greece - Airport) as shown below, so my estimation for vertices is around 1,000 but with many edges since it won't be based on country but regions so a country may have 6-10 regions all having vertices for transportation methods.

 

 

8XpmIqx.png

 

 

In this scenario, Dijkstra seems to be enough for calculating cheapest route based on weight. But the problem is weights are different for each country (or even region). For example, there may have an avalanche at Slovenia blocking railroad traffic so edge Greece-Train -> Slovenia-Train is weighted infinite or Italy may impose higher toll fare for Greeks than Slovenians. So, I need to calculate according to weights based on several factors changing like originating country, destination country and route.

 

My first naive implementation was using Dijkstra and caching results (actually using a graph database like OrientDB or Neo4J solely for this) , but I am not sure if it is a wise choice in performance terms.

 

Then, I considered Floyd-Warshall Algorithm (which is basically Dijkstra run up to n^3 times apparently) with an extension of storing path as well, not only weight matrix.

 

But the problem is, everytime there is a weight change in a single edge, I need to recalculate entire matrix for all countries. Didn't have chance to test but doubt it will be blazing fast.

 

So, my plan atm is having a "tick number" and getting route from matrix if "matrix tick number" is same, using Dijkstra if not until matrix is recreated.

 

 

After this wall of text, my question is,

 

Is this right approach in your opinion or what would you recommend instead if not?

 

Thanks in advance,

Edited by Unduli

Share this post


Link to post
Share on other sites

The idea behind using both Dijkstra and Floyd-Warshall is ensuring that player will get an updated result while reconstructing Floyd-Warshall matrix for all vertices.

 

Floyd-Warshall is supposed to eliminate the need for running Dijkstra once constructed.

Share this post


Link to post
Share on other sites

Why are you classifying Dijkstra's as a single-pair search algorith? In my experience, Djikstra's is usually used to find the optimal path from all locations to a minimal-cost destination, by exploring a search space which you then "roll downhill" on.

 

1. At the destination D, set the cost of the destination C(D) to zero. Set the cost of all other locations to positive infinity (or some other arbitrarily excessive value).

2. Set up the edge cost function W(A,B), which gives the non-negative cost of traversing the edge directly from A to B. Directed edges work fine. Zero-cost edges are allowed.

3. For all locations L, let their new cost C'(L) be the lowest value among their current C(L) or among all adjacent locations A, C(A)+W(L,A).

4. Repeat (3) until no new lowest costs are discovered during an iteration.

 

To use the data, to go from any location X towards the destination D, traverse the edge from X to the lowest C(Y) among Y adjacent to X (aka "roll downhill"). This algorithm is tolerant of the data changing in-between steps. All locations in disconnected subgraphs that do not include D will have a cost of positive infinity.

 

When you dirty your edge costs, start re-calculating the costs to each destination. You can do one destination per tick, if you like. The strict Djikstra algorithm doesn't give you usable data in-between step-3 iterations, but neither does A*, so what the hell.

Share this post


Link to post
Share on other sites

Why are you classifying Dijkstra's as a single-pair search algorith? In my experience, Djikstra's is usually used to find the optimal path from all locations to a minimal-cost destination, by exploring a search space which you then "roll downhill" on.

 

1. At the destination D, set the cost of the destination C(D) to zero. Set the cost of all other locations to positive infinity (or some other arbitrarily excessive value).

2. Set up the edge cost function W(A,B), which gives the non-negative cost of traversing the edge directly from A to B. Directed edges work fine. Zero-cost edges are allowed.

3. For all locations L, let their new cost C'(L) be the lowest value among their current C(L) or among all adjacent locations A, C(A)+W(L,A).

4. Repeat (3) until no new lowest costs are discovered during an iteration.

 

To use the data, to go from any location X towards the destination D, traverse the edge from X to the lowest C(Y) among Y adjacent to X (aka "roll downhill"). This algorithm is tolerant of the data changing in-between steps. All locations in disconnected subgraphs that do not include D will have a cost of positive infinity.

 

When you dirty your edge costs, start re-calculating the costs to each destination. You can do one destination per tick, if you like. The strict Djikstra algorithm doesn't give you usable data in-between step-3 iterations, but neither does A*, so what the hell.

 

(Assuming that I understood what you meant,)

 

As weights will change for each country (therefore a new graph for each country) , actually I only need to know cheapest paths from each region of country to all abroad per graph as cost of A->B is not necessarily same as B->A. In that case , apparently I can speed things up using Dijkstra in the way you described (which I hope same as the way I got smile.png )

 

Actuallyi I just noticed that for changes that are not imminent but expected (like country A proposes a law about transit fee for country B, which takes 24 hours to be voted) , there can be precalculated results making transition delay-free.

Edited by Unduli

Share this post


Link to post
Share on other sites
You can compute ahead when a natural disaster will happen internally, and update the costs in the background, so you have them available immediately after you announce the disaster to the players.

Anyway, I'd recommend you first implement Dijkstra and see or measure how fast or slow it is compared to your needs. You can play this worrying/guessing game forever, but without hard data no way to know where you stand.

Share this post


Link to post
Share on other sites

How I learned to stop worrying (about the relative size inefficiency) and love Dijkstra maps:

http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

 

That's the other thing about Dijkstra's algorithm. You don't need to have one global destination; if you have multiple destinations, then all points will simply pathfind to their local minima. Even if your minima are of different values, it still works out. It's expensive to store if you have absolutely massive maps, but if they're only moderate-sized maps, the space inefficiency more than makes up for the fact that it supports any number of actors using it.

Share this post


Link to post
Share on other sites

How I learned to stop worrying (about the relative size inefficiency) and love Dijkstra maps:

http://www.roguebasin.com/index.php?title=The_Incredible_Power_of_Dijkstra_Maps

 

That's the other thing about Dijkstra's algorithm. You don't need to have one global destination; if you have multiple destinations, then all points will simply pathfind to their local minima. Even if your minima are of different values, it still works out. It's expensive to store if you have absolutely massive maps, but if they're only moderate-sized maps, the space inefficiency more than makes up for the fact that it supports any number of actors using it.

 

Thanks for the link. Seems they use a similar approach here @ https://people.mpi-inf.mpg.de/~funke/Papers/DIMACS06/DIMACS06.pdf as well.

Share this post


Link to post
Share on other sites

This topic is 811 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.

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

Sign in to follow this