Minimum Cost / Maximum Profit Algorithm

58 posts

Flag Post

Does anyone know the algorithm where you have a list of successive nodes in an ordered list, various pairs of nodes can be connected (e.g. the 4th and the 8th, rendering the 5th, 6th and 7th obselete), which cuts costs or increases profits by a certain figure; and what I want to do is choose the optimal set of pair of nodes to minimise costs / maximise profits where a particular node can’t be used if rendered obselete by a chosen pair?

Thanks in advance,
Dealmaster13

 
Flag Post

Essentially you want a pathfinding algorithm like A* where your paths (node connections) are weighted by that cost/benefit choice.

 
Flag Post
Originally posted by Draco18s:

Essentially you want a pathfinding algorithm like A* where your paths (node connections) are weighted by that cost/benefit choice.

Thanks, I’ll think about that.

A pathfinding algorithm within a pathfinding algorithm.

 
Flag Post

Nope not really. Go read up on Dijkstra’s algorithm. Much easier than coding up A* (And A* is based on Dijkstra’s anyways). Since A* is heuristic it will not always find the optimal path, which is why you can’t use it since you want a deterministic algorithm.

 
Flag Post
Originally posted by jonathanasdf:

Nope not really. Go read up on Dijkstra’s algorithm. Much easier than coding up A* (And A* is based on Dijkstra’s anyways). Since A* is heuristic it will not always find the optimal path, which is why you can’t use it since you want a deterministic algorithm.

But I think Dijkstra’s requires you to put in the nodes first, and I can’t really do that; but of course I can use Dijkstra’s with my nodes problem because I’ve got them by then.

I’m thinking I’ll also need to put the original paths back in as well as the new connections so that I can tell the algorithm to get from A to B.

 
Flag Post
Since A* is heuristic it will not always find the optimal path, which is why you can’t use it since you want a deterministic algorithm.

A* should always find the lowest cost. Yes, it uses a heuristic to eliminate search branches, but it keeps the pruning conservative by requiring that heuristic be admissible (i.e. low-ball).

Both of the mentioned algorithms will get an answer, but there should be a way to take advantage of complete ordering of the nodes. I have some fuzzy ideas floating around, but I can’t imagine an application that would need it.

 
Flag Post

Although Dijkstra’s algorithm and A* are available options, the data is a directed acyclic graph (description needs reworking but I assume it is) and a topological sort has already been performed on it. As a result, an asymptotically optimal algorithm taking advantage of the DAG’s topological ordering is available using the straightforward method that is dynamic programming.

 
Flag Post

Here is an example:

http://img534.imageshack.us/img534/5998/captureulr.png

I want to get from A to B and have already calculated the nodes and connections and their costs.
The black nodes and grey connections are produced by an initial tile-based A* algorithm and the red nodes and orange connections are produced by another algorithm mentioned in my original post (note that the orange connections alone don’t always get you from A to B.
I’ve ticked the connections that get me from A to B with the shortest route, and of course I want to produce an algorithm to get that.

Any further ideas?

 
Flag Post
Originally posted by Dealmaster13:
I want to produce an algorithm to get [the connections that get me from A to B with the shortest route].

What’s wrong with just using another A* algorithm on the new set of nodes and connections?

Yes, it would be a pathfinding algorithm within a pathfinding algorithm, but that alone isn’t a reason not to use it…


If you still don’t like the idea, go with dynamic programming, as Nabb suggested. Go through the list of nodes, starting with A, and make a note (at the appropriate index in an array) of which path, of the ones leading to it, gets to it fastest.
For example, at the fourth red node (the one reached from the checked path from A), there are two possible paths – one coming from the previous node on the gray path, and one coming from A. The two would be close in length, but the direct one would be slightly shorter, so you’d put that path (and its length) into the array at index 5.
Later, when you got to the fourth black node (the one reached from the second checked path), you’d have to compare a total of four inputs, and, by adding the length of the input path with the distance required to get to the previous node, you’d find that the longest input path represented the shortest route. You’d then put a reference to that orange path, plus the total distance required so far, into the array at index 9.

This could probably be optimized by using some of the ideas behind A*, but I’m not sure.

 
Flag Post
Originally posted by player_03:
Originally posted by Dealmaster13:
I want to produce an algorithm to get [the connections that get me from A to B with the shortest route].

What’s wrong with just using another A* algorithm on the new set of nodes and connections?

Yes, it would be a pathfinding algorithm within a pathfinding algorithm, but that alone isn’t a reason not to use it…


If you still don’t like the idea, go with dynamic programming, as Nabb suggested. Go through the list of nodes, starting with A, and make a note (at the appropriate index in an array) of which path, of the ones leading to it, gets to it fastest.
For example, at the fourth red node (the one reached from the checked path from A), there are two possible paths – one coming from the previous node on the gray path, and one coming from A. The two would be close in length, but the direct one would be slightly shorter, so you’d put that path (and its length) into the array at index 5.
Later, when you got to the fourth black node (the one reached from the second checked path), you’d have to compare a total of four inputs, and, by adding the length of the input path with the distance required to get to the previous node, you’d find that the longest input path represented the shortest route. You’d then put a reference to that orange path, plus the total distance required so far, into the array at index 9.

This could probably be optimized by using some of the ideas behind A*, but I’m not sure.

Thanks for taking the time to explain the dynamic programming concept.

I guess in short I’d just go through the nodes in order to see which is the shortest path from the start to it.
Sounds pretty straightforward now, however it does mean that I have to put the original nodes and connections back in.

 
Flag Post
Originally posted by Dealmaster13:
I have to put the original nodes and connections back in.

I’m not sure what you mean by this, but it sounds unnecessary; the algorithm I described would work given only the nodes and connections you showed in your diagram.

 
Flag Post

I know a neat pathfinding algorithm. only 31 lines of code and works like a charm. Sadly, thjis is not what you are looking for :D

 
Flag Post
Originally posted by player_03:
Originally posted by Dealmaster13:
I have to put the original nodes and connections back in.

I’m not sure what you mean by this, but it sounds unnecessary; the algorithm I described would work given only the nodes and connections you showed in your diagram.

The original nodes and connections are the black and grey ones, created using a standard tile-based A* pathfinding algorithm.
The red and orange ones are made using an optimising algortihm.

 
Flag Post

Well, I completely misunderstood what you were trying to do, sorry. But even now I still don’t really know what you’re trying to do. Are the black nodes the shortest L1 path that you’ve found already from A to B, or just any random tile-based path from A to B? So, now you want your character instead of following the path along the black dots, to take a more realistic path through the orange lines? How are you finding the red points and how are you storing them? Couldn’t you figure out an O(N) algorithm for this then (if N is the number of black nodes)?

Anyhow, Nabb is right, this is definitely a DAG but I think it’s not even as difficult as that if what I’m saying above is what you want to do. I’m going to need confirmation that I actually understand what you’re trying to do though, as well as the specifics of how you’re finding and storing the red nodes though to give a more specific response.

And i didn’t know that about A* since I’ve never used it nor researched much about it before. It’s just that whenever I hear that something is “Heuristics based” then I assume it doesn’t always find the optimal solution for all inputs.

 
Flag Post

A* is a heuristic version of Dijkstra’s algorithm. It’s slightly more efficient in certain cases.

 
Flag Post

This is probably the best representation of the problem I can create in paint, without showing you the program itself:

http://img253.imageshack.us/img253/2333/51607086.png

Firstly, before I say anything else, this could be a very inefficient way of getting around what I want to do, however I’m happy with what I’ve got at the moment, mainly because I thought up the ideas to optimise the A* algorithm myself (of course, someone else might have written the same algorithm ages ago, but that’s beside the point).

So I’ve got my start at A, my finish at B and various obstacles represented by black boxes laid out in a tile-based fashion.
I run through A*, also trying to get as few right angle turns as possible (note instead of going down then right, I could have gone right then down), and produce these grey nodes by splicing out the non-turning points (note this is a pathfinding algortihm for a moving object).
I then produce these red nodes at the points where along the A* path a change in the surrounding four obstacle pattern for that particular tile occurs.
My theory was that much of the time, the red nodes would prove helpful generally in creating these diagonal paths to gaps in obstacles, but of course, if there’s a single obstacle blocking an orange path, then we have a problem – but it’s not going to be a concern in this situation as I can simply create another algorithm for that.

I’m all ears, so if you can think of little tweaks or new ideas, that’d be great, but I think you can see that the method that player_03 mentioned which I summarised after should work for my particular problem.

 
Flag Post

I think I do have a better way. (Perhaps not a simpler way, but a better way.)

Pathfinding Example

When you set up the level, you want to go through, mark the red tiles, and form the orange connections. When you want to get from tile A to tile B, all you have to do is add the blue connections and run A* once.

The red tiles are the tiles diagonally next to a wall tile but not directly adjacent to one. The orange lines connect most pairs of red tiles in sight of one another.

You may notice that I said, “most,” not “all.” You may also notice that some red tiles in the diagram (most notably, the one near A) seem to be missing connections. This wasn’t an oversight on my part; it’s because those connections aren’t necessary.

Consider the tile near A – there are no tiles in sight of it that aren’t also in sight of the red tiles below it. On the other hand, there are tiles in sight of it that aren’t in sight of A. More generally speaking, that tile would never need to be connected to a tile directly below it, directly right of it, or below and to the right of it. Now take a look at the other tiles that seem to be missing connections and apply the same logic.

This makes the setup easier – you can safely ignore an average of half of all red tiles when line-of-sight testing. Not only can you ignore tiles in two of the four cardinal directions, you can ignore tiles in between those two directions, plus tiles in between the two opposite directions (that is, the tiles blocked by the wall).

One final caveat: the above doesn’t quite apply to tiles diagonally touching two different walls (like the exit to the large area in your diagram). Probably the most efficient way to deal with cases like this would be to treat it as two nodes on the same tile, each one only paying attention to one of the walls. This might mean rethinking your data structures, but it would allow you to exclude tiles as I described above, and it would avoid potential inefficiencies that could result from connecting a single node to all visible tiles.


To summarize:

When you create the map:
• Make a node at each external corner of a wall, allowing up to four per tile depending on the number of walls diagonally adjacent to that tile.
• For each node, connect it to all nodes in view of it, except for those that are in a cardinal direction going away from the wall, or between those two cardinal directions (sorry for the inelegant description; I just can’t think of a better way to put it). Also, make sure not to add the same connection twice and perform the cardinal direction check in both directions.

When you want to find a path between tiles A and B:
• Check if B is in sight of A. If so, just return the direct path.
If A or B is on a red tile, connect it to all the nodes on that tile.
Otherwise, Connect A and B to all red tiles in sight, except those that they don’t need to be connected to (perform the cardinal direction check described above; they also don’t need to be connected to the tiles they’re on).
• Run A*.

 
Flag Post

I’d just like to let you know that I’ve recognised your post, but will have to go over it tomorrow.

It looks very interesting but I haven’t managed to grasp the logic behind it yet.

A couple things I’d like to throw out before I hit the hay is that is it possible to exclude certain directions given certain maps can completely deceive heuristic methods and require you to double back or go down a normally uncommon route, and surely for this method to work 100%, you’re going to have to plug in every single red node given the above circumstances without getting an initial idea for the route via A* or something similar?

 
Flag Post

You do pass the entire graph (red nodes, plus orange and blue connections) to A*, if that’s what you’re saying. It’s just that you can take shortcuts when making the graph, because some potential connections would be redundant.

I did realize that I made a mistake in my summary, though. You can’t simply connect A and B to any nodes on the same tile (if there are nodes on the same tile). The red nodes aren’t necessarily connected to every node in sight, and both A and B must be connected to every node in sight except those that fail the cardinal direction check. (I still wish there was a better way to describe that…)

 
Flag Post

See? You’ve managed to get a response that gives you a much better method.

Though, player_03, I don’t get what you mean about the caveat when tiles diagonally touch 2 different walls. It doesn’t seem like you need to do anything special to make it work. Everything else seems to work though, but I haven’t really bothered to go through a strict proof of it.

I can’t off the top of my head think of a certain possible map that would make this fail (of course maps where there is no path from the entrance to the exit would make this fail) and if you A* or Dijkstra on this it should give you the shortest path. Since now you only check the red tiles instead of all tiles this is likely faster than your A* then optimize then A* again solution.

As for why there would be more than 1 node on the same tile, I still don’t get it. Please explain. And for the direction check, I understood it. But anyways, you don’t need to necessarily ignore it, you can just connect it and A* or Dijkstra would just ignore it anyways because the distance is longer. It would just be a bit slower.

 
Flag Post

Caveat Example

The central red tile here is diagonally adjacent to two different wall tiles. The potential problem here is this: if you ignore red tiles above it and/or to its left (because of the wall tile below and right of it) and ignore red tiles above it and/or to its right (because of the wall tile below and left of it), you end up ignoring too many tiles.

I was originally going to suggest inverting this (ignoring only tiles that passed both tests rather than either test), but I couldn’t figure out a good way to describe that. Besides, there are two reasons to use multiple nodes on the same tile.

First, consider what would happen if the two nodes on that tile were merged. While it obviously wouldn’t disrupt the algorithm, it would add a couple superfluous paths. For example, it would never be necessary to take the path from A to the left node, followed immediately by the path from the right node to the tile below B. I’ll admit that it doesn’t make much difference either way; I just think that it’s more elegant to keep them separate.

Second, I’m pretty sure it’s easier to code them separately than to have to handle all the different possibilities. If you keep them separate, you don’t have to worry about these cases, because each node will behave the same way whether or not there are other nodes on that tile.

 
Flag Post

I don’t think you ignore too many because those tiles are visible from A. In your drawn diagram, the center red node only needs to worry about the node below it, it doesn’t need to worry about any of the nodes above it, so I still don’t see what the problem is.

 
Flag Post
Originally posted by jonathanasdf:

I don’t think you ignore too many because those tiles are visible from A.

That’s not relevant; the network of orange lines must work for all possible locations of A and B.

Originally posted by jonathanasdf:

In your drawn diagram, the center red node only needs to worry about the node below it, it doesn’t need to worry about any of the nodes above it, so I still don’t see what the problem is.

If A was in the single cutout tile below the red tile on the left and B was in the very bottom area, and the center red tile was only connected to the bottom red tile, there would be no path from A to B.

 
Flag Post

Actually with your drawn picture there is no problem since even though the center node wouldn’t connect to the left one, the left node would connect to the center one. But I can see there would be a problem if the leftmost red node and the empty block below it was swapped with the 2 tiles directly to the right of it, and A was in the empty block and B on the bottom right area.

Then I think instead of having 2 nodes at the same tile you can just do this: if a node is touching more than 1 wall diagonally, then the tiles you don’t have to check is the intersection of the tiles you don’t have to check for each wall.

But anyways I still think it would be easier to do this instead of having multiple nodes at the same tile.

 
Flag Post
Originally posted by jonathanasdf:

Actually with your drawn picture there is no problem since even though the center node wouldn’t connect to the left one, the left node would connect to the center one.

You shouldn’t be making a connection at all if either one of the tiles fails the cardinal direction check from the other’s point of view. That’s just inefficient.
(Speaking of which, I noticed and removed a redundant connection in that second diagram. You may have to refresh the page to see the change.)

You probably weren’t suggesting that this is a directed graph, but if you were, you’re wrong.

Originally posted by jonathanasdf:

Then I think instead of having 2 nodes at the same tile you can just do this: if a node is touching more than 1 wall diagonally, then the tiles you don’t have to check is the intersection of the tiles you don’t have to check for each wall.

That’s correct. It’s just harder to do it that way than put multiple nodes on the same tile.

Why? Consider this:
If you have multiple nodes per tile, you get to treat every node exactly the same, no matter how many walls it’s diagonal to. You don’t have to find the intersection of two regions every time you’re considering connecting two nodes (or store that intersection for every node, even though that’s a waste for the vast majority of nodes). You’ll end up with significantly cleaner code as a result, with the only drawback being one or two extra node objects in an array.

Why would you want to create extra edge cases for yourself, when you have the opportunity to make every case behave exactly the same, and doing so actually improves performance slightly?