More on Dijkstra’s and finding the best path

Yesterday, I wrote about implementing Dijkstra’s algorithm to find the shortest/best path between two nodes. When I implemented this, it worked, but it was VERY slow. So, last night decided to approach this a different way. I figured I’d see what I could come up with on my own.

By the way, in that other post, I couldn’t figure out why it was messing up towards the end – it was because I set up the “grid” incorrectly and I was missing two edges/connections!

First, imagine this scenario: on a game screen, you have a grid. The player can put up obstacles on this grid. The enemy is trying to get from the left side of the screen to the right side, and it can only move around your obstacles.

TheGrid

So imagine your enemy is going to come in at location A1 and your home base is at I3. What path should the enemy take? Well, Dijkstra has this notion that you have nodes (or vertices) which have a “cost”, and connections in between the nodes (called edges), that have a weight (or cost). In other words, if I went from A1 –> B1 –> C1 – that would “cost” me 102. A1 is 1, B2 is 100, and C1 is 1 – well, plus the cost of the connection to each too.

If I went A1->A2->A3->B3->C3->C2->C1 – that costs me 7. So, I want an algorithm that will figure out it is easier/better to go around B1 and B2, even though it’s the longer route.

My Approach:
There are a few premises from which I worked:

  • I need to explore every possible way of getting from the starting box to the ending box
  • I can “walk” the tree in any direction, so long as I don’t go back to the node I just came from, and so long as I don’t hit the same node twice. This should allow me to even zig-zag backwards in the map, if that is cheapest route.
  • I want to stop if the current scenario I’m trying is starting to get more expensive than a cheaper scenario I’ve already found. No sense wasting time, I know this new scenario is going not going to win.
  • Walking the path will include the connection cost PLUS the node cost. So, going from A1 to B2 will cost A1’s cost, plus the “edge” connection from A1 to B1’s cost, and then also add B1’s cost. That is (I think?) a bit different than Dijkstra – but A) it’s much easier to implement my grid and B) it makes more logical sense to me.
  • I first want to come up with a list of all possible solutions – and then a secondary step will be figuring out which is best.

The first part, about getting all combinations was relatively easy. I have a few more properties and data structures than Dijkstra, but it’s also a lot easier to make sense of all of this data. So, what I did is starting at a given node, loop through all of the edges (look at all of the connections). For each connection, copy the path that you’ve taken so far – and then (using recursion), process that next node, keeping track of the path that you’ve taken to get to where you currently are.

Here’s pretty much the entire algorithm for that part:

mx39300

When I run this, this populates the “path” collection with all of the possible paths. Once I have all of those paths, I have a few convenience methods for analyzing the results:

mx37EA3

As you can see, GetCheapestPath() just uses some lambda expressions to:

  • Find all paths that include the starting point AND the ending point (some paths may have dead-ended)
  • Sort by Total cost of all node and connection costs for the entire path
  • Return the first one you find (which, would be the lowest/cheapest)

OK, so how well does this work? Let’s run the numbers!

mx31AE

So, Dijkstra’s algorithm (see my previous post) took 25 seconds – and mine takes .13 seconds!!  That is 192x faster!!

But wait, it’s not all unicorns and rainbows. The original problem statement is that I want a grid for a game. Using Radiant Defense as a model, that has a minimum grid size of 21×10. How well does this do with a bigger grid? Well, just going to 9×9 grid, and specifying I9 as the ending node, this takes almost 47 seconds.

mx3FBF4

When I tried a 21×10 grid, it ran for several minutes, then I got an OutOfMemoryException… on my 16GB workstation.

Ugh. So, we made a huge improvement in performance, but it’s still not nearly enough. I’m sure my algorithm could be optimized slightly, but I don’t think it will make a big enough difference.

Time to do some more research…

Posted in Uncategorized, XNA and MonoGame

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
Categories

Enter your email address to follow this blog and receive notifications of new posts by email.

Join 2 other followers

%d bloggers like this: